Optimization of a subclass of conjunctive queries (Q1346219)

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.