On the decidability of semi-linearity for semi-algebraic sets and its implications for spatial databases (extended abstract)

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On the decidability of semi-linearity for semi-algebraic sets and its implications for spatial databases (extended abstract)

Full text

Pdf (1.69 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: 68 - 77

Year of Publication: 1997

ISBN:0-89791-910-6

Authors

Freddy Dumortier	Dept. WNI, University of Limburg, Universitaire Campus, B-3590, Diepenbeek, Belgium
Marc Gyssens	Dept. WNI, University of Limburg, Universitaire Campus, B-3590, Diepenbeek, Belgium
Luc Vandeurzen	Dept. WNI, University of Limburg, Universitaire Campus, B-3590, Diepenbeek, Belgium
Dirk Van Gucht	Computer Science Dept., Indiana University, Bloomington, IN

Sponsor

SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 16, Citation Count: 10

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.263670 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	Foto N. Afrati , Stavros S. Cosmadakis , Stéphane Grumbach , Gabriel M. Kuper, Linear vs Polynomial Constraints in Database Query Languages, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.181-192, May 02-04, 1994
	2	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]
	3	J. Bochnak, M. Coste, and M-F. Roy, Gdomdtrie algdbrique rdeUe, Springer-Verlag, Berlin-Heidelberg, 1987.
	4	Divesh Srivastava , Raghu Ramakrishnan , Peter Z. Revesz, Constraint Objects, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.218-228, May 02-04, 1994
	5	Ingrid Carlbom, An algorithm for geometric set operations using cellular subdivision techniques, IEEE Computer Graphics and Applications, v.7 n.5, p.44-55, May 1987 [doi>10.1109/MCG.1987.276987]
	6	D.Q. Goldin and P.C. Kanellalds, "Constraint Query Algebras," Constraints Jourv.al, 1, 1996, pp. 1-41.
	7	Oliver Günther, Efficient structures for geometric data management, Springer-Verlag New York, Inc., New York, NY, 1989
	8	3. Heintz, T. Recio, and M.-F. Roy, "Algorithms in Real Algebraic Geometry and Applications to Computational Geometry," in Discrete and Computational Geometry: Papers from the DIMACS Special Year, J.E. Goodman, It. Pollack, and W. Steiger, eds., in DL MA GB Series in Discrete Mathematics and Theoretical Oomputer Science, vol. 6, 1991, pp. 137-163.
	9	Tien Huynh , Catherine Lassez , Jean-Louis Lassez, Fourier Algorithm Revisited, Proceedings of the Second International Conference on Algebraic and Logic Programming, p.117-131, October 01-03, 1990
	10	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
	11	Alfons Kemper , Mechtild Wallrath, An analysis of geometric modeling in database systems, ACM Computing Surveys (CSUR), v.19 n.1, p.47-91, March 1987 [doi>10.1145/28865.28866]
	12	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
	13	Gabriel M. Kuper, On the expressive power of the relational calculus with arithmetic constraints (extended abstract), Proceedings of the third international conference on database theory on Database theory, p.202-211, November 1990, Paris, France
	14	G. Kuper, personal communications, Antwerp, December 3, 1996.
	15	T. Mostowski , E. Rannou, Complexity of the Computation of the Canonical Whitney Stratification of an Algebraic Set in Cn, Proceedings of the 9th International Symposium, on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, p.281-291, October 07-11, 1991
	16	J. Nievergelt and M. Freeston, eds., Special issue on spatial data, Oomputer Journal, 37:1, 1994.
	17	Jan Paredaens , Jan Van den Bussche , Dirk Van Gucht, Towards a theory of spatial database queries (extended abstract), Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.279-288, May 24-27, 1994, Minneapolis, Minnesota, United States [doi>10.1145/182591.182640]
	18	Niki Pissinou , Richard Thomas Snodgrass , Ramez Elmasri , Inderpal S. Mumick , Tamer Özsu , Barbara Pernici , Arie Segev , Babis Theodoulidis , Umeshwar Dayal, Towards an infrastructure for temporal databases: report of an invitational ARPA/NSF workshop, ACM SIGMOD Record, v.23 n.1, p.35-51, March 1994 [doi>10.1145/181550.181557]
	19	H. Pollard and H.G. Diamond. "The Theory of Algebraic Numbers." The Oarus Mathematical Monograph~ 9, 2rid edition, The Mathematical Association of America, 1975, p. 41.
	20	L. K. Putnam , P. A. Subrahmanyam, Boolean operations on n-dimensional objects, IEEE Computer Graphics and Applications, v.6 n.6, p.43-51, June 1986 [doi>10.1109/MCG.1986.276741]
	21	A. Seidenberg, "A New Decision Procedure for Elementary Algebra," Annals of Mathematics, 60, 1954, pp. 365-374.
	22	A. Tarski, "A Decision Method for Elementary Algebra and Geometry," University of California Pres% Berke. Icy, California, 1951.
	23	Luc Vandeurzen , Marc Gyssens , Dirk Van Gucht, On the Desirability and Limitations of Linear Spatial Database Models, Proceedings of the 4th International Symposium on Advances in Spatial Databases, p.14-28, August 06-09, 1995
	24	L. Vandeurzen, M. Gyssens, and D. Van Gucht, "On Query Languages for Linear Queries Definable with Polynomial Constraints," in Proceedings Ser~nd International Conference on Principles and Practice of Constraint Programming (Cambridge, Massachusetts, USA, August 1996), E. Freuder, ed., in Zeeture Notes in Computer Science, vol. 1118, Springer-Verlag, 1996, pp. 468-481.
	25	H. Whitney, "Elementary Structure of Real Algebraic Varieties," Annals of Mathematics, 66, 1957, pp. 545- 556.

CITED BY 10

	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
	Pankaj K. Agarwal , Lars Arge , Jeff Erickson , Paolo G. Franciosa , Jeffry Scott Vitter, Efficient searching with linear constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.169-178, June 01-04, 1998, Seattle, Washington, United States
	Stéphane Grumbach , Philippe Rigaux , Luc Segoufin, The DEDALE system for complex spatial queries, ACM SIGMOD Record, v.27 n.2, p.213-224, June 1998
	Stephan Kreutzer, Fixed-point query languages for linear constraint databases, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.116-125, May 15-18, 2000, Dallas, Texas, United States
	Richard J. Howarth, Spatial Models for Wide-Area Visual Surveillance: Computational Approaches and Spatial Building-Blocks, Artificial Intelligence Review, v.23 n.2, p.97-155, April 2005
	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
	Floris Geerts , Bart Kuijpers, Linear approximation of planar spatial databases using transitive-closure logic, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.126-135, May 15-18, 2000, Dallas, Texas, United States
	Jan Chomicki , Dina Goldin , Gabriel Kuper , David Toman, Variable Independence in Constraint Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1422-1436, November 2003
	Brian E. Weinrich , Markus Schneider, Use of rational numbers in the design of robust geometric primitives for three-dimensional spatial database systems, Proceedings of the 13th annual ACM international workshop on Geographic information systems, November 04-05, 2005, Bremen, Germany
	Jan Chomicki , Peter Z. Revesz, Constraint-based Interoperability of Spatiotemporal Databases*, Geoinformatica, v.3 n.3, p.211-243, September 1999