Suppose that R 1 ,...,R n is a decomposition of schema R obtained by a sequence of binary lossless decompositions (beginning with a decomposition of R). Prove that R 1 ,...,R n is a lossless decomposition of R.
What will be an ideal response?
Proof by induction on n.
1. Base case: n = 2. The decomposition R1, R2 of R is lossless, but construction.
2. Inductive assumption. Suppose R1,...,Rn is a lossless decomposition of R.
We need to prove that R1,...,Rn?1, R'n, R"n is a lossless decompositions of R, if R'n, R"n is a lossless binary decomposition of Rn.
Suppose r is a relation over R and t is an arbitrary tuple over the attribute set of R such that
?R1(t ) ? ?R1(r),...,?Rn?1(t ) ? ?Rn?1(r), ?R'n(t ) ? ?R'n(r), ?R"n(t ) ? ?R"n(r)
Because R 'n R"n is a lossless binary decomposition of Rn, it follows that ?Rn(t ) ? ?Rn(r). Hence, by the de?nition of a join, t ? (?R1(r) ... ?Rn(r)) = r. The last equality here holds because R1,...,Rn is a lossless decompositions or R, by the inductive assumption.
You might also like to view...
The ternary operator of C++ takes:
A. no operands B. one operand C. two operands D. three operands
The _________________________ architecture establishes a system of dynamic storage provisioning so that cloud consumers are billed, on a granular level, for the exact amount of storage actually being used at any given time.
Fill in the blank(s) with the appropriate word(s).
Illegal copies of software are referred to as _______ software.
Fill in the blank(s) with the appropriate word(s).
You run a cable for a new computer and the requirement is CAT6. What should you use when terminating the cable?
A. BNC B. RJ-12 C. RJ-45 D. ST E. F-connector