enter search term and/or author name
On preservation under homomorphisms and unions of conjunctive queries
Albert Atserias, Anuj Dawar, Phokion G. Kolaitis
Unions of conjunctive queries, also known as select-project-join-union queries, are the most frequently asked queries in relational database systems. These queries are definable by existential positive first-order formulas and are preserved under...
Conjunctive queries over trees
Georg Gottlob, Christoph Koch, Klaus U. Schulz
We study the complexity and expressive power of conjunctive queries over unranked labeled trees represented using a variety of structure relations such as “child”, “descendant”, and “following” as well as unary...
A characterization of first-order topological properties of planar spatial data
Michael Benedikt, Bart Kuijpers, Christof Löding, Jan Van den Bussche, Thomas Wilke
Planar spatial datasets can be modeled by closed semi-algebraic sets in the plane. We establish a characterization of the topological properties of such datasets expressible in the relational calculus with real polynomial constraints. The...