Conjunctive-query containment and constraint satisfaction

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Conjunctive-query containment and constraint satisfaction

Full text

Pdf (1.24 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: 205 - 213

Year of Publication: 1998

ISBN:0-89791-996-3

Authors

Phokion G. Kolaitis	Computer Science Department, University of California, Santa Cruz, Santa Cruz, CA
Moshe Y. Vardi	Department of Computer Science, Rice University, Houston, TX

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): 8, Downloads (12 Months): 45, Citation Count: 26

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.275511 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
	Bib88	W. Bibel, Constraint satisfaction from a deductive viewpoint (Research Note), Artificial Intelligence, v.35 n.3, p.401-416, July 1988 [doi>10.1016/0004-3702(88)90023-9]
	Bod93	Hans L. Bodlaender, A linear time algorithm for finding tree-decompositions of small treewidth, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.226-234, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167161]
	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]
	CR97	Chandra Chekuri , Anand Rajaraman, Conjunctive Query Containment Revisited, Proceedings of the 6th International Conference on Database Theory, p.56-70, January 08-10, 1997
	Dec90	Rina Dechter, Decomposing a relation into a tree of binary relations, Journal of Computer and System Sciences, v.41 n.1, p.2-24, August 1990 [doi>10.1016/0022-0000(90)90031-F]
	Dec92	R. Dechter. Constraint networks. In S.C. Shapiro, editor, Encyclopedia of Artificial Intelligence, pages 276-185. Wiley, New York, 1992.
	DP92	Rina Dechter , Judea Pearl, Structure identification in relational data, Artificial Intelligence, v.58 n.1-3, p.237-270, Dec. 1992 [doi>10.1016/0004-3702(92)90009-M]
	FV93	Tomás Feder , Moshe Y. Vardi, Monotone monadic SNP and constraint satisfaction, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.612-622, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167245]
	GJ79	Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
	GJC94	Marc Gyssens , Peter G. Jeavons , David A. Cohen, Decomposing constraint satisfaction problems using database techniques, Artificial Intelligence, v.66 n.1, p.57-89, March 1994 [doi>10.1016/0004-3702(94)90003-5]
	HN90	Pavol Hell , Jaroslav Nešetřil, On the complexity of H-coloring, Journal of Combinatorial Theory Series B, v.48 n.1, p.92-110, Feb. 1990 [doi>10.1016/0095-8956(90)90132-J]
	JC95	Peter Jeavons , David Cohen, An Algebraic Characterization of Tractable Constraints, Proceedings of the First Annual International Conference on Computing and Combinatorics, p.633-642, August 24-26, 1995
	JCG95	Peter Jeavons , David Cohen , Marc Gyssens, A Unifying Framework for Tractable Constraints, Proceedings of the First International Conference on Principles and Practice of Constraint Programming, p.276-291, September 19-22, 1995
	JCG96	P, Jeavons, D. Cohen, and M. Gyssens. A test for tractability. In E.G. Freuder, editor, Proceedings of 2nd International Conference on Principles and Practice of Constraint Programming, cPgb', pages 267'-281. Springer-Verlag, 1996.
	Jea97	Peter Jeavons, On the algebraic structure of combinatorial problems, Theoretical Computer Science, v.200 n.1-2, p.185-204, June 28, 1998 [doi>10.1016/S0304-3975(97)00230-2]
	Kum92	Vipin Kumar, Algorithms for constraint-satisfaction problems: a survey, AI Magazine, v.13 n.1, p.32-44, Spring 1992
	KV	Ph.G, Kolaitis and M.Y. Vardi. A game-theoretic approach to constraint satisfaction. Forthcoming.
	KV92	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]
	KV95	Phokion G. Kolaitis , Moshe Y. Vardi, On the expressive power of Datalog: tools and a case study, Journal of Computer and System Sciences, v.51 n.1, p.110-134, Aug. 1995
	KV96	P. G. Kolaitis , M. Y. Vardi, On the expressive power of variable-confined logics, Proceedings of the 11th Annual IEEE Symposium on Logic in Computer Science, p.348, July 27-30, 1996
	LMSS95	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 [doi>10.1145/212433.220198]
	McK43	J. McKinsey. The decision problem for some classes of sentence without quantifiers. Journal of Symbolic Logic, 8:61-76, 1943.
	Mes89	P. Meseguer. Constraint satisfaction problem: an overview. AICOM, 2:3-16, 1989.
	MF93	A.K. Mackworth and E.G. Freuder. The complexity of constraint satisfaction revisited. Artificial Intelligence, 59(1-2):57-62, 1993.
	PJ97	J. Pearson and P. Jeavons. A survey of tractable constraint satisfaction problems. Technical Report CSD-TR-97-15, Royal Holloway University of London, 1997.
	PT87	Robert Paige , Robert E. Tarjan, Three partition refinement algorithms, SIAM Journal on Computing, v.16 n.6, p.973-989, December 1, 1987 [doi>10.1137/0216062]
	Qia96	Xiaolei Qian, Query Folding, Proceedings of the Twelfth International Conference on Data Engineering, p.48-55, February 26-March 01, 1996
	Riv74	I. Rival. Maximal sublattices of finite distributive lattices. Proc. AMS, 44:263--268, 1974.
	RSU95	Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman, Answering queries using templates with binding patterns (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.105-112, May 22-25, 1995, San Jose, California, United States [doi>10.1145/212433.220199]
	Sar91	Yatin P. Saraiya, Subtree-elimination algorithms in deductive databases, Stanford University, Stanford, CA, 1991
	Sch78	Thomas J. Schaefer, The complexity of satisfiability problems, Proceedings of the tenth annual ACM symposium on Theory of computing, p.216-226, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804350]
	Tsa93	E.P.K. Tsang. Foundations o.f Constraint Satisfaction. Academic Press, 1993.
	Ull89	Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
	Ull97	Jeffrey D. Ullman, Information Integration Using Logical Views, Proceedings of the 6th International Conference on Database Theory, p.19-40, January 08-10, 1997
	Var95	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]
	vL90	J. van Leeuwen, Graph algorithms, Handbook of theoretical computer science (vol. A): algorithms and complexity, MIT Press, Cambridge, MA, 1991
	Yan81	M. Yannakakis. Node-deletion problems on bipartite graphs. SIAM Journal o} 6'omputing, 10:310- 327t 1981.

CITED BY 26

	Sihem Amer-Yahia , SungRan Cho , Laks V. S. Lakshmanan , Divesh Srivastava, Minimization of tree pattern queries, ACM SIGMOD Record, v.30 n.2, p.497-508, June 2001
	Martin Grohe, The parameterized complexity of database queries, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.82-92, May 2001, Santa Barbara, California, United States
	Georg Gottlob , Nicola Leone , Francesco Scarcello, Hypertree decompositions and tractable queries, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.21-32, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
	Georg Gottlob , Francesco Scarcello , Martha Sideri, Fixed-parameter complexity in AI and nonmonotonic reasoning, Artificial Intelligence, v.138 n.1-2, p.55-86, June 2002
	Jörg Flum , Markus Frick , Martin Grohe, Query evaluation via tree-decompositions, Journal of the ACM (JACM), v.49 n.6, p.716-752, November 2002
	Yannis Kotidis , Nick Roussopoulos, A case for dynamic view management, ACM Transactions on Database Systems (TODS), v.26 n.4, p.388-423, December 2001
	Moshe Y. Vardi, Constraint satisfaction and database theory: a tutorial, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.76-85, May 15-18, 2000, Dallas, Texas, United States
	Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-based query containment, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.56-67, June 09-11, 2003, San Diego, California
	Domenico Beneventano , Sonia Bergamaschi , Claudio Sartori, Description logics for semantic query optimization in object-oriented database systems, ACM Transactions on Database Systems (TODS), v.28 n.1, p.1-50, March 2003
	Yannis Kotidis, Aggregate view management in data warehouses, Handbook of massive data sets, Kluwer Academic Publishers, Norwell, MA, 2002
	Ji-Hoon Kang , Ki-Hyung Hong , Kyu-Young Whang , Jung-Wan Cho, Generalization of ZYT-linearizability for bilinear datalog programs, Information and Computation, v.188 n.1, p.77-98, 10 January 2004
	Tomás Feder , Florent Madelaine , Iain A. Stewart, Dichotomies for classes of homomorphism problems involving unary functions, Theoretical Computer Science, v.314 n.1, p.1-43, 25 February 2004
	Dan Suciu, On database theory and XML, ACM SIGMOD Record, v.30 n.3, September 2001
	Lefteris M. Kirousis , Phokion G. Kolaitis, The complexity of minimal satisfiability problems, Information and Computation, v.187 n.1, p.20-39, November 25, 2003
	Foto Afrati , Stavros Cosmadakis , Eugénie Foustoucos, Datalog programs and their persistency numbers, ACM Transactions on Computational Logic (TOCL), v.6 n.3, p.481-518, July 2005
	Martin Grohe , Dániel Marx, Constraint solving via fractional edge covers, Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm, p.289-298, January 22-26, 2006, Miami, Florida
	Ashwin Machanavajjhala , Johannes Gehrke, On the efficiency of checking perfect privacy, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	Georg Gottlob , Christoph Koch , Klaus U. Schulz, Conjunctive queries over trees, Journal of the ACM (JACM), v.53 n.2, p.238-272, March 2006
	Martin Grohe, The complexity of homomorphism and constraint satisfaction problems seen from the other side, Journal of the ACM (JACM), v.54 n.1, p.1-es, March 2007
	Maria Luisa Damiani , Elisa Bertino , Barbara Catania , Paolo Perlasca, GEO-RBAC: A spatially aware RBAC, ACM Transactions on Information and System Security (TISSEC), v.10 n.1, p.2-es, February 2007
	S. Flesca , F. Furfaro , E. Masciari, On the minimization of Xpath queries, Proceedings of the 29th international conference on Very large data bases, p.153-164, September 09-12, 2003, Berlin, Germany
	Todd J. Green , Grigoris Karvounarakis , Val Tannen, Provenance semirings, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China
	S. Amer-Yahia , S. Cho , L. V. S. Lakshmanan , D. Srivastava, Tree pattern query minimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.4, p.315-331, December 2002
	Martin Groher , Thomas Schwentick , Luc Segoufin, When is the evaluation of conjunctive queries tractable?, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.657-666, July 2001, Hersonissos, Greece
	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
	Murray Patterson , Yongmei Liu , Eugenia Ternovska , Arvind Gupta, Grounding for model expansion in k-guarded formulas with inductive definitions, Proceedings of the 20th international joint conference on Artifical intelligence, p.161-166, January 06-12, 2007, Hyderabad, India