Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 53 Issue 2, March 2006

Dan Suciu, Victor Vianu
Page: 207
DOI: 10.1145/1131342.1131343

On preservation under homomorphisms and unions of conjunctive queries
Albert Atserias, Anuj Dawar, Phokion G. Kolaitis
Pages: 208-237
DOI: 10.1145/1131342.1131344
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
Pages: 238-272
DOI: 10.1145/1131342.1131345
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
Pages: 273-305
DOI: 10.1145/1131342.1131346
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...