On guarded simulations and acyclic first-order languages
George Fletcher, Jan Hidders, Stijn Vansummeren, Yongming Luo, François Picalausa, Paul M. De Bra · 2011
An exact structural characterization of the expressive power of the acyclic conjunctive queries is given in terms of guarded simulations. The study of this fragment of first order logic is motivated by the central role it plays in query languages across a wide range of data models. The study of a structural characterization of the language is motivated by the applications of such characterizations, for example, in the design of efficient indexing and query processing strategies. In addition to a presentation of our main result, we discuss the results of a small empirical study which indicate the practicality of guarded simulation based reductions of database instances. 1.