We address the problem of deriving lower and upper bounds for the cardinality of the projections of a database relation, given a set of functional dependencies on the relation schema and measures of the cardinalities of the attributes in the schema. It is shown that deciding whether a given number is the least upper bound of a projection cardinality is an NP-complete problem, whereas determining whether the greatest lower bound and the least upper bound coincide can be easily solved in linear time. © 1992.
Ciaccia P., Maio D. (1992). On the complexity of finding bounds for projection cardinalities in relational databases. INFORMATION SYSTEMS, 17(6), 511-515 [10.1016/0306-4379(92)90029-M].
On the complexity of finding bounds for projection cardinalities in relational databases
Ciaccia P.;Maio D.
1992
Abstract
We address the problem of deriving lower and upper bounds for the cardinality of the projections of a database relation, given a set of functional dependencies on the relation schema and measures of the cardinalities of the attributes in the schema. It is shown that deciding whether a given number is the least upper bound of a projection cardinality is an NP-complete problem, whereas determining whether the greatest lower bound and the least upper bound coincide can be easily solved in linear time. © 1992.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
