Testing containment of conjunctive queries under functional and inclusion dependencies

From MaRDI portal





The relational database model is studied from the point of view of optimization of queries. A brief basic definition of the relational database model, a formal definition of inclusion (IND) and functional (FD) dependencies and the key-based property are presented (Section 2). Next, the authors show how to test for query containment in nondeterministic polynomial time if the set of dependencies obeys a fixed bound on IND width and either contains no FD or is key-based. The results assume that infinite databases are allowed (Section 3). The following discussion deals with a more practical problem: containment for finite databases (Section 4). Final remarks and a discussion of open problems and directions of future research are added to conclude the article.




Cited in
(53)








This page was built for publication: Testing containment of conjunctive queries under functional and inclusion dependencies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1057666)