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, T ...
, a lossless join decomposition is a decomposition of a
relation
Relation or relations may refer to:
General uses
* International relations, the study of interconnection of politics, economics, and law on a global level
* Interpersonal relationship, association or acquaintance between two or more people
* ...
into relations
such that a
natural join In relational algebra, a join is a binary operation, written as R \bowtie S where R and S represent relations, that combines their data where they have a common attribute.
Natural join
Natural join (⨝) is a binary operator that is written as ...
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 or a type of data store based on the use of a database management system (DBMS), the software that interacts with end users, applications, and the database itself to capture and a ...
s while preserving the original data. Lossless join can also be called non-additive.
Definition
A relation
on schema
''decomposes losslessly'' onto schemas
and
if
, that is
is the natural join of its
projections onto the smaller schemas.
A pair
is a ''lossless-join decomposition'' of
or said to ''have a lossless join'' with respect to a set of
functional dependencies if any relation
that satisfies
decomposes losslessly onto
and
.
Decompositions into more than two schemas can be defined in the same way.
Criteria
A decomposition
has a lossless join with respect to
if and only if
In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
the
closure of
includes
or
. In other words, one of the following must hold:
*
*
Criteria for multiple sub-schemas
Multiple sub-schemas
have a lossless join if there is some way in which we can repeatedly perform lossless joins until all the schemas have been joined into a single schema. Once we have a new sub-schema made from a lossless join, we are not allowed to use any of its isolated sub-schema to join with any of the other schemas. For example, if we can do a lossless join on a pair of schemas
to form a new schema
, we use this new schema (rather than
or
) to form a lossless join with another schema
(which may already be joined (e.g.,
)).
Example
* Let
be the relation schema, with attributes , , and .
* Let
be the set of functional dependencies.
* Decomposition into
and
is lossless under because
and we have a functional dependency
. In other words, we have proven that
.
References
{{Reflist
Databases
Data modeling
Database constraints
Database normalization
Relational algebra