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
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