Proof that a decomposition into 3 relations is lossless

Question

Given this relation scheme with set of attributes R and set of dependencies F:

R = (ABCD) F = {AB -> C, B -> D; C -> A}

The function dependency B -> D violate BCNF because B is not a superkey so I converted the relation in BCNF by decomposing it in 3 relations using this algorithm:

Given a schema R.

    Compute keys for R.
    Repeat until all relations are in BCNF.
        Pick any R' having a F.D A --> B that violates BCNF.
        Decompose R' into R1(A,B) and R2(A,Rest of attributes).
        Compute F.D's for R1 and R2.
        Compute keys for R1 and R2.

The result I got (which is correct as I checked the available solution) is:

R1:(BD), R2:(CA), R3:(BC).

I know that a property of the conversion algorithm is that the decomposition preserves the data and I want to prove it as en exercise.

Usually with a decomposition into two relations R1 and R2 the procedure is: check for the attributes in common between R1 and R2, do the closure of the result you found, if the closure include all the attributes of either R1 or R2 then the decomposition preserve the data, else is does not.

In the case of this exercise there are no attributes in common between R1,R2 and R3, so I can't do the closure to determine if the decomposition preserve data or not and I don't know how else I could proceed. What should I do the prove that the decomposition is lossless?

Your "I have these FDs" doesn't make sense. "These are all the FDs that hold"?--Not possible. "These are all the non-trivial FDs that hold"?--Not possible. "These are some FDs that hold"?--Question can't be answered. Find out what a *cover* is & what the exact conditions are to apply a particular definition/rule/algorithm. To determine CKs & NFs we must be given FDs that form a cover. Sometimes a minimal/irreducible cover. And the set of all attributes must be given. [See this answer.](https://stackoverflow.com/a/53386492/3404097) — philipxy, Aug 09 '21 at 19:27
Please: Clarify via edits, not comments. Put what is needed to ask your question in your question as text not just a link. Please act on the rest of my comments. PS [How do I ask and answer homework questions?](https://meta.stackoverflow.com/q/334822/3404097) [What is the policy here on homework?](https://meta.stackexchange.com/q/18242/266284) — philipxy, Aug 09 '21 at 20:57
@philipxy by intersection of the 3 relations is Ø I mean that there is no attribute in common between the 3 relations when doing the intersection. In two relations decomposition you have to check for R1 ∩ R2 → R1 or R1 ∩ R2 → R2, in this case I don't know how to proceed. — Spyromancer, Aug 09 '21 at 20:59
"Clarify via edits, not comments." Etc etc. PS You are confusing using symbols for relations with using the same symbols for sets of attributes that are the headings/schemas of relations. PS Use enough words, sentences & references to parts of examples to clearly & fully say what you mean. — philipxy, Aug 09 '21 at 21:06
There's still no question in this post. You make a bunch of statements. (And if the question is about proving losslessness, the decomposition details are not relevant.) Etc etc. (Including, quote relevant definitions & theorems, including the 1 theorem you were given about losslessness & FDs.) (Should we if you won't?) Also the statements near the end are still not clear about your reasoning or how they have bearing on whatever your question is. PS https://stackoverflow.com/a/58190709/3404097 — philipxy, Aug 09 '21 at 21:38
@philipxy " the decomposition details are not relevant." I think they are relevant because they show that I know the common situation where you have a decomposition into two relations and you have to check for the intersection of R1 and R2 and find the closure of that result to determine if the decomposition is lossless or not. "There's still no question in this post." That situation I explained is different from this specific situation where I stated that I don't know how to proceed which is the reason why I made this post. — Spyromancer, Aug 09 '21 at 21:48

Renzo · Accepted Answer · 2021-08-11T10:07:16.970

To show that the decomposition is lossless, you can proceed in two steps, along the lines of the steps of the decomposing algorithm.

Starting from your schema, let’s apply the first step of the algorithm.

(1) R = (ABCD) F = {AB -> C, B -> D; C -> A}

considering that B -> D violates the BCNF (since the candidate keys are AB and BC), we decompose R in:

(2) R1 = (BD), F1 = {B -> D} and R2 = {ABC}, F2 = {C -> A, AB -> C}

Here we can prove that R1 and R2 are a lossless decomposition, since their intersection is {B}, which is a candidate key for F1 (according to the theorem the you cited).

Now, since R2 is not in BCNF because of C -> A, according to the algorithm we must decompose R2 in R3 = (CA) and R4 = (CB), so the final decomposition is {R1 = (BD), R3 = (CA), R4 = (CB)}. To show the this decomposition of R is lossless, we can use another theorem that says:

If ρ = {R₁,..., R_m} is a lossless decomposition of R<T,F> (where T are the attributes of R and F are a cover of the dependencies of R), and σ = {S₁, S₂} a lossless decomposition of R₁ with respect to π_(T₁)(F), then the decomposition {S₁, S₂, R₂, ..., R_m) is lossless with respect to F.

In the theorem, π_(T₁)(F) is the projection of the dependencies F onto the attributes T₁ of R₁.

In this case, we decompose R2(ABC) and π_(T₂)(F) = {C -> A, AB -> C}, so the theorem can be applied since R3 and R4 are a lossless decomposition with respect to those dependencies.

This assumes F is a cover & doesn't explain what R(T,F) means or what "lossless decomposition with respect to" means. Also it doesn't say what F1 & F2 have to do with R1 & R2 or justify it. (And once you justify it, you can just reuse the 1st theorem on the 2nd decomposition & you don't need the 2nd theorem.) — philipxy, Aug 11 '21 at 03:28

score 1 · Answer 2 · answered Oct 03 '22 at 21:49

a decomposition is lossless if we can recover r by using a natural join on the decomposed relations.

if we don't lose the exact information(instance) that was on r, it's lossless.

Now, there is a rule that says that if we have two decomposed relations we can determine whether the decomposition is lossless by intersecting R1 with R2 and if the result we get is an attribute that is a superkey for at least one of them, then the decomposition is lossless.

That's all good but what do we do when we have more than two decomposed relations ? How can we check if the decomposition is lossless in that case ?

well, let's take a look at the following picture for a second.

on this picture each circle represents a relation.

now what we are going to do with that picture ? we are going to apply the rule i stated above about finding if decomposition between two relations is lossless and draw a connecting lines between those relation that fulfill the rule.

so for example on this picture we found that R1 and R3 share a common attribute which is B now B is a superkey for R1, because those conditions are fulfilled we draw a line connecting between those relations.

So we get

now we find a common attribute with R2 and we see that R3 also have C and C is a superkey for R2.

because those conditions are fulfilled we draw a line connecting between R2 and R3

So in that "Graph" you could say, we can "travel" to all the circles because the lines are connected and we don't have any isolation.

so we can move from R1 to R3 and to R2.

because we got such Graph we can say that the decomposition is lossless so R1 ⋈ R3 ⋈ R2 = R

Proof that a decomposition into 3 relations is lossless

2 Answers2