Ronald Fagin
Phokion G. Kolaitis
ABSTRACT
Schema mappings are high-level specifications that describe the relationship between two database schemas. Two operators on schema mappings, namely the composition operator and the inverse operator, are regarded as especially important. Progress on the study of the inverse operator was not made until very recently, as even finding the exact semantics of this operator turned out to be a fairly delicate task. Furthermore, this notion is rather restrictive, since it is rare that a schema mapping possesses an inverse.
In this paper, we introduce and study the notion of a quasi-inverse of a schema mapping. This notion is a principled relaxation of the notion of an inverse of a schema mapping; intuitively, it is obtained from the notion of an inverse by not differentiating between instances that are equivalent for data-exchange purposes. For schema mappings specified by source-to-target tuple-generating dependencies (s-t tgds), we give a necessary and sufficient combinatorial condition for the existence of a quasi-inverse, and then use this condition to obtain both positive and negative results about the existence of quasi-inverses. In particular, we show that every LAV (local-as-view) schema mappinghas a quasi-inverse, but that there are schema mappings specified by full s-t tgds that have no quasi-inverse. After this, we study the language needed to express quasi-inverses of schema mappings specifiedby s-t tgds, and we obtain a complete characterization. We also characterize the language needed to express inverses of schema mappings, and thereby solve a problem left open in the earlier study of the inverse operator. Finally, we show that quasi-inverses can be used in many cases to recover the data that was exported by the original schemamapping when performing data exchange.
- P. A. Bernstein. Applying Model Management to Classical Meta-Data Problems. In Conference on Innovative Data Systems Research (CIDR), pages 209--220, 2003.Google Scholar
- A. Deutsch and V. Tannen. Optimization Properties for Classes of Conjunctive Regular Path Queries. In International Workshop on Database Programming Languages (DBPL), pages 21--39, 2001. Google ScholarDigital Library
- R. Fagin. Inverting Schema Mappings. In ACM Symposium on Principles of Database Systems (PODS), pages 50--59, 2006. Google ScholarDigital Library
- R. Fagin, P. G. Kolaitis, R. J. Miller, and L. Popa. Data Exchange: Semantics and Query Answering. Theoretical Computer Science (TCS), 336(1):89--124, 2005. Google ScholarCross Ref
- R. Fagin, P. G. Kolaitis, L. Popa, and W. -C. Tan. Composing Schema Mappings: Second-order Dependencies to the Rescue. ACM Transactions on Database Systems (TODS), 30(4):994--1055, 2005. Google ScholarDigital Library
- P. G. Kolaitis. Schema Mappings, Data Exchange, and Metadata Management. In ACM Symposium on Principles of Database Systems (PODS), pages 61--75, 2005. Google ScholarDigital Library
- M. Lenzerini. Data Integration: A Theoretical Perspective. In ACM Symposium on Principles of Database Systems (PODS), pages 233--246, 2002. Google ScholarDigital Library
- J. Madhavan and A. Y. Halevy. Composing Mappings Among Data Sources. In International Conference on Very Large Data Bases (VLDB), pages 572--583, 2003. Google ScholarDigital Library
- S. Melnik. Generic Model Management: Concepts and Algorithms, volume 2967 of Lecture Notes in Computer Science. Springer, 2004. Google ScholarDigital Library
- A. Nash, P. A. Bernstein, and S. Melnik. Composition of Mappings Given by Embedded Dependencies. In ACM Symposium on Principles of Database Systems (PODS), pages 172--183, 2005. Google ScholarDigital Library
Index Terms
- Quasi-inverses of schema mappings
Recommendations
Quasi-inverses of schema mappings
Schema mappings are high-level specifications that describe the relationship between two database schemas. Two operators on schema mappings, namely the composition operator and the inverse operator, are regarded as especially important. Progress on the ...
Inverting schema mappings
PODS '06: Proceedings of the twenty-fifth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systemsA schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). Although the notion of an inverse of a schema mapping is ...
Composing schema mappings: Second-order dependencies to the rescue
Special Issue: SIGMOD/PODS 2004A schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). A fundamental problem is composing schema mappings: given ...
Comments