Databases Reference
In-Depth Information
tractable fragment of Description Logics, namely
DL-Lite
[15] can be represented
with Datalog
C
by filling the gap between databases and the Semantic Web. Suitable
fragments of Datalog
C
are embodied by: (1) guarded TGDs (GTGDs); (2) linear
TGDs (LTGDs); (3) (1) or (2) with equation-generating dependencies and negative
constraints. A tgd
is guarded iff it contains an atom in its body that has all univer-
sally quantified variables of
. A subset of GTGDs is represented by LTGDs, iff it
contains only a singleton body atom. If we look at the s-t tgds illustrated in Sect.
2
,
then
m
1
,
m
3
,and
m
4
are LTGDs (and, thus, guarded) and
m
2
is a nonguarded TGD.
The main result of
Cal`ıetal.
[
2009b
] is that query answering with (3) that do not
conflict with the tgds is feasible in polynomial time in the data complexity and thus
is first-order rewritable.
6.3
Distributing Schema Mappings Across Several Sites
We are currently witnessing a substantial interest in distributed database manage-
ment systems, called PDMS that are based on highly decentralized P2P infrastruc-
tures. Such PDMSs might share heterogeneous data and exchange such data in a
seamless fashion.
In Piazza [
Ives et al. 2004
], each peer stores semantic mappings and storage
descriptions. Semantic mappings are equalities or subsumptions between query
expressions, provided in XQuery. Storage descriptions are equalities or subsump-
tions between a query and one or more relations stored on a peer. In Piazza,
semantic mappings are first used to do query rewriting using the MiniCon algo-
rithm [
Pottinger and Halevy 2001
]. When semantic mappings cannot be applied
further, storage descriptions are used to do query reformulation. The result of this
phase is a reformulation of peer relations into stored relations, which can be either
in GAV or in LAV style. Query routing in Piazza requires a centralized index that
stores all the mappings at a global level.
In HePToX [
Bonifati et al. 2005
,
2010
], the exact mapping rules are derived
automatically from correspondences, which are intuitively displayed in a peer-based
GUI. In contrast to Piazza, HePToX is totally decentralized and its scalability is less
than linear (i.e., logarithmic, as in DHT-based systems). Thus, mappings are locally
stored on each peer and used at need when doing query reformulation.
HePToX query rewriting can be done in both directions, along and against
the mappings, leading to forward and backward query translations. The seman-
tics of HePToX's forward query translation is similar to answering queries using
views [
Levy et al. 1995
]. However, HePToX can leverage Skolem functions and
the form of the mapping rules to perform forward translation efficiently. Backward
query translation is totally new and was never defined in other systems.
Orchestra [
Ives et al. 2008
] extends PDMSs for life scientists. It focuses on
provenance, trust, and updates. While it can be extended to XML, it uses the rela-
tional model. Orchestra's mapping rules translate from tgds to Datalog, rather than
HePToX's mapping rules which translate from a visual language to TreeLog. Unlike
HePToX, which supports the user in easily creating the mapping between schemas,
Orchestra relies on other systems to create the initial mappings. Moreover, the Q
