An Efficient Algorithm for Testing Losslessness of Joins in Relational Data Bases

Abstract

Answering queries in a relational database model often requires the computation of joins of relations. Losslessness of joins is an important property for joins of relations to be semantically meaningful. In this paper we present an $O(n^{3})$ algorithm for testing losslessness of joins in relational databases with functional dependencies, which improves the $O(n^{4})$ result by Aho, Beeri and Ullman.