Edinburgh Research Archive >
Informatics, School of >
Informatics thesis and dissertation collection >
Please use this identifier to cite or link to this item:
|Title: ||XML data exchange under expressive mappings|
|Authors: ||Amano, Shun’ichi|
|Supervisor(s): ||Libkin, Leonid|
|Issue Date: ||2009|
|Publisher: ||The University of Edinburgh|
|Abstract: ||Data Exchange is the problem of transforming data in one format (the source schema)
into data in another format (the target schema). Its core component is a schema mapping,
which is a high level specification of how such transformation should be done. Relational
data exchange has been extensively studied, but exchanging XML data have been paid
much less attention. The goal of this thesis is to develop a theory of XML data exchange
with expressive schema mappings, extending a previous work using restricted mappings.
Our mapping language is based on tree patterns that can use horizontal navigation and
data comparison in addition to downward navigation.
First we look at static analysis problems concerning a single mapping. More specif-
ically, we consider consistency problems with different flavours. One such problem, for
instance, asks if any tree has a solution under the given mapping. Then we turn to analyse
the complexity of mapping themselves, i.e., recognising pairs of trees such that the one
is mapped to the other. For both problems, we provide classifications based on sets of
features used in the mappings.
Second we investigate the composition of XML schema mappings. Generally it is hard,
or rather simply impossible, to achieve closure under composition in XML settings unlike
in relational settings. Nevertheless we identify a class of XML schema mappings that is
closed under composition.
Lastly we consider the problem of query answering. It is important to exchange data
so that we can feasibly answer queries while it often leads to intractability. We identify the
dividing line between tractable and intractable cases: answering queries with extended
features is always intractable while tractability of answering simple queries can be retained
in extended mappings.|
|Keywords: ||data exchange|
|Appears in Collections:||Informatics thesis and dissertation collection|
Items in ERA are protected by copyright, with all rights reserved, unless otherwise indicated.