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

From MaRDI portal
scientific article
Language Label Description Also known as
English
Testing containment of conjunctive queries under functional and inclusion dependencies
scientific article

    Statements

    Testing containment of conjunctive queries under functional and inclusion dependencies (English)
    0 references
    0 references
    1984
    0 references
    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.
    0 references
    0 references
    functional dependencies
    0 references
    inclusion dependencies
    0 references
    relational database
    0 references
    optimization of queries
    0 references
    query containment
    0 references
    0 references
    0 references