Losslessness and project-join constructibility in relational databases

G Loizou, P Thanisch

Research output: Contribution to journalArticlepeer-review


Checking a database scheme for the lossless join property with respect to a set, M, of multivalued dependencies (MVDs) is NP-hard. We prove that, for a class of MVDs that includes the set of projected full MVDs, this check can be performed in polynomial time. Even with a lossless database scheme and a consistent database, joining the set of relations in the database can take time and space that is exponential in the size of the relation finally obtained. Joining the set of relations of such a database can be performed in polynomial time if the database scheme is project-join constructible with respect to M. We prove that project-join constructibility, a stricter condition than the lossless join property, can be detected in a database scheme in polynomial time. © 1987 Springer-Verlag.

Original languageEnglish
Pages (from-to)131-144
Number of pages14
JournalActa Informatica
Issue number2
Publication statusPublished - Apr 1987


Dive into the research topics of 'Losslessness and project-join constructibility in relational databases'. Together they form a unique fingerprint.

Cite this