The complexity of querying indefinite data about linearly ordered domains

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of querying indefinite data about linearly ordered domains

Full text

Pdf (1.62 MB)

Source

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

San Diego, California, United States

Pages: 331 - 345

Year of Publication: 1992

ISBN:0-89791-519-4

Author

R. van der Meyden

Sponsors

SIGACT: ACM Special Interest Group on Algorithms and Computation Theory
SIGART: ACM Special Interest Group on Artificial Intelligence
SIGMOD: ACM Special Interest Group on Management of Data

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 3, Downloads (12 Months): 22, Citation Count: 32

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/137097.137902 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 , Paris Kanellakis , Gösta Grahne, On the representation and querying of sets of possible worlds, Theoretical Computer Science, v.78 n.1, p.159-187, Jan. 21, 1991
	2	James F. Allen, Maintaining knowledge about temporal intervals, Communications of the ACM, v.26 n.11, p.832-843, Nov. 1983 [doi>10.1145/182.358434]
	3	Ashok K. Chandra , Dexter C. Kozen , Larry J. Stockmeyer, Alternation, Journal of the ACM (JACM), v.28 n.1, p.114-133, Jan. 1981 [doi>10.1145/322234.322243]
	4	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]
	5	M. R. Fellows , M. A. Langston, Nonconstructive advances in polynomial-time complexity, Information Processing Letters, v.26 n.3, p.155-162, Nov. 23, 1987
	6	Michael R. Fellows , Michael A. Langston, Nonconstructive tools for proving polynomial-time decidability, Journal of the ACM (JACM), v.35 n.3, p.727-739, July 1988 [doi>10.1145/44483.44491]
	7	M.C. Golumbic. Algortthm#c Graph Theory and Perfect Graphs. Academic Press, New York, 1980.
	8	M.C. Golumbic and R. Shamir. Complexity and algorithms for reasoning about time: A graph-theoretic approach. Technical Report RRR No. 22-91, RUT- COR: Rutgers Center for Operations Research, New Brunswick NJ, May 1991.
	9	J. Halpern and Y. Shoham. A propositional modal logic of time intervals. In Proceedings of the Symposium on Logic in Computer Science, pages 279-292, 1986.
	10	Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
	11	D.G. Kendall. Some methods and problems in statistical archeology. World Archeology, pages 68-76, 1969.
	12	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]
	13	J.B. Kruskal. The theory of well-quasi-ordering: A frequently discovered concept. Journal of Combznator#al Theory (Ser. A), 13:297-305, 1972.
	14	Jean-Louis Lassez, Querying constraints, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.288-298, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298581]
	15	David Maier, The Complexity of Some Problems on Subsequences and Supersequences, Journal of the ACM (JACM), v.25 n.2, p.322-336, April 1978 [doi>10.1145/322063.322075]
	16	D.J. Rosenkrantz and H.B. Hunt. Processing conjunctive predicates and queries. In Proceedings of the Swcth International Conference on Very Large Databases, pages 64-72, 1980.
	17	E.D. Sacerdoti. A Structure for Plans and Behav#our. Elsevier, New York, 1977.
	18	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	19	Peter van Beek , Robin Cohen, Exact and approximate reasoning about temporal relations, Computational Intelligence, v.6 n.3, p.132-147, Aug. 1990 [doi>10.1111/j.1467-8640.1990.tb00130.x]
	20	R. van der Meyden, Recursively indefinite databases (extended abstract), Proceedings of the third international conference on database theory on Database theory, p.364-378, November 1990, Paris, France
	21	Ronald van der Meyden, The complexity of querying indefinite information: defined relations, recursion and linear order, Rutgers University, New Brunswick, NJ, 1992
	22	Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
	23	Moshe Y Vardi, Querying logical databases, Journal of Computer and System Sciences, v.33 n.2, p.142-160, Oct. 1986 [doi>10.1016/0022-0000(86)90016-4]
	24	M. Vilain and H. Kautz. Constraint propagation algorithms for temporal reasoning. In AAAI: Proceedings of the National Conference zn Artificial Intelhgence, pages 377-382. Morgan Kaufinan, 1986.

CITED BY 32

	Foto Afrati , Chen Li , Prasenjit Mitra, Answering queries using views with arithmetic comparisons, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	Ashish Gupta , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom, Constraint checking with partial information, Proceedings of the thirteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.45-55, May 24-27, 1994, Minneapolis, Minnesota, United States
	Alon Y. Levy , Yehoshua Sagiv, Semantic query optimization in Datalog programs (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.163-173, May 22-25, 1995, San Jose, California, United States
	Werner Nutt , Yehoshus Sagiv , Sara Shurin, Deciding equivalences among aggregate queries, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.214-223, June 01-04, 1998, Seattle, Washington, United States
	Todd Millstein , Alon Levy , Marc Friedman, Query containment for data integration systems, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.67-75, May 15-18, 2000, Dallas, Texas, United States
	Alon Y. Levy , Alberto O. Mendelzon , Yehoshua Sagiv, Answering queries using views (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.95-104, May 22-25, 1995, San Jose, California, United States
	Paris Kanellakis, Constraint programming and database languages: a tutorial, Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.46-53, May 22-25, 1995, San Jose, California, United States
	Daniela Florescu , Alon Levy , Dan Suciu, Query containment for conjunctive queries with regular expressions, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.139-148, June 01-04, 1998, Seattle, Washington, United States
	Alon Y. Levy , Dan Suciu, Deciding containment for queries with complex objects (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.20-31, May 11-15, 1997, Tucson, Arizona, United States
	Sara Cohen , Werner Nutt , Alexander Serebrenik, Rewriting aggregate queries using views, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.155-166, May 31-June 03, 1999, Philadelphia, Pennsylvania, 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
	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
	Mizuhito Ogawa, A linear time algorithm for monadic querying of indefinite data over linearly ordered domains, Information and Computation, v.186 n.2, p.236-259, 01 November 2003
	Oscar H. Ibarra , Jianwen Su, On the containment and equivalence of database queries with linear constraints (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.32-43, May 11-15, 1997, Tucson, Arizona, United States
	Ernest Teniente , Toni Urpí, Checking query containment with the CQC method, Data & Knowledge Engineering, v.53 n.2, p.163-223, May 2005
	Dan Suciu, On database theory and XML, ACM SIGMOD Record, v.30 n.3, September 2001
	Xubo Zhang , Z. Meral Ozsoyoglu, Implication and Referential Constraints: A New Formal Reasoning, IEEE Transactions on Knowledge and Data Engineering, v.9 n.6, p.894-910, November 1997
	Sara Cohen , Yehoshua Sagiv , Werner Nutt, Equivalences among aggregate queries with negation, ACM Transactions on Computational Logic (TOCL), v.6 n.2, p.328-360, April 2005
	Sara Cohen, Containment of aggregate queries, ACM SIGMOD Record, v.34 n.1, March 2005
	Todd Millstein , Alon Halevy , Marc Friedman, Query containment for data integration systems, Journal of Computer and System Sciences, v.66 n.1, p.20-39, 01 February 2003
	Sara Cohen, Equivalence of queries combining set and bag-set semantics, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Paris Kanellakis, Database querying and constraint programming, ACM SIGACT News, v.25 n.4, p.22-87, Dec. 1994
	Sara Cohen , Werner Nutt , Yehoshua Sagiv, Deciding equivalences among conjunctive aggregate queries, Journal of the ACM (JACM), v.54 n.2, p.5-es, April 2007
	Xin Dong , Alon Y. Halevy , Igor Tatarinov, Containment of nested XML queries, Proceedings of the Thirtieth international conference on Very large data bases, p.132-143, August 31-September 03, 2004, Toronto, Canada
	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
	Sara Cohen , Werner Nutt , Yehoshua Sagiv, Equivalences among aggregate queries with negation, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.215-226, May 2001, Santa Barbara, California, United States
	Alon Y. Levy , Yehoshua Sagiv, Queries Independent of Updates, Proceedings of the 19th International Conference on Very Large Data Bases, p.171-181, August 24-27, 1993
	Alon Y. Levy, Obtaining Complete Answers from Incomplete Databases, Proceedings of the 22th International Conference on Very Large Data Bases, p.402-412, September 03-06, 1996
	Foto Afrati , Chen Li , Vassia Pavlaki, Data exchange in the presence of arithmetic comparisons, Proceedings of the 11th international conference on Extending database technology: Advances in database technology, March 25-29, 2008, Nantes, France
	Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
	Fang Wei , Georg Lausen, A unified apriori-like algorithm for conjunctive query containment, Proceedings of the 2008 international symposium on Database engineering & applications, September 10-12, 2008, Coimbra, Portugal
	David DeHaan, Equivalence of nested queries with mixed semantics, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA