Article

Computing full disjunctions

Authors:

Yehoshua SagivAuthors Info & Claims

PODS '03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

Pages 78 - 89

https://doi.org/10.1145/773153.773162

Published: 09 June 2003 Publication History

Abstract

Under either the OR-semantics or the weak semantics, the answer to a query over semistructured data consists of maximal rather than complete matchings, i.e., some query variables may be assigned null values. In the relational model, a similar effect is achieved by computing the full disjunction (rather than the natural join or equijoin) of the given relations. It is shown that under either the OR-semantics or the weak semantics, query evaluation has a polynomial-time complexity in the size of the query, the database and the result. It is also shown that the evaluation of full disjunctions is reducible to query evaluation under the weak semantics and hence can be done in polynomial time in the size of the input and the output. Complexity results are also given for two related problems. One is evaluating a projection of the full disjunction and the other is evaluating the set of all tuples in the full disjunction that are non-null on some given attributes. In the special case of γ-acyclic relation schemes, both problems have polynomial-time algorithms in the size of the input and the output. In the general case, such algorithms do not exist, assuming that P ≠ NP. Finally, it is shown that the weak semantics can generalize full disjunctions by allowing tuples to be joined according to general types of conditions, rather than just equalities among attributes.

References

[1]

S. Abiteboul, P.Kanellakis, and G. Grahne. On the representation and querying sets of possible worlds. Theoretical Computer Science, 78(1):158--187, 1991.

Digital Library

[2]

S. Abiteboul, L. Segoufin, and V. Vianu. Representing and querying XML with incomplete information. In Proceedings of the 20th ACM Symposium on Principles of Databae Systems, Santa Barbara (California, USA), May 2001.

Digital Library

[3]

C. Beeri, R. Fagin, D. Maier, and M. Yannakakis. On the desirability of acyclic database schemes. Journal of the ACM, 30(3):479--513, 1983.

Digital Library

[4]

G. Bhargava, P. Goel, and B. Iyer. Hypergraph based reorderings of outer join queries with complex predicates. In Proceedings of the of 1995 ACM SIGMOD International Conference on Management of Data, pages 304--315, San Jose (California, USA), 1995.

Digital Library

[5]

A. L. P. Chen. Outer join optimization in multidatabase systems. In Proceedings of the 2nd International Symposium on Databases in Parallel and Distributed Systems, pages 211--218, Dublin, (Ireland), July 1990.

Digital Library

[6]

E. F. Codd. Extending the relational database model to capture more meaning. ACM Transactions on Database Systems, 4(4):397--434, 1979.

Digital Library

[7]

C. J. Date. The outer join. In Proceedings of the 2nd International Conference on Databases, pages 76--106, Cambridge, 1983.

[8]

R. Fagin. Degree of acyclicity for hypergraphs and relational database schemas. Journal of the ACM, 7(3):343--360, 1983.

Digital Library

[9]

R. Fagin, O. Mendelzon, and J. D. Ullman. A simplified universal relation assumption and its properties. ACM Transactions on Database Systems, 7(3):343--360, 1982.

Digital Library

[10]

C. Galiando-Legaria and A. Rosenthal. Outerjoin simplification and reordering for query optimization. ACM Transactions on Database Systems, 22(1):43--73, 1997.

Digital Library

[11]

C. Galindo-Legaria. Outerjoins as disjunctions. In Proceedings of the of 1994 ACM SIGMOD International Conference on Management of Data, pages 348--358, Minneapolis (Minnesota, USA), May 1994.

Digital Library

[12]

M. Graham and M. Yannakakis. Independent database schemas. Journal of Computer and System Sciences, 28(1):121--141, 1984.

[13]

P. Honeyman. Testing satisfaction of functional dependencies. Journal of the ACM, 29(3):668--677, 1982.

Digital Library

[14]

T. Imielinski and W. Lipski. Incomplete information in relational databases. Journal of the ACM, 31:761--791, 1984.

Digital Library

[15]

Y. Kanza, W. Nutt, and Y. Sagiv. Queries with incomplete answers over semistructured data. In Proceedings of the 18th ACM Symposium on Principles of Database Systems, pages 227--236, Philadelphia, (Pennsylvania), May 1999.

Digital Library

[16]

Y. Kanza, W. Nutt, and Y. Sagiv. Querying incomplete information in semistructured data. Journal of Computer and System Sciences, 64(3):655--693, 2002.

Digital Library

[17]

M. Lacroix and A. Pirotte. Generalized joins. ACM SIGMOD Record, 8(3):14--15, 1976.

Digital Library

[18]

A. Y. Levy, A. Rajaraman, and J. J. Ordille. Query-answering algorithms for information agents. In Proceedings of the 13th National Conference on Artificial Intelligence and 8th Innovative Applications of Artificial Intelligence Conference, pages 40--47, Portland (Oragon), August 1996.

Digital Library

[19]

A. Y. Levy, A. Rajaraman, and J. J. Ordille. The world wide web as a collection of views: Query processing in the information manifold. In Workshop on Materialized Views: Techniques and Applications, pages 43--55, Monteal, (Canada), June 1996.

[20]

D. Maier, Y. Sagiv, and M. Yannakakis. On the complexity of testing implications of functional and join dependencies. Journal of the ACM, 28(4):680--695, 1981.

Digital Library

[21]

Y. Papakonstantinou, H. Garcia-Molina, and J. Widom. Object exchange across heterogeneous information sources. In Proceedings of the 11th International Conference on Data Engineering, pages 251--260, Taipei, Mar. 1995.

Digital Library

[22]

D. Quass, J. Widom, R. Goldman, K. Haas, Q. Luo, J. McHugh, S. Nestorov, A. Rajaraman, H. Rivero, S. Abiteboul, J. Ullman, and J. Wiener. LORE: A lightweight object repository for semistructured data. In Proceedings of the of 1996 ACM SIGMOD International Conference on Management of Data, Montreal (Canada), June 1996.

Digital Library

[23]

A. Rajaraman and J. D. Ullman. Integrating information by outerjoins and full disjunctions. In Proceedings of the 15th ACM Symposium on Principles of Database Systems, Montreal, (Canada), June 1996.

Digital Library

[24]

R. Reiter. A sound and sometimes complete query evaluation algorithm for relational databases with null values. Journal of the ACM, 33(2):349--370, 1986.

Digital Library

[25]

A. Rosenthal and D. Reiner. Extending the algebric framework of query processing to handle outerjoins. In Proceedings of the 10th International Conference on Very Large Data Bases, pages 334--343, Singapore, 1984.

Digital Library

[26]

Y. Sagiv. A characterization of globally consistent databases and their correct access paths. ACM Transactions on Database Systems, 8(2):266--286, 1983.

Digital Library

[27]

Y. Sagiv. Evaluation of queries in independent database schemes. Journal of the ACM, 38(1):120--161, 1991.

Digital Library

[28]

M. Y. Vardi. The complexity of relational query languages. In Proceedings of the 14th ACM Symposium on Theory of Computing, pages 137--146, San Francisco (California, USA), May 1982.

Digital Library

[29]

M. Y. Vardi. On the integrity of databases with incomplete information. In Proceedings of the 5th ACM Symposium on Principles of Database Systems, pages 252--266, Cambridge (Massachusetts, USA), 1986.

Digital Library

[30]

M. Yannakakis. Algorithms for acyclic database schemes. In Proceedings of the 7th International Conference on Very Large Data Bases, pages 82--94, Cannes (France), September 1981.

Cited By

Khatiwada AShraga RGatterbauer WMiller R(2022)Integrating Data Lake TablesProceedings of the VLDB Endowment10.14778/3574245.357427416:4(932-945)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.14778/3574245.3574274
Kanza YShalem M(2018)Combined geo-social searchGeoinformatica10.5555/3238836.323886122:3(615-660)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.5555/3238836.3238861
Kanza YShalem M(2017)Combined geo-social search: computing top-k join queries over incomplete informationGeoInformatica10.1007/s10707-017-0297-y22:3(615-660)Online publication date: 25-Mar-2017
https://doi.org/10.1007/s10707-017-0297-y
Show More Cited By

Index Terms

Computing full disjunctions

Recommendations

Outerjoins as disjunctions
SIGMOD '94: Proceedings of the 1994 ACM SIGMOD international conference on Management of data

The outerjoin operator is currently available in the query language of several major DBMSs, and it is included in the proposed SQL2 standard draft. However, “associativity problems” of the operator have been pointed out since its introduction. In this ...
An incremental algorithm for computing ranked full disjunctions

The full disjunction is a variation of the join operator that maximally combines tuples from connected relations, while preserving all information in the relations. The full disjunction can be seen as a natural extension of the binary outerjoin operator ...
An incremental algorithm for computing ranked full disjunctions
PODS '05: Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

The full disjunction is a variation of the join operator that maximally combines tuples from connected relations, while preserving all information in the relations. The full disjunction can be seen as a natural extension of the binary outerjoin operator ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

PODS '03: Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems

June 2003

291 pages

ISBN:1581136706

DOI:10.1145/773153

Conference Chair:
Frank Neven
Limburgs Universitair Centrum
,
General Chair:
Catriel Beeri
Hebrew University of Jerusalem
,
Program Chair:
Tova Milo
Tel Aviv University & INRIA

Copyright © 2003 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 09 June 2003

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Conference

SIGMOD/PODS03

Sponsor:

SIGMOD/PODS03: International Conference on Management of Data and Symposium on Principles Database and Systems

June 9 - 11, 2003

California, San Diego

Acceptance Rates

PODS '03 Paper Acceptance Rate 27 of 136 submissions, 20%;

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

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

6
Total Citations
View Citations
502
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Khatiwada AShraga RGatterbauer WMiller R(2022)Integrating Data Lake TablesProceedings of the VLDB Endowment10.14778/3574245.357427416:4(932-945)Online publication date: 1-Dec-2022
https://dl.acm.org/doi/10.14778/3574245.3574274
Kanza YShalem M(2018)Combined geo-social searchGeoinformatica10.5555/3238836.323886122:3(615-660)Online publication date: 1-Jul-2018
https://dl.acm.org/doi/10.5555/3238836.3238861
Kanza YShalem M(2017)Combined geo-social search: computing top-k join queries over incomplete informationGeoInformatica10.1007/s10707-017-0297-y22:3(615-660)Online publication date: 25-Mar-2017
https://doi.org/10.1007/s10707-017-0297-y
Vijay Kumar TShridhar AGhoshal A(2009)Computing full disjunction using COJOInformation Technology and Management10.1007/s10799-008-0043-010:1(3-20)Online publication date: 1-Mar-2009
https://dl.acm.org/doi/10.1007/s10799-008-0043-0
Cohen SKimelfeld BSagiv Y(2008)Generating all maximal induced subgraphs for hereditary and connected-hereditary graph propertiesJournal of Computer and System Sciences10.1016/j.jcss.2008.04.00374:7(1147-1159)Online publication date: 1-Nov-2008
https://dl.acm.org/doi/10.1016/j.jcss.2008.04.003
Cohen SSagiv Y(2007)An incremental algorithm for computing ranked full disjunctionsJournal of Computer and System Sciences10.1016/j.jcss.2006.10.01573:4(648-668)Online publication date: 1-Jun-2007
https://dl.acm.org/doi/10.1016/j.jcss.2006.10.015

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents