Compilation of Query-Rewriting Problems into Tractable Fragments of Propositional Logic

We consider the problem of rewriting a query efficiently using materialized views. In the context of information integration, this problem has received significant attention in the scope of emerging infrastructures such as WWW, Semantic Web, Grid, and P2P which require efficient algorithms. The problem is in general intractable, and the current algorithms do not scale well when the number of views or the size of the query grow. We show however that this problem can be encoded as a propositional theory in CNF such that its models are in correspondence with the rewritings of the query. The theory is then compiled into a normal form, that is called d-DNNF and supports several operations like model counting and enumeration in polynomial time (in the size of the compiled theory), for computing the rewritings. Although this method is also intractable in the general case, it is not necessarily so in all cases. We have developed, along these lines and from offthe-shelf propositional engines, novel algorithms for finding maximally-contained rewritings of the query given the set of accessible resources (views). The algorithms scale much better than the current state-of-the-art algorithm, the MiniCon algorithm, over a large number of benchmarks and show in some cases improvements in performance of a couple ordersof-magnitude.

Authors

• Yolife Arvelo Blai Bonet

Keywords

No keywords are indexed for this paper.