Article

Free access

A decision procedure for conjunctive query disjointness

Author:

C. ElkanAuthors Info & Claims

PODS '89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

Pages 134 - 139

https://doi.org/10.1145/73721.73735

Published: 29 March 1989 Publication History

PDF eReader

Abstract

This paper presents an algorithm that decides whether two conjunctive query expressions always describe disjoint sets of tuples. The decision procedure solves an open problem identified by Blakeley, Coburn, and Larson: how to check whether an explicitly stored view relation must be recomputed after an update, taking into account functional dependencies. For nonconjunctive queries, the disjointness problem is NP-hard. For conjunctive queries, the time complexity of the algorithm given cannot be improved unless the reachability problem for directed graphs can be solved in sublinear time. The algorithm is novel in that it combines separate decision procedures for the theory of functional dependencies and for the theory of dense orders. Also, it uses tableaux that are capable of representing all six comparison operators <, ≤, =, ≥, >, and ≠.

References

[1]

A. V. Aho, Y. Sagiv, and J. D. Ullman. Equivalence of relational expressions. SIAM Journal of Computing, 8(2):218-246, May 1979.

Digital Library

Google Scholar

[2]

J. A. Blakeley, N. Coburn, and P.-A. Larson. Updating derived relations: Detecting irrelevant and autonomously computable updates. Technical Report 235, Indiana University Computer Science Department, November 1987. To appear in A CM Transactions on Database Systems.

Crossref

Google Scholar

[3]

J. A. Blakely, P. Larson, and F. Tompa. Efficiently updating materialized views. In Proceedings of the A CM SIGMOD International Conference on Mana gement of Data, pages 61-71, May 1986.

Digital Library

Google Scholar

[4]

P. J. Downey, R. Sethi, and R. E. Tarjan. Variations on the common subexpression problem. Journal of the A CM, 27(4):758-771, October 1980.

Digital Library

Google Scholar

[5]

C. Elkan. Adaptive locking. Technical Report 87-829, Department of Computer Science, Cornell University, 1987.

Crossref

Google Scholar

[6]

K. P. Eswaran, J. N. Gray, R. A. Lorie, and I. L. Traiger. The notions of consistency and predicate locks in a database system. Communications of the A CM, 19(11):624--633, November 1976.

Digital Library

Google Scholar

[7]

H. B. Hunt Iil and D. J. Rosenkrantz. The complexity of testing predicate locks. In Proceedings of the A CM SIGMOD International Conference on Management of Data, pages 127-133, May 1979.

Digital Library

Google Scholar

[8]

A. Klug. Locking expressions for increased data. base concurrency. Journal o.f the A CM, 30(1):36- 54, January 1983.

Digital Library

Google Scholar

[9]

P.-A. Larson and H. Z. Yang. Computing queries from derived relations. In Proceedings of the International Conference on Very Large Databases, pages 259-269, 1985.

Google Scholar

[10]

D. Maier. The Theory of Relational Databases. Computer Science Press, Roekville, Maryland, 1983.

Digital Library

Google Scholar

[11]

G. Nelson and D. C. Oppen. Simplification by cooperating decision procedures. A CM Transactions on Programming Languages and SI/stems, 1(2):245- 252, October 1979.

Digital Library

Google Scholar

[12]

D. C. Oppen. Complexity, convexity, and combination of theories. Theoretical Competer Science, 12(3):291-302, November 1980.

Crossref

Google Scholar

[13]

C. H. Papadimitriou. Personal communication.

Google Scholar

[14]

R. E. Tarjan. Efficiency of a good but not linear set union algorithm. Journal of the A CM, 22(2):215- 225, April 1975.

Digital Library

Google Scholar

Cited By

View all

Agoun JHacid M(2020)Data Publishing: Availability of Data Under Security PoliciesFoundations of Intelligent Systems10.1007/978-3-030-59491-6_26(277-286)Online publication date: 17-Sep-2020
https://doi.org/10.1007/978-3-030-59491-6_26
Lo EBinnig CKossmann DTamer Özsu MHon W(2010)A framework for testing DBMS featuresThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-009-0157-y19:2(203-230)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1007/s00778-009-0157-y
Vincent MMohania MIwaihara M(2009)Detecting privacy violations in database publishing using disjoint queriesProceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology10.1145/1516360.1516390(252-262)Online publication date: 24-Mar-2009
https://dl.acm.org/doi/10.1145/1516360.1516390
Show More Cited By

Index Terms

Recommendations

Conjunctive query containment and answering under description logic constraints

Query containment and query answering are two important computational tasks in databases. While query answering amounts to computing the result of a query over a database, query containment is the problem of checking whether, for every database, the ...
Determinacy and query rewriting for conjunctive queries and views

Answering queries using views is the problem which examines how to derive the answers to a query when we only have the answers to a set of views. Constructing rewritings is a widely studied technique to derive those answers. In this paper we consider ...
Conjunctive query optimization in OWL2-DL
DEXA'11: Proceedings of the 22nd international conference on Database and expert systems applications - Volume Part II

Conjunctive query answering is becoming a very important task on the Semantic Web as the adoption of SPARQL query language increases. There is considerable work done in the area of optimizing conjunctive query answering for RDF and OWL2-DL ontologies, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

PODS '89: Proceedings of the eighth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems

March 1989

401 pages

ISBN:0897913086

DOI:10.1145/73721

Chairman:
Avi Silberschatz
Univ. of Texas, Austin

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 29 March 1989

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

PODS '89

Sponsor:

PODS '89: Principles of database systems

Pennsylvania, Philadelphia, USA

Acceptance Rates

Overall Acceptance Rate 642 of 2,707 submissions, 24%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

10
Total Citations
View Citations
326
Total Downloads

Downloads (Last 12 months)43
Downloads (Last 6 weeks)8

Reflects downloads up to 22 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Agoun JHacid M(2020)Data Publishing: Availability of Data Under Security PoliciesFoundations of Intelligent Systems10.1007/978-3-030-59491-6_26(277-286)Online publication date: 17-Sep-2020
https://doi.org/10.1007/978-3-030-59491-6_26
Lo EBinnig CKossmann DTamer Özsu MHon W(2010)A framework for testing DBMS featuresThe VLDB Journal — The International Journal on Very Large Data Bases10.1007/s00778-009-0157-y19:2(203-230)Online publication date: 1-Apr-2010
https://dl.acm.org/doi/10.1007/s00778-009-0157-y
Vincent MMohania MIwaihara M(2009)Detecting privacy violations in database publishing using disjoint queriesProceedings of the 12th International Conference on Extending Database Technology: Advances in Database Technology10.1145/1516360.1516390(252-262)Online publication date: 24-Mar-2009
https://dl.acm.org/doi/10.1145/1516360.1516390
Ataullah AAboulnaga ATompa FShanahan JAmer-Yahia SManolescu IZhang YEvans DKolcz AChoi KChowdury A(2008)Records retention in relational database systemsProceedings of the 17th ACM conference on Information and knowledge management10.1145/1458082.1458197(873-882)Online publication date: 26-Oct-2008
https://dl.acm.org/doi/10.1145/1458082.1458197
Maher M(2005)Constrained dependenciesPrinciples and Practice of Constraint Programming — CP '9510.1007/3-540-60299-2_11(170-185)Online publication date: 1-Jun-2005
https://doi.org/10.1007/3-540-60299-2_11
Ishakbeyoğlu NÖzsoyoğlu Z(2005)On the maintenance of implication integrity constraintsDatabase and Expert Systems Applications10.1007/3-540-57234-1_20(221-232)Online publication date: 27-May-2005
https://doi.org/10.1007/3-540-57234-1_20
Maher MSrivastava DHull R(1996)Chasing constrained tuple-generating dependenciesProceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/237661.237693(128-138)Online publication date: 3-Jun-1996
https://dl.acm.org/doi/10.1145/237661.237693
Guo SSun WWeiss M(1996)On Satisfiability, Equivalence, and Implication Problems Involving Conjunctive Queries in Database SystemsIEEE Transactions on Knowledge and Data Engineering10.1109/69.5362538:4(604-616)Online publication date: 1-Aug-1996
https://dl.acm.org/doi/10.1109/69.536253
Meghini CThanos C(1996)An Optimal Predicate Locking SchedulerJournal of Computer and System Sciences10.1006/jcss.1996.008053:3(443-468)Online publication date: 1-Dec-1996
https://dl.acm.org/doi/10.1006/jcss.1996.0080
Elkan CRosenkrantz DSagiv Y(1990)Independence of logic database queries and updateProceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems10.1145/298514.298557(154-160)Online publication date: 2-Apr-1990
https://dl.acm.org/doi/10.1145/298514.298557

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

Conjunctive query containment and answering under description logic constraints

Determinacy and query rewriting for conjunctive queries and views

Conjunctive query optimization in OWL2-DL