Query Rewriting using Semistructured Views

We address the problem of query rewriting for 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 which were developed for structured, relational data. At the same time we develop an algorithm for equivalence checking of MSL queries. We show that the rewriting algorithm is sound and complete, i.e., it always finds every conjunctive MSL rewriting query of q, and we discuss its complexity. We currently incorporate the algorithm in the TSIMMIS system. 1 Introduction Recently, many semistructured data models, query and view definition languages have been proposed [GM + 97, MAG + 97, BDHS96, AV97a, MM97, KS95, PGMU96,..