1. Use Armstrong’s axioms to prove the soundness of the decomposition rule. 2. L
ID: 3761375 • Letter: 1
Question
1. Use Armstrong’s axioms to prove the soundness of the decomposition rule.
2. List the three design goals for relational databases, and explain why each is dsirable.
3. Solve the below queries using Tuple Relational Calculus.
a- Find the ID, name, dept_name, salary for instructors whose salary is greater than $80,000.
b- Find the names of all instructors whose department is in the Watson building
4. Solve the below queries using Domain Relational Calculus.
a- Find the ID, name, dept_name, salary for instructors whose salary is greater than $80,000
b- Find the ID, name, dept_name, salary for instructors whose salary is greater than $80,000
5. Convert given below table in 1NF, 2NF & 3NF.
ITEM
COLORS
PRICE
TAX
T-Shirt
red, blue
12.00
0.60
Polo
red, yellow
12.00
0.60
T-Shirt
red, blue
12.00
0.60
Sweatshirt
blue ,black
25.00
1.25
ITEM
COLORS
PRICE
TAX
T-Shirt
red, blue
12.00
0.60
Polo
red, yellow
12.00
0.60
T-Shirt
red, blue
12.00
0.60
Sweatshirt
blue ,black
25.00
1.25
Explanation / Answer
AMSTRONG AXIOMS
F1: reflexivity if Y Í X then X ® Y
F2: augmentation if X ® Y then XZ ® YZ
F3: transitivity if X ® Y and Y ® Z then X ® Z
Theorem: Armstrong’s axioms are a sound and complete set of inference rules
Sound: the Armstrong’s rules generate only FDs in F*
F+ Í F*
Complete: the Armstrong’s rules generate all FDs in F*
F* Í F +
If complete and sound then F+ = F*
Armstrong’s axioms generate all FDs in F*
EXAMPLE
Attr(R)=LMNO
X=L
F={L M , M N, O N}
then X+ = L+ = LMN
Completeness:
("R, " X,Y ÍAttr(R), "F true in R : : X Y Î F* => X Y Î F +)
Idea: (A => B) (ØA v B) (B v ØA) (ØB =>ØA)
To establish completeness, it is sufficient to show:
if X ® Y cannot be deduced from F using Armstrong’s axioms then also X ® Y is not logically implied by F:
("R, " X,Y ÍAttr(R), "F true in R : : X Y Ï F+ => X Y Ï F*)
there is a relational instance r in R (rÎR) in which all the dependencies in F are true, but X Y does not hold
3.
a.{t|employee(t[id]=s[id]^s[sal]>$8000}
the set of all tuples such that there exists a tuple in the relation employee for which the values of and for the eid attribute are equal, and the value of for the amount attribute is greater than $80000
b. {t|<name>| employee dept=’watsonbuilding’}
4 a. {< id,name,dept,sal > | employee sal >$80000}
b. {< id,name,dept,sal > | employee sal >$80000}
1NF
ITEM
COLORS
PRICE
TAX
T-Shirt
red
12.00
0.60
Polo
red
12.00
0.60
T-Shirt
red
12.00
0.60
Sweatshirt
blue
25.00
1.25
T-Shirt
blue
12.00
0.60
Polo
yellow
12.00
0.60
T-Shirt
blue
12.00
0.60
Sweatshirt
black
25.00
1.25
2NF
ITEM
PRICE
TAX
T-Shirt
12.00
0.60
Polo
12.00
0.60
T-Shirt
12.00
0.60
Sweatshirt
25.00
1.25
T-Shirt
12.00
0.60
Polo
12.00
0.60
T-Shirt
12.00
0.60
Sweatshirt
25.00
1.25
ITEM
COLORS
T-Shirt
red
Polo
red
T-Shirt
red
Sweatshirt
blue
T-Shirt
blue
Polo
yellow
T-Shirt
blue
Sweatshirt
black
COLORS
PRICE
TAX
red
12.00
0.60
red
12.00
0.60
red
12.00
0.60
blue
25.00
1.25
blue
12.00
0.60
yellow
12.00
0.60
blue
12.00
0.60
black
25.00
1.25
3NF
ITEM
COLORS
PRICE
TAX
T-Shirt
red
12.00
0.60
Polo
red
12.00
0.60
T-Shirt
red
12.00
0.60
Sweatshirt
blue
25.00
1.25
T-Shirt
blue
12.00
0.60
Polo
yellow
12.00
0.60
T-Shirt
blue
12.00
0.60
Sweatshirt
black
25.00
1.25
ITEM
PRICE
T-Shirt
12.00
Polo
12.0025.00
Sweatshirt
AMSTRONG AXIOMS
F1: reflexivity if Y Í X then X ® Y
F2: augmentation if X ® Y then XZ ® YZ
F3: transitivity if X ® Y and Y ® Z then X ® Z
Theorem: Armstrong’s axioms are a sound and complete set of inference rules
Sound: the Armstrong’s rules generate only FDs in F*
F+ Í F*
Complete: the Armstrong’s rules generate all FDs in F*
F* Í F +
If complete and sound then F+ = F*
Armstrong’s axioms generate all FDs in F*
EXAMPLE
Attr(R)=LMNO
X=L
F={L M , M N, O N}
then X+ = L+ = LMN
Completeness:
("R, " X,Y ÍAttr(R), "F true in R : : X Y Î F* => X Y Î F +)
Idea: (A => B) (ØA v B) (B v ØA) (ØB =>ØA)
To establish completeness, it is sufficient to show:
if X ® Y cannot be deduced from F using Armstrong’s axioms then also X ® Y is not logically implied by F:
("R, " X,Y ÍAttr(R), "F true in R : : X Y Ï F+ => X Y Ï F*)
there is a relational instance r in R (rÎR) in which all the dependencies in F are true, but X Y does not hold
3.
a.{t|employee(t[id]=s[id]^s[sal]>$8000}
the set of all tuples such that there exists a tuple in the relation employee for which the values of and for the eid attribute are equal, and the value of for the amount attribute is greater than $80000
b. {t|<name>| employee dept=’watsonbuilding’}
4 a. {< id,name,dept,sal > | employee sal >$80000}
b. {< id,name,dept,sal > | employee sal >$80000}
1NF
ITEM
COLORS
PRICE
TAX
T-Shirt
red
12.00
0.60
Polo
red
12.00
0.60
T-Shirt
red
12.00
0.60
Sweatshirt
blue
25.00
1.25
T-Shirt
blue
12.00
0.60
Polo
yellow
12.00
0.60
T-Shirt
blue
12.00
0.60
Sweatshirt
black
25.00
1.25
2NF
ITEM
PRICE
TAX
T-Shirt
12.00
0.60
Polo
12.00
0.60
T-Shirt
12.00
0.60
Sweatshirt
25.00
1.25
T-Shirt
12.00
0.60
Polo
12.00
0.60
T-Shirt
12.00
0.60
Sweatshirt
25.00
1.25
ITEM
COLORS
T-Shirt
red
Polo
red
T-Shirt
red
Sweatshirt
blue
T-Shirt
blue
Polo
yellow
T-Shirt
blue
Sweatshirt
black
COLORS
PRICE
TAX
red
12.00
0.60
red
12.00
0.60
red
12.00
0.60
blue
25.00
1.25
blue
12.00
0.60
yellow
12.00
0.60
blue
12.00
0.60
black
25.00
1.25
3NF
ITEM
COLORS
PRICE
TAX
T-Shirt
red
12.00
0.60
Polo
red
12.00
0.60
T-Shirt
red
12.00
0.60
Sweatshirt
blue
25.00
1.25
T-Shirt
blue
12.00
0.60
Polo
yellow
12.00
0.60
T-Shirt
blue
12.00
0.60
Sweatshirt
black
25.00
1.25
ITEM
PRICE
T-Shirt
12.00
Polo
12.00
Sweatshirt
25.00
ITEM
COLORS
PRICE
TAX
T-Shirt
red
12.00
0.60
Polo
red
12.00
0.60
T-Shirt
red
12.00
0.60
Sweatshirt
blue
25.00
1.25
T-Shirt
blue
12.00
0.60
Polo
yellow
12.00
0.60
T-Shirt
blue
12.00
0.60
Sweatshirt
black
25.00
1.25
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.