Data exchange and schema mappings in open and closed worlds

ABSTRACT

In the study of data exchange one usually assumes an open-world semantics, making it possible to extend instances of target schemas. An alternative closed-world semantics only moves 'as much data as needed' from the source to the target to satisfy constraints of a schema mapping. It avoids some of the problems exhibited by the open-world semantics, but limits the expressivity of schema mappings. Here we propose a mixed approach: one can designate different attributes of target schemas as open or closed, to combine the additional expressivity of the open-world semantics with the better behavior of query answering in closed worlds.

We define such schema mappings, and show that they cover a large space of data exchange solutions with two extremes being the known open and closed-world semantics. We investigate the problems of query answering and schema mapping composition, and prove two trichotomy theorems, classifying their complexity based on the number of open attributes. We find conditions under which schema mappings compose, extending known results to a wide range of closed-world mappings. We also provide results for restricted classes of queries and mappings guaranteeing lower complexity.

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 , 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: 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]
• 4: Paolo Atzeni , Nicola M Morfuni, Functional dependencies and constraints on Null values in database relations, Information and Control, v.70 n.1, p.1-31, July 1986 [doi>10.1016/S0019-9958(86)80022-5]
• 5: Philip A. Bernstein , Todd J. Green , Sergey Melnik , Alan Nash, Implementing mapping composition, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 6: Philip A. Bernstein , Sergey Melnik, Model management 2.0: manipulating richer mappings, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247482]
• 7: Laura Chiticariu , Wang-Chiew Tan, Debugging schema mappings with routes, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 8: Giuseppe De Giacomo , Domenico Lembo , Maurizio Lenzerini , Riccardo Rosati, On reconciling data exchange, data integration, and peer data management, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265549]
• 9: Alin Deutsch , Val Tannen, Reformulation of XML Queries and Constraints, Proceedings of the 9th International Conference on Database Theory, p.225-241, January 08-10, 2003
• 10: 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]
• 11: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa, Data exchange: getting to the core, ACM Transactions on Database Systems (TODS), v.30 n.1, p.174-210, March 2005 [doi>10.1145/1061318.1061323]
• 12: Ronald Fagin , Phokion G. Kolaitis , Lucian Popa , Wang-Chiew Tan, Composing schema mappings: Second-order dependencies to the rescue, ACM Transactions on Database Systems (TODS), v.30 n.4, p.994-1055, December 2005 [doi>10.1145/1114244.1114249]
• 13: 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
• 14: G. Grahne, Problem of Incomplete Information in Relational Databases, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 15: Andre Hernich , Nicole Schweikardt, CWA-solutions for data exchange settings with target dependencies, Proceedings of the twenty-sixth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 11-13, 2007, Beijing, China [doi>10.1145/1265530.1265547]
• 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: 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]
• 18: Maurizio Lenzerini, Data integration: a theoretical perspective, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543644]
• 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: Leonid Libkin, Data exchange and incomplete information, Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 26-28, 2006, Chicago, IL, USA [doi>10.1145/1142351.1142360]
• 21: 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]
• 22: Jayant Madhavan , Alon Y. Halevy, Composing mappings among data sources, Proceedings of the 29th international conference on Very large data bases, p.572-583, September 09-12, 2003, Berlin, Germany
• 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: J. Makowsky and Y. Pnueli. Arity and alternation in second-order logic. APAL, 78 (1996), 189--202.
• 25: 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]
• 26: Alan Nash , Philip A. Bernstein , Sergey Melnik, Composition of mappings given by embedded dependencies, ACM Transactions on Database Systems (TODS), v.32 n.1, p.4-es, March 2007 [doi>10.1145/1206049.1206053]
• 27: Lucian Popa , Yannis Velegrakis , Mauricio A. Hernández , Renée J. Miller , Ronald Fagin, Translating web data, Proceedings of the 28th international conference on Very Large Data Bases, p.598-609, August 20-23, 2002, Hong Kong, China
• 28: R. Reiter. On closed world databases. In Logic and Databases, Plenum Press, 1978, pages 55--76.

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.4 Systems
          Subjects: Relational databases; Query processing

General Terms:
Languages, Theory

Keywords:
closed world assumption, data exchange, incomplete information, open world assumption, schema mappings