OPTIMIZATION OF A SUBCLASS OF CONJUNCTIVE QUERIES

The optimization problem for a subclass of conjunctive queries which i s formed by the union of the class of fan-out free queries and a subcl ass of typed fan-out queries is investigated. The typed fan-out querie s in this class are obtained from simple tableaux by allowing atmost o ne attribute to violate the simple-tableau property. The optimization problem for several restricted subsets of typed fan-out queries is alr eady known to be NP-hard. It is shown that the queries under considera tion possess several useful properties which are then used to obtain a n O(n(2)) optimization algorithm based on the implication graph techni que. The optimization of typed fan-out queries, obtained from simple t ableaux by allowing atmost two attributes to violate the simple tablea u property, is shown to be NP-hard. The optimization of simple tableau x in the presence of functional dependencies is also investigated and is shown to be NP-hard.