On the containment and equivalence of database queries with linear constraints (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the containment and equivalence of database queries with linear constraints (extended abstract)

Full text

Pdf (1.70 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: 32 - 43

Year of Publication: 1997

ISBN:0-89791-910-6

Authors

Oscar H. Ibarra	Department of Computer Science, University of California, Santa Barbara, California
Jianwen Su	Department of Computer Science, University of California, Santa Barbara, California

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 15, Citation Count: 4

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.263666 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.

	AHV95	Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
	ASU79a	A. V. Aho , Y. Sagiv , J. D. Ullman, Efficient optimization of a class of relational expressions, ACM Transactions on Database Systems (TODS), v.4 n.4, p.435-454, Dec. 1979 [doi>10.1145/320107.320112]
	ASU79b	A. V. Aho, Y. Sagiv, and 1. D. UUman. Equivalence among relational expressions. SIAM Journal on Computing, 8(2):218-246, May 1979.
	BB74	B. Baker and R. Book. Reversal-bounded multipushdown machines. Journal of Computer and System Sciences, 8:315-332, 1974.
	BDLW96	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]
	BL96	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
	Che76	Peter Pin-Shan Chen, The entity-relationship model—toward a unified view of data, ACM Transactions on Database Systems (TODS), v.1 n.1, p.9-36, March 1976 [doi>10.1145/320434.320440]
	CK73	C. C. Chang and H. J. Keisler. Model Theory, volume 73 of Studies in Logic. North-Holland, 1973.
	CM77	Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
	Cod70	E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
	CV93	Surajit Chaudhuri, Optimization of real conjunctive queries, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.59-70, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153856]
	DS96	Guozhu Dong , Jianwen Su, Conjunctive query containment with respect to views and constraints, Information Processing Letters, v.57 n.2, p.95-102, Jan. 29, 1996 [doi>10.1016/0020-0190(95)00192-1]
	End72	H. B. Enderton. A Mathematical introduction to Logic. Academic Press, Inc., 1972.
	Fag93	Ronald Fagin, Finite-model theory—a personal perspective, Theoretical Computer Science, v.116 n.1, p.3-31, Aug. 2, 1993
	FR74	M. J. Fischer and M. O. Rabin. Superexponential complexity of Presburger arithmetic. SIAM-AMS Proceedings, 7:27-41, 1974.
	FR75	J. Ferrante and C. W. Rackoff. A decision procedure for the first order theory of real addition with order. SlAM Journal on Computing, 4(1 ):69- 76, March 1975.
	für82	M. Fiirer. The complexity of Presburger arithmetic with bounded quantifier alternation depth. Theoretical Computer Science, 18(1):105- 111, April 1982.
	Gai81	H. Gaifman. On local and non local properties. In J. Stem, editor, Proc. Herbrand Symposium Logic Colloquium, pages 105-135. North Holland, 1981.
	GI81	E.M. Gurari and O. H. Ibarra. The complexity of decision problems for finite-turn mulficounter machines. Journal of Computer and System Sciences, 22:220-229, 1981.
	GI82	Eitan M. Gurari , Oscar H. Ibarra, Two-Way Counter Machines and Diophantine Equations, Journal of the ACM (JACM), v.29 n.3, p.863-873, July 1982 [doi>10.1145/322326.322340]
	GS94	Stéphane Grumbach , Jianwen Su, Finitely representable databases (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.289-300, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182654]
	GS95	Stéphane Grumbach , Jianwen Su, Dense-order constraint databases (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.66-77, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212453]
	GS96	Stéphane Grumbach , Jianwen Su, Queries with arithmetical constraints, Theoretical Computer Science, v.173 n.1, p.151-181, Feb. 1997 [doi>10.1016/S0304-3975(96)00194-6]
	Iba78	Oscar H. Ibarra, Reversal-Bounded Multicounter Machines and Their Decision Problems, Journal of the ACM (JACM), v.25 n.1, p.116-133, Jan. 1978 [doi>10.1145/322047.322058]
	IJTW95	Oscar H. Ibarra , Tao Jiang , Nicholas Tran , Hui Wang, New Decidability Results Concerning Two-Way Counter Machines, SIAM Journal on Computing, v.24 n.1, p.123-137, Feb. 1995 [doi>10.1137/S0097539792240625]
	KG94	Paris C. Kanellakis , Dina Q. Goldin, Constraint Programming and Database Query Languages, Proceedings of the International Conference on Theoretical Aspects of Computer Software, p.96-120, April 19-22, 1994
	KKR95	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
	Klu88	Anthony Klug, On conjunctive queries containing inequalities, Journal of the ACM (JACM), v.35 n.1, p.146-160, Jan. 1988 [doi>10.1145/42267.42273]
	Kup93	G. M. Kuper. Aggregation in constraint databases. In Proc. Workshop on the Principles and Practice of Constraint Programming, pages 176--183, April 1993.
	LRU96	Alon Y. Levy , Anand Rajaraman , Jeffrey D. Ullman, Answering queries using limited external query processors (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.227-237, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237716]
	LW94	Leonid Libkin , Limsoon Wong, New techniques for studying set languages, bag languages and aggregate functions, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.155-166, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182609]
	Min61	M. Minsky. Reeursive unsolvability of Post's problem of Tag and other topics in the theory of Turing machines. Ann. of Math., 74:437--455, 1961.
	PVV95	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
	Ren92	James Renegar, On the computational complexity and geometry of the first-order theory of the reals. Par I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Journal of Symbolic Computation, v.13 n.3, p.255-299, March 1992
	Rev93	Peter Z. Revesz, A closed-form evaluation for Datalog queries with integer (gap)-order constraints, Theoretical Computer Science, v.116 n.1, p.117-149, Aug. 2, 1993
	RL78	C. R. Reddy , D. W. Loveland, Presburger arithmetic with bounded quantifier alternation, Proceedings of the tenth annual ACM symposium on Theory of computing, p.320-325, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804361]
	ST96	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]
	Tar51	A. Tarski. A Decision Method for Elementary Algebra and Geometry. University of California Presz, Berkeley, California, 1951.
	Tra50	B. A. Trakhtenbrot. The impossibilty of an algorithm for the decision problem for finite models. Doklady Akademii Nauk SSR, 70:569- 572, 1950.
	Ull88	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	vdM92	R. van der Meyden, The complexity of querying indefinite data about linearly ordered domains, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.331-345, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137902]
	VP75	L. Valiant and M. Patterson. Deterministic onecounter automata. Journal of Computer and System Sciences, I0:340-350, 1975.

CITED BY 4

	Stéphane Grumbach , Maurizio Rafanelli , Leonardo Tininini, Querying aggregate data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.174-184, May 31-June 03, 1999, Philadelphia, Pennsylvania, 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
	Jef Wijsen , Alexis Bès, On query optimization in a temporal SPC algebra, Data & Knowledge Engineering, v.44 n.2, p.165-192, February 2003
	Rona Machlin, Index-based multidimensional array queries: safety and equivalence, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China