The complexity of query reliability

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

The complexity of query reliability

Full text

Pdf (1.16 MB)

Source

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

Seattle, Washington, United States

Pages: 227 - 234

Year of Publication: 1998

ISBN:0-89791-996-3

Authors

Erich Grädel	University of Technology Aachen
Yuri Gurevich	Universtity of Michigan
Colin Hirsch	University of Technology Aachen

Sponsors

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

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 2, Downloads (12 Months): 39, Citation Count: 19

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/275487.295124 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	Erich Grädel , Yuri Gurevich, Metafinite model theory, Information and Computation, v.140 n.1, p.26-81, Jan. 10, 1998 [doi>10.1006/inco.1997.2675]
	2	G. Hirseh, The Reliability of Queries, Diploma Thesis (P~WTH-Aaehen, 1998).
	3	David S. Johnson, A catalog of complexity classes, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	4	tL Karp and M. Luby, Monte Carlo algorithms for enumeration and reliability problems, Proceedings of the 24th Symposium on Foundations of Computer Science FOCS 1983, 56-64.
	5	Laks V. S. Lakshmanan , Fereidoon Sadri, Probabilistic deductive databases, Proceedings of the 1994 International Symposium on Logic programming, p.254-268, November 1994, Symposia, Melbourne
	6	Laks V. S. Lakshmanan , Nicola Leone , Robert Ross , V. S. Subrahmanian, ProbView: a flexible probabilistic database system, ACM Transactions on Database Systems (TODS), v.22 n.3, p.419-469, Sept. 1997 [doi>10.1145/261124.261131]
	7	C. Papadimitriou, Computational Complexity, Addison-Wesley (1994).
	8	K. Regan and T. Schwentick, On the Power of One Bit of a #P Function, Proceedings of the Fourth Italian Conference on Theoretical Computer Science (1992), 317-329.
	9	Michel de Rougemont, The reliability of queries (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.286-291, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.212479]
	10	Raymond Ng , V. S. Subrahmanian, Stable semantics for probabilistic deductive databases, Information and Computation, v.110 n.1, p.42-83, April 1994 [doi>10.1006/inco.1994.1023]
	11	L. Valiant, The complexity of enumeration and reliabil. ity problems, SIAM J. Computing 8 (1979), 410-421.
	12	K W Wagner, Some observations on the connection between counting and recursion, Theoretical Computer Science, v.47 n.2, p.131-147, Nov. 1986
	13	Esteban Zimányi, Query evaluation in probabilistic relational databases, Theoretical Computer Science, v.171 n.1-2, p.179-219, Jan. 15, 1997

CITED BY 19

	Alberto O. Mendelzon , George A. Mihaila, Querying partially sound and complete data sources, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.162-170, May 2001, Santa Barbara, California, United States
	Dan Suciu, Probabilistic databases, ACM SIGACT News, v.39 n.2, June 2008
	Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.16 n.4, p.523-544, October 2007
	Reynold Cheng , Dmitri V. Kalashnikov , Sunil Prabhakar, Evaluation of probabilistic queries over imprecise data in constantly-evolving environments, Information Systems, v.32 n.1, p.104-130, March, 2007
	Nilesh Dalvi , Dan Suciu, Management of probabilistic data: foundations and challenges, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-12, June 11-13, 2007, Beijing, China
	Nilesh Dalvi , Christopher Ré , Dan Suciu, Probabilistic databases: diamonds in the dirt, Communications of the ACM, v.52 n.7, July 2009
	Benny Kimelfeld , Yehoshua Sagiv, Matching twigs in probabilistic XML, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
	Christopher Re , Dan Suciu, Management of data with uncertainties, Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, p.3-8, November 06-10, 2007, Lisbon, Portugal
	Nilesh Dalvi , Dan Suciu, Efficient query evaluation on probabilistic databases, Proceedings of the Thirtieth international conference on Very large data bases, p.864-875, August 31-September 03, 2004, Toronto, Canada
	Nilesh Dalvi , Dan Suciu, The dichotomy of conjunctive queries on probabilistic structures, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	Chen Li, Computing complete answers to queries in the presence of limited access patterns, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.3, p.211-227, October 2003
	Christoph Koch, Approximating predicates and expressive queries on probabilistic databases, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	Benny Kimelfeld , Yuri Kosharovsky , Yehoshua Sagiv, Query efficiency in probabilistic XML models, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada
	Reynold Cheng , Jinchuan Chen , Xike Xie, Cleaning uncertain data with quality guarantees, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Christopher Ré , Dan Suciu, Approximate lineage for probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Christoph Koch , Dan Olteanu, Conditioning probabilistic databases, Proceedings of the VLDB Endowment, v.1 n.1, August 2008
	Michaela Götz , Christoph Koch, A compositional framework for complex queries over uncertain data, Proceedings of the 12th International Conference on Database Theory, March 23-25, 2009, St. Petersburg, Russia
	Sara Cohen , Benny Kimelfeld , Yehoshua Sagiv, Running tree automata on probabilistic XML, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Christoph Koch, On Query Algebras for Probabilistic Databases, ACM SIGMOD Record, v.37 n.4, December 2008