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

Proceedings of the AAAI Conference on Artificial Intelligence, 21

Volume

Technical Papers

Knowledge Representation and 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 off the 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 orders of magnitude.