Composition of mappings given by embedded dependencies

ABSTRACT

Composition of mappings between schemas is essential to support schema evolution, data exchange, data integration, and other data management tasks. In many applications, mappings are given by embedded dependencies. In this article, we study the issues involved in composing such mappings.

Our algorithms and results extend those of Fagin et al. [2004], who studied the composition of mappings given by several kinds of constraints. In particular, they proved that full source-to-target tuple-generating dependencies (tgds) are closed under composition, but embedded source-to-target tgds are not. They introduced a class of second-order constraints, SO tgds, that is closed under composition and has desirable properties for data exchange.

We study constraints that need not be source-to-target and we concentrate on obtaining (first-order) embedded dependencies. As part of this study, we also consider full dependencies and second-order constraints that arise from Skolemizing embedded dependencies. For each of the three classes of mappings that we study, we provide: (a) an algorithm that attempts to compute the composition; and (b) sufficient conditions on the input mappings which guarantee that the algorithm will succeed.

In addition, we give several negative results. In particular, we show that full and second-order dependencies that are not limited to be source-to-target are not closed under composition (for the latter, under the additional restriction that no new function symbols are introduced). Furthermore, we show that determining whether the composition can be given by these kinds of dependencies is undecidable.

REFERENCES

• 1: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 2: 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
• 3: Bernstein, P. A. 2003. Applying model management to classical meta-data problems. In Proceedings of the Conference on Innovative Data Systems Research (CIDR). 209--220.
• 4: Phillip A. Bernstein , Alon Y. Halevy , Rachel A. Pottinger, A vision for management of complex models, ACM SIGMOD Record, v.29 n.4, p.55-63, Dec. 2000 [doi>10.1145/369275.369289]
• 5: 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
• 6: Ebbinhaus, H.-D. and Flum, J. 1999. Finite Model Theory. Springer Verlag.
• 7: Fagin, R. 1975. Monadic generalized spectra. Zeitschr. Math. Logik Grundlagen Math. 21, 89--96.
• 8: Ronald Fagin, Multivalued dependencies and a new normal form for relational databases, ACM Transactions on Database Systems (TODS), v.2 n.3, p.262-278, Sept. 1977 [doi>10.1145/320557.320571]
• 9: Ronald Fagin, Horn clauses and database dependencies, Journal of the ACM (JACM), v.29 n.4, p.952-985, Oct. 1982 [doi>10.1145/322344.322347]
• 10: Ronald Fagin, Inverting schema mappings, 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.1142359]
• 11: 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
• 12: 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]
• 13: 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]
• 14: 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]
• 15: Halevy, A. Y., Ives, Z. G., Suciu, D., and Tatarinov, I. 2003. Schema mediation in peer data management systems. In Proceedings of the International Conference on Data Engineering (ICDE).
• 16: Anthony Klug , Rod Price, Determining View dependencies using tableaux, ACM Transactions on Database Systems (TODS), v.7 n.3, p.361-380, Sept. 1982 [doi>10.1145/319732.319738]
• 17: Christoph Koch, Query Rewriting with Symmetric Constraints, Proceedings of the Second International Symposium on Foundations of Information and Knowledge Systems, p.130-147, February 20-23, 2002
• 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: Madhavan, J. and Halevy, A. Y. 2003. Composing mappings among data sources. In Proceedings of the International Conference on Very Large Data Bases (VLDB). 572--583.
• 20: Melnik, S. 2004. Generic model management: Concepts and algorithms. Ph.D. Thesis, University of Leipzig. Lecture Notes in Computer Science, vol. 2967. Springer Verlag.
• 21: Sergey Melnik , Philip A. Bernstein , Alon Halevy , Erhard Rahm, Supporting executable mappings in model management, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066177]
• 22: Sergey Melnik , Erhard Rahm , Philip A. Bernstein, Rondo: a programming platform for generic model management, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872782]
• 23: Nicolas, J. M. 1987. First order logic formalization for function, multivalued, and mutual dependencies. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 40--46.
• 24: Yehoshua Sagiv , Mihalis Yannakakis, Equivalences Among Relational Expressions with the Union and Difference Operators, Journal of the ACM (JACM), v.27 n.4, p.633-655, Oct. 1980 [doi>10.1145/322217.322221]
• 25: Michael Sipser, Introduction to the Theory of Computation, International Thomson Publishing, 1996
• 26: Michael Stonebraker, Implementation of integrity constraints and views by query modification, Proceedings of the 1975 ACM SIGMOD international conference on Management of data, May 14-16, 1975, San Jose, California [doi>10.1145/500080.500091]
• 27: Cong Yu , Lucian Popa, Constraint-based XML query rewriting for data integration, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007611]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Management, Theory

Keywords:
Metadata management, database theory