Relative information completeness

ABSTRACT

The paper investigates the question of whether a partially closed database has complete information to answer a query. In practice an enterprise often maintains master data Dm, a closed-world database. We say that a database D is partially closed if it satisfies a set V of containment constraints of the form "q(D) is a subset of p(Dm)", where q is a query in a language Lc and p is a projection query. The part of D not constrained by (Dm,V) is open, from which some tuples may be missing. The database D is said to be complete for a query Q relative to (Dm,V) if for all partially closed extensions D' of D, Q(D')=Q(D), i.e., adding tuples to D either violates some constraints in V or does not change the answer to Q.

We first show that the proposed model can also capture the consistency of data, in addition to its relative completeness. Indeed, integrity constraints studied for consistency can be expressed as containment constraints. We then study two problems. One is to decide, given Dm, V, a query Q in a language Lq and a partially closed database D, whether D is complete for Q relative to (Dm,V). The other is to determine, given Dm, V and Q, whether there exists a partially closed database that is complete for Q relative to (Dm,V). We establish matching lower and upper bounds on these problems for a variety of languages Lq and Lc. We also provide characterizations for a database to be relatively complete, and for a query to allow a relatively complete database, when Lq and Lc are conjunctive queries.

REFERENCES

• 1: 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 [doi>10.1145/275487.275516]
• 2: S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, 1995.
• 3: 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]
• 4: Carlo Batini , Monica Scannapieco, Data Quality: Concepts, Methodologies and Techniques (Data-Centric Systems and Applications), Springer-Verlag New York, Inc., Secaucus, NJ, 2006
• 5: Loreto Bravo , Wenfei Fan , Shuai Ma, Extending dependencies with conditions, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 6: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 7: Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini , Moshe Y. Vardi, View-based query processing: On the relationship between rewriting, answering and losslessness, Theoretical Computer Science, v.371 n.3, p.169-182, February 2007 [doi>10.1016/j.tcs.2006.11.006]
• 8: J. Chomicki. Consistent query answering: Five easy pieces. In ICDT, 2007.
• 9: Evgeny Dantsin , Andrei Voronkov, Complexity of Query Answering in Logic Databases with Complex Values, Proceedings of the 4th International Symposium on Logical Foundations of Computer Science, p.56-66, July 06-12, 1997
• 10: Alin Deutsch , Bertram Ludäscher , Alan Nash, Rewriting queries using views with access patterns under integrity constraints, Theoretical Computer Science, v.371 n.3, p.200-226, February 2007 [doi>10.1016/j.tcs.2006.11.008]
• 11: A. Dreibelbis, E. Hechler, B. Mathews, M. Oberhofer, and G. Sauter. Master data management architecture patterns. IBM, 2007.
• 12: Charles Elkan, Independence of logic database queries and update, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.154-160, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298557]
• 13: Wenfei Fan, Dependencies revisited for improving data quality, Proceedings of the twenty-seventh ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376916.1376940]
• 14: Wenfei Fan , Floris Geerts , Xibei Jia , Anastasios Kementsietsidis, Conditional functional dependencies for capturing data inconsistencies, ACM Transactions on Database Systems (TODS), v.33 n.2, p.1-48, June 2008 [doi>10.1145/1366102.1366103]
• 15: Georg Gottlob , Roberto Zicari, Closed World Databases Opened Through Null Values, Proceedings of the 14th International Conference on Very Large Data Bases, p.50-61, August 29-September 01, 1988
• 16: G. Grahne, Problem of Incomplete Information in Relational Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 17: 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]
• 18: 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
• 19: 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
• 20: Chen Li, Computing complete answers to queries in the presence of limited access patterns, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.3, p.211-227, October 2003 [doi>10.1007/s00778-002-0085-6]
• 21: David Loshin, Master Data Management, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2008
• 22: Amihai Motro, Integrity = validity + completeness, ACM Transactions on Database Systems (TODS), v.14 n.4, p.480-502, Dec. 1989 [doi>10.1145/76902.76904]
• 23: C.H. Papadimitriou. Computational Complexity. Addison-Wesley, 1994.
• 24: J. Radcliffe and A. White. Key issues for master data management. Gartner, 2008.
• 25: Luc Segoufin , Victor Vianu, Views and queries: determinacy and rewriting, Proceedings of the twenty-fourth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 13-15, 2005, Baltimore, Maryland [doi>10.1145/1065167.1065174]
• 26: M. Spielmann. Abstract state machines: Verification problems and complexity. PhD thesis, RWTH Aachen, 2000.
• 27: Ron van der Meyden, Logical approaches to incomplete information: a survey, Logics for databases and information systems, Kluwer Academic Publishers, Norwell, MA, 1998
• 28: 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]

INDEX TERMS

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

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Computational logic

General Terms:
Algorithms, Design, Languages

Keywords:
consistency, constraints, information completeness, master data