Computing full disjunctions

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: Serge Abiteboul , Paris Kanellakis , Gösta Grahne, On the representation and querying of sets of possible worlds, Theoretical Computer Science, v.78 n.1, p.159-187, Jan. 21, 1991
• 2: Serge Abiteboul , Luc Segoufin , Victor Vianu, Representing and querying XML with incomplete information, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.150-161, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375571]
• 3: Catriel Beeri , Ronald Fagin , David Maier , Mihalis Yannakakis, On the Desirability of Acyclic Database Schemes, Journal of the ACM (JACM), v.30 n.3, p.479-513, July 1983 [doi>10.1145/2402.322389]
• 4: Gautam Bhargava , Piyush Goel , Bala Iyer, Hypergraph based reorderings of outer join queries with complex predicates, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.304-315, May 22-25, 1995, San Jose, California, United States
• 5: Arbee L. P. Chen, Outerjoin optimization in multidatabase systems, Proceedings of the second international symposium on Databases in parallel and distributed systems, p.211-218, July 02-04, 1990, Dublin, Ireland [doi>10.1145/319057.319101]
• 6: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 7: C. J. Date. The outer join. In Proceedings of the 2nd International Conference on Databases, pages 76--106, Cambridge, 1983.
• 8: Ronald Fagin, Degrees of acyclicity for hypergraphs and relational database schemes, Journal of the ACM (JACM), v.30 n.3, p.514-550, July 1983 [doi>10.1145/2402.322390]
• 9: Ronald Fagin , Alberto O. Mendelzon , Jeffrey D. Ullman, A simplied universal relation assumption and its properties, ACM Transactions on Database Systems (TODS), v.7 n.3, p.343-360, Sept. 1982 [doi>10.1145/319732.319735]
• 10: César Galindo-Legaria , Arnon Rosenthal, Outerjoin simplification and reordering for query optimization, ACM Transactions on Database Systems (TODS), v.22 n.1, p.43-74, March 1997 [doi>10.1145/244810.244812]
• 11: César A. Galindo-Legaria, Outerjoins as disjunctions, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.348-358, May 24-27, 1994, Minneapolis, Minnesota, United States
• 12: M. Graham and M. Yannakakis. Independent database schemas. Journal of Computer and System Sciences, 28(1):121--141, 1984.
• 13: Peter Honeyman, Testing satisfaction of functional dependencies, Journal of the ACM (JACM), v.29 n.3, p.668-677, July 1982 [doi>10.1145/322326.322330]
• 14: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 15: Yaron Kanza , Werner Nutt , Yehoshua Sagiv, Queries with incomplete answers over semistructured data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.227-236, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303999]
• 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.
• 17: M. Lacroix , A. Pirotte, Generalized joins, ACM SIGMOD Record, v.8 n.3, p.14-15, September 1976 [doi>10.1145/984378.984379]
• 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.
• 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: David Maier , Yehoshua Sagiv , Mihalis Yannakakis, On the Complexity of Testing Implications of Functional and Join Dependencies, Journal of the ACM (JACM), v.28 n.4, p.680-695, Oct. 1981 [doi>10.1145/322276.322280]
• 21: Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom, Object Exchange Across Heterogeneous Information Sources, Proceedings of the Eleventh International Conference on Data Engineering, p.251-260, March 06-10, 1995
• 22: Dallan Quass , Jennifer Widom , Roy Goldman , Kevin Haas , Qingshan Luo , Jason McHugh , Svetlozar Nestorov , Anand Rajaraman , Hugo Rivero , Serge Abiteboul , Jeff Ullman , Janet Wiener, LORE: a Lightweight Object REpository for semistructured data, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.549, June 04-06, 1996, Montreal, Quebec, Canada
• 23: Anand Rajaraman , Jeffrey D. Ullman, Integrating information by outerjoins and full disjunctions (extended abstract), Proceedings of the fifteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.238-248, June 04-06, 1996, Montreal, Quebec, Canada [doi>10.1145/237661.237717]
• 24: Raymond Reiter, A sound and sometimes complete query evaluation algorithm for relational databases with null values, Journal of the ACM (JACM), v.33 n.2, p.349-370, April 1986 [doi>10.1145/5383.5388]
• 25: Arnon Rosenthal , David S. Reiner, Extending the Algebraic Framework of Query Processing to Handle Outerjoins, Proceedings of the 10th International Conference on Very Large Data Bases, p.334-343, August 27-31, 1984
• 26: Yehoshua Sagiv, A characterization of globally consistent databases and their correct access paths, ACM Transactions on Database Systems (TODS), v.8 n.2, p.266-286, June 1983 [doi>10.1145/319983.319988]
• 27: Yehoshua Sagiv, Evaluation of queries in independent database schemes, Journal of the ACM (JACM), v.38 n.1, p.120-161, Jan. 1991 [doi>10.1145/102782.102787]
• 28: Moshe Y. Vardi, The complexity of relational query languages (Extended Abstract), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.137-146, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802186]
• 29: Moshe Vardi, On the integrity of databases with incomplete information, Proceedings of the fifth ACM SIGACT-SIGMOD symposium on Principles of database systems, p.252-266, March 24-26, 1986, Cambridge, Massachusetts, United States [doi>10.1145/6012.15419]
• 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.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval
          Subjects: Query formulation

  K. Computing Milieux
  K.8 PERSONAL COMPUTING
      K.8.1 Application Packages
          Subjects: Database processing

General Terms:
Experimentation, Theory