The Power of Tree Projections: When Local Consistency Answers Conjunctive Queries
Gianluigi Greco, Francesco Scarcello · arXiv (Cornell University) · 2012
Enforcing local consistency is a well-known technique to simplify the evaluation of conjunctive queries. It consists of repeatedly taking the semijion between every pair of query atoms, until the procedure stabilizes. If some relation becomes empty, then the query has an empty answer. Otherwise, we cannot say anything in general, unless we have some information on the structure of the given query. In fact, a fundamental result in database theory states that the class of queries for which---on every database---local consistency entails global consistency is precisely the class of acyclic queries. In the last few years, several efforts have been spent to define structural decomposition methods isolating larger classes of nearly-acyclic queries, yet retaining the same nice properties as acyclic ones. In this paper, we precisely characterize the power of local consistency procedures in the general framework of tree projections, where a query Q and a set W of views (i.e., resources that can be used to answer Q) are given, and where one looks for an acyclic hypergraph covering Q, and covered by W---all known structural decomposition methods are just special cases of this framework, defining their specific set of resources. We show that the existence of tree projections of certain subqueries is a necessary and sufficient condition to guarantee that local consistency allows the query to be answered efficiently, even without computing any tree projection. In particular, tight characterizations are given not only for the decision problem, but also when answers have to be computed.