#3.2

A relation schema is a type definition. A relation is an instance of that schema. For example, student(ss#, name) is a relation schema and

ss# name

123-45-6789 Tom Jones

456-78-9012 Joe Brown

is a relation based upon that schema.

#3.3

person (driver-id, name, address)

car (license, year, model)

accident (report-number, location, date)

owns (driver-id, license)

participated (license, driver-id, report-number, damage amount)

#3.5

(a) P _person-name (s _{company-name = "First Bank Corporation"} (works))

(b) P _{person-name, city} (employee |X| (s _{company-name = "First Bank Corporation"} (works)))

(c) P _{person-name, street, city} (employee |X|

(d) P _person-name (works |X| employee|X| company)

(e) P _person-name ((employee |X| manages)

(f) P _person-name (s _{company-name != "First Bank Corporation"} (works))

(g) P _person-name (works) ¾ (P _{works.person-name} (works

(h) P _company-name (company ¸

#3.6

The rewritten query is:

(a) Jackson has a loan, but no address is given for Jackson in the customer relation. Since no tuple in customer joins with the jackson tuple of borrower, jackson does not appear in the result.

(b) The best solution is to insert an address for Jackson in the customer relation. Null values may be used if no values are known; alternatively a special value (such as unknown) that is an unlikely value for an actual address might be used.

(c)

P _{customer-name, customer-city} ((borrower loan) customer)

#3.7

The left outer theta join of r(R) and s(S) can be defined as

(r theta-join s) È ((r - P _R (r theta-join s)) ´ (null, null, null, … null))

where the tuple of nulls is of size equal to the number of attributes in S.

Similarly, the right outer theta join of r(R) and s(S) can be defined as

(r theta-join s) È ((s - P _S (r theta-join s)) ´ (null, null, null, … null))

where the tuple of nulls is of size equal to the number of attributes in R.

And the full outer theta join of r(R) and s(S) can be defined as

(r theta-join s) È ((r - P _R (r theta-join s)) ´ (null, null, null, … null))

È ((s - P _S (r theta-join s)) ´ (null, null, null, … null))

where the first tuple of nulls is the same size as R and the second tuple of nulls is the same size as S.

#3.8

My mistake -- I told you that you would not be responsible for the updates section in the relational algebra, and then I assigned a question on that section. This question will not be graded.

#3.9

(a) P _{account-number} (s _{count-names>2}(_{account-number} G _count(customer-name) as count-names (depositor)))

(b) t1 ¬ (r _d1(depositor) ´ r _d2(depositor) ´ r _d3(depositor))

t2 ¬ s _{d1.account-number = d2.account-number Ù d2.account-number = d3.account-number} (t1)

P _{d1.account-number} (s _{d1.customer-name != d2.customer-name Ù d2.customer-name != d3.customer-name Ù d1.customer-name != d3.customer-name} (t2)

#3.16

(a) P _A (s _B=17 (r))

(b) r s

(c) P _A (r) È (r ¸ s _B (P _C (s)))

(d) P _r.A (r s ) (s _{c=r2.A Ù r.B > r2.B} (r _r2(r)))

#4.1

One typographical note: The second attribute of the participated relation in figure 4.12 should be license, not car. License is an attribute name; car is a relation name.

(a) select count (distinct name)

from accident, participated, owns, person

(b) select count (distinct *)

from accident

(c) insert into accident

(d) delete car

where model = "Mazda" and license in

Note: this deletes every Mazda that John Smith owns, if he owns more than one.

(e) update participated

set damage-amount = 3000

#4.2

(a) select employee-name

from works

(b) select e.employee-name, city

from works w, employee e

e.employee-name = w.employee-name

(c) select e.employee-name, street, city

from works w, employee e

e.employee-name = w.employee-name and

(d) select e.employee-name

from works w, employee e, company c

(e) select e.employee-name

from employee e, employee x, manages m

e.city = x.city

(f) select employee-name

from works

(g) select employee-name

from works

from works

(h) select T.company-name

from company T

from company R

from company S

(i) select w.employee-name

from works w

(j) select company-name

from works

(select count (distinct employee-name)

from works

group-by company-name)

(k) select company-name

from works

(select sum (salary)

from works

group-by company-name)

(l) select company-name

from works

#4.4 given the following relation schemas:

R = (A, B, C)

S = (D, E, F)

Give an SQL expression equivalent to the following queries

(a) P _A(r)

select A

from r

(b) s _B=17 (r)

select *

from r

where B=17

(c) r X s

select *

from r, s

(d) P _A,F ( s _C=D (r X s))

select A, F

from r, s

where C=D

#4.5 with R = (A, B, C) and r₁ and r₂ both relations on schema R, give an SQL expression equivalent to:

(a) r_{1 È} r₂

(select *

from r₁)

union

from r₂)

(b) r₁ Ç r₂

here are two possible solutions:

from r₁)

intersect

from r₂)

or alternatively with a nested subquery

select *

from r₁

from r₂)

(c) r₁ ¾ r₂

from r₁

from r₂)

another possible solution would be to use the except clause

(d) P _AB (r₁) P _BC (r₂)

select r₁.A, r₁.B, r₂.C

from r₁, r₂

where r₁.B = r₂.B

#4.6 With R= (A, B) and S= (A, C), and r, s relations on schemas R,S respectively, write an SQL expression for the following:

(a)

select A

from r

where B=17

(b)

select r.A, r.B, s.C

from r, s

where r.A = s.A

(c)

select s.A

from s, r r₁, r r₂

where s.A = r₁.A and s.A = r₂.A and

r₁.B > r₂.B

#4.7

There are a number of ways to express this.

Comparing (x not in S) with (x <> all S), for a given value x1,

Clearly if x1 satisfies (x1 <> all S), then for any value y in S, x1 <> y, which shows that x1 is not a value contained in S. In other words, x1 not in S.

In the other direction, if x1satisfies the condition (x1 not in S), then for any value y in S, the condition (y <> x1) will be satisfied. In other words, x1 <> all S

#4.8 will not be graded

#7.2 A decomposition of R into R1 and R2 is a lossless join if R1 Ç R2 à R1 or R1 Ç R2 à R2

R1 Ç R2 = (A).

We have A à BC, so A is a candidate key for R1. Therefore the join is lossless: A à ABC, so A à R1

We could also show that

1) A à BC, so A à B, and B à D, so Aà D.

2) A à BC, and B à D, so A à DC. CD à E, so Aà E

3) by the above, A à D and Aà E, so A à DE.

Therefore A is also a candidate key for R2. Therefore the join is lossless: A à ADE, so A à R2.

#7.4

A à B

C à B

#7.5 sound means that they do not generate incorrect functional dependencies.

Definition of functional dependencies:

A à B holds on schema R if, in any legal relation r in R, for every pair of tuples t1 and t2 in relation r, if t1[A] = t2[A] then we also have t1[B] = t2[B]

Armstrong's Axioms:

Reflexivity: if A is a set of attributes and B is a subset of A, then Aà B

By definition, if t1[A] = t2[A] then on every attribute X within set A, t1[X]=t2[X]. Since B is a subset of A, every attribute X that appears within B also appears within A, so t1[B]=t2[B] .

Augmentation: if A à B holds and C is a set of attributes, then AC à BC

For any attribute X in C, X à X (if t1[X]=t2[X] then t1[X]=t2[X] is a tautology).

By reflexivity, AC à C since C is a subset of AC. By our initial assumption, we also have A à B; by reflexivity again, this means that AC à B. By the definition of FDs, then, AC à BC

Transitivity: if A à B holds and B à C holds, then A à C.

By the definition of FDs, A à B means if t1[A] = t2[A] then we also have t1[B] = t2[B]. By the definition of FDs again, Bà C means if t1[B] = t2[B] then we also have t1[C] = t2[C]. Since equality is transitive, therefore we have if t1[A]=t2[A] then t1[C]=t2[C], which by definition is A à C

#7.11

1. A à BC

2. CD à E

3. B à D

4. E à A

Candidate keys:

(1)

1 and the trivial Aà A gives us with A à ABC

3. gives us A à ABCD

2. gives us A à ABCDE: A is a candidate key

(2)

2 gives us CD à E

2 and 4, by transitivity, gives us CD à AE

since A à ABCDE, this gives us CD à ABCDE. CD is also a candidate key

(3)

3 and Augmentation gives us BC à CD. CD is a candidate key, so BC is also a candidate key.

(4) E à A, and A is a candidate key, so E is also a candidate key.

#7.12

Compute B+ from the dependencies of 7.11.

1) start with B à B, the trivial dependency

2) using FD#3, B à BD

3) that is all.

#7.15

There are several ways to write this query; I have chosen a simple one

(a) select b

from r

group-by b

having count ( distinct c) > 1

(b) create assertion dependency-preserve check

from r

group-by b

having count ( distinct c) > 1))

#7.16

let r be the following relation:

A B C D E

a1 b1 c1 d1 e1

a2 b2 c1 d2 e2

now P _A,B,C (r) is:

A B C

a1 b1 c1

a2 b2 c1

and P _C,D,E (r) is:

C D E

c1 d1 e1

c1 d2 e2

now the result of P _A,B,C (r) natural-join P _C,D,E (r) gives us all the following tuples:

A B C D E

a1 b1 c1 d1 e1

a2 b2 c1 d2 e2

a1 b1 c1 d2 e2

a2 b2 c1 d1 e1

Which is erroneous. Therefore lossy join.

#7.21

Bà D is the non-trivial dependency with the left-hand side not being a superkey, so splitting into {(A,B,C,E) , (B, D)} is in BCNF

#7.23

With BCNF it is sometimes not possible to preserve all the dependencies. As a result, we are sometimes forced to choose between violating some dependencies and having the database in BCNF.

Web Accessibility