Optimization of a subclass of conjunctive queries

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 atmost one attribute to violate the simple-tablau 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²) optimization algorithm based on the implication graph technique. The optimization of typed fan-out queries, obtained from simple tableaux by allowing atmost 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.Supported by DFG grant Bi 311/1-2; present address: School of Computer & Systems Sciences, Jawaharlal Nehru University, New Delhi 110067, India.Supported by NSF grant IRI-87-22886, AFOSR grant 88-0266 and a grant from IBM Corp.