Data exchange and incomplete information

ABSTRACT

Data exchange is the problem of finding an instance of a target schema, given an instance of a source schema and a specification of the relationship between the source and the target, and answering queries over target instances in a way that is semantically consistent with the information in the source. Theoretical foundations of data exchange have been actively explored recently. It was also noticed that the standard certain answers semantics may behave in very odd ways.In this paper I explain that this behavior is due to the fact that the presence of incomplete information in target instances has been ignored; in particular, proper query evaluation techniques for databases with nulls have not been used, and the distinction between closed and open world semantics has not been made. I present a concept of target solutions based on the closed world assumption, and show that the space of all solutions has two extreme points: the canonical universal solution and the core, well studied in data exchange. I show how to define semantics of query answering taking into account incomplete information, and show that the well-known anomalies go away with the new semantics. The paper also contains results on the complexity of query answering, upper approximations to queries (maybe-answers), and various extensions.

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: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 3: 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
• 4: Marcelo Arenas , Pablo Barceló , Ronald Fagin , Leonid Libkin, Locally consistent transformations and query answering in data exchange, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055592]
• 5: 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]
• 6: Marcelo Arenas , Leonid Libkin, XML data exchange: consistency and query answering, 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.1065171]
• 7: Leopoldo Bertossi , Jan Chomicki , Parke Godfrey , Phokion G. Kolaitis , Alex Thomo , Calisto Zuzarte, Exchange, integration, and consistency of data: report on the ARISE/NISR workshop, ACM SIGMOD Record, v.34 n.3, September 2005 [doi>10.1145/1084805.1084825]
• 8: O. P. Buneman , S. B. Davidson , A. Watters, A semantics for complex objects and approximate answers, Journal of Computer and System Sciences, v.43 n.1, p.170-218, Aug. 1991 [doi>10.1016/0022-0000(91)90035-4]
• 9: Peter Buneman , Achim Jung , Atsushi Ohori, Using powerdomains to generalize relational databases, Theoretical Computer Science, v.91 n.1, p.23-55, Dec. 9, 1991 [doi>10.1016/0304-3975(91)90266-5]
• 10: Ronald Fagin , Phokion G. Kolaitis , Renée J. Miller , Lucian Popa, Data Exchange: Semantics and Query Answering, Proceedings of the 9th International Conference on Database Theory, p.207-224, January 08-10, 2003
• 11: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.90-101, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773163]
• 12: Ronald Fagin , Phokion G. Kolaitis , Wang-Chiew Tan , Lucian Popa, Composing schema mappings: second-order dependencies to the rescue, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055572]
• 13: Georg Gottlob, Computing cores for data exchange: new algorithms and practical solutions, 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.1065187]
• 14: 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
• 15: Carl A. Gunter, The mixed powerdomain, Theoretical Computer Science, v.103 n.2, p.311-334, 14 Sept. 1992 [doi>10.1016/0304-3975(92)90017-A]
• 16: Pavol Hell , Jaroslav Nešetřil, The core of a graph, Discrete Mathematics, v.109 n.1-3, p.117-126, Nov. 12, 1992 [doi>10.1016/0012-365X(92)90282-K]
• 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: Phokion G. Kolaitis, Schema mappings, data exchange, and metadata management, 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.1065176]
• 19: Mark Levene , George Loizou, Axiomatisation of functional dependencies in incomplete relations, Theoretical Computer Science, v.206 n.1-2, p.283-300, Oct. 6, 1998 [doi>10.1016/S0304-3975(98)80029-7]
• 20: Mark Levene , George Loizou, Null inclusion dependencies in relational databases, Information and Computation, v.136 n.2, p.67-108, Aug. 1, 1997 [doi>10.1006/inco.1997.2631]
• 21: Leonid Libkin, Models of approximation in databases, Theoretical Computer Science, v.190 n.2, p.167-210, Jan. 20, 1998 [doi>10.1016/S0304-3975(97)00090-X]
• 22: Witold Lipski, Jr., On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.262-296, Sept. 1979 [doi>10.1145/320083.320088]
• 23: Aleksander Madry, Data exchange: on the complexity of answering queries with inequalities, Information Processing Letters, v.94 n.6, p.253-257, 30 June 2005 [doi>10.1016/j.ipl.2005.03.001]
• 24: Renée J. Miller , Mauricio A. Hernández , Laura M. Haas , Lingling Yan , C. T. Howard Ho , Ronald Fagin , Lucian Popa, The Clio project: managing heterogeneity, ACM SIGMOD Record, v.30 n.1, p.78-83, March 2001 [doi>10.1145/373626.373713]
• 25: L. Popa, Y. Velegrakis, R. Miller, M. Hernández, R. Fagin. Translating web data. In VLDB 2002, pages 598--609.
• 26: R. Reiter. On closed world databases. In "Logic and Databases", H. Gallaire and J. Minker eds, Plenum Press, 1978, pages 55--76.
• 27: R. Reiter. Towards a logical reconstruction of relational database theory. In: "On Conceptual Modeling" (M. Brodie and J. Schmidt eds.), Springer Verlag, 1984, pages 163--189.
• 28: N. C. Shu , B. C. Housel , R. W. Taylor , S. P. Ghosh , V. Y. Lum, EXPRESS: a data EXtraction, Processing, and Restructuring System, ACM Transactions on Database Systems (TODS), v.2 n.2, p.134-174, June 1977 [doi>10.1145/320544.320549]
• 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: C. Zaniolo. Database relations with null values. Journal of Computer and System Sciences 28 (1984), 142--166.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.5 Heterogeneous Databases

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications

General Terms:
Algorithms, Theory

Keywords:
canonical solution, certain answers, core, data exchange, maybe answers, null values