$Id: CIS-631.exercise2.txt,v 1.2 2005/09/16 02:11:23 dxt22 Exp dxt22 $

Legend:

  P   Project
  S   Select

2. Which museums have only impressionist (style) paintings?

MWP <- P      (COLLECTION join PAINITNG)
        MUSEUM

MWOS <- P      (S                        [COLLECTION join PAINTING])
         MUSEUM  STYLE != 'IMPRESSIONIST'

RESULT <- MWP - MWOS

Mnemonic Devices:
    MWP     Museums With Paintings
    MWOS    Museums With Other Styles

Explanation:
    This is a three-step procedure.  In the first step, we figure out
    the set of museums that have at least one painting in them.  It
    would be incorrect to do a simple projection on COLLECTION, as we
    may get museums that have no paintings.  By doing a join with
    PAINTING, we make sure that museums that have no paintings do not
    get included.  The second step is to select all museums that have
    paintings with style other than impressionist.  Now, the difference
    between the two sets is the answer.



3. Which museums have no impressionist paintings?

Approach:
    The key is to notice how this problem is similar to problem 2.
    In problem 2, MUSEUMS is a superset of MWP, which in turn is a
    superset of MWOS.  Here, we have MWP and we have museums that
    have impressionist paintings (MWIP).  Therefore, the difference
    between MWP and MWIP would give us the list of museum with no
    impressionist paintings.  Only the second step in our solution
    is different from problem 2:

MWP <- P      (COLLECTION join PAINITNG)
        MUSEUM

MWIP <- P      (S                       [COLLECTION join PAINTING])
         MUSEUM  STYLE = 'IMPRESSIONIST'

RESULT <- MWP - MWIP

Mnemonic Devices:
    MWIP    Museums With Impressionist Paintings.


4. Which museums have all the paintings by Vasarely?

Approach:
    This problem looks very similar to problem 1, which I drew up on
    the board at the end of the last class.  Problem 1 was itself
    similar to the Drinkers/Beer example which Prof. Oria used to
    introduce the division operator.  If you remember, problem 1
    solutions looks like this:

# This is a variable, not a production.
$CONDITION = "PAINTER = 'DALI' AND YEAR >= 1950 AND YEAR <= 1960"

MP <- P               (S          [COLLECTION join PAINITNG])
       MUSEUM,PAINTING  $CONDITION

DPOTP <- P           (S          [PAINTING])
          PAINTING_ID  $CONDITION

RESULT <- MP : DPOTP

Mnemonic Devices:
    MP      Museum, Painting
    DPOTP   Dali Paintings Of That Period

Explanation:
    The point of steps 1 and 2 is to reduce the problem to that of
    Drinkers/Beer and Beers database, so that we can use division
    operator.  The condition (see $CONDITION above) places some
    restrictions on paintings: by Dali, in the 1950s.  So, between
    problems 1 and 4, only condition changes:

$CONDITION = "PAINTER = 'VASARELY'"

    We can safely use the template from problem 1 to solve problem 4.


5. Which museums have at least one painting of every style of the
   XIX century?

Approach:
    Here, the restction is on paintings (19th century), but museums
    are selected based on style.  Let us convert 'at least' to 'all':
    Which museums have all styles of paintings of the XIX century?
    This 'all' will allow us to use the division operator on two sets
    to get the result.  The first set should contain MUSEUM and STYLE
    while the second set will contain STYLE.  The more difficult
    question is how we produce those sets.  Let's assume the second
    set is all styles we can find in PAINTING in the 19th century:

$CONDITION = "YEAR > 1800 and YEAR <= 1900"

STYLES <- P     (S          [PAINTING])
           STYLE  $CONDITION

    We will base the first set on based styles above.  Note that the
    question talks about only 'style of the 19th century', not
    'painting of the 19th century'.  This means that a museum of
    modern art (second half of 20th century) that has all styles we
    found in 19th century will satisfy the requirement.  The
    following production filters the result of join of COLLECTION
    and PAINTING based on style.  Projection is then used to create
    the MUSEUM, STYLE set.

MS <- P            ([COLLECTION join PAINTING] join STYLE)
       MUSEUM,STYLE

    The hardest part is behind us, we reduced the problem to (the now
    trivial) division:

RESULT <- MS : STYLES