Mos oDEx: A ool o exchange RDF da a using exchange
samples
Ca los R. Ri e o, Inma He nández, Da id Ruiz , Ra ael Co chuelo
a Uni e si y o Idaho, 875 Pe ime e D i e, MS 1010, Moscow, ID 83844-1010, Uni ed S a es
b Uni e sidad Au onoma de Chile, C/ Ca los An unez, 1920 San iago, Chile
c Uni e si y o Se illa, ETSI In o má ica, A da. Reina Me cedes s/n, Se illa E-41012, Spain
Keywo ds:
Da a exchange
RDF
Schema mappings
a b s a c
The Web is e ol ing in o a Web o Da a in which RDF da a a e becoming pe asi e, and i is o ganised
in o da ase s ha sha e a common pu pose bu ha e been de eloped in isola ion. This mo i a es he need
o de ise complex in eg a ion asks, which a e usually pe o med using schema mappings; gene a ing
hem au oma ically is appealing o elie e use s om he bu den o handc a ing hem. Many ools a e
based on he da a models o be in eg a ed: classes, p ope ies, and cons ain s. Un o una ely, many da a
models in he Web o Da a comp ise e y ew o no cons ain s a all, so elying on cons ain s o gene a e
schema mappings is no appealing. O he ools ely on handc a ing he schema mappings, which is no
appealing a all. A ew o he ools ely on exchange samples bu equi e use in e en ion, o a e hyb id
and equi e cons ain s o be a ailable. In his a icle, we p esen Mos oDEx, a ool o gene a e schema
mappings be ween wo RDF da ase s. I uses a single exchange sample and a se o co espondences, bu
does no equi e any cons ain s o be a ailable o any use in e en ion. We alida ed and e alua ed
Mos oDEx using many expe imen s ha p o e i s e ec i eness and e ficiency in p ac ice.
1. In oduc ion
The cu en Web is p og essi ely e ol ing in o a Web o Da a
in which RDF (Resou ce Desc ip ion F amewo k) da a a e becom-
ing pe asi e (Hea h and Bize , 2011). The e a e housands o
da ase s a ailable, many o which sha e a common pu pose bu
ha e been de eloped by independen o ganisa ions in isola ion
(Bize e al., 2009). The e a e many ini ia i es whose goal is o link
hese da ase s, which is he fi s s ep o pe o m complex in eg a-
ion p ocesses (Hea h and Bize , 2011).
In eg a ion usually e e s o se e al c ucial asks, such as da a
in eg a ion (Lenze ini, 2002), da a wa ehousing (Ma ileo e al.,
2012), model e olu ion (Flou is e al., 2008), model ma ching
(Sh aiko and Euzena , 2013), eco d linkage (Wang e al., 2013),
o da a exchange (Fagin e al., 2005). In his a icle, we ocus on he
la e , whose goal is o popula e a a ge da ase using da a ha
come om one o mo e sou ce da ase s. Da a exchange has been
paid much a en ion in he da abase con ex , i.e., ela ional, nes ed-
ela ional, o XML (A enas and Libkin, 2008; Fagin e al., 2005; Popa
e al., 2002). Fu he mo e, he eme gence o RDF is mo i a ing some
∗Co esponding au ho . Tel.: +1 2088856592.
au ho s o wo k on da a exchange in he con ex o he Web o Da a
(Ba celó e al., 2013; Pa ei as e al., 2008; Ri e o e al., 2013b).
Da a exchange is pe o med by means o schema mappings,
which a e decla a i e specifica ions o he ela ionships amongs
a sou ce and a a ge da ase s (Alexe e al., 2011a). Gene a ing
schema mappings au oma ically is appealing because his elie es
use s om he bu den o handc a ing hem, so esea che s ha e
ocused on helping use s gene a e hem (Qian e al., 2012). Many
cu en ools a e based on he da a models o be in eg a ed (Haas
e al., 2005; Boni a i e al., 2005; Ra fio e al., 2008; Mecca e al.,
2009; Ma ne e e al., 2011; Ri e o e al., 2013c). By da a model,
we e e o a se s o en i ies ( ha is, classes and p ope ies) and a
se o cons ain s ha desc ibe addi ional ea u es o en i ies ( o
ins ance, class Ais a specialisa ion o class B, p ope y Phas class
Cas i s domain, and so on). In he Web o Da a, he e a e many
da a models ha comp ise e y ew o no cons ain s a all, which
ypically esul s in da a models ha me ely speci y se o en i ies
(Lausen e al., 2008; Hea h and Bize , 2011). The e o e, elying on
da a models wi h cons ain s o gene a e schema mappings is no
appealing in he gene al con ex o he Web o Da a.
The e exis o he ools ha do no ely on da a models. Un o u-
na ely, hey ely on handc a ing he schema mappings (Mocan and
Cimpian, 2007; Maedche e al., 2002; Pa ei as e al., 2008; Bize
and Schul z, 2010; Dou e al., 2005; Ressle e al., 2007), which is
no appealing a all; and a ew o he s ely on exchange samples
(Alexe e al., 2008, 2006, 2011b; Qian e al., 2012), which make
E-mail add esses: [email p o ec ed] (C.R. Ri e o), [email p o ec ed]
(I. He nández), [email p o ec ed] (D. Ruiz), [email p o ec ed] (R. Co chuelo).
hem mo e appealing, bu equi e use in e en ion, o a e hyb id
and equi e cons ain s o be a ailable. No e ha an exchange sam-
ple is an example o sou ce da a and how i is exchanged in o a ge
da a.
In his a icle, we p esen Mos oDEx,1a ool o au oma ically
gene a e schema mappings be ween wo RDF da ase s using a
single exchange sample and a se o n:mco espondences. An
exchange sample comp ises a subse o sou ce da a and a subse
o a ge da a ha is he expec ed esul o exchanging he sou ce
da a. Co espondences a e hin s ha speci y which en i ies in he
sou ce and a ge da ase s co espond o each o he , i.e., a e some-
wha ela ed (Bellahsene e al., 2011). These schema mappings can
be easily ans o med in o SPARQL que ies.
Ou ool does no ely on cons ain s o he sou ce and a -
ge da a models and does no equi e any use in e en ion, no
e en o epai he inpu exchange sample. We ha e alida ed ou
ool using en da a exchange p oblems amongs a ious eal-wo ld
da ase s. In ou alida ion, he execu ion ime ne e exceeded one
second, and he da a exchanged we e as expec ed by expe s in
e e y case, which sugges s ha i is e y e ficien in p ac ice and
ha he gene a ed schema mappings a e app op ia e. Addi ionally,
we ha e e alua ed he pe o mance o ou ool when da a exchange
p oblems scale. We used ou syn he ic da a exchange pa e ns p o-
posed by Mos oBM (Ri e o e al., 2013a), a benchma k o es ing
da a exchange p oposals in he con ex o he Web o Da a. We
ins an ia ed he syn he ic da a exchange pa e ns in o 2000 non-
i ial da a exchange p oblems ha we used o e alua e ou ool.
Ou e alua ion esul s sugges ha ou ool wo ks well as he da a
exchange p oblems scale.
The es o he a icle is o ganised as ollows: Sec ion 2p esen s
he ools ela ed o Mos oDExand i smain con ibu ions o hes a e
o he a ; Sec ion 3p esen s some p elimina ies ha a e necessa y
o unde s and he in e nal de ails o ou ool; Sec ion 4desc ibes
how ou ool wo ks; Sec ion 5 epo s on he alidi y and scalabili y
e alua ion o Mos oDEx; and, finally, Sec ion 6 ecaps on ou main
conclusions.
2. Rela ed wo k
In his sec ion, we p esen o he exis ing ools ha a e ela ed
o Mos oDEx. We p esen some ools ha equi e he use o hand-
c a he schema mappings in Sec ion 2.1, o he s a e based on he
cons ain s ha comp ise he sou ce and a ge da a models o be
in eg a ed in Sec ion 2.2, and a las g oup o ools a e based on
samples o da a o pe o m da a exchange in Sec ion 2.3. Finally,
we analyse and discuss he d awbacks o hese ools in Sec ion 2.4,
which mo i a ed us o wo k on a new p oposal.
2.1. Handc a -based ools
The e a e a numbe o ools ha ocus on handc a ing schema
mappings, which a e exp essed as que ies bu can be iewed
as implici ly gene a ing schema mappings: WSEE (Mocan and
Cimpian, 2007), which s ands o he Web Se ices Execu ion
En i onmen , builds on a o mal amewo k o desc ibe co e-
spondences in e ms o fi s -o de logic o mulae ha a e used o
gene a e schema mappings using he Web Se ice Modeling Lan-
guage (WSML). This ool ocuses on he p oblem o da a exchange
in he con ex o seman ic-web se ices, i.e., web se ices ha a e
en iched wi h seman ic anno a ions o imp o e hei disco e y
and composi ion (Fo e e al., 2008). This ool is simila in spi i
o MAFRA (Maedche e al., 2002) (MApping FRAmewo k), whose
1A echnical epo and a esea ch p o o ypea e a ailablesomewhe e else(Ri e o
e al., 2013, 2013).
ocus is on modelling co espondences in a gene al-pu pose se -
ing. The main di e ence wi h he p e ious ool is ha WSEE goes a
s ep beyond o malising co espondences and execu es hem using
aWSML easone o exchange da a.
MBOTL (Pa ei as e al., 2008) (Model-Based On ology T ans-
la ion Language) builds on he amewo k o Model-D i en
Enginee ing in which he ATL (ATLAS T ans o ma ion Language)
me amodel is ex ended o suppo RDF da a models, which allows
o exp ess cons ain s on hem using OCL (Objec Cons ain Lan-
guage). MBOTL comp ises a mapping language by means o which
use s can exp ess schema mappings ha a e la e ans o med in o
he SPARQL que y language by means o a lib a y o ATL ans o ma-
ions. This is simila in spi i o R2R (Bize and Schul z, 2010) (RDF
o RDF), On oMe ge (Dou e al., 2005), and Snoogle (Ressle e al.,
2007), he di e ence is he language used o ep esen he schema
mappings: R2R and Snoogle use SPARQL 1.0; whe eas On oMe ge
uses Web-PDDL schema mappings ha a e un by means o a fi s -
o de logic easone .
2.2. Cons ain -based ools
They ocus on gene a ing schema mappings building on co e-
spondences and cons ain s on he sou ce and a ge da a models.
These ools a e able o compu e subse s o da a in he sou ce da ase
ha need o be exchanged as a whole, and subse s o da a in he
a ge da ase ha need o be c ea ed as a whole (Ri e o e al.,
2013b). To compu e hem, hey ely on use -defined cons ain s
and he inhe en cons ain s o ce ain da a models, such as pa hs
om he oo o a lea in a nes ed- ela ional da a model, o hie a -
chy ela ions amongs classes in an RDF da a model. Then, se e al
combina ions o hese subse s o da a a e used o gene a e he final
schema mappings (Popa e al., 2002).
Clio (Haas e al., 2005) is he s a e-o - he-a ool in his field. I
akes a sou ce and a a ge nes ed- ela ional da a models, a numbe
o cons ain s o each da a model, and a numbe o 1 : 1 co espon-
dences be ween hem as inpu , and i gene a es schema mappings
ha can be easily ans o med in o di e en que y languages, such
as XQue y, XSLT, o SQL. HePToX (Boni a i e al., 2005) is simila
o Clio bu i ocuses on XML da a models, which a e a supe se
o nes ed- ela ional da a models. Clip (Ra fio e al., 2008) allows
o gene a e schema mappings based on n:1 co espondences, and
i uses a mapping isual language ha was specifically designed
o nes ed- ela ional da a models, which includes g ouping unc-
ions,agg ega ion unc ions, o dependen co espondences.+Spicy
(Mecca e al., 2009) allows o compu e co e schema mappings
ha gene a e non- edundan a ge da a when pe o ming da a
exchange.++Spicy (Ma ne ee al.,2011) imp o es+Spicy byallow-
ing mo e exp essi e a ge cons ain s. Mos oDE (Ri e o e al.,
2013c) is able o wo k wi h RDF da a models whose cons ain s a e
in e p e ed as g aphs ha a e a e sed o compu e sou ce and a -
ge ke nels. A ke nel comp ises a subse o he sou ce da a model
ha needs o be exchanged as a whole, and a subse o he a -
ge da a model ha needs o be c ea ed as a whole. Ke nels a e
ansla ed in o schema mappings ha a e ep esen ed in SPARQL
1.1.
2.3. Sample-based ools
These ools aim o gene a e schema mappings om a se o
exchange samples. In he ela ional o nes ed- ela ional con ex s,
SPIDER (Alexe e al., 2006) helps use s unde s and and main ain
he schema mappings gene a ed by Clio by ex ac ing exchange
samples om he sou ce and a ge da ase s, and i illus a es he
ollowing: (1) ela ionships in a specific schema mapping, (2) sam-
ple sou ce da a ha his schema mapping would ex ac when
pe o ming da a exchange, and (3) he a ge da a gene a ed by
Table 1
Compa ison o ools o gene a e schema mappings.
F1F2F3F4F5F6
Handc a -based ools
Bize and Schul z (2010) X√X X √X
Dou e al. (2005) XXXX√X
Maedche e al. (2002) X X √XXX
Mocan and Cimpian (2007) XXXX√X
Pa ei as e al. (2008) X√X X √X
Ressle e al. (2007) X√X X √X
Cons ain -based ools
Boni a i e al. (2005) √XXX√X
Haas e al. (2005) √XXX√ √
Ma ne e e al. (2011) √XXX√ √
Mecca e al. (2009) √XXX√X
Ra fio e al. (2008) XXXX√X
Ri e o e al. (2013c) √XXX√ √
Sample-based ools
Alexe e al. (2011b) X√XXXX
Alexe e al. (2008) √XXXXX
Alexe e al. (2006) √XXXXX
Qian e al. (2012) √XXXXX
Mos oDEx √√√√√√
hose sou ce da a. Muse (Alexe e al., 2008) aids use s in gene -
a ing and unde s anding schema mappings building on exchange
samples. I assumes ha sou ce and a ge da a models, oge he
wi h hei cons ain s, exis , and i in e s g ouping unc ions by
analysing he answe s o some ques ions i poses o he use s.
EIRENE (Alexe e al., 2011b) gene a es a numbe o schema
mappings by means o a fini e se o exchange samples. This ool
compu es whe he o no wo inpu exchange samples ha e inco-
he ences om a s uc u al poin o iew, i.e., whe he o no hese
wo exchange samples gene a e schema mappings ha will esul
in e oneous a ge da a. I he inpu se o exchange samples does
no ha e any incohe ences, hen i gene a es he schema mappings.
MWea e (Qian e al., 2012) is based on exchange samples and
i ocuses on a ge da a only. Use s a e esponsible o p o iding
he a ge da a ha hey wish o be c ea ed; hen, e e y piece o
da a ha appea s in bo h sou ce and a ge da a ep esen s a co e-
spondence be ween wo en i ies. Co espondences and sou ce and
a ge cons ain s a e used o gene a e schema mappings.
2.4. Discussion
Table 1 summa ises he compa ison o cu en ools o gene a e
schema mappings. The √symbol deno es ha he ool suppo s
a ea u e, and symbol ×implies ha he ool does no suppo a
ea u e. The ea u es we ha e analysed a e he ollowing: (1) F1
de e mines i a ool equi es he in e en ion o he use du ing
he gene a ion o he schema mappings; (2) F2de e mines i a ool
equi es he exis ence o sou ce and a ge cons ain s o gene -
a e he schema mappings; (3) F3de e mines i a ool allows n:m
co espondences; (4) F4de e mines i a ool pe o ms au oma ic
comple ions when he same sou ce da a lead o di e en a ge
da a; (5) F5de e mines i a ool has been es ed wi h eal-wo ld
scena ios; (6) F6de e mines i he scalabili y o a ool has been
es ed.
Rega ding handc a -based ools (Mocan and Cimpian, 2007;
Maedche e al., 2002; Pa ei as e al., 2008; Bize and Schul z, 2010;
Dou e al., 2005; Ressle e al., 2007), hey ocus on handc a ing
schema mappings, which is no appealing since use s ha e o w i e
hem, check whe he hey wo k as expec ed o no , make changes
i necessa y, and es a his cycle (Pe opoulos e al., 2007). Con-
a ily, ou ool au oma ically gene a es schema mappings wi hou
he in e en ion o he use , and i uses a single exchange sample
and a numbe o co espondences as inpu .
Rega ding cons ain -based ools (Haas e al., 2005; Boni a i
e al., 2005; Ra fio e al., 2008; Mecca e al., 2009; Ma ne e e al.,
2011; Ri e o e al., 2013c), hey a e no so appealing in he gene al
con ex o he Web o Da a because (Hea h and Bize , 2011): (1) he
main di e ence be ween RDF and o he da a modelling languages
is ha i allows o ep esen da a wi hou an explici da a model;
(2) i is no possible o model he whole Web o Da a wi h a single
da a model, and se e al da a models may exis o he same RDF
da ase ; (3) da a models in his con ex usually comp ise e y ew
cons ain s o no cons ain s a all, which en ails ha hey a e only
simple ocabula ies o c ea e web da a. Con a ily, ou ool does
no ely on cons ain s bu on a single exchange sample and a se
o co espondences.
Some sample-based ools assume ha sou ce and a ge da a
models exis , oge he wi h hei cons ain s (Alexe e al., 2008,
2006; Qian e al., 2012). The e o e, hei main d awback, as in he
p e ious case, is ha i is no appealing o ely on sou ce and a ge
da a models, oge he wi h hei cons ain s, in he gene al con ex
o he Web o Da a. Finally, EIRENE (Alexe e al., 2011b) does no
ha e he p e ious d awback, bu i equi es he use o p o ide
an exchange sample o each schema mapping o be au oma i-
cally gene a ed. Fu he mo e, i his ool finds he inpu exchange
samples inapp op ia e o gene a e schema mappings, he use is
esponsible o epai ing hem. Con a ily, ou ool equi es he use
o p o ide a single exchange sample and a se o co espondences
and finds epai s au oma ically.
Finally, when dealing wi h la ge RDF da ase s, a key ea u e o
hese ools is hei scalabili y (Fe nández e al., 2013). Tes ing he
scalabili y o hese ools is challenging since i equi es o collec
su ficien ly la ge da ase s, and o p o ide he inpu da a o he ools
and he expec ed ou pu o alida e hem. Cu en ly, his can be a
daun ing ask since, o he bes o ou knowledge, he e a e no any
ools o help use s pe o m his alida ion. Fu he mo e, mos o
hese ools a e esea ch p o o ypes, he e o e, i is no likely ha
hey ake scalabili y issues in o accoun . We ha e analysed he scal-
abili y o ou ool using syn he ic da a exchange p oblems ha a e
gene a ed wi h he help o Mos oBM (Ri e o e al., 2013a), and we
epo on ou esul s in Sec ion 5.2.
3. P elimina ies
In his sec ion, we p esen some p elimina ies ha a e neces-
sa y o unde s and ou ool. We ini ially in oduce ou esea ch
me hodology in Sec ion 3.1. A e wa ds, ou ool elies on a concep-
ual model ha is p esen ed in Sec ion 3.2. Fu he mo e, Sec ion 3.3
desc ibes he unning example ha we use o illus a e i h ough-
ou his a icle.
3.1. Resea ch me hodology
Ou esea ch me hodology is based on he Unified P ocess
amewo k, aka UP (K uch en, 2003). This choice is suppo ed by
he expe ience o ou esea ch g oup in applying i o esea ch o
echnology ans e . The p oposed li e cycle in UP is i e a i e and
inc emen al, which is sui able o he de elopmen o high dynamic
so wa e p ojec s o scien ific publica ions in his a ea.
I comp ises he ollowing s eps:
1. Iden i ying esea ch con ex : p e ious o his piece o esea ch
wo k, we iden ified ha exchanging da a amongs RDF da ase s
was an in e es ing opic and decided o ocus on he au o-
ma ic gene a ion o schema mappings. In Mos oDE (Ri e o e al.,
2013c), we s udied his au oma ic gene a ion based on sou ce
and a ge cons ain s. In his a icle, ou ocus consis s on gen-
e a ing hem au oma ically using exchange samples.
2. Sys ema ic e iew o he bibliog aphy: we upda ed he e e -
ences ha we iden ified when analysing he bibliog aphy o
ou Mos oDE a icle.
3. Iden i ying compa ison ea u es: we iden ified hose ea u es
ha a e common o exis ing ools in ou esea ch con ex . These
ea u es a e desc ibed in Sec ion 2.4.
4. Iden i ying d awbacks: using he p e ious ea u es, we analysed
exis ing ools in he bibliog aphy ega ding whe he hey ha e
hese ea u es o no . The conclusion was ha , o he bes o ou
knowledge, no ool has all o he ea u es.
5. Design and implemen a ion o ou ool: we de ised Mos oDEx
o ake all o he iden ified ea u es in o accoun .
6. Design o he expe imen s: e e y ool should be es ed using
eal-wo ld scena ios o e alua e i s e ec i eness and e ficiency.
Fu he mo e, i is manda o y o e alua e i s scalabili y. We
de ised 10 eal-wo ld da a exchange p oblems o es ou ool
(see Sec ion 5.1), and 2000 syn he ic da a exchange p oblems o
e alua e i s scalabili y (see Sec ion 5.2).
3.2. Concep ual model
An RDF da ase comp ises a se o iples, each o which is a
h ee- uple whose componen s, which a e called subjec , p edica e,
and objec , can be URIs (Uni o m Resou ce Iden ifie ) and li e als o
simple ypes. A schema mapping is a wo- uple whose componen s
a e se s o iple pa e ns ha a e implici ly connec ed using logical
ANDs. A iple pa e n gene alises he concep o iple by allow-
ing he subjec and/o he objec o be a iables o blank nodes. In
his a icle, we e e o iple pa e ns as pa e ns o he sake o
b e i y. Schema mappings may be easily ans o med in o SPARQL
que ies in which he wo se s o pa e ns o m he WHERE and he
CONSTRUCT clauses, espec i ely. No e ha he se o iple pa -
e ns includes he se o iples; ha is why we usually use he
e m pa e n o e e o bo h iple pa e ns and iples.
A homomo phism maps he cons an s, a iables, o blank
nodes o a se o pa e ns on o he cons an s, a iables, o blank
nodes o ano he se o pa e ns. Homomo phisms can be ei he
eplacemen s o subs i u ions: a eplacemen is a fini e map om
cons an s o cons an s and a subs i u ion is a fini e map om con-
s an s o a iables o blank nodes.
Rega ding ou ool, we es ic ou a en ion o he iples ha
desc ibe da a, ha is, iples o he o m (c, d : ype,C), in which
cis a cons an and Cis a class, o (c1,p,c2), in which c1and c2
a e cons an s and pis a p ope y. An exchange sample comp ises a
sou ce da ase and a a ge da ase . An n:mco espondence ela es
a se o en i ies wi h a di e en se o en i ies. A da a exchange
p oblem comp ises a single exchange sample and a se o co e-
spondences ha ela e some o he sou ce en i ies wi h some o
he a ge en i ies.
Ou algo i hms use he ollowing p ojec ion unc ions: sou ce
o ge he sou ce da ase o an exchange sample, he sou ce en i-
ies o a gi en co espondence, o he sou ce iples o a gi en
da ase ; a ge o ge he a ge da ase o an exchange sample,
he a ge en i ies o a gi en co espondence, o he a ge iples
o a gi en da ase ; sample and co espondences o ge he single
exchange sample o he co espondences o a da a exchange p ob-
lem, espec i ely; and cons an s o ge he cons an s in a se o
pa e ns.
Fig. 1 p esen s an UML-like concep ual model, in which a
Da aExchangeP oblem comp ises a sou ce RDFDa ase ( he sou ce
exchange sample), a a ge RDFDa ase ( he a ge exchange sam-
ple), and a numbe o Co espondences. Each Co espondence has a
numbe o sou ce and a ge En i ies, each o which is ep esen ed
by a URI and can be ei he a Class,Da aP ope y o Objec P ope y.
An RDFDa ase comp ises a se o Pa e ns, each o which is a iple
ha con ains a subjec , a p edica e and an objec Nodes. A Node can
Fig. 1. Concep ual model.
be ei he a URI, a Li e al o a Va iable. A SchemaMapping comp ises
a se o sou ce and a ge Pa e ns. Finally, a Homomo phism can be
ei he a Replacemen o a Subs i u ion ha maps o a se o Nodes.
3.3. Running example
Figs. 2 and 3 p esen a eal-wo ld da a exchange p oblem ha
we use o illus a e ou ool. Ou goal is o gene a e a numbe o
schema mappings o pe o m da a exchange om a pa o DBpedia
3.8 o a pa o Go WILD. On he one hand, DBpedia (Bize e al.,
2009) is a communi y e o o anno a e and make he da a s o ed a
Wikipedia accessible by means o RDF echnologies. On he o he
hand, Go WILD (Böhm e al., 2012) is a public RDF da ase ha
comp ises da a om US and EU go e nmen s ha a e connec ed
wi h financial da a o go e nmen s o public unds.
The exchange sample in Fig. 2 comp ises a se o sou ce iples
ega ding Angela Me kel and Da id Came on, hei names, and he
da e o bi h; and a se o a ge iples ha speci y how hese da a
a e s uc u ed acco ding o he a ge en i ies. This exchange sam-
ple is ep esen ed using a ee-based g aphical no a ion in which
each oo node is he subjec o a iple, and iples a e g ouped by
subjec . A URI o a blank node is ep esen ed using a diamond, a
li e al using a apezium, a da a p ope y using a squa e, and an
Fig. 2. Running example: exchange sample.
Fig. 3. Running example: co espondences.
Table 2
Summa y o p efixes.
P efix URI
:h p://dbpedia.o g/ esou ce/
d h p://www.w3.o g/1999/02/22- d -syn ax-ns#
d s h p://www.w3.o g/2000/01/ d -schema#
oa h p://xmlns.com/ oa /0.1/
dpo h p://dbpedia.o g/on ology/
gw h p://go wild.o g/0.6/GWOn ology. d #
gwd h p://go wild.o g/id/da e/
objec p ope y using a pen agon. We use he p efixes in Table 2,
in which he fi s ow specifies he de aul URI.
Fig. 3 shows h ee co espondences, namely: 1 ela es a pe son
in he DBpedia and he Go WILD da ase s; 2s a es ha he name
o a pe son in DBpedia is ela ed o he label in Go WILD; and 3
indica es ha a pe son and he /hisda e o bi h inDBpedia is ela ed
o a new URI o class gw:Da e in Go WILD. Co espondences a e
ep esen ed using a ee-based g aphical no a ion in which each
oo node is an en i y, which is ep esen ed using a ci cle, a squa e,
o a pen agon i i is a class, a da a p ope y, o an objec p ope y,
espec i ely.
4. Gene a ing schema mappings
Ou ool akes a da a exchange p oblem as inpu , which com-
p ises a single exchange sample and a se o co espondences. The
single exchange sample is expec ed o be an equi alen sample o
he sou ce and a ge da a ha he use wishes o exchange. Fu -
he mo e, ou ool akes a numbe o n:mco espondences o e
he sou ce and a ge en i ies as inpu . This se indica es he ela-
ionships ha exis amongs he sou ce and a ge en i ies in he
Fig. 5. Gene a ing schema mappings.
da a exchange p oblem ha we wish o sol e. I is expec ed ha he
use has o ela e he sou ce en i ies ha should be exchanged as a
whole, and he a ge en i ies ha need o be c ea ed as a whole.
Ou ool gene a es a numbe o schema mappings o exchange
da a be ween he sou ce and a ge da ase s. Fig. 4 p esen s an
o e iew o ou echnique o gene a e schema mappings ha com-
p ises fi e s eps, namely: (1) “Gene a e exchange samples” akes a
single exchange sample and a numbe o co espondences as inpu ,
and au oma ically gene a es a se o candida e exchange samples.
(2) “Disca d exchange samples” disca ds p e iously gene a ed can-
dida e exchange samples ha a e no use ul o gene a e he final
se o schema mappings. (3) “Comple e exchange samples” adds
a ge da a o he di e en exchange samples i he same sou ce
da a can lead o di e en a ge da a. (4) “P une exchange samples”
emo es exchange samples ha gene a e he same schema map-
pings. (5) “C ea e schema mappings” ans o ms each exchange
sample in o a schema mapping. Fig. 5 p esen s he main algo i hm
ha implemen s such wo kflow. In ou algo i hms, we use he
ollowing con ol s uc u es: o each,i , and while; he ollowing
logical connec i es: nega ion (¬), and (∧), o (∨); he ollowing se
ope a o s: cons uc o ({...}), union (∪), in e sec ion (∩), a fini e
powe se (F). Fu he mo e, we also use he coun ope a o (|...|)
and a mapping unc ion (→).
These s eps a e explained in he es o his sec ion.
4.1. Fi s s ep
This s ep au oma ically compu es a numbe o candida e
exchange samples, each o which comp ises a subse o sou ce da a
ha need o be exchanged as a whole, and a subse o a ge da a
ha need o be c ea ed as a whole. To compu e hem, o each co -
espondence in isola ion, we combine all o he pieces o connec ed
da a ha con ain he en i ies in he co espondence.
Fig. 4. O e iew o ou schema mapping gene a ion p ocess.

Fig. 6. Gene a ing candida e exchange samples.
Fig. 6 shows ou algo i hm o gene a e candida e exchange sam-
ples om a gi en co espondence and a single exchange sample.
Fi s , we compu e he iples ela ed o co espondence o he
single exchange sample d, i.e., he iples ha comp ise he en i ies
ela ed by . They a e s o ed in a se o da ase s. Then, we com-
pu e he dis ibu i e ca esian p oduc o bo h he iples ela ed o
sou ce( ) and he iples ela ed o a ge ( ), which is deno ed as .
We i e a e o e each se o sou ce and a ge da ase s, and we ans-
o m hem in o exchange samples only i each da ase comp ises a
unique connec ed componen .
Example 1. To illus a e his s ep, we ocus on co espondence
2in ou unning example. I s sou ce en i ies a e dpo: Pe son and
oa :name. The iples ha comp ise dpo:Pe son a e he ollowing:
( 1) : Angela Me kel d : ype dpo :Pe son
( 2) : Da id Came on d : ype dpo :Pe son
and he iples ha comp ise oa :name a e he ollowing:
( 3) : Angela Me kel oa :name “Angela Me kel
( 4) : Da id Came on oa :name “Da id Came on
The compu eRela edT iples algo i hm ou pu s he ollowing se
in his case:GS={{ 1, 2},{ 3, 4}}; he dis ibu i e ca esian p oduc
o GSis GS={{ 1, 3},{ 1, 4},{ 2, 3},{ 2, 4}}.
The a ge en i y o 2is d s:label, and he iples ha comp ise
i a e he ollowing:
( 5) : Angela Me kel d s :label “Angela Me kel
( 6) : Da id Came on d s :label “Da id Came on
( 7)gwd : 1954 −7−17 d s :label “1954 −07 −17
No e ha GT={{ 5, 6, 7}} =GT. Addi ionally, each o he sub-
se s in {{ 2, 3},{ 1, 4}} ⊆GShas wo connec ed componen s,
since he e is no iple ha does no ha e any iple in com-
mon wi h a leas ano he iple. The e o e, we disca d hese se s
o iples. Candida e exchange samples a e gene a ed by com-
bining he sou ce iples in GSand he a ge iples in GT,
namely: d21 = ({ 1, 3},{ 5}), d22 = ({ 1, 3},{ 6}), d23 = ({ 1, 3},{ 7}),
d24 = ({ 2, 4},{ 5}), d25 = ({ 2, 4},{ 6}), d26 = ({ 2, 4},{ 7}), which
a e depic ed in Fig. 7.
Fig. 7. Exchange samples gene a ed in he fi s s ep o co espondence 2.
4.2. Second s ep
This s ep consis s o disca ding candida e exchange samples ha
a eno use ul o gene a e he finalse o schemamappings. Wekeep
candida e exchange samples in which he e is, a leas , a subse o
a ge da a ha can be gene a ed using he sou ce da a, and we
minimise he a ge da a ha do no exis in he sou ce. The in u-
i ion behind his s ep is ha we keep only he exchange samples
ha p o ide he maximum in o ma ion o gene a e he a ge da a,
i.e., when hese exchange samples a e ans o med in o schema
mappings, hey comp ise as less blank nodes as possible.
Fig. 8 shows ou algo i hm o disca d candida e exchange sam-
ples. An exchange example is kep o disca ded acco ding o i s
Fig. 8. Disca ding candida e exchange samples.
numbe o co e ed and unco e ed cons an s. A cons an in he a -
ge is said o be co e ed i he e is, a leas , a iple in he sou ce
ha in ol es ha cons an ; o he wise, i is said o be unco e ed.
The algo i hm fi s compu es he minimum numbe o unco e ed
cons an s in he inpu se o exchange samples; i hen i e a es o e
his se and disca ds e e y exchange sample ha does no ha e a
leas a co e ed cons an o has mo e unco e ed cons an s han he
minimum.
Example 2. Ou ool gene a es six exchange samples o co e-
spondence 2(see Fig. 7), and he minimum numbe o unco e ed
cons an s in hese exchange samples is equal o ze o, since e e y
cons an in d21 is co e ed; he e o e, ou ool disca ds exchange
samples d22,d23,d24, and d26 in he second s ep because each o
hem has wo unco e ed cons an s::Da id Came on and “Da id
Came on”, gwd:1954-7-17 and “1954-07-17”,:Angela Me kel and
“Angela Me kel”, and gwd:1954-7-17 and “1954-07-17”, espec-
i ely.
Fu he mo e, in Fig. 9, we p esen he schema mappings ha
ou ool ou pu s o co espondence 3o ou unning example.
No e ha he minimum numbe o unco e ed cons an s in hese
exchange samples is equal o one, since gwd:1954-7-17 is no
p esen in he sou ce in any exchange sample. The e o e, ou ool
disca ds d32 since i has wo unco e ed cons an s: gwd:1954-7-17
and “Angela Me kel”.
4.3. Thi d s ep
The hi d s ep consis s o comple ing exchange samples, i.e., i
he same sou ce da a can lead o di e en da a in di e en exchange
samples, i is hen necessa y o comple e hose exchange samples
by adding a ge da a o hem. The e o e, we iden i y he exchange
samples ha ha e he same sou ce da a bu di e in he a ge
da a, and we comple e hem wi hou he use in e en ion. The
comple ion o exchange samples depends on he specifica ion o
he inpu exchange sample. Ou comple ion p ocess is simila o
he p ocess desc ibed in (Alexe e al., 2011a), which p o es ha i
is a sound and comple e p ocess.
The algo i hm in Fig. 10 akes a se o exchange samples as inpu
and ou pu s a numbe o comple e exchange samples. I compu es i
he inpu se needs o be comple ed because he same sou ce da a
gene a es di e en a ge da a. To pe o m his, we compu e he
Fig. 9. Exchange samples gene a ed in he fi s s ep o co espondence 3.
Fig. 10. Comple ing exchange samples.
Fig. 11. Exchange samples o co espondence 1a e he second s ep.
eplacemen s be ween he exchange samples ha ha e he same
sou ce da a and, i hey ha e some missing iples, we au oma ically
add hem o comple e he a ge da a. In his case, es a indica es i
new iples ha e been added o he exchange samples, and we i e -
a e un il no new iple is added. We ex ac wo di e en exchange
samples om he inpu se d1and d2, espec i ely. We compu e
he eplacemen s be ween hei sou ce iples, and we apply each
eplacemen o he a ge iples o d1; i he esul ing iples a e
no p esen in he a ge iples o d2, we ha e o add hem.
Example 3. To illus a e his s ep, we p esen he wo
exchange samples ha esul ed om co espondence 1a e
he second s ep (see Fig. 11). The e exis s a single eplace-
men be ween sou ce(d12) and sou ce(d31) (see Fig. 9), which
is he ollowing: {:Da id Came on →:Angela Me kel}. When
we apply i o a ge (d12), i esul s in he ollowing iple:
:Angela Me kel d : ype gw :Pe son. This iple is no included in
a ge (d31), so i is necessa y o add his iple o a ge (d31), and
he exchange sample is comple ed as d
31, which is depic ed in
Fig. 12. The in ui ion behind his is ha we ha e mapped an ins ance
o dpo :Pe son as gw :Pe son in exchange sample d12; howe e , in
exchange sample d31, an ins ance o dpo:Pe son is no mapped on o
an ins ance o gw :Pe son.
No e also ha Fig. 12 p esen s d
21 and d
25, which esul om
comple ing exchange samples d21 and d25, espec i ely (see Fig. 7).
Ou ool au oma ically comple es he inpu exchange samples,
which is a clea ad an age wi h espec o some o he exis ing
ools in he bibliog aphy ha equi e he in e en ion o he use
o comple e hem (Alexe e al., 2011b).
4.4. Fou h s ep
In his s ep, ou ool p unes edundan exchange samples, i.e.,
samples ha gene a e he same schema mappings. Fig. 13 shows
ou algo i hm o p une hese exchange samples. Replacemen s a e
used o de ec hem, i.e., wo exchange samples d1and d2a e edun-
dan i he e exis , a leas , ou eplacemen s om he sou ce and
a ge iples o d1 o he sou ce and a ge iples o d2, and om
he sou ce and a ge iples o d2 o he sou ce and a ge iples
o d1.
Example 4. In ou unning example, d11 and d12 (see Fig. 11)
a e edundan since he e exis wo eplacemen s om sou ce(d11)
o sou ce(d12) and ice e sa, and wo o he eplacemen s om
a ge (d11) o a ge (d12) and ice e sa. The e o e, ou ool p unes
one o hem andomly, e.g., d11. The same happens wi h exchange
samples d
21 and d
25 (see Fig. 12), ou ool p unes one o hem
andomly, e.g., d
25.
Fig. 12. Comple ed exchange samples.
4.5. Fi h s ep
This final s ep ans o ms each exchange sample in o a schema
mapping, which is buil by subs i u ing he sou ce and a ge con-
s an s by a iables, o blank nodes o gene a e labelled nulls (Fagin
e al., 2005; Mallea e al., 2011). These schema mappings may be
Fig. 13. P uning exchange samples.
Fig. 14. C ea ing schema mappings.
easily ans o med in o SPARQL que ies o exchange da a be ween
he in eg a ed da ase s.
Fig. 14 shows ou algo i hm o ans o m each exchange sample
in o a schema mapping, which is buil by subs i u ing sou ce and
a ge da a by a iables o blank nodes, depending on whe he he
a ge da a is known o no . To pe o m his, o each exchange sam-
ple, we e ie e i s sou ce and a ge cons an s. Then, we compu e
a sou ce and a a ge subs i u ion as ollows: o hose cons an s in
he sou ce, we add a esh a iable o bo h subs i u ions. Fo hose
cons an s ha a e p esen in he a ge bu no in he sou ce, we
add a esh blank node o he a ge subs i u ion. Finally, we apply
bo h subs i u ions o he sou ce and a ge iples o gene a e he
sou ce and a ge pa e ns o he schema mapping.
Example 5. In ou unning example, ou ool gene a es h ee
schema mappings ha esul om ans o ming exchange sam-
ples d12, d
21, and d
31 (see Figs. 11 and 12, espec i ely). Ou
ool ans o ms exchange sample d12 in o schema mapping
m12 by using he ollowing sou ce and a ge subs i u ion:
{:Da id Came on →?u2}. Bo h subs i u ions a e he same
because all o he a ge cons an s a e al eady p esen in he sou ce
subs i u ion; so no blank nodes a e gene a ed.
Fu he mo e, ou ool ans o ms exchange sample d
21
in o schema mapping m21 by compu ing he ollowing
sou ce and a ge subs i u ions: {:Angela Me kel →?u3,
“Angela Me kel →?l4}. No e ha bo h subs i u ions a e also
he same. Ou ool also ans o ms exchange sample d
31 in o
schema mapping m31. I compu es he ollowing sou ce sub-
s i u ion: {:Angela Me kel →?u1, “ 1954 −07 −17 →?l0},
and he ollowing a ge subs i u ion: {:Angela Me kel →?u1,
“ 1954 −07 −17 →?l0, gwd : 1954 −7−17 → :bn0}. The la e
Fig. 15. Final schema mappings.
comp ises a blank node since cons an gwd : 1954 −7−17 is no
p esen in he sou ce.
Fig. 15 depic s schema mappings m12,m21, and m31.
5. E alua ion
Ou ool is suppo ed by a g aphical in e ace ha has been
implemen ed using Ja a 1.6 and Jena TDB 0.9.3 (Ca oll e al., 2004).
Fu he mo e, we ha e used Gua a 13.0.1 o implemen ancilla y se
ope a ions (Google, 2014), and JG aphT 0.8.3 o compu e he con-
nec ed componen s o a se o pa e ns (Na eh, 2014). Ou ool has
a Se up module and fi e addi ional modules, each o which imple-
men s a s ep o ou p oposal, namely: Gene a e, Disca d, Comple e,
P une, and T ans o m.
In he Se up module, he use may selec he files in which he
sou ce and a ge da a o he single exchange sample a e s o ed.
When bo h files a e selec ed, he use is esponsible o p o id-
ing a numbe o n:mco espondences be ween sou ce and a ge
en i ies. The Gene a e module is esponsible o aking he single
exchange sample and he co espondences o he p e ious mod-
ule as inpu , and gene a ing he whole se o candida e exchange
samples. The Disca d module akes he se o candida e exchange
samples as inpu and disca ds exchange samples om his se . The
Comple e module is esponsible o aking he p e ious samples as
inpu and comple ing hem, i.e., i he same sou ce da a gene a e
di e en a ge da a in di e en exchange samples, i is neces-
sa y o comple e hose samples by adding new iples o he a ge
da a. The P une module is esponsible o p uning exchange sam-
ples ha a e edundan , i.e., hey a e ans o med in o he same
schema mappings. Finally, he T ans o m module akes he p e-
ious exchange samples and ans o ms hem in o a numbe o
schema mappings.
Ou expe imen s we e un on a i ual compu e ha was
equipped wi h a ou - h eaded In el Xeon 3.00 GHz CPU and 16 GiB
RAM, unning on Windows Se e 2008 (64-bi s). In he es o
his sec ion, we p esen he alidi y e alua ion in Sec ion 5.1, he