On the Tradeoff between Mapping and Querying Power in XML Data Exchange
Authors
- Shunichi Amano (Univ of Edinburgh, UK)
- Claire David (University of Edinburgh, UK)
- Leonid Libkin (University of Edinburgh, UK)
- Filip Murlak (, )
Abstract
In XML data exchange, a schema mapping specifies rules for restructuring a source document under the target schema, and queries over the target document must be answered in a way consistent with the source information. Mapping rules and queries in this scenario are typically based on various kinds of tree patterns. Patterns with downward navigation have been studied, and tractable classes of mappings and queries have been isolated.
In this paper we extend schema mappings and queries with general tree patterns that include horizontal navigation and data-value comparisons, and study their impact on the tractability of the query answering problem. Our main results state that, in the nutshell, extending the tractable cases for downward patterns with expressive schema mappings is harmless, but adding new features to queries quickly leads to intractability even for very simple schema mapping.
Session
ICDT Research Session 4: Data Exchange 1 (Wednesday, March 24, 11:00—12:30)