The process of normalizing a global schema involves its decomposition into sub-schemas, on the basis of data dependencies existing in the global schema. While decomposing a schema into sub-schemas, it is to be ensured that the decomposition is lossless-join decomposition (or non-loss decomposition). Presently, there exists an algorithm proposed by Aho, Beeri and Ullman (1979), popularly known as ABU's algorithm, that is used to determine whether a given decomposition is a non-loss decomposition or not. This paper proposes a graph-based algorithm to perform the same task.

Decomposition *(R₁, R₂,…..R_n) of a relational schema R is said to be a non-loss decomposition (where R₁ È R₂ È…….ÈR_n = R), if for each legal relation r(R), the following equality is satisfied:

r(R)= Õ_R1(r) * Õ_R2(r)*…..* Õ_Rn(r), where R_i(r) represents a projection of relation `r' (1 < i < n).

This implies that a decomposition *(R₁,R₂,….. R_n) of R would be non-loss, if each legal relation r(R) can be exactly reconstructed from the natural join of its projections; with no spurious tuple added.

In the case of a lossy decomposition, the natural join of the projections of a legal relation r(R) would have some spurious tuples added to the relation r, i.e., the following inequality will hold:

r (R) Ì Õ_R1(r) * Õ_R2(r) *…….*Õ_Rn(r )

This implies that r(R) will be a proper subset of the natural join of its projections. Thus, a lossy decomposition is, in fact, an `additive' decomposition, wherein some spurious tuples (the tuples, which did not exist in the original relation `r') are added. That is why non-loss decomposition is sometimes referred to as `non-additive' decomposition.