Losslessness and project-join constructibility in relational databases

G Loizou, P Thanisch

Research output: Contribution to journalArticle

Abstract

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
Volume24
Issue number2
DOIs
Publication statusPublished - Apr 1987

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

  • Cite this