Principles of Guarded Structural Indexing

We present a new structural characterization of the expressive power of the acyclic conjunctive queries in terms of guarded simulations, and give a nite preservation theorem for the guarded simulation invariant fragment of rst order logic. We discuss the relevance of these results as a formal basis for constructing so-called guarded structural indexes. Structural indexes were rst proposed in the context of semistructured query languages and later successfully applied as an XML indexation mechanism for XPath-like queries on trees and graphs. Guarded structural indexes provide a generalization of structural indexes from graph databases to relational databases.