1. a.

select x.fID, count(x.fWord)
from   FrenchDocs x
group by x.fID

b.

select x.eID
from EnglishDocs x, EnglishDocs y
where y.eID = 'e424' and
      x.eID <> 'e424 and
      x.eWord = y.eWord
groupby x.eID
having count(distinct x.eWord) > 100

c.

select distinct x.fID
from FrenchDocs x, Dictionary y, EnglishDocs z
where x.fWord = y.fWord and y.eWord = z.eWord and z.eID = 'e424'
groupby x.fID, z.eID
having sum(confidence) >= 0.9 * sqrt(count(x.fWord) * count(z.eWord))

d.

insert into Eng lishDocs(eID, eWord)

select 'e916' as eID, y.eWord
from FrenchDocs x, Dictionary y
where x.fID = 'f822' and x.fWord = y.fWord and y.confidence=1.0

e.

select distinct x.eID
from   EnglishDocs x, EnglishDocs y
where  x.eID = y.eID and x.word='vacation'
       and y.word='summer'
       and not exists (select z.eID
                       from EnglishDocs z, EnglishDocs u
                       where x.eID=z.eID and z.eID=u.eID
                             and z.word='hicking'
                             and u.word='bicking')

we run this query: if the answer is empty, then the conjecture is
correct.  otherwise, the query returns all documents that violate the
conjecture.

2.

a.

/vacation/region/package[airline/text()="Northwest Airlines"][price/text()<=2000]
/vacation/region[name/text()="Northwest"]/package[month/text()="December"]/hotel

b.

<vacation>
 { let $h-all := distinct-values(/vacation/region/package/hotel/text())
   for $h in $h-all
   return
     <hotel>
       <name> { $h } </name>
       { for $r in /vacation/region
             $p in $r/package[hotel/text()=$h]
         return <package>
                    <region> { $r/name/text()} </region>
                    { $r/airline, $r/month, $r/price }
                </package>
       }
  }
</vacation>





3.

a. forall c.forall y.(G(x,c,y) => c='red')

b. forall y.(G(x,'blue',y) =>
            (exists z.(G(y,'green',z) and (forall c.forall u.(G(z,c,u) => c='red')))))


c.

P(x,c,y) :- G(x,c,y)
P(x,c,y) :- P(x,c,z), G(z,c,y)
Answer(x,y)   :- P(x,c,y)


4. a.


after 5:

     -------
    | 3   5 |
     -------
  /    	 \     \
  ---  	 ---   	--
 |1 2|  |3 4|  |5 |
  ---	 --- 	--

after 7:
    	       ----
              | 5  |
	  /    ----    \
      --	   	  ---
     |3 |                | 7 |
    / -- \     	       	/ ---  \
  ---  	 ---   	      ---      	  ---
 |1 2|  |3 4|        |5 6|       | 7 |
  ---  	 ---   	      ---      	  ---


after 14:

		    -------
                   | 5  9  |
		    -------
       	   /   	       |       	 \
     ---	      ---      	       -------
    | 3 |            | 7 |            | 11 13 |
     ---	      ---      	       -------
  /      \     	    /      \         /     \      \
  ---    ---        ---    ---       ----   -----   -----
 |1 2|  |3 4|      |5 6|  |7 8|     |9 10| |11 12| |13 14|
  ---    ---        ---    ---       ----   -----   -----

after 16:

       	       	     ---
                    | 9	|
       	      /	     ---      \
	 ---   	       	       	----
        | 5 |                  | 13 |
	 ---   	       	       	----
      /	     \             /         \
   ---       ---        ----           ----
  | 3 |     | 7 |      | 11 |         | 15 |
   ---       ---        ----           ----
 /     \    /    \     /     \         /      \
--    ---  ---  ---    ----  -----    -----    -----
1,2   3,4  5,6  7,8    9,10  11,12    13,14    15,16
--    ---  ---  ---    ----  -----    -----    -----






b. (i) During the first pass, quicksort produces runs of length 100:
there will be 100 such runs.  A second pass is needed to merge the
runs and output the sorted sequence.  Hence, each record is read twice
and written twice.

(ii) During the first pass replacement selection produces a single
run, of length 10000.  There is no need for a second pass.  Hence,
each record is read once, and written once.

c.

            V(R,A)=1   |   V(R,A)=10000
         ===============================
        | index-join   | index join    |
M=101   | c=10k+4*10k= | c = 10k+4=    |
        |  =40000      |     10004     |
         ===============================
        | b-nested loop| index join    |
M=5002  | c=10k+2*10k  | c = 10k+4=    |
        |  =30000      |     10004     |
         ===============================

Full credit also with any of these answers:

            V(R,A)=1   |   V(R,A)=10000
         ===============================
        | p-hash-join  | index join    |
M=101   | c=3*(10k+10k)| c =  5k+4=    |
        |  =60000      |      5004     |
         ===============================
        | b-nested loop| index join    |
M=5002  | c=10k+2*10k  | c =  5k+4=    |
        |  =30000      |      5004     |
         ===============================

The index join here is assuming more than typical optimizers do,
namely that R.A is a key.

5.

a.

<!ELEMENT sales-by-city (city*)>
<!ELEMENT city (name, manufacturer*)>
<!ELEMENT manufacturer (name, product*)>
<!ELEMENT product (#PCDATA)>

b.

select distinct p.city
from product p


select p.name
from product.p
where p.city = 'Seattle'

select manufacturer
from (select distinct manufacturer, city from product) as t