Optimization of a subclass of conjunctive queries (Q1346219)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Optimization of a subclass of conjunctive queries
scientific article

    Statements

    Optimization of a subclass of conjunctive queries (English)
    0 references
    0 references
    0 references
    0 references
    22 March 1995
    0 references
    The optimization problem for a subclass of conjunctive queries which is formed by the union of the class of fan-out free queries and a subclass of typed fan-out queries is investigated. The typed fan-out queries in this class are obtained from simple tableaux by allowing at most one attribute to violate the simple-tableau property. The optimization problem for several restricted subsets of typed fan-out queries is already known to be NP-hard. It is shown that the queries under consideration possess several useful properties which are then used to obtain an \(O(n^ 2)\) optimization algorithm based on the implication graph technique. The optimization of typed fan-out queries, obtained from simple tableaux by allowing at most two attributes to violate the simple tableau property, is shown to be NP-hard. The optimization of simple tableaux in the presence of functional dependencies is also investigated and is shown to be NP-hard.
    0 references
    query optimization
    0 references
    otimization problem
    0 references
    implication graph technique
    0 references

    Identifiers