Testing containment of conjunctive queries under functional and inclusion dependencies (Q1057666)

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.