CSE 544, Spring 2002

Assignment 2: due Wednesday, May 1st

Total points: 100

Solution

  1. [25 points] Define the SQL relational schema that captures the E/R diagram below. Choose realistic domains for the attributes, and specify key and foreign key constraints.

     

  2. [30 points] Consider the relational schema below:

    1. [10 points] Write the following queries in First Order Logic (FO):
      1. [2 points] Find all bars that sell both "Bud" and "Miller".
      2. [2 points] Find all bars that sell no other beer except "Bud" and "Miller".
      3. [2 points] Find all drinkers who frequent only bars that serve some beer they like.
      4. [2 points] Find all drinkers who frequent some bar that serves only beers they like.
      5. [2 points] Find all drinkers who frequent only bars that sell only beers that they don't like.
    2. [10 points] Write all the queries above in SQL
    3. [10 points] Write the following queries in SQL:
      1. [5 points] Find all pairs of bars that sell at least 50 beers in common
      2. [5 points] For each drinker and bar he frequents list the total number of beers served at that bar that the drinker likes.
  3. [20 points] Consider a database schema with three relations: R(x,y), S(x), U(x,y) (i.e. R is binary, S is unary, and U is binary). 
    1. [2 points] Write a query qa(x) that computes the active domain of a database with that schema.

      For each of the FO queries below indicate whether they are safe or not, and whether they return a finite answer or not. 
    2. [3 points] {x | S(x) and  forall y.(not R(x,y))}
    3. [3 points] { x |  S(x) and (forall y. (R(x,y) ==> exists z.(S(z) or U(y,z))))  }
    4. [3 points] { x |  exists y.(S(y) ==> forall z. (R(x,y) and U(y,z)))  }
    5. [3 points] { x | S(x) and forall y.(S(y) and R(x,y))  }
    6. [3 points] { x | S(x) and forall y.(U(x,y) or forall z. (not R(y,z)))  }
    7. [3 points] { (x,y) | exists z. (R(x,z)  or U(z,y))  }
  4. [25 points] Consider the DTD below:

    <!ELEMENT wnyc (piece*)>
    <!ELEMENT piece (time, title, composer, conductor?, orchestra?, soloist*, publisher>
    <!ELEMENT time (#PCDATA)>
    . . .  [the content model of all leaf elements is  #PCDATA] . . .
    <!ELEMENT publisher (#PCDATA)>
    <!ATTLIST wnyc id ID REQUIRED>
    . . .  [all elements have an id attribute] . . .
    <!ATTLIST publisher id ID REQUIRED>

    1. [5 points] design a relational schema that can store one XML document of this DTD
    2. [5 points] show the relational database instance that corresponds to the following XML document:

      <wnyc id="0">
         <piece id="1"> <time id="10"> 12:26 PM </time>
                      <title id="11"> Mad Rush </title>
                      <composer id="12"> Philip Glass </composer>
                      <soloist id="13"> Aleck Karis, piano </soloist>
                      <publisher id="14"> Romeo 7204 </publisher>
         </piece>
         <piece id="2"> <time id="21"> 12:49 PM </time>
                      <title id="22"> Concerto No. 12 in E, Op. 3, RV 265 </title>
                      <composer id="23"> Antonio Vivaldi </composer>
                      <conductor id="24"> Fabio Biondi </conductor>
                      <orchestra id="25"> Europa Galante </orchestra>
                      <publisher id="26"> Virgin Classics 45315 </publisher>
          </piece> 
          <piece id="3"> <time id="31"> 1:01 PM </time>
                        <title id="32"> Symphony No. 1 in e, Op. 39 </title>
                        <composer id="33"> Jean Sibelius </composer>
                        <conductor id="34"> Leonard Bernstein </conductor>
                        <orchestra id="35"> Vienna Philharmonic Orchestra </orchestra>
                        <publisher id="36"> Deutsche Grammophon 435351 </publisher>
          </piece>
          <piece id="4"> <time id="41"> 1:47 PM </time>
                        <title id="42"> Andante for Piano ("Andante favori") </title>
                        <composer id="43"> Ludwig van Beethoven </composer>
                        <soloist id="44"> Alfred Brendel, piano </soloist>
                        <publisher id="45"> Philips 438472 </publisher>
           </piece>
           <piece id="5"> <time id="51"> 1:57 PM </time>
                        <title id="52"> Upon Enchanted Ground </title>
                         <composer id="53"> Alan Hovhaness </composer>
                        <soloist id="55"> Yolanda Kondonassis, harp </soloist>
                        <soloist id="56"> Frank Hendrickx, alto flute </soloist>
                        <soloist id="57"> Herwig Coryn, cello </soloist>
                        <soloist id="58"> Patrick De Smet, tam-tam </soloist>
                        <publisher id="59"> Telarc 80530 </publisher>
            </piece>
      </wnyc>
    3. [15 points] write queries in XQuery to do the following:
      1. [5 points] Retrieve all conductors that conduct "Mad Rush" by "Philip Glass", and the times they are broadcasting.
      2. [10 points] Restructure the entire XML document into a document that groups first by soloists  then by conductor. That is, the DTD of the query's output is:
        <!ELEMENT wnyc-by-solo (solo*)>
        <!ELEMENT solo (name,  conductor*)>
        <!ELEMENT conductor (name, piece*)>
        <!ELEMENT piece (title, composer)>
        Make sure that each soloist is listed only once, and, for each soloist each conductor is listed only once. Notice that some information from the input XML document is not included in the output, e.g. the time. You may need to consult the XQuery recommendation at http://www.w3.org/XML/Query