Query Rewriting using Semistructured Views

Yannis Papakonstantinou       Vasilis Vassalos*
UC San Diego       Stanford University
yannis@cs.ucsd.edu       vassalos@cs.stanford.edu

Abstract

We address the problem of query rewriting for b-MSL, which is a fragment of MSL, a semistructured language developed at Stanford in the TSIMMIS project for information integration. We develop and present an algorithm that, given a semistructured query q and a set of semistructured views V, finds rewriting queries, i.e., queries that access the views and produce the same result as q. Our algorithm is based on appropriately generalizing containment mappings, the chase, and unification -- techniques that were developed for structured, relational data. We also develop an algorithm for equivalence checking of b-MSL queries.

We show that the algorithm is sound and complete for b-MSL, i.e., it always finds every b-MSL rewriting query of q, and we discuss its complexity. We currently incorporate the algorithm in the TSIMMIS system.