Languages for relational databases over interpreted structures

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Languages for relational databases over interpreted structures

Full text

Pdf (2.21 MB)

Source

Symposium on Principles of Database Systems archive
Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems table of contents

Tucson, Arizona, United States

Pages: 87 - 98

Year of Publication: 1997

ISBN:0-89791-910-6

Authors

Michael Benedikt	Bell Laboratories, 1000 E. Warrenville Rd., Naperville, IL
Leonid Libkin	Bell Laboratories, 600 Mountain Avenue, Murray Hill, NJ

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 14, Citation Count: 11

Additional Information:

references cited by index terms collaborative colleagues

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/263661.263672 What is a DOI?

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	2	Serge Abiteboul , Victor Vianu, Datalog extensions for database queries and updates, Journal of Computer and System Sciences, v.43 n.1, p.62-124, Aug. 1991 [doi>10.1016/0022-0000(91)90032-Z]
	3	A.K. Ailamazyan, M.M. Gihla, A.P. Stolboushkin and G.F. Shwrts. Reduction of a rdational model with infinite domains to the finite-domain case. Soviet Physics - Doklady, 31 (1986), 11-13.
	4	David A. Mix-Barrington , Neil Immerman , Howard Straubing, On uniformity within NC1, Journal of Computer and System Sciences, v.41 n.3, p.274-306, Dec. 1990 [doi>10.1016/0022-0000(90)90022-D]
	5	Catriel Beeri , Tova Milo, Functional and predictive programming in OODB's, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.176-190, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137863]
	6	Michael Benedikt , Guozhu Dong , Leonid Libkin , Limsoon Wong, Relational expressive power of constraint query languages, Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.5-16, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237667]
	7	Michael Benedikt , Leonid Libkin, On the Structure of Queries in Constraint Query Languages, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.25, July 27-30, 1996
	8	M. Benedikt and L. Libkin. Languages for relational databases over interpreted structures. Technical Memo, Bell Labs, 1996.
	9	Michael Ben-Or , Dexter Kozen , John Reif, The complexity of elementary algebra and geometry, Journal of Computer and System Sciences, v.32 n.2, p.251-264, April 1986 [doi>10.1016/0022-0000(86)90029-2]
	10	L. Cabibbo and J. Van den Bussche. On the expressive power of many-sorted logic. Manuscript, 1996.
	11	A. Chandra and D. Hard. Computable queries for relational databases. JGSS 21(2):156-178, 1980.
	12	A. Chandra and D. Hard. Structure and complexity of relational queries. JGSS 25 (1982), 99-128.
	13	C.C. Chang and H.J. Keisler. Model Theory. North Holland, 1990.
	14	Anuj Dawar , Steven Lindell , Scott Weinstein, First Order Logic, Fixed Point Logic and Linear Order, Selected Papers from the9th International Workshop on Computer Science Logic, p.161-177, September 22-29, 1995
	15	H.-D. Ebbinghaus and J. Fhm. Finite Model Theory. Springer Verlag, 1995.
	16	Martha Escobar-Molano , Richard Hull , Dean Jacobs, Safety and translation of calculus queries with scalar functions, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.253-264, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153909]
	17	Kousha Etessami, Counting quantifiers, successor relations, and logarithmic space, Journal of Computer and System Sciences, v.54 n.3, p.400-411, June 1997 [doi>10.1006/jcss.1997.1485]
	18	Erich Grädel , Yuri Gurevich, Metafinite Model Theory, Selected Papers from the International Workshop on Logical and Computational Complexity, p.313-366, October 13-16, 1994
	19	R.L. Graham, B.L. Rothschild and 3.H. Spencer. Ram. sey Theory. John Wiley & Sons, 1990.
	20	Stéphane Grumbach , Jianwen Su, First-order Definability over Constraint Databases, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.121-136, September 19-22, 1995
	21	Y. Gurevich and S. Shelah. Fixed-point extensions of first-order logic. Annals of Pure and Applied I, ogic 32 (1986), 265-280.
	22	Richard Hull , Jianwen Su, On the expressive power of database queries with intermediate types, Journal of Computer and System Sciences, v.43 n.1, p.219-267, Aug. 1991 [doi>10.1016/0022-0000(91)90036-5]
	23	Richard Hull , Jianwen Su, Domain independence and the relational calculus, Acta Informatica, v.31 n.6, p.513-524, Sept. 1994 [doi>10.1007/BF01213204]
	24	Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
	25	Michael Kifer , Raghu Ramakrishnan , Avi Silberschatz, An axiomatic approach to deciding query safety in deductive databases, Proceedings of the seventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.52-60, March 1988, Austin, Texas, United States [doi>10.1145/308386.308412]
	26	Phokion G. Kolaitis , Moshe Y. Vardi, 0-1 laws and decision problems for fragments of second-order logic, Information and Computation, v.87 n.1-2, p.302-338, July/August 1990 [doi>10.1016/0890-5401(90)90065-P]
	27	Phokion G. Kolaitis , Moshe Y. Vardi, Infinitary logics and 0–1 laws, Information and Computation, v.98 n.2, p.258-294, June 1992 [doi>10.1016/0890-5401(92)90021-7]
	28	Alon Levy , Inderpal Singh Mumick , Yehoshua Sagiv , Oded Shmueli, Equivalence, query-reachability and satisfiability in Datalog extensions, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-122, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153860]
	29	Leonid Libkin , Limsoon Wong, Query languages for bags and aggregate functions, Journal of Computer and System Sciences, v.55 n.2, p.241-272, Oct. 1997 [doi>10.1006/jcss.1997.1523]
	30	Yiannis N Moschovakis, Elementary induction on abstract structures (Studies in logic and the foundations of mathematics), American Elsevier Pub. Co, 1974
	31	Martin Otto , Jan Van den Bussche, First-order queries on databases embedded in an infinite structure, Information Processing Letters, v.60 n.1, p.37-41, Oct. 14, 1996 [doi>10.1016/S0020-0190(96)00140-8]
	32	Jan Paredaens , Jan Van den Bussche , Dirk Van Gucht, First-Order Queries on Finite Structures Over the Reals, Proceedings of the 10th Annual IEEE Symposium on Logic in Computer Science, p.79, June 26-29, 1995
	33	A. Pillay, C. Steinhorn. Definable sets in ordered structures. III. Trans. of the AMS 309 (1988), 469-476.
	34	Alexei P. Stolboushkin , Michael A. Taitslin, Linear vs. order constraint queries over rational databases (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.17-27, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237669]
	35	A. Tarski. A Decision Method }or Elementary Algebra and Geometry. 2nd ed., Univ. California Pressj 1951.
	36	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	37	Moshe Y. Vardi, On the complexity of bounded-variable queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.266-276, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212474]

CITED BY 11

	Luc Vandeurzen , Marc Gyssens , Dirk Van Gucht, An expressive language for linear spatial database queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.109-118, June 01-04, 1998, Seattle, Washington, United States
	Saugata Basu, New results on quantifier elimination over real closed fields and applications to constraint databases, Journal of the ACM (JACM), v.46 n.4, p.537-555, July 1999
	Sergei Vorobyov , Andrie Voronkov, Complexity of nonrecursive logic programs with complex values, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.244-253, June 01-04, 1998, Seattle, Washington, United States
	Evgeny Dantsin , Thomas Eiter , Georg Gottlob , Andrei Voronkov, Complexity and expressive power of logic programming, ACM Computing Surveys (CSUR), v.33 n.3, p.374-425, September 2001
	Michael Benedikt , Guozhu Dong , Leonid Libkin , Limsoon Wong, Relational expressive power of constraint query languages, Journal of the ACM (JACM), v.45 n.1, p.1-34, Jan. 1998
	Evgeny Dantsin , Andrei Voronkov, Expressive power and data complexity of nonrecursive query languages for lists and trees (extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.157-165, May 15-18, 2000, Dallas, Texas, United States
	Michael Benedikt , Leonid Libkin, Relational queries over interpreted structures, Journal of the ACM (JACM), v.47 n.4, p.644-680, July 2000
	Michael Benedikt , Leonid Libkin, Exact and approximate aggregation in constraint query languages, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.102-113, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Saugata Basu, Uniform quantifier elimination and constraint query processing, Proceedings of the 1997 international symposium on Symbolic and algebraic computation, p.21-27, July 21-23, 1997, Kihei, Maui, Hawaii, United States
	David Gross , Michel de Rougemont, Uniform generation in spatial constraint databases and applications (Extended abstract), Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.254-259, May 15-18, 2000, Dallas, Texas, United States
	Michael Benedikt , Leonid Libkin, Safe constraint queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.99-108, June 01-04, 1998, Seattle, Washington, United States