From complete to incomplete information and back

ABSTRACT

Incomplete information arises naturally in numerous data management applications. Recently, several researchers have studied query processing in the context of incomplete information. Most work has combined the syntax of a traditional query language like relational algebra with a nonstandard semantics such as certain or ranked possible answers. There are now also languages with special features to deal with uncertainty. However, to the standards of the data management community, to date no language proposal has been made that can be considered a natural analog to SQL or relational algebra for the case of incomplete information.

In this paper we propose such a language, World-set Algebra, which satisfies the robustness criteria and analogies to relational algebra that we expect. The language supports the contemplation on alternatives and can thus map from a complete database to an incomplete one comprising several possible worlds. We show that World-set Algebra is conservative over relational algebra in the sense that any query that maps from a complete database to a complete database (a complete-to-complete query) is equivalent to a relational algebra query. Moreover, we give an efficient algorithm for effecting this translation.

We then study algebraic query optimization of such queries. We argue that query languages with explicit constructs for handling uncertainty allow for the more natural and simple expression of many real-world decision support queries. The results of this paper not only suggest a language for specifying queries in this way, but also allow for their efficient evaluation in any relational database management system.

REFERENCES

• 1: S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
• 2: 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
• 3: P. Andritsos, A. Fuxman, and R. J. Miller. Clean answers over dirty databases: A probabilistic approach. In Proc. ICDE, 2006.
• 4: L. Antova, C. Koch, and D. Olteanu. 10¹⁰⁶ worlds and beyond: Efficient representation and processing of incomplete information. In Proc. ICDE, 2007.
• 5: L. Antova, C. Koch, and D. Olteanu. World-set decompositions: Expressiveness and efficient algorithms. In Proc. ICDT, 2007.
• 6: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Consistent query answers in inconsistent databases, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.68-79, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303983]
• 7: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki, Answer sets for consistent query answering in inconsistent databases, Theory and Practice of Logic Programming, v.3 n.4, p.393-424, July 2003 [doi>10.1017/S1471068403001832]
• 8: Omar Benjelloun , Anish Das Sarma , Alon Halevy , Jennifer Widom, ULDBs: databases with uncertainty and lineage, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 9: O. Benjelloun, A. D. Sarma, C. Hayworth, and J. Widom. An Introduction to ULDBs and the Trio System. IEEE Data Engineering Bulletin, 29(1):5--16, Mar. 2006.
• 10: N. Dalvi and D. Suciu. Efficient query evaluation on probabilistic databases. In Proc. VLDB, 2004
• 11: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data exchange: semantics and query answering, Theoretical Computer Science, v.336 n.1, p.89-124, 25 May 2005 [doi>10.1O16/j.tcs.2004.10.033]
• 12: Gösta Grahne, Dependency Satisfaction in Databases with Incomplete Information, Proceedings of the 10th International Conference on Very Large Data Bases, p.37-45, August 27-31, 1984
• 13: G. Grahne, Problem of Incomplete Information in Relational Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 14: T. J. Green and V. Tannen. "Models for Incomplete and Probabilistic Information". In International Workshop on Incompleteness and Inconsistency in Databases (IIDB), 2006.
• 15: Timothy Griffin , Richard Hull, A framework for implementing hypothetical queries, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.231-242, May 11-15, 1997, Tucson, Arizona, United States
• 16: 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]
• 17: Tomasz Imielinski , Shamim Naqvi , Kumar Vadaparty, Incomplete object—a data model for design and planning applications, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.288-297, May 29-31, 1991, Denver, Colorado, United States
• 18: Nicola Leone , Gianluigi Greco , Giovambattista Ianni , Vincenzino Lio , Giorgio Terracina , Thomas Eiter , Wolfgang Faber , Michael Fink , Georg Gottlob , Riccardo Rosati , Domenico Lembo , Maurizio Lenzerini , Marco Ruzzi , Edyta Kalka , Bartosz Nowicki , Witold Staniszkis, The INFOMIX system for advanced integration of incomplete and inconsistent data, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066286]
• 19: Leonid Libkin , Limsoon Wong, Semantic representations and query languages for or-sets, Proceedings of the twelfth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.37-48, May 25-28, 1993, Washington, D.C., United States [doi>10.1145/153850.153854]
• 20: Jan Paredaens , Dirk Van Gucht, Converting nested algebra expressions into flat algebra expressions, ACM Transactions on Database Systems (TODS), v.17 n.1, p.65-93, March 1992 [doi>10.1145/128765.128768]
• 21: Meikel Poess , Chris Floyd, New TPC benchmarks for decision support and web commerce, ACM SIGMOD Record, v.29 n.4, p.64-71, Dec. 2000 [doi>10.1145/369275.369291]
• 22: R. Rantzau and C. Mangold. Laws for rewriting queries containing division operators. In Proc. ICDE, 2006.
• 23: Stanford Trio Project. TriQL-The Trio Query Language, Oct. 2006. http://infolab.stanford.edu/~widom/triql.html.
• 24: Transaction Processing Performance Council. TPC Benchmark H (Decision Support), revision 2.6.0 edition, 2006. http://www.tpc.org/tpch/spec/tpch2.6.0.pdf.

INDEX TERMS

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

General Terms:
Design, Languages

Keywords:
hypothetical queries, incomplete information, query rewriting, use cases, world-set algebra