On conjunctive queries containing inequalities

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

On conjunctive queries containing inequalities

Full text

Pdf (1.26 MB)

Source

Journal of the ACM (JACM) archive
Volume 35 , Issue 1 (January 1988) table of contents

Pages: 146 - 160

Year of Publication: 1988

ISSN:0004-5411

Author

Anthony Klug

Univ. of Wisconsin, Madison

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 11, Downloads (12 Months): 76, Citation Count: 78

Additional Information:

abstract references cited by index terms review 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/42267.42273 What is a DOI?

ABSTRACT

Conjunctive queries are generalized so that inequality comparisons can be made between elements of the query. Algorithms for containment and equivalence of such “inequality queries” are given, under the assumption that the data domains are dense and totally ordered. In general, containment does not imply the existence of homomorphisms (containment mappings), but the homomorphism property does exist for subclasses of inequality queries. A minimization algorithm is defined using the equivalence algorithm. It is first shown that the constants appearing in a query can be divided into “essential” and “nonessential” subgroups. The minimum query can be nondeterministically guessed using only the essential constants of the original query.

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	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]
	2	AHO, A. V., SAGIV, Y., AND ULLMAN, J.O. Equivalences among relational expressions. SIAM J. Comput. 8, 2 (May 1979), 218-246.
	3	M. M. Astrahan , M. W. Blasgen , D. D. Chamberlin , K. P. Eswaran , J. N. Gray , P. P. Griffiths , W. F. King , R. A. Lorie , P. R. McJones , J. W. Mehl , G. R. Putzolu , I. L. Traiger , B. W. Wade , V. Watson, System R: relational approach to database management, ACM Transactions on Database Systems (TODS), v.1 n.2, p.97-137, June 1976 [doi>10.1145/320455.320457]
	4	BEERI, C., BERNSTEIN, P., AND GOODMAN, N. A sophistieate's introduction to database normalization theory. In Proceedings of the 1978 VLDB Conference (West Berlin). 1978.
	5	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]
	6	CODD, E.F. Relational completeness of data base sublanguages. In Data Base Systems, R. Rustin, Ed. Prentice-Hall, Englewood Cliffs, N.J., 1972.
	7	Umeshwar Dayal , Nathan Goodman , Randy H. Katz, An extended relational algebra with control over duplicate elimination, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588132]
	8	JOHNSON, D., AND KLUG, A. Optimizing conjunctive queries that contain untyped variables. SIAMJ. Comput. 12, 4 (Nov. 1983), 616-640.
	9	JOHNSON, D., AND KLUG, A. Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28, 1 (Feb. 1984), 167-189.
	10	SAGIV, Y. Quadratic algorithms for minimizing joins in restricted relational expressions. Tech. Rep. UIUCDCS-R-79-992. Computer Science Dept., Univ. of Illinois, Urbana, I11., 1979.
	11	Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
	12	SHOVNFIELD, J.R. Mathematical Logic. Addison-Wesley, Reading, Mass., 1967.
	13	Martin K. Solomon, Some properties of relational expressions, Proceedings of the 17th annual Southeast regional conference, p.111-116, April 09-11, 1979, Orlando, Florida [doi>10.1145/503506.503525]
	14	Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
	15	ULLMAN, J. D. A view of directions in relational database theory. Rep. STAN-CS-81-852. Computer Science Dept., Stanford Univ., Stanford, Calif., 1981.
	16	YANNAKAKIS, M., AND PAPADIMITRIOU, C. Algebraic dependencies. J. Comput. Syst. Sci. 25, 1 (1982), 2--41.

CITED BY 78

	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
	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
	Marc Andries , Luca Cabibbo , Jan Paredaens , Jan Van den Bussche, Applying an update method to a set of receivers (extended abstract), Proceedings of the fourteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.208-218, 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
	Phokion G. Kolaitis , David L. Martin , Madhukar N. Thakur, On the complexity of the containment problem for conjunctive queries with built-in predicates, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.197-204, June 01-04, 1998, Seattle, Washington, United States
	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
	Sha Guo , Wei Sun , Mark A. Weiss, Solving satisfiability and implication problems in database systems, ACM Transactions on Database Systems (TODS), v.21 n.2, p.270-293, June 1996
	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
	Alon Levy , Yehoshua Sagiv, Constraints and redundancy in datalog, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.67-80, June 02-05, 1992, San Diego, California, United States
	Serge Abiteboul , Oliver M. Duschka, Complexity of answering queries using materialized views, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.254-263, 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
	Christos H. Papadimitriou , Mihalis Yannakakis, On the complexity of database queries (extended abstract), Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.12-19, May 11-15, 1997, Tucson, Arizona, United States
	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
	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
	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
	Alon Y. Levy, Logic-based techniques in data integration, Logic-based artificial intelligence, Kluwer Academic Publishers, Norwell, MA, 2000
	Michael Benedikt , Leonid Libkin, Relational queries over interpreted structures, Journal of the ACM (JACM), v.47 n.4, p.644-680, July 2000
	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
	Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, On the decidability of query containment under constraints, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.149-158, June 01-04, 1998, Seattle, Washington, United States
	Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin
	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
	W. Sun , M. A. Weiss, An Improved Algorithm for Implication Testing Involving Arithmetic Inequalities, IEEE Transactions on Knowledge and Data Engineering, v.6 n.6, p.997-1001, December 1994
	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
	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
	Alexander Brodsky, Constraint databases: promising technology or just intellectual exercise?, ACM Computing Surveys (CSUR), v.28 n.4es, Dec. 1996
	S. T. Shenoy , Z. M. Ozsoyoglu, Design and Implementation of a Semantic Query Optimizer, IEEE Transactions on Knowledge and Data Engineering, v.1 n.3, p.344-361, September 1989
	Georg Lausen , Fang Wei, On the containment of conjunctive queries, Computer science in perspective, Springer-Verlag New York, Inc., New York, NY, 2003
	Andrea Calí , Domenico Lembo , Maurizio Lenzerini , Riccardo Rosati, Source integration for data warehousing, Multidimensional databases: problems and solutions, Idea Group Publishing, Hershey, PA, 2003
	Dimitri Theodoratos , Wugang Xu, Constructing search spaces for materialized view selection, Proceedings of the 7th ACM international workshop on Data warehousing and OLAP, November 12-13, 2004, Washington, DC, USA
	D. Calvanese , G. De Giacomo , M. Lenzerini , M. Y. Vardi, Reasoning on regular path queries, ACM SIGMOD Record, v.32 n.4, December 2003
	Marc Andries , Luca Cabibbo , Jan Paredaens , Jan van den Bussche, Applying an update method to a set of receivers, ACM Transactions on Database Systems (TODS), v.26 n.1, p.1-40, March 2001
	Reza Sadri , Carlo Zaniolo , Amir Zarkesh , Jafar Adibi, Expressing and optimizing sequence queries in database systems, ACM Transactions on Database Systems (TODS), v.29 n.2, p.282-318, June 2004
	Sha Guo , Wei Sun , Mark A. Weiss, On Satisfiability, Equivalence, and Implication Problems Involving Conjunctive Queries in Database Systems, IEEE Transactions on Knowledge and Data Engineering, v.8 n.4, p.604-616, August 1996
	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
	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
	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
	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
	A. Pirotte , D. Roelants , E. Zimanyi, Controlled Generation of Intensional Answers, IEEE Transactions on Knowledge and Data Engineering, v.3 n.2, p.221-236, June 1991
	Diego Calvanese , Giuseppe De Giacomo , Moshe Y. Vardi, Decidable containment of recursive queries, Theoretical Computer Science, v.336 n.1, p.33-56, 25 May 2005
	Ali Kiani , Nematollaah Shiri, Answering queries with arithmetic expressions in heterogeneous systems, Proceedings of the first international workshop on Interoperability of heterogeneous information systems, November 04-04, 2005, Bremen, Germany
	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
	T. S. Jayram , Phokion G. Kolaitis , Erik Vee, The containment problem for <bi>Real</bi> conjunctive queries with inequalities, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	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
	Marco Cadoli , Toni Mancini, Automated reformulation of specifications by safe delay of constraints, Artificial Intelligence, v.170 n.8, p.779-801, June 2006
	Paris Kanellakis, Database querying and constraint programming, ACM SIGACT News, v.25 n.4, p.22-87, Dec. 1994
	Qingyuan Bai , Jun Hong , Michael F. McTear , Hui Wang, Bucket-Based Query Rewriting with Disjunctive Data Source, Proceedings of the 2004 IEEE/WIC/ACM International Conference on Web Intelligence, p.566-569, September 20-24, 2004
	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
	Stefan Brass , Christian Goldberg, Semantic errors in SQL queries: a quite complete list, Journal of Systems and Software, v.79 n.5, p.630-644, May 2006
	Riccardo Rosati, On the decidability and finite controllability of query processing in databases with incomplete information, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA
	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
	Naci S. Ishakbeyoglu , Z. Meral Ozsoyoglu, Maintenance of implication integrity constraints under updates to constraints, The VLDB Journal — The International Journal on Very Large Data Bases, v.7 n.2, p.67-78, May 1998
	Rachel Pottinger , Alon Halevy, MiniCon: A scalable algorithm for answering queries using views, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.2-3, p.182-198, September 2001
	Alon Y. Halevy, Answering queries using views: A survey, The VLDB Journal — The International Journal on Very Large Data Bases, v.10 n.4, p.270-294, December 2001
	Rada Chirkova , Chen Li , Jia Li, Answering queries using materialized views with minimum size, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.3, p.191-210, September 2006
	Aditya N. Saharia , Yair M. Babad, Enhancing data warehouse performance through query caching, ACM SIGMIS Database, v.31 n.2, p.43-63, Spring 2000
	Rachel Pottinger , Alon Y. Levy, A Scalable Algorithm for Answering Queries Using Views, Proceedings of the 26th International Conference on Very Large Data Bases, p.484-495, September 10-14, 2000
	Nam Huyn, Multiple-View Self-Maintenance in Data Warehousing Environments, Proceedings of the 23rd International Conference on Very Large Data Bases, p.26-35, August 25-29, 1997
	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
	Alexander Brodsky , Joxan Jaffar , Michael J. Maher, Toward Practical Constraint Databases, Proceedings of the 19th International Conference on Very Large Data Bases, p.567-580, 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
	Aditya N. Saharia , Yair M. Babad, Enhancing data warehouse performance through query caching, ACM SIGMIS Database, v.31 n.3, p.43-63, Summer 2000
	Mihalis Yannakakis, Perspectives on database theory, ACM SIGACT News, v.27 n.3, p.25-49, Sept. 1996
	Alexander Brodsky , Victor E. Segal , Jia Chen , Pavel A. Exarkhopoulo, The CCUBE Constraint Object-Oriented Database System, Constraints, v.2 n.3-4, p.245-277, 1997
	Alexander Brodsky , Joxan Jaffar , Michael J. Maher, Toward Practical Query Evaluation for Constraint Databases, Constraints, v.2 n.3-4, p.279-304, 1997
	Alexander Brodsky, Constraint Databases: Promising Technology or Just IntellectualExercise?, Constraints, v.2 n.1, p.35-44, April 1997
	Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini, Conjunctive query containment and answering under description logic constraints, ACM Transactions on Computational Logic (TOCL), v.9 n.3, p.1-31, June 2008
	Wenfei Fan , Floris Geerts , Wouter Gelade , Frank Neven , Antonella Poggi, Complexity and composition of synthesized web services, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada
	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
	Wenfei Fan , Floris Geerts , Frank Neven, Expressiveness and complexity of XML publishing transducers, ACM Transactions on Database Systems (TODS), v.33 n.4, p.1-49, November 2008
	Luca Cabibbo, On keys, foreign keys and nullable attributes in relational mapping systems, Proceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology, March 24-26, 2009, Saint Petersburg, Russia
	Rada Chirkova , Michael R. Genesereth, Equivalence of SQL queries in presence of embedded dependencies, Proceedings of the twenty-eighth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 29-July 01, 2009, Providence, Rhode Island, USA
	Faiz Currim , Eunjin Jung , Xin Xiao , Insoon Jo, Privacy policy enforcement for health information data access, Proceedings of the 1st ACM international workshop on Medical-grade wireless networks, May 18-18, 2009, New Orleans, Louisiana, USA
	Sara Cohen, Equivalence of queries that are sensitive to multiplicities, The VLDB Journal — The International Journal on Very Large Data Bases, v.18 n.3, p.765-785, June 2009
	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

INDEX TERMS

Primary Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.3 Languages
Subjects: Query languages

Additional Classification:
H. Information Systems
H.2 DATABASE MANAGEMENT
H.2.1 Logical Design
Subjects: Data models

General Terms:
Algorithms, Languages, Theory

REVIEW

"Kazem Taghva : Reviewer"

Conjunctive queries are a subset of domain calculus expressions built from relational atomic formulas using the logical connective and. In the database setting, the connective and is interpreted as the join opera more...

Collaborative Colleagues:

Anthony Klug: colleagues

Adobe Acrobat

QuickTime

Windows Media Player

Real Player