Journal of the ACM Bibliography

Preliminary version

A preliminary version of these results was presented in: Michael Benedikt, Guozhu Dong, Leonid Libkin, and Limsoon Wong. Relational expressive power of constraint query languages. In Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 5-16, Montreal, Canada, 3-5 June 1996.

Categories and Subject Descriptors: F.4.1 [Mathematical Logic and Formal Languages]: Mathematical Logic; H.2.3 [Database Management]: Languages

General Terms: Languages, Theory

Additional Key Words and Phrases: Constraints, constraint query language, database, expressive power, relational calculus

Selected papers that cite this one

• Michael Benedikt, Timothy Griffin, and Leonid Libkin. Verifiable properties of database transactions. Accepted for publication in Information and Computation. Final manuscript received for publication February 24, 1998.

Selected references

• Foto N. Afrati, Theodoros Andronikos, and Theodoros G. Kavalieros. On the expressiveness of first-order constraint languages. In Gabriel M. Kuper and Mark Wallace, editors, Constraint Databases and Applications, volume 1034 of Lecture Notes in Computer Science, pages 22-39, Friedrichshafen, Germany, 8-9 September 1995. Springer, 1996.

• Alfred V. Aho and Jeffrey D. Ullman. The universality of data retrieval languages. In Conference Record of the Sixth Annual ACM Symposium on Principles of Programming Languages, pages 110-120, San Antonio, Texas, January 1979.

• Michael Benedikt and H. Jerome Keisler. Expressive power of unary counters. In Foto N. Afrati and Phokion Kolaitis, editors, Database Theory -- ICDT'97, 6th International Conference, volume 1186 of Lecture Notes in Computer Science, pages 291-305, Delphi, Greece, 8-10 January 1997. Springer.

• Michael Benedikt and Leonid Libkin. On the structure of queries in constraint query languages. In Proceedings, 11th Annual IEEE Symposium on Logic in Computer Science, pages 25-34, New Brunswick, New Jersey, 27-30 July 1996. IEEE Computer Society Press.

• Michael Benedikt and Leonid Libkin. Languages for relational databases over interpreted structures. In Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 87-98, Tucson, Arizona, 12-15 May 1997.

• Ashok K. Chandra and David Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156-178, October 1980.

• Stéphane Grumbach and Jianwen Su. Finitely representable databases. In Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 289-300, Minneapolis, Minnesota, 24-26 May 1994.

• Richard Hull and Jianwen Su. Domain independence and the relational calculus. Acta Informatica, 31(6):513-524, 1994.

• Richard Hull and Chee K. Yap. The format model: A theory of database organization. Journal of the ACM, 31(3):518-537, July 1984.

• Paris C. Kanellakis. Constraint programming and database languages: A tutorial. In Proceedings of the Fourteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 46-53, San Jose, California, 22-25 May 1995.

• Paris C. Kanellakis, Gabriel M. Kuper, and Peter Z. Revesz. Constraint query languages. Journal of Computer and System Sciences, 51(1):26-52, August 1995.

• Gabriel M. Kuper. On the expressive power of the relational calculus with arithmetic constraints. In S. Abiteboul and P. C. Kanellakis, editors, ICDT'90, Third International Conference on Database Theory, volume 470 of Lecture Notes in Computer Science, pages 202-211, Paris, France, 12-14 December 1990. Springer.

• Martin Otto and Jan Van den Bussche. First-order queries on databases embedded in an infinite structure. Information Processing Letters, 60(1):37-41, 14 October 1996.

• Jan Paredaens, Jan Van den Bussche, and Dirk Van Gucht. Towards a theory of spatial database queries. In Proceedings of the Thirteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 279-288, Minneapolis, Minnesota, 24-26 May 1994.

• Jan Paredaens, Jan Van den Bussche, and Dirk Van Gucht. First-order queries on finite structures over the reals. In Proceedings, Tenth Annual IEEE Symposium on Logic in Computer Science, pages 79-87, San Diego, California, 26-29 June 1995. IEEE Computer Society Press.

• Alexei P. Stolboushkin and Michael A. Taitslin. Linear vs. order contstrained queries over rational databases. In Proceedings of the Fifteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, pages 17-27, Montreal, Canada, 3-5 June 1996.

Shortcuts: