Lossless join decomposition
   HOME

TheInfoList



OR:

In
database design Database design is the organization of data according to a database model. The designer determines what data must be stored and how the data elements interrelate. With this information, they can begin to fit the data to the database model.Teorey, ...
, a lossless join decomposition is a decomposition of a relation R into relations R_1, R_2 such that a natural join of the two smaller relations yields back the original relation. This is central in removing redundancy safely from
database In computing, a database is an organized collection of data stored and accessed electronically. Small databases can be stored on a file system, while large databases are hosted on computer clusters or cloud storage. The design of databases sp ...
s while preserving the original data.


Criteria

Lossless join can also be called nonadditive. If R is split into R_1 and R_2, for this decomposition to be lossless (i.e., R_1 \bowtie R_2 = R) then at least one of the two following criteria should be met.


Check 1: Verify join explicitly

Projecting on R_1 and R_2, and joining them back, results in the relation you started with.


Check 2: Via functional dependencies

Let R be a relation schema. Let be a set of
functional dependencies In relational database theory, a functional dependency is a constraint between two sets of attributes in a relation from a database. In other words, a functional dependency is a constraint between two attributes in a relation. Given a relation ' ...
on R. Let R_1 and R_2 form a decomposition of R . The decomposition is a lossless-join decomposition of R if at least one of the following functional dependencies are in + (where + stands for the closure for every attribute or attribute sets in ): * R_1 \cap R_2 \rightarrow R_1 * R_1 \cap R_2 \rightarrow R_2


Examples

* Let R = (A, B, C, D) be the relation schema, with attributes , , and . * Let F = \ be the set of functional dependencies. * Decomposition into R_1 = (A, B, C) and R_2 = (A, D) is lossless under because R_1 \cap R_2 = A). is a superkey in R_1, meaning we have a functional dependency \.  In other words, now we have proven that (R_1 \cap R_2 \rightarrow R_1) \in F^+.


References

{{Reflist Databases Data modeling Database constraints Database normalization Relational algebra