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

Polynomials
Joining

Cite this

Loizou, G ; Thanisch, P. / Losslessness and project-join constructibility in relational databases. In: Acta Informatica. 1987 ; Vol. 24, No. 2. pp. 131-144.
@article{10046f7d2c404f9cbf16b195b7941979,
title = "Losslessness and project-join constructibility in relational databases",
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. {\circledC} 1987 Springer-Verlag.",
author = "G Loizou and P Thanisch",
year = "1987",
month = "4",
doi = "10.1007/BF00264360",
language = "English",
volume = "24",
pages = "131--144",
journal = "Acta Informatica",
issn = "0001-5903",
publisher = "Springer",
number = "2",

}

Losslessness and project-join constructibility in relational databases. / Loizou, G; Thanisch, P.

In: Acta Informatica, Vol. 24, No. 2, 04.1987, p. 131-144.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Losslessness and project-join constructibility in relational databases

AU - Loizou, G

AU - Thanisch, P

PY - 1987/4

Y1 - 1987/4

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0023328444&partnerID=8YFLogxK

U2 - 10.1007/BF00264360

DO - 10.1007/BF00264360

M3 - Article

VL - 24

SP - 131

EP - 144

JO - Acta Informatica

JF - Acta Informatica

SN - 0001-5903

IS - 2

ER -