%PDF-1.4
%
5 0 obj
<< /S /GoTo /D (section.1) >>
endobj
8 0 obj
(Introduction)
endobj
9 0 obj
<< /S /GoTo /D (section.2) >>
endobj
12 0 obj
(CDSS Update Exchange)
endobj
13 0 obj
<< /S /GoTo /D (subsection.2.1) >>
endobj
16 0 obj
(Update Translation and Query Answers)
endobj
17 0 obj
<< /S /GoTo /D (subsection.2.2) >>
endobj
20 0 obj
(Trust Policies and Provenance)
endobj
21 0 obj
<< /S /GoTo /D (section.3) >>
endobj
24 0 obj
(Update Exchange Formalized)
endobj
25 0 obj
<< /S /GoTo /D (subsection.3.1) >>
endobj
28 0 obj
(Update Translation)
endobj
29 0 obj
<< /S /GoTo /D (subsection.3.2) >>
endobj
32 0 obj
(Provenance Expressions and Graphs)
endobj
33 0 obj
<< /S /GoTo /D (subsection.3.3) >>
endobj
36 0 obj
(Assigning Trust to Provenance)
endobj
37 0 obj
<< /S /GoTo /D (section.4) >>
endobj
40 0 obj
(Performing Update Exchange)
endobj
41 0 obj
<< /S /GoTo /D (subsection.4.1) >>
endobj
44 0 obj
(Computing Instances with Provenance)
endobj
45 0 obj
<< /S /GoTo /D (subsubsection.4.1.1) >>
endobj
48 0 obj
(Datalog for Computing Peer Instances)
endobj
49 0 obj
<< /S /GoTo /D (subsubsection.4.1.2) >>
endobj
52 0 obj
(Incorporating Provenance)
endobj
53 0 obj
<< /S /GoTo /D (subsubsection.4.1.3) >>
endobj
56 0 obj
(Derivation Testing)
endobj
57 0 obj
<< /S /GoTo /D (subsection.4.2) >>
endobj
60 0 obj
(Incremental Update Exchange)
endobj
61 0 obj
<< /S /GoTo /D (section.5) >>
endobj
64 0 obj
(Implementation)
endobj
65 0 obj
<< /S /GoTo /D (subsection.5.1) >>
endobj
68 0 obj
(RDBMS-based Implementation)
endobj
69 0 obj
<< /S /GoTo /D (subsection.5.2) >>
endobj
72 0 obj
(Tukwila-based Implementation)
endobj
73 0 obj
<< /S /GoTo /D (section.6) >>
endobj
76 0 obj
(Experimental Evaluation)
endobj
77 0 obj
<< /S /GoTo /D (subsection.6.1) >>
endobj
80 0 obj
(Experimental CDSS Configurations)
endobj
81 0 obj
<< /S /GoTo /D (subsection.6.2) >>
endobj
84 0 obj
(Methodology)
endobj
85 0 obj
<< /S /GoTo /D (subsection.6.3) >>
endobj
88 0 obj
(Incremental vs. Complete Recomputation)
endobj
89 0 obj
<< /S /GoTo /D (subsection.6.4) >>
endobj
92 0 obj
(Scale-up)
endobj
93 0 obj
<< /S /GoTo /D (subsection.6.5) >>
endobj
96 0 obj
(Impact of Cycles and Mappings)
endobj
97 0 obj
<< /S /GoTo /D (section.7) >>
endobj
100 0 obj
(Related Work)
endobj
101 0 obj
<< /S /GoTo /D (section.8) >>
endobj
104 0 obj
(Future Work)
endobj
105 0 obj
<< /S /GoTo /D (section.9) >>
endobj
108 0 obj
(References)
endobj
109 0 obj
<< /S /GoTo /D [110 0 R /Fit ] >>
endobj
112 0 obj
<<
/Length 14645
/LC /QQAP
>>
stream
q
BT
/F63 17.9328 Tf 93.4566 707.5726 Td[(Update)-278(Exc)10(hang)-10(e)-278(with)-278(Mappings)-278(and)-278(Pr)20(o)20(venance)]TJ/F64 11.9552 Tf -11.6705 -40.5978 Td[(T)120(odd)-278(J)30(.)-278(Green)-2965(Gr)-15(igor)-15(is)-278(Kar)-30(v)25(ounar)10(akis)-2965(Zachar)-30(y)-278(G.)-278(Iv)25(es)-2965(V)70(al)-278(T)120(annen)]TJ/F64 9.9626 Tf 118.5228 -10.4608 Td[(Computer)-278(and)-278(Inf)30(or)-25(mation)-278(Science)-278(Depar)-40(tment)]TJ 46.6351 -10.4607 Td[(Univ)25(ersity)-278(of)-278(P)50(ennsylv)25(ania)]TJ/F64 11.9552 Tf -57.9566 -15.8526 Td[({tjg)10(reen,gkar)-30(v)25(oun,ziv)25(es)15(,v)25(al}@cis)15(.upenn.edu)]TJ/F66 11.9552 Tf -135.1891 -54.39 Td[(ABSTRA)55(CT)]TJ/F67 8.9664 Tf 0 -14.4459 Td[(W)80(e)-302(consider)-303(systems)-302(for)-303(data)-302(sharing)-303(among)-302(heterogeneous)-303(peers)]TJ 0 -10.4607 Td[(related)-268(by)-268(a)-268(netw)10(ork)-268(of)-268(schema)-268(mappings.)-364(Each)-269(peer)-268(has)-268(a)-268(locally)]TJ 0 -10.4608 Td[(controlled)-350(and)-350(edited)-350(database)-349(instance,)-375(b)20(ut)-350(w)10(ants)-350(to)-350(ask)-350(queries)]TJ 0 -10.4608 Td[(o)15(v)15(er)-317(related)-317(data)-317(from)-317(other)-317(peers)-317(as)-317(well.)-511(T)80(o)-317(achie)25(v)15(e)-317(this,)-334(e)25(v)15(ery)]TJ 0 -10.4608 Td[(peer')55(s)-393(updates)-393(propag)5(ate)-393(along)-393(the)-393(mappings)-393(to)-394(the)-393(other)-393(peers.)]TJ 0 -10.4607 Td[(Ho)25(we)25(v)15(er)40(,)-294(this)]TJ/F66 8.9664 Tf 52.3164 0 Td[(update)-285(exchange)]TJ/F67 8.9664 Tf 66.8877 0 Td[(is)-285(\002ltered)-286(by)]TJ/F66 8.9664 Tf 48.0265 0 Td[(trust)-285(conditions)]TJ/F67 8.9664 Tf 62.9064 0 Td[(\227)]TJ -230.137 -10.4608 Td[(e)15(xpressing)-284(what)-284(data)-284(and)-283(sources)-284(a)-284(peer)-284(judges)-284(to)-284(be)-284(authoritati)25(v)15(e)]TJ 0 -10.4608 Td[(\227)-357(which)-357(may)-357(cause)-357(a)-357(peer)-357(to)-357(reject)-357(another')55(s)-357(updates.)-632(In)-357(order)]TJ 0 -10.4608 Td[(to)-374(support)-375(such)-374(\002ltering,)-406(updates)-374(carry)]TJ/F66 8.9664 Tf 147.1773 0 Td[(pr)18(o)10(v)10(enance)]TJ/F67 8.9664 Tf 47.3457 0 Td[(information.)]TJ -194.523 -10.4607 Td[(These)-283(systems)-283(tar)18(get)-283(scienti\002c)-283(data)-283(sharing)-283(applications,)-291(and)-283(their)]TJ 0 -10.4608 Td[(general)-250(principles)-250(and)-250(architecture)-250(ha)20(v)15(e)-250(been)-250(described)-250(in)-250([20].)]TJ 8.9664 -10.4608 Td[(In)-423(this)-424(paper)-423(we)-423(present)-424(methods)-423(for)-423(realizing)-423(such)-424(systems.)]TJ -8.9664 -10.4608 Td[(Speci\002cally)65(,)-332(we)-316(e)15(xtend)-316(techniques)-316(from)-316(data)-316(inte)15(grat)1(ion,)-333(data)-316(e)15(x-)]TJ 0 -10.4607 Td[(change,)-410(and)-377(incremental)-378(vie)25(w)-378(maintenance)-377(to)-378(propag)5(ate)-378(updates)]TJ 0 -10.4608 Td[(along)-190(mappings;)-210(we)-190(inte)15(grate)-190(a)-190(no)15(v)15(el)-190(model)-190(for)-190(tracking)-190(data)-190(pro)15(v)15(e-)]TJ 0 -10.4608 Td[(nance,)-342(such)-324(that)-323(curators)-324(may)-324(\002lter)-323(updates)-324(based)-323(on)-324(trust)-324(condi-)]TJ 0 -10.4608 Td[(tions)-266(o)15(v)15(er)-265(this)-266(pro)15(v)15(enance;)-274(we)-266(discuss)-265(strate)15(gies)-266(for)-266(implementing)]TJ 0 -10.4607 Td[(our)-212(techniques)-212(in)-212(conjunction)-211(with)-212(an)-212(RDBMS;)-212(and)-212(we)-212(e)15(xperimen-)]TJ 0 -10.4608 Td[(tally)-336(demonstrate)-335(the)-336(viability)-336(of)-336(our)-335(techniques)-336(in)-336(the)-361(O)]TJ/F67 7.1731 Tf 210.5638 0 Td[(R)-62(C)-61(H)-62(E)-62(S)]TJ/F67 8.9664 Tf 25.3296 0 Td[(-)]TJ/F67 7.1731 Tf -235.6692 -10.4608 Td[(T)-61(R)-62(A)]TJ/F67 8.9664 Tf 17.6904 0 Td[(prototype)-250(system.)]TJ/F66 11.9552 Tf -17.9146 -26.4684 Td[(1.)-1000(INTR)30(ODUCTION)]TJ/F67 8.9664 Tf 8.9664 -12.9515 Td[(One)-359(of)-359(the)-358(most)-359(elusi)25(v)15(e)-359(goals)-359(of)-359(the)-358(data)-359(inte)15(gration)-359(\002eld)-359(has)]TJ -8.9664 -10.4608 Td[(been)-351(supporting)-352(sharing)-351(across)-352(lar)18(ge,)-376(heterogeneous)-352(populations.)]TJ 0 -10.4607 Td[(While)-395(data)-394(inte)15(gration)-395(and)-395(its)-395(v)25(ariants)-394(\050e.g.,)-431(data)-395(e)15(xchange)-395([12])]TJ 0 -10.4608 Td[(and)-292(w)10(arehousing\051)-292(are)-292(being)-291(adopted)-292(in)-292(corporations)-292(or)-292(small)-292(con-)]TJ 0 -10.4608 Td[(federations,)-434(little)-397(progress)-397(has)-398(been)-397(made)-397(in)-397(inte)15(grating)-398(broader)]TJ 0 -10.4608 Td[(communities.)-342(Y)100(et)-261(the)-261(need)-261(for)-261(sharing)-260(data)-261(across)-261(lar)18(ge)-261(communi-)]TJ 0 -10.4607 Td[(ties)-320(is)-321(increasing:)-451(most)-320(of)-321(the)-320(ph)5(ysical)-321(and)-320(life)-321(sciences)-320(ha)20(v)15(e)-321(be-)]TJ 0 -10.4608 Td[(come)-238(data-dri)25(v)15(en)-238(as)-238(the)15(y)-238(ha)20(v)15(e)-238(attempted)-238(to)-238(tackle)-238(lar)18(ger)-238(questions.)]TJ 0 -10.4608 Td[(The)-242(\002eld)-241(of)-242(bioinformatics,)-243(for)-242(instance,)-243(has)-242(a)-241(plethora)-242(of)-242(dif)25(ferent)]TJ 0 -10.4608 Td[(databases,)-254(each)-254(pro)15(viding)-253(a)-254(dif)25(ferent)-253(perspecti)25(v)15(e)-253(on)-254(a)-253(collection)-254(of)]TJ 0 -10.4607 Td[(or)18(g)5(anisms,)-339(genes,)-340(proteins,)-339(diseases,)-340(and)-321(so)-322(on.)-524(Associations)-322(e)15(x-)]TJ 0 -10.4608 Td[(ist)-259(between)-260(the)-259(dif)25(ferent)-260(databases')-259(data)-260(\050e.g.,)-262(links)-259(between)-260(genes)]TJ 0 -10.4608 Td[(and)-323(proteins,)-342(or)-323(gene)-323(homologs)-323(between)-323(species\051.)-530(Unfortunately)65(,)]TJ 0 -10.4608 Td[(data)-326(in)-327(this)-326(domain)-327(is)-326(surprisingly)-326(dif)25(\002cult)-327(to)-326(inte)15(grate,)-346(primarily)]TJ 0 -10.4607 Td[(because)-231(con)40(v)15(entional)-231(data)-231(inte)15(gration)-231(techniques)-231(require)-231(the)-231(de)25(v)15(el-)]TJ/F67 7.9701 Tf 0 -32.5104 Td[(Permission)-186(to)-186(cop)10(y)-186(without)-186(fee)-186(all)-186(or)-185(part)-186(of)-186(this)-186(material)-186(is)-186(granted)-186(pro)15(vided)]TJ 0 -8.9663 Td[(that)-229(the)-230(copies)-229(are)-230(not)-229(made)-230(or)-229(distrib)20(uted)-230(for)-229(direct)-230(commercial)-229(adv)25(antage,)]TJ 0 -8.9664 Td[(the)-160(VLDB)-160(cop)10(yright)-160(notice)-161(and)-160(the)-160(title)-160(of)-160(the)-160(publication)-161(and)-160(its)-160(date)-160(appear)40(,)]TJ 0 -8.9664 Td[(and)-335(notice)-334(is)-335(gi)25(v)15(en)-334(that)-335(cop)10(ying)-335(is)-334(by)-335(permission)-335(of)-334(the)-335(V)111(ery)-334(Lar)18(ge)-335(Data)]TJ 0 -8.9664 Td[(Base)-338(Endo)25(wment.)-625(T)80(o)-338(cop)10(y)-338(otherwise,)-361(or)-338(to)-338(republish,)-360(to)-338(post)-338(on)-338(serv)15(ers)]TJ 0 -8.9664 Td[(or)-286(to)-286(redistrib)20(ute)-286(to)-286(lists,)-295(requires)-286(a)-286(fee)-286(and/or)-286(special)-286(permission)-286(from)-286(the)]TJ 0 -8.9663 Td[(publisher)40(,)-250(A)40(CM.)]TJ/F72 7.9701 Tf 0 -8.9664 Td[(VLDB)-250(`07,)]TJ/F67 7.9701 Tf 36.527 0 Td[(September)-250(23\25528,)-250(2007,)-250(V)60(ienna,)-250(Austria.)]TJ -36.527 -8.9664 Td[(Cop)10(yright)-250(2007)-250(VLDB)-250(Endo)25(wment,)-250(A)40(CM)-250(978\2551\25559593\255649\2553/07/09.)]TJ/F67 8.9664 Tf 263.0137 503.3125 Td[(opment)-345(of)-345(a)-345(single)-344(global)-345(schema)-345(and)-345(complete)-345(global)-345(data)-345(con-)]TJ 0 -10.4607 Td[(sistenc)15(y)65(.)-410(Designing)-283(one)-284(schema)-283(for)-283(an)-284(entire)-283(community)-283(lik)10(e)-284(sys-)]TJ 0 -10.4608 Td[(tems)-357(biology)-357(is)-357(arduous,)-383(requires)-357(man)15(y)-357(re)25(visions,)-384(and)-357(requires)-357(a)]TJ 0 -10.4608 Td[(central)-313(administrator)]TJ/F67 5.9776 Tf 75.0198 3.809 Td[(1)]TJ/F67 8.9664 Tf 3.4869 -3.809 Td[(.)-499(Ev)15(en)-313(more)-313(problematic)-312(is)-313(the)-313(f)10(act)-313(that)-313(the)]TJ -78.5067 -10.4608 Td[(data)-314(or)-314(associations)-315(in)-314(dif)25(ferent)-314(databases)-314(are)-314(often)-315(contradictory)65(,)]TJ 0 -10.4608 Td[(forcing)-286(indi)25(vidual)-286(biologists)-287(to)-286(choose)-286(v)25(alues)-286(from)-286(databases)-287(the)15(y)]TJ 0 -10.4607 Td[(personally)-328(consider)-327(most)-328(authoritati)25(v)15(e)-328([28].)-543(Such)-328(inconsistencies)]TJ 0 -10.4608 Td[(are)-271(not)-272(handled)-271(by)-272(data)-271(inte)15(gration)-272(tools,)-277(since)-271(there)-272(is)-271(no)-272(consen-)]TJ 0 -10.4608 Td[(sus)-356(or)-357(\223clean\224)-356(v)15(ersion)-356(of)-356(the)-357(data.)-628(Thus,)-383(scientists)-356(simply)-357(mak)10(e)]TJ 0 -10.4608 Td[(their)-266(databases)-267(publicly)-266(do)25(wnloadable,)-271(so)-266(users)-266(can)-267(cop)10(y)-266(and)-267(con-)]TJ 0 -10.4607 Td[(v)15(ert)-256(them)-256(into)-256(a)-257(local)-256(format)-256(\050using)-256(custom)-256(Perl)-256(scripts)-256(or)-257(other)-256(ad)]TJ 0 -10.4608 Td[(hoc)-244(m)1(easures\051.)-308(Meanwhile)-244(the)-243(original)-244(data)-243(sources)-244(continue)-243(to)-244(be)]TJ 0 -10.4608 Td[(edited.)-300(In)-218(some)-219(cases)-219(the)-219(data)-219(pro)15(viders)-218(publish)-219(weekly)-219(or)-219(monthly)]TJ 0 -10.4608 Td[(lists)-317(of)-317(updates)-317(\050)]TJ/F72 8.9664 Tf 60.8293 0 Td[(deltas)]TJ/F67 8.9664 Tf 21.4203 0 Td[(\051)-317(to)-317(help)-317(others)-317(k)10(eep)-317(synchronized.)-512(T)80(oday)65(,)]TJ -82.2496 -10.4607 Td[(fe)25(w)-259(participants,)-262(e)15(xcept)-260(those)-259(with)-260(direct)-259(replicas,)-262(can)-259(actually)-260(e)15(x-)]TJ 0 -10.4608 Td[(ploit)-206(such)-205(deltas)-206(\227)-206(hence,)-214(once)-206(data)-205(has)-206(been)-206(copied)-205(to)-206(a)-206(dissimilar)]TJ 0 -10.4608 Td[(database,)-250(it)-250(be)15(gins)-250(to)-250(di)25(v)15(er)18(ge)-250(from)-250(the)-250(original.)]TJ 8.9664 -10.4608 Td[(T)80(o)-278(address)-277(the)-278(needs)-278(of)-277(scientists,)-285(we)-277(ha)20(v)15(e)-278(pre)25(viously)-278(proposed)]TJ -8.9664 -10.4607 Td[(an)-250(e)15(xtremely)-250(\003e)15(xible)-250(scheme)-249(for)-250(sharing)-250(data)-250(among)-250(dif)25(ferent)-250(par)20(-)]TJ 0 -10.4608 Td[(ticipants,)-245(which,)-245(rather)-243(than)-244(pro)15(viding)-243(a)-244(global)-243(vie)25(w)-244(of)-243(all)-244(data,)-245(in-)]TJ 0 -10.4608 Td[(stead)-341(f)10(acilitates)-342(import)-341(and)-342(e)15(xport)-341(among)-341(autonomous)-342(databases.)]TJ 0 -10.4608 Td[(The)]TJ/F72 8.9664 Tf 17.556 0 Td[(collabor)15(ative)-403(data)-403(sharing)-403(system)]TJ/F67 8.9664 Tf 129.383 0 Td[(\050abbre)25(viated)-403(CDSS\051)-403([20])]TJ -146.939 -10.4607 Td[(pro)15(vides)-284(a)-284(principled)-284(architecture)-284(that)-284(e)15(xtends)-285(t)1(he)-285(data)-284(inte)15(gration)]TJ 0 -10.4608 Td[(approach)-216(to)-216(encompass)-216(today')55(s)-216(scienti\002c)-216(data)-216(sharing)-216(practices)-216(and)]TJ 0 -10.4608 Td[(requirements:)-293(Our)-217(goal)-217(with)-217(the)-217(CDSS)-217(is)-217(to)-217(pro)15(vide)-217(the)-217(basic)-217(capa-)]TJ 0 -10.4608 Td[(bility)-293(of)]TJ/F72 8.9664 Tf 31.6581 0 Td[(update)-293(e)20(xc)15(hang)10(e)]TJ/F67 8.9664 Tf 60.486 0 Td[(,)-304(which)-293(publ)1(ishes)-293(a)-293(participant')55(s)-293(updates)]TJ -92.1441 -10.4607 Td[(to)-232(\223the)-231(w)10(orld\224)-232(at)-232(lar)18(ge,)-235(and)-232(then)-231(maps)-232(others')-232(updates)-231(to)-232(the)-232(partic-)]TJ 0 -10.4608 Td[(ipant')55(s)-300(local)-301(schema)-300(\227)-300(also)-301(\002ltering)-300(which)-301(ones)-300(to)-300(apply)-301(accord-)]TJ 0 -10.4608 Td[(ing)-378(to)-378(the)-378(local)-378(administra)1(tor')55(s)-378(unique)-378(trust)-378(policies.)-694(Data)-378(shar)20(-)]TJ 0 -10.4608 Td[(ing)-382(occurs)-381(among)]TJ/F72 8.9664 Tf 69.5348 0 Td[(loosely)]TJ/F67 8.9664 Tf 28.8238 0 Td[(coupled)-382(confederations)-381(of)-382(participants)]TJ -98.3586 -10.4607 Td[(\050peers\051.)-297(Each)-212(participant)-211(controls)-212(a)-211(local)-212(database)-211(instance,)-220(encom-)]TJ 0 -10.4608 Td[(passing)-352(all)-352(data)-353(it)-352(wishes)-352(to)-352(manipulate,)-378(including)-352(data)-353(imported)]TJ 0 -10.4608 Td[(from)-346(other)-347(participants.)-599(As)-347(edits)-346(are)-347(made)-346(to)-347(this)-346(database,)-371(the)15(y)]TJ 0 -10.4608 Td[(are)-337(logged.)-570(Declarati)25(v)15(e)]TJ/F72 8.9664 Tf 89.7102 0 Td[(sc)15(hema)-337(mappings)]TJ/F67 8.9664 Tf 67.6627 0 Td[(specify)-337(one)-336(database')55(s)]TJ -157.3729 -10.4607 Td[(relationships)-347(to)-346(other)-347(participants,)-371(much)-346(as)-347(in)-346(peer)-347(data)-347(manage-)]TJ 0 -10.4608 Td[(ment)-412(systems)-411([18];)-493(each)-412(peer)-411(operates)-412(in)-412(\223of)25(\003ine\224)-411(mode)-412(for)-412(as)]TJ 0 -10.4608 Td[(long)-355(as)-355(it)-355(lik)10(es,)-381(b)20(ut)-356(i)1(t)-356(occasional)1(ly)-356(performs)-355(an)-355(update)-355(e)15(xchange)]TJ 0 -10.4608 Td[(operation,)-350(which)-330(propag)5(ates)-329(updates)-330(to)-330(mak)10(e)-330(its)-330(database)-330(consis-)]TJ 0 -10.4607 Td[(tent)-350(with)-351(the)-350(others)-350(according)-351(to)-350(the)-351(schema)-350(mappings)-350(and)-351(local)]TJ 0 -10.4608 Td[(trust)-382(policies.)-706(The)-382(update)-382(e)15(xchange)-383(proce)1(ss)-383(is)-382(bidirectional)-382(and)]TJ 0 -10.4608 Td[(in)40(v)20(olv)15(es)-376(publishing)-376(an)15(y)-376(updates)-376(made)-376(locally)-377(by)-376(the)-376(participant,)]TJ 0 -10.4608 Td[(then)-247(importing)-246(ne)25(w)-247(updates)-247(from)-247(other)-246(participants)-247(\050after)-247(mapping)]TJ 0 -10.4607 Td[(them)-346(across)-346(schemas)-346(and)-346(\002ltering)-346(them)-346(according)-347(to)-346(trust)-346(condi-)]TJ 0 -10.4608 Td[(tions\051.)-527(As)-323(a)-322(prerequisite)-322(to)-323(assessing)-322(trust,)-341(the)-322(CDSS)-322(records)-323(the)]TJ 0 -10.4608 Td[(deri)25(v)25(ation)-280(of)-281(the)-280(updates,)-288(i.e.,)-288(their)-280(pro)15(v)15(enance)-280(or)-281(lineage)-280([4,)-288(8,)-288(7,)]TJ
ET
1 0 0 1 316.812 103.0986 cm
q
[]0 d
0 J
0.3985 w
0 0.1992 m
95.6399 0.1992 l
S
Q
1 0 0 1 -316.812 -103.0986 cm
BT
/F67 5.9776 Tf 317.8082 96.4316 Td[(1)]TJ/F67 8.9664 Tf 3.487 -3.809 Td[(Peer)-256(data)-256(management)-256([3,)-258(22,)-257(27,)-258(18])-256(supports)-256(multiple)-256(mediated)]TJ -4.4832 -8.9664 Td[(schemas,)-381(thus)-355(relaxing)-354(some)-355(aspects)-355(of)-354(administration,)-381(b)20(ut)-355(it)-355(as-)]TJ 0 -8.9663 Td[(sumes)-250(data)-250(is)-250(consistent.)]TJ
ET
Q
1 0 0 1 295.992 36 cm
0 Tr
/QQAPF481df14d 12 Tf
0 0 0 rg
100 Tz
0 Ts
0 Tw 0 Tc
BT
1 0 0 1 0 0 Tm
(675)Tj
ET
1 0 0 1 0 0 cm
1 0 0 1 -295.992 -36 cm
endstream
endobj
110 0 obj
<<
/Type /Page
/Resources 111 0 R
/MediaBox [ 0 0 612 792 ]
/Parent 145 0 R
/Annots [ 128 0 R 129 0 R 133 0 R 134 0 R 135 0 R 136 0 R 137 0 R 138 0 R 139 0 R 141 0 R
142 0 R 143 0 R 144 0 R ]
/Contents [ 112 0 R ]
>>
endobj
128 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [265.6168 453.8197 276.5757 463.8684]
/Subtype /Link
/A << /S /GoTo /D (cite.orchestra) >>
>> endobj
129 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [279.9532 299.3313 290.9121 309.38]
/Subtype /Link
/A << /S /GoTo /D (cite.FKMP05) >>
>> endobj
133 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[1 0 0]
/Rect [390.8355 541.491 396.315 553.3103]
/Subtype /Link
/A << /S /GoTo /D (Hfootnote.1) >>
>> endobj
134 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [460.6926 510.1086 471.6515 520.1573]
/Subtype /Link
/A << /S /GoTo /D (cite.mork-pql) >>
>> endobj
135 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [542.9669 353.2867 553.9258 363.2681]
/Subtype /Link
/A << /S /GoTo /D (cite.orchestra) >>
>> endobj
136 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [372.513 206.7462 383.4719 216.7949]
/Subtype /Link
/A << /S /GoTo /D (cite.p2p-mediation) >>
>> endobj
137 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [529.5818 112.5993 536.0575 122.6479]
/Subtype /Link
/A << /S /GoTo /D (cite.DBLP:conf/icdt/BunemanKT01) >>
>> endobj
138 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [538.888 112.5993 545.3638 122.6479]
/Subtype /Link
/A << /S /GoTo /D (cite.cui-thesis) >>
>> endobj
139 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [548.1943 112.5993 554.67 122.6479]
/Subtype /Link
/A << /S /GoTo /D (cite.spider06) >>
>> endobj
141 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [406.8605 89.6852 413.3362 101.5045]
/Subtype /Link
/A << /S /GoTo /D (cite.trento-lrm) >>
>> endobj
142 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [415.8946 89.6852 426.8535 101.5045]
/Subtype /Link
/A << /S /GoTo /D (cite.hyperion) >>
>> endobj
143 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [429.4119 89.6852 440.3708 101.5045]
/Subtype /Link
/A << /S /GoTo /D (cite.p2p-bav) >>
>> endobj
144 0 obj <<
/Type /Annot
/Border[0 0 1]/H/I/C[0 1 0]
/Rect [442.9292 89.6852 453.8881 101.5045]
/Subtype /Link
/A << /S /GoTo /D (cite.p2p-mediation) >>
>> endobj
113 0 obj <<
/D [110 0 R /XYZ 53.7983 763.1083 null]
>> endobj
120 0 obj <<
/D [110 0 R /XYZ 53.7983 585.7733 null]
>> endobj
124 0 obj <<
/D [110 0 R /XYZ 53.7983 571.6344 null]
>> endobj
6 0 obj <<
/D [110 0 R /XYZ 53.7983 348.1483 null]
>> endobj
140 0 obj <<
/D [110 0 R /XYZ 321.2952 101.589 null]
>> endobj
111 0 obj
<<
/Font <<
/F63 116 0 R
/F64 119 0 R
/F66 123 0 R
/F67 127 0 R
/F72 132 0 R
/QQAPF481df14d 553 0 R
>>
/ProcSet [ /PDF /Text ]
>>
endobj
159 0 obj
<<
/Length 21484
/LC /QQAP
>>
stream
q
BT
/F67 8.9664 Tf 53.7983 728.2391 Td[(2].)-678(After)-372(the)-373(update)-372(e)15(xchange,)-404(the)-372(participant)-373(has)-372(an)-373(up-to-date)]TJ 0 -10.4608 Td[(data)-327(instance,)-347(incorporating)-327(trusted)-328(changes)-327(made)-327(by)-328(participants)]TJ 0 -10.4608 Td[(transiti)25(v)15(ely)-299(reachable)-300(via)-300(sc)1(hema)-300(mappings.)-459(Update)-299(e)15(xchange)-300(in-)]TJ 0 -10.4608 Td[(troduces)-195(a)-195(number)-195(of)-196(no)15(v)15(el)-195(challenges)-195(that)-195(we)-195(address)-195(in)-196(this)-195(paper:)]TJ/F46 8.9664 Tf 13.325 -17.3425 Td[(\017)]TJ/F67 8.9664 Tf 9.0909 0 Td[(Building)-431(upon)-431(techniques)-431(for)-431(e)15(xchanging)]TJ/F66 8.9664 Tf 158.649 0 Td[(data)]TJ/F67 8.9664 Tf 20.8017 0 Td[(using)-431(net-)]TJ -179.4507 -10.4608 Td[(w)10(orks)-426(of)-426(schema)-426(mappings)1(,)-470(we)-426(map)]TJ/F66 8.9664 Tf 142.4939 0 Td[(updates)]TJ/F67 8.9664 Tf 33.712 0 Td[(across)-426(par)20(-)]TJ -176.2059 -10.4607 Td[(ticipants')-382(schemas:)-573(this)-382(f)10(acilitates)-382(incremental)-382(vie)25(w)-382(main-)]TJ 0 -10.4608 Td[(tenance)-220(in)-220(a)-220(CDSS,)-220(and)-220(it)-220(also)-221(genera)1(lizes)-221(peer)-220(data)-220(manage-)]TJ 0 -10.4608 Td[(ment)-250([18])-250(and)-250(data)-250(e)15(xchange)-250([31,)-250(12].)]TJ/F46 8.9664 Tf -9.0909 -16.7203 Td[(\017)]TJ/F67 8.9664 Tf 9.0909 0 Td[(W)80(e)-190(allo)25(w)-190(each)-190(participant)-190(to)-190(perform)-190(modi\002cations)-190(that)-190(\223o)15(v)15(er)20(-)]TJ 0 -10.4608 Td[(ride\224)-308(data)-308(imported)-308(from)-309(else)25(where)-308(\050i.e.,)-322(remo)15(v)15(e)-309(or)-308(replace)]TJ 0 -10.4608 Td[(imported)-214(data)-214(in)-215(the)-214(local)-214(instance\051,)-221(or)-214(add)-215(to)-214(it)-214(\050i.e.,)-221(add)-215(ne)25(w)]TJ 0 -10.4607 Td[(data)-250(to)-250(the)-250(local)-250(database)-250(instance\051.)]TJ/F46 8.9664 Tf -9.0909 -16.7204 Td[(\017)]TJ/F67 8.9664 Tf 9.0909 0 Td[(In)-423(order)-423(to)-423(allo)25(w)-423(CDSS)-422(participants)-423(to)-423(specify)-423(what)-423(data)]TJ 0 -10.4607 Td[(the)15(y)-308(trust)-307(and)-308(wish)-308(to)-307(import,)-322(we)-308(propose)-308(the)-307(use)-308(of)]TJ/F72 8.9664 Tf 193.958 0 Td[(semir)20(-)]TJ -193.958 -10.4608 Td[(ing)-315(pr)45(o)10(venance)]TJ/F67 8.9664 Tf 58.4402 0 Td[([16])-315(to)-315(trace)-315(the)-314(deri)25(v)25(ation)-315(of)-315(each)-315(mapped)]TJ -58.4402 -10.4608 Td[(update,)-279(and)-274(we)-273(\002lter)-274(updates)-273(with)-273(participant-speci\002ed)]TJ/F72 8.9664 Tf 200.2435 0 Td[(trust)]TJ -200.2435 -10.4608 Td[(conditions)]TJ/F67 8.9664 Tf 37.3625 0 Td[(.)]TJ/F46 8.9664 Tf -46.4534 -16.7203 Td[(\017)]TJ/F67 8.9664 Tf 9.0909 0 Td[(W)80(e)-298(de)25(v)15(elop)-298(a)-297(complete)-298(implementation)-298(of)-298(update)-298(e)15(xchange)]TJ 0 -10.4608 Td[(in)-268(our)-293(O)]TJ/F67 7.1731 Tf 30.8761 0 Td[(R)-62(C)-61(H)-62(E)-62(S)-61(T)-62(R)-61(A)]TJ/F67 8.9664 Tf 43.1795 0 Td[(CDSS)-268(prototype,)-272(with)-268(no)15(v)15(el)-267(algorithms)]TJ -74.0556 -10.4608 Td[(and)-301(encoding)-300(schemes)-301(to)-301(translate)-301(updates,)-313(maintain)-301(pro)15(v)15(e-)]TJ 0 -10.4607 Td[(nance,)-272(and)-267(apply)-267(trust)-267(conditions.)-362(W)80(e)-267(pro)15(vide)-267(a)-267(detailed)-268(e)15(x-)]TJ 0 -10.4608 Td[(perimental)-362(study)-361(of)-362(the)-362(scalability)-362(and)-361(performance)-362(of)-362(our)]TJ 0 -10.4608 Td[(implementation.)]TJ -13.4496 -17.3425 Td[(This)-280(paper)-280(is)-281(part)-280(of)-280(an)-280(ongoing)-281(ef)25(fort)-280(to)-280(realize)-280(the)-280(CDSS)-281(pro-)]TJ -8.9663 -10.4608 Td[(posal)-320(of)-320([20].)-520(It)-320(complements)-320(our)-320(recent)-320(w)10(ork)-320(in)-320([32],)-338(which)-320(fo-)]TJ 0 -10.4608 Td[(cuses)-257(on)-257(algorithms)-257(to)-256(reconcile)-257(con\003icting)-257(updates)-257(made)-257(o)15(v)15(er)-257(the)]TJ/F66 8.9664 Tf 0 -10.4607 Td[(same)]TJ/F67 8.9664 Tf 21.7977 0 Td[(schema.)-355(Here)-265(we)-265(not)-265(only)-265(de)25(v)15(elop)-266(a)-265(complete)-265(semantics)-265(for)]TJ -21.7978 -10.4608 Td[(translating)-322(updates)-323(into)-322(a)-322(tar)18(get)-323(schema,)-340(maintaining)-323(pro)15(v)15(enance,)]TJ 0 -10.4608 Td[(and)-224(\002ltering)-225(untrusted)-224(updates,)-230(b)20(ut)-224(also)-225(a)-224(concrete)-225(implementation.)]TJ 0 -10.4608 Td[(This)-262(paper)-262(also)-262(b)20(uilds)-262(upon)-262([16],)-265(which)-262(presents)-262(a)-262(formal)-262(study)-262(of)]TJ 0 -10.4607 Td[(the)-253(pro)15(v)15(enance)-253(model)-253(that)-253(we)-253(implement)-253(in)-253(this)-254(paper)55(.)-319(Finally)65(,)-254(we)]TJ 0 -10.4608 Td[(note)-303(that)-303(our)-303(algorithms)-303(are)-303(of)-304(i)1(ndependent)-304(interest)-303(for)-303(incremen-)]TJ 0 -10.4608 Td[(tal)-259(maintenance)-258(with)-259(pro)15(v)15(enance)-259(in)-259(other)-258(data)-259(inte)15(gration)-259(and)-259(data)]TJ 0 -10.4608 Td[(e)15(xchange)-250(settings)-250(besides)-250(the)-250(CDSS.)]TJ/F66 8.9664 Tf 0 -13.2954 Td[(Roadmap.)]TJ/F67 8.9664 Tf 55.2448 0 Td[(Section)-385(2)-384(pro)15(vides)-385(an)-385(o)15(v)15(ervie)25(w)-384(of)-385(the)-385(CDSS)-384(up-)]TJ -55.2448 -10.4608 Td[(date)-271(e)15(xchange)-271(process.)-373(Section)-271(3)-272(formali)1(zes)-272(system)-271(operation)-271(and)]TJ 0 -10.4607 Td[(our)-321(data)-320(model.)-522(Section)-320(4)-321(presents)-320(algorithms)-321(for)-320(supporting)-321(up-)]TJ 0 -10.4608 Td[(date)-249(e)15(xchange,)-249(and)-249(Section)-249(5)-248(describes)-249(ho)25(w)-249(we)-249(implemented)-249(them)]TJ 0 -10.4608 Td[(within)-339(the)-364(O)]TJ/F67 7.1731 Tf 47.0959 0 Td[(R)-62(C)-61(H)-62(E)-62(S)-61(T)-62(R)-61(A)]TJ/F67 8.9664 Tf 43.816 0 Td[(system.)-576(W)80(e)-339(e)15(xperimentally)-339(e)25(v)25(aluate)-338(our)]TJ -90.9119 -10.4608 Td[(w)10(ork)-284(in)-283(Section)-284(6,)-292(describe)-283(related)-284(w)10(ork)-283(in)-284(Section)-283(7,)-292(and)-284(present)]TJ 0 -10.4607 Td[(our)-250(conclusions)-250(and)-250(future)-250(plans)-250(in)-250(Section)-250(8.)]TJ/F66 11.9552 Tf 0 -22.9968 Td[(2.)-1000(CDSS)-250(UPD)35(A)95(TE)-250(EXCHANGE)]TJ/F67 8.9664 Tf 8.9664 -12.9514 Td[(The)-276(CDSS)-275(model)-276(b)20(uilds)-276(upon)-276(the)-275(fundamentals)-276(of)-276(data)-276(inte)15(gra-)]TJ -8.9664 -10.4608 Td[(tion)-203(and)-203(peer)-203(data)-204(manageme)1(nt)-204([18],)-212(b)20(ut)-203(adds)-203(se)25(v)15(eral)-204(no)15(v)15(el)-203(aspects.)]TJ 0 -10.4608 Td[(As)-306(in)-305(a)-306(PDMS,)-305(the)-306(CDSS)-305(contains)-306(a)-306(set)-305(of)]TJ/F72 8.9664 Tf 159.6525 0 Td[(peer)10(s)]TJ/F67 8.9664 Tf 19.3312 0 Td[(,)-319(each)-306(represent-)]TJ -178.9837 -10.4608 Td[(ing)-336(an)-336(autonomous)-336(domain)-336(of)-336(control.)-568(Each)-336(peer')55(s)-336(administrator)]TJ 0 -10.4607 Td[(has)-260(full)-261(control)-260(o)15(v)15(er)-260(a)-260(local)-261(DBMS,)-260(its)-260(schema,)-263(and)-260(the)-261(conditions)]TJ 0 -10.4608 Td[(under)-363(which)-363(the)-363(peer)-363(t)1(rusts)-363(data.)-649(W)40(ithout)-363(loss)-363(of)-363(generality)65(,)-391(we)]TJ 0 -10.4608 Td[(assume)-357(that)-357(each)-357(peer)-357(has)-356(a)-357(schema)-357(disjoint)-357(from)-357(the)-357(others.)-631(In)]TJ 0 -10.4608 Td[(this)-368(paper)-369(we)-368(assume)-368(relational)-369(schemas,)-398(b)20(ut)-368(our)-368(model)-369(e)15(xtends)]TJ 0 -10.4607 Td[(naturally)-250(to)-250(other)-250(data)-250(models)-250(such)-250(as)-250(XML)-250(or)-250(RDF)80(.)]TJ 10.1868 -17.3425 Td[(E)]TJ/F67 7.1731 Tf 5.9268 0 Td[(X)-62(A)-61(M)-63(P)-61(L)-62(E)]TJ/F67 8.9664 Tf 36.9011 0 Td[(1.)]TJ/F72 8.9664 Tf 11.208 0 Td[(F)45(igur)37(e)-190(1)-190(illustr)15(ates)-190(an)-190(e)20(xample)-190(bioinformatics)-190(col-)]TJ -64.2227 -10.4608 Td[(labor)15(ative)-370(data)-369(sharing)-370(system,)-400(based)-370(on)-369(a)-370(r)37(eal)-370(application)-370(and)]TJ 0 -10.4608 Td[(databases)-321(of)-321(inter)37(est)-321(to)-321(af)18(\002liates)-321(of)-321(the)-321(P)80(enn)-321(Center)-321(for)-321(Bioinfor)20(-)]TJ 0 -10.4608 Td[(matics.)-305(GUS,)-234(the)-235(Genomics)-234(Uni\002ed)-234(Sc)15(hema,)-238(contains)-234(g)10(ene)-235(e)20(xpr)37(es-)]TJ 0 -10.4607 Td[(sion,)-430(pr)45(otein,)-431(and)-394(taxon)-395(\050or)37(ganism\051)-394(information;)-466(BioSQL,)-395(af)18(\002li-)]TJ 0 -10.4608 Td[(ated)-292(wit)1(h)-292(the)-292(BioP)80(erl)-291(pr)45(oject,)-302(contains)-291(very)-292(similar)-291(concepts;)-313(and)]TJ
ET
1 0 0 1 328.3637 632.7728 cm
q 0.30093 0 0 0.30093 0 0 cm
q
1 0 0 1 -40.08 -20.0735 cm
/Im1 Do
Q
Q
1 0 0 1 -328.3637 -632.7728 cm
BT
/F67 8.9664 Tf 316.812 620.1606 Td[(Figure)-311(1:)]TJ/F67 7.9701 Tf 39.8401 0 Td[(Example)-311(collaborati)25(v)15(e)-311(data)-311(sharing)-311(system)-311(for)-311(three)-311(bioinfor)20(-)]TJ -39.8401 -8.9664 Td[(matics)-297(sources.)-452(F)15(or)-298(simplicity)65(,)-309(we)-297(assume)-298(one)-297(relation)-297(at)-298(each)-297(participant)]TJ 0 -8.9663 Td[(\050)]TJ/F66 7.9701 Tf 2.654 0 Td[(P)]TJ/F9 4.9813 Tf 3.6475 -0.9963 Td[(GU)-109(S)]TJ/F78 7.9701 Tf 15.5612 0.9963 Td[(;)]TJ/F66 7.9701 Tf 3.7637 0 Td[(P)]TJ/F9 4.9813 Tf 3.6475 -0.9963 Td[(B)-47(i)1(oS)-51(QL)]TJ/F78 7.9701 Tf 26.7237 0.9963 Td[(;)]TJ/F66 7.9701 Tf 3.7637 0 Td[(P)]TJ/F9 4.9813 Tf 3.6475 -0.9963 Td[(uB)-47(i)1(o)]TJ/F67 7.9701 Tf 16.2696 0.9963 Td[(\051.)-306(Schema)-237(mappings)-237(are)-238(indicated)-237(by)-238(labeled)-237(arcs.)]TJ/F72 8.9664 Tf -79.6784 -32.3175 Td[(a)-322(thir)37(d)-321(sc)15(hema,)-340(uBio,)-340(establishes)-322(s)1(ynonyms)-322(and)-322(canonical)-322(names)]TJ 0 -10.4608 Td[(for)-341(taxa.)-584(Instances)-341(of)-342(these)-341(databases)-341(contain)-341(taxon)-342(information)]TJ 0 -10.4608 Td[(that)-294(is)-295(autonomously)-294(maintained)-295(b)20(ut)-294(of)-295(mutual)-294(inter)37(est)-295(to)-294(the)-295(oth-)]TJ 0 -10.4607 Td[(er)10(s.)-550(Suppose)-330(that)-330(a)-330(peer)-330(with)-330(BioSQL)37(')40(s)-330(sc)15(hema,)]TJ/F66 8.9664 Tf 181.8156 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9963 Td[(B)-47(i)1(oS)-51(QL)]TJ/F72 8.9664 Tf 26.7237 0.9963 Td[(,)-350(wants)]TJ -212.7955 -10.4608 Td[(to)-338(import)-337(data)-338(fr)45(om)-337(another)-338(peer)111(,)]TJ/F66 8.9664 Tf 126.7955 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9962 Td[(GU)-109(S)]TJ/F72 8.9664 Tf 15.5612 0.9962 Td[(,)-359(as)-338(shown)-338(by)-337(the)-338(ar)37(c)-337(la-)]TJ -146.6128 -10.4608 Td[(beled)]TJ/F44 8.9664 Tf 21.686 0 Td[(m)]TJ/F43 5.9776 Tf 8.1188 -0.9962 Td[(1)]TJ/F72 8.9664 Tf 4.151 0.9962 Td[(,)-253(b)20(ut)-253(the)-252(con)40(ver)10(se)-253(is)-253(not)-252(true)15(.)-318(Similarly)55(,)-253(peer)]TJ/F66 8.9664 Tf 161.4295 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9962 Td[(uB)-47(i)1(o)]TJ/F72 8.9664 Tf 18.5347 0.9962 Td[(wants)]TJ -218.1761 -10.4608 Td[(to)-341(import)-340(data)-341(fr)45(om)]TJ/F66 8.9664 Tf 75.5811 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9962 Td[(GU)-109(S)]TJ/F72 8.9664 Tf 15.5612 0.9962 Td[(,)-363(along)-341(ar)37(c)]TJ/F44 8.9664 Tf 43.6526 0 Td[(m)]TJ/F43 5.9776 Tf 8.1188 -0.9962 Td[(2)]TJ/F72 8.9664 Tf 4.1511 0.9962 Td[(.)-582(Additionally)55(,)]TJ/F66 8.9664 Tf 56.8025 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9962 Td[(B)-47(i)1(oS)-51(QL)]TJ/F72 8.9664 Tf -212.3796 -9.4645 Td[(and)]TJ/F66 8.9664 Tf 16.1219 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9963 Td[(uB)-47(i)1(o)]TJ/F72 8.9664 Tf 18.942 0.9963 Td[(a)10(gr)37(ee)-298(to)-298(mutually)-298(shar)37(e)-298(some)-298(of)-298(their)-298(data:)-406(e)15(.g)15(.,)]TJ/F66 8.9664 Tf 179.2576 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9963 Td[(uB)-47(i)1(o)]TJ/F72 8.9664 Tf -222.8338 -9.4645 Td[(imports)-252(taxon)-252(synonyms)-252(fr)45(om)]TJ/F66 8.9664 Tf 107.7575 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9962 Td[(B)-47(i)1(oS)-51(QL)]TJ/F72 8.9664 Tf 28.9835 0.9962 Td[(\050via)]TJ/F44 8.9664 Tf 16.2022 0 Td[(m)]TJ/F43 5.9776 Tf 8.1188 -0.9962 Td[(3)]TJ/F72 8.9664 Tf 4.1511 0.9962 Td[(\051)-252(and)]TJ/F66 8.9664 Tf 20.9547 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9962 Td[(B)-47(i)1(oS)-51(QL)]TJ/F72 8.9664 Tf 28.9834 0.9962 Td[(uses)]TJ -223.6635 -10.4608 Td[(tr)15(ansitivity)-197(to)-197(infer)-196(ne)15(w)-197(entries)-197(in)-197(its)-197(database)10(,)-207(via)-197(mapping)]TJ/F44 8.9664 Tf 211.4179 0 Td[(m)]TJ/F43 5.9776 Tf 8.1188 -0.9962 Td[(4)]TJ/F72 8.9664 Tf 4.151 0.9962 Td[(.)-292(F)45(i-)]TJ -223.6877 -10.4608 Td[(nally)55(,)-284(eac)15(h)-278(participant)-277(may)-277(have)-278(a)-277(certain)]TJ/F67 8.9664 Tf 155.5535 0 Td[(trust)-277(polic)15(y)]TJ/F72 8.9664 Tf 43.1978 0 Td[(about)-277(what)]TJ -198.7513 -10.4607 Td[(data)-354(it)-354(wishes)-354(to)-353(incorpor)15(ate:)-518(e)15(.g)15(.,)]TJ/F66 8.9664 Tf 132.6671 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9963 Td[(B)-47(i)1(oS)-51(QL)]TJ/F72 8.9664 Tf 29.8968 0.9963 Td[(may)-354(only)-354(trust)-354(data)]TJ -166.8201 -10.4608 Td[(fr)45(om)]TJ/F66 8.9664 Tf 19.2945 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9962 Td[(uB)-47(i)1(o)]TJ/F72 8.9664 Tf 19.0304 0.9962 Td[(if)-308(it)-308(was)-308(derived)-307(fr)45(om)]TJ/F66 8.9664 Tf 81.1488 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9962 Td[(GU)-109(S)]TJ/F72 8.9664 Tf 18.3219 0.9962 Td[(entries.)-484(The)-308(CD)1(SS)-308(facili-)]TJ -146.3078 -10.4608 Td[(tates)-321(data\003ow)-321(am)1(ong)-321(these)-321(systems,)-338(using)-321(mappings)-321(and)-321(policies)]TJ 0 -10.4608 Td[(de)15(veloped)-250(by)-250(the)-250(independent)-250(participants')-250(administr)15(ator)10(s.)]TJ/F67 8.9664 Tf 8.9664 -23.3122 Td[(The)-291(arcs)-291(between)-291(participants)-291(in)-291(the)-291(e)15(xample)-291(are)-292(formall)1(y)-292(a)-291(set)]TJ -8.9664 -10.4608 Td[(of)]TJ/F72 8.9664 Tf 10.1311 0 Td[(sc)15(hema)-297(mappings)]TJ/F67 8.9664 Tf 64.2877 0 Td[(.)-451(These)-297(are)-296(logical)-297(assertions)-297(that)-297(relate)-297(mul-)]TJ -74.4188 -10.4608 Td[(tiple)-396(relations)-396(from)-396(dif)25(ferent)-396(peer)-396(schemas.)-748(W)80(e)-397(adopt)-396(the)-396(well-)]TJ 0 -10.4608 Td[(kno)25(wn)-357(formalism)-357(of)]TJ/F72 8.9664 Tf 78.1107 0 Td[(tuple-g)10(ener)15(ating)-357(dependencies)]TJ/F67 8.9664 Tf 114.246 0 Td[(\050tgds\051.)-631(Tgds)]TJ -192.3567 -10.4607 Td[(are)-349(a)-350(popular)-349(means)-349(of)-350(specifyi)1(ng)-350(constraints)-349(and)-349(mappings)-350([12,)]TJ 0 -10.4608 Td[(9])-438(in)-439(data)-438(sharing,)-486(and)-438(the)15(y)-438(are)-439(equi)25(v)25(alent)-438(to)-438(so-called)]TJ/F72 8.9664 Tf 213.1997 0 Td[(global-)]TJ -213.1997 -10.4608 Td[(local-as-vie)15(w)]TJ/F67 8.9664 Tf 51.6603 0 Td[(or)]TJ/F72 8.9664 Tf 10.9536 0 Td[(GLA)105(V)]TJ/F67 8.9664 Tf 25.6481 0 Td[(mappings)-389([14,)-423(18],)-423(which)-389(in)-388(turn)-389(gener)20(-)]TJ -88.262 -10.4608 Td[(alize)-286(the)-286(earlier)-286(global-as-vie)25(w)-286(and)-286(local-as-vie)25(w)-286(mapping)-286(formu-)]TJ 0 -10.4607 Td[(lations)-250([23].)-310(A)-250(tgd)-250(is)-250(a)-250(logical)-250(assertion)-250(of)-250(the)-250(form:)]TJ/F46 8.9664 Tf 64.8499 -18.8956 Td[(8)]TJ/F31 8.9664 Tf 5.6835 0 Td[(\026)]TJ/F44 8.9664 Tf -0.5639 0 Td[(x;)]TJ/F31 8.9664 Tf 9.9574 0 Td[(\026)]TJ/F44 8.9664 Tf -0.6382 0 Td[(y)]TJ/F31 8.9664 Tf 7.1018 0 Td[(\050)]TJ/F44 8.9664 Tf 3.5838 0 Td[(\036)]TJ/F31 8.9664 Tf 5.4849 0 Td[(\050)-63(\026)]TJ/F44 8.9664 Tf 3.5838 0 Td[(x;)]TJ/F31 8.9664 Tf 9.9574 0 Td[(\026)]TJ/F44 8.9664 Tf -0.6382 0 Td[(y)]TJ/F31 8.9664 Tf 4.8602 0 Td[(\051)]TJ/F46 8.9664 Tf 6.1436 0 Td[(!)-285(9)]TJ/F31 8.9664 Tf 17.4397 0 Td[(\026)]TJ/F44 8.9664 Tf -0.5449 0 Td[(z)-293(\040)]TJ/F31 8.9664 Tf 13.2489 0 Td[(\050)-63(\026)]TJ/F44 8.9664 Tf 3.5837 0 Td[(x;)]TJ/F31 8.9664 Tf 9.864 0 Td[(\026)]TJ/F44 8.9664 Tf -0.5448 0 Td[(z)]TJ/F31 8.9664 Tf 4.6734 0 Td[(\051\051)]TJ/F67 8.9664 Tf -167.086 -18.8956 Td[(where)-268(the)-268(left)-268(hand)-268(side)-268(\050LHS\051)-268(of)-269(the)-268(implication,)]TJ/F44 8.9664 Tf 182.7901 0 Td[(\036)]TJ/F67 8.9664 Tf 5.485 0 Td[(,)-273(is)-268(a)-268(conjunc-)]TJ -188.2751 -10.4608 Td[(tion)-232(of)-232(atoms)-231(o)15(v)15(er)-232(v)25(ariables)]TJ/F31 8.9664 Tf 101.6058 0 Td[(\026)]TJ/F44 8.9664 Tf -0.5638 0 Td[(x)]TJ/F67 8.9664 Tf 7.302 0 Td[(and)]TJ/F31 8.9664 Tf 15.6642 0 Td[(\026)]TJ/F44 8.9664 Tf -0.6382 0 Td[(y)]TJ/F67 8.9664 Tf 4.8602 0 Td[(,)-235(and)-232(the)-232(right)-232(hand)-232(side)-231(\050RHS\051)]TJ -128.2302 -10.4608 Td[(of)-348(the)-348(implication,)]TJ/F44 8.9664 Tf 71.1056 0 Td[(\040)]TJ/F67 8.9664 Tf 6.3338 0 Td[(,)-373(is)-348(a)-348(conjunction)-349(of)-348(atoms)-348(o)15(v)15(er)-348(v)25(ariables)]TJ/F31 8.9664 Tf 157.0044 0 Td[(\026)]TJ/F44 8.9664 Tf -0.5639 0 Td[(x)]TJ/F67 8.9664 Tf -233.8799 -10.4608 Td[(and)]TJ/F31 8.9664 Tf 15.6758 0 Td[(\026)]TJ/F44 8.9664 Tf -0.5448 0 Td[(z)]TJ/F67 8.9664 Tf 4.6734 0 Td[(.)-308(The)-243(tgd)-244(e)15(xpresses)-243(a)-244(constraint)-243(about)-244(the)-243(e)15(xistence)-244(of)-243(a)-244(tuple)]TJ -19.8044 -10.4608 Td[(in)-208(the)-209(instance)-208(on)-209(the)-208(RHS,)-209(gi)25(v)15(en)-208(a)-208(particular)-209(combination)-208(of)-209(tuples)]TJ 0 -10.4607 Td[(satisfying)-250(the)-250(constraint)-250(of)-250(the)-250(LHS.)]TJ/F66 8.9664 Tf 0 -13.2954 Td[(Notation.)]TJ/F67 8.9664 Tf 44.808 0 Td[(W)80(e)-265(use)]TJ/F31 8.9664 Tf 28.4298 0 Td[(\006)]TJ/F67 8.9664 Tf 9.0305 0 Td[(for)-265(the)]TJ/F66 8.9664 Tf 26.1614 0 Td[(union)]TJ/F67 8.9664 Tf 24.3064 0 Td[(of)-265(all)-265(peer)-265(schemas)-264(and)]TJ/F31 8.9664 Tf 87.0658 0 Td[(\006\050)]TJ/F66 8.9664 Tf 10.2393 0 Td[(P)]TJ/F31 8.9664 Tf 5.4784 0 Td[(\051)]TJ/F67 8.9664 Tf -235.5196 -10.4608 Td[(for)-310(the)-310(schema)-311(of)-310(peer)]TJ/F66 8.9664 Tf 85.1096 0 Td[(P)]TJ/F67 8.9664 Tf 5.4784 0 Td[(.)-491(W)80(e)-310(use)]TJ/F46 8.9664 Tf 35.8847 0 Td[(M)]TJ/F67 8.9664 Tf 13.8028 0 Td[(for)-310(the)-310(set)-311(of)-310(all)-310(mappings,)]TJ -140.2755 -10.4608 Td[(which)-278(we)-279(can)-278(think)-279(of)-278(as)-279(logical)-278(constraints)-279(on)]TJ/F31 8.9664 Tf 172.8813 0 Td[(\006)]TJ/F67 8.9664 Tf 6.6556 0 Td[(.)-395(When)-279(we)-278(refer)]TJ -179.5369 -10.4608 Td[(to)-317(mappings)-316(we)-317(will)-316(use)-317(the)-317(notation)-316(of)-317(tgds.)-510(F)15(or)-316(readability)65(,)-334(we)]TJ 0 -10.4607 Td[(will)-293(omit)-293(the)-293(uni)25(v)15(ersal)-292(quanti\002ers)-293(for)-293(v)25(ariables)-293(in)-293(the)-293(LHS.)-293(When)]TJ 0 -10.4608 Td[(we)-266(later)-267(refer)-266(to)-267(queries,)-270(including)-267(queries)-266(based)-267(on)-266(mappings,)-271(we)]TJ 0 -10.4608 Td[(will)-315(use)-316(the)-315(similar)-316(notation)-315(of)-316(datalog)-315(\050which,)-332(ho)25(we)25(v)15(er)40(,)-332(re)25(v)15(erses)]TJ 0 -10.4608 Td[(the)-232(orde)1(r)-232(of)-232(impl)1(ication,)-236(specifying)-231(the)-232(output)-231(of)-232(a)-231(rule)-232(on)-231(the)-232(left\051.)]TJ 10.1868 -23.3122 Td[(E)]TJ/F67 7.1731 Tf 5.9268 0 Td[(X)-62(A)-61(M)-63(P)-61(L)-62(E)]TJ/F67 8.9664 Tf 36.9011 0 Td[(2.)]TJ/F72 8.9664 Tf 11.208 0 Td[(Refer)-322(to)-322(F)45(igur)37(e)-322(1.)-526(P)80(eer)10(s)]TJ/F66 8.9664 Tf 92.6643 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9963 Td[(GU)-109(S)]TJ/F44 8.9664 Tf 15.5613 0.9963 Td[(;)]TJ/F66 8.9664 Tf 5.4466 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9963 Td[(B)-47(i)1(oS)-51(QL)]TJ/F44 8.9664 Tf 26.7238 0.9963 Td[(;)]TJ/F66 8.9664 Tf 5.4466 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9963 Td[(uB)-47(i)1(o)]TJ/F72 8.9664 Tf -222.8338 -9.4645 Td[(have)-221(one-r)37(elation)-221(sc)15(hemas)-221(describing)-220(taxa)-221(IDs,)-227(names,)-227(and)-221(canon-)]TJ 0 -10.4608 Td[(ical)-2387(names:)]TJ/F31 8.9664 Tf 79.9056 0 Td[(\006\050)]TJ/F66 8.9664 Tf 10.2393 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9962 Td[(GU)-109(S)]TJ/F31 8.9664 Tf 15.5612 0.9962 Td[(\051)-2422(=)]TJ/F46 8.9664 Tf 54.1909 0 Td[(f)]TJ/F44 8.9664 Tf 4.6077 0 Td[(G)]TJ/F31 8.9664 Tf 7.2158 0 Td[(\050)]TJ/F44 8.9664 Tf 3.5838 0 Td[(id)1(;)-172(can;)-172(na)-1(m)]TJ/F31 8.9664 Tf 49.1099 0 Td[(\051)]TJ/F46 8.9664 Tf 3.5837 0 Td[(g)]TJ/F72 8.9664 Tf 4.6077 0 Td[(,)]TJ/F31 8.9664 Tf -236.8618 -10.4608 Td[(\006\050)]TJ/F66 8.9664 Tf 10.2394 0 Td[(P)]TJ/F9 4.9813 Tf 4.2561 -0.9962 Td[(B)-47(i)1(oS)-51(QL)]TJ/F31 8.9664 Tf 26.7238 0.9962 Td[(\051)-285(=)]TJ/F46 8.9664 Tf 15.8709 0 Td[(f)]TJ/F44 8.9664 Tf 4.6077 0 Td[(B)]TJ/F31 8.9664 Tf 7.4197 0 Td[(\050)]TJ/F44 8.9664 Tf 3.5838 0 Td[(id)1(;)-172(nam)]TJ/F31 8.9664 Tf 30.5836 0 Td[(\051)]TJ/F46 8.9664 Tf 3.5838 0 Td[(g)]TJ/F72 8.9664 Tf 4.6077 0 Td[(,)]TJ/F31 8.9664 Tf 4.4832 0 Td[(\006\050)]TJ/F66 8.9664 Tf 10.2393 0 Td[(P)]TJ/F9 4.9813 Tf 4.2562 -0.9962 Td[(uB)-47(i)1(o)]TJ/F31 8.9664 Tf 16.2696 0.9962 Td[(\051)-285(=)]TJ/F46 8.9664 Tf 15.8709 0 Td[(f)]TJ/F44 8.9664 Tf 4.6077 0 Td[(U)]TJ/F31 8.9664 Tf 7.2366 0 Td[(\050)]TJ/F44 8.9664 Tf 3.5837 0 Td[(nam)-1(;)-172(can)]TJ/F31 8.9664 Tf 37.0861 0 Td[(\051)]TJ/F46 8.9664 Tf 3.5837 0 Td[(g)]TJ/F72 8.9664 Tf 4.6077 0 Td[(.)]TJ -214.3347 -10.4607 Td[(Among)-416(these)-417(peer)10(s)-416(ar)37(e)-417(mappings)]TJ/F46 8.9664 Tf 128.3218 0 Td[(M)]TJ/F31 8.9664 Tf 16.4226 0 Td[(=)]TJ/F46 8.9664 Tf 12.569 0 Td[(f)]TJ/F44 8.9664 Tf 4.6077 0 Td[(m)]TJ/F43 5.9776 Tf 8.1188 -0.9963 Td[(1)]TJ/F44 8.9664 Tf 4.151 0.9963 Td[(;)-172(m)]TJ/F43 5.9776 Tf 12.2146 -0.9963 Td[(2)]TJ/F44 8.9664 Tf 4.151 0.9963 Td[(;)-172(m)]TJ/F43 5.9776 Tf 12.2146 -0.9963 Td[(3)]TJ/F44 8.9664 Tf 4.151 0.9963 Td[(;)-172(m)]TJ/F43 5.9776 Tf 12.2145 -0.9963 Td[(4)]TJ/F46 8.9664 Tf 4.1511 0.9963 Td[(g)]TJ/F72 8.9664 Tf 4.6077 0 Td[(,)]TJ
ET
Q
1 0 0 1 295.992 36 cm
0 Tr
/QQAPF481df14d 12 Tf
0 0 0 rg
100 Tz
0 Ts
0 Tw 0 Tc
BT
1 0 0 1 0 0 Tm
(676)Tj
ET
1 0 0 1 0 0 cm
1 0 0 1 -295.992 -36 cm
endstream
endobj
158 0 obj
<<
/Type /Page
/Resources 157 0 R
/MediaBox [ 0 0 612 792 ]
/Parent 145 0 R
/Annots [ 161 0 R 165 0 R 166 0 R 167 0 R 168 0 R 169 0 R 170 0 R 171 0 R 172 0 R 173 0 R
174 0 R 175 0 R 176 0 R 177 0 R 178 0 R 179 0 R 181 0 R 195 0 R 196 0 R 197 0 R 198 0 R
199 0 R 204 0 R ]
/Contents [ 159 0 R ]
>>
endobj
156 0 obj <<
/Type /XObject
/Subtype /Form
/FormType 1
/PTEX.FileName (./figs/cdss.pdf)
/PTEX.PageNumber 1
/PTEX.InfoDict 205 0 R
/Matrix [0.00000000 -1.00000000 1.00000000 0.00000000 20.00650000 410.49350000]
/BBox [40.08000000 20.07350000 390.42000000 737.84700000]
/Resources <<
/ColorSpace <<
/Cs6 206 0 R
>>/Font << /TT2 207 0 R/TT4 208 0 R>>
/ProcSet [ /PDF /Text ]
/ExtGState <<
/GS1 209 0 R
>>>>
/Length 12327
/Filter /FlateDecode
>>
stream
x};-;r^
e&Sv u}-@G\3=&UzKzkMS>{y_J*-mX,=+N~}=|}ی-'p^=R{=FaXw;?Fgou&}?;DW^zW_]=miK4˻@ROUR^P-oқ^_9B2ǿAy"ߣ|OwƻweU_="q&J3}km{z8MHWth51hhwhFsS>W'&-L!\{d{ f̼osrwuք]vCi[jGQC4M :W
\3&o\niP yBw]ӛ֘K$.YZNNם|_z7IU{TL}$epl=*"399%a5_5w{4aS絔kVDV_ r{Ɲ&̇ZdM)ARs`sxZ (UOzLRs&2ݚ8y1?Sx 3ܽR|a:~6͆VUդhG*mDi((ƍ!n "F9;G݄[nMM=~vVG@ɀ7W
A'/{?ŧ K_l?ޙ +bU2DVO:գ6hC4tL8 b~y.]Y;J'RO:#,) z]ikpk?3Hb9+y-[`?X Z DΘ.\jN+tSo;P^̆:WbL,=bT;cFjFcz
VͮK
^ݳ:ٲrp uRU{Vy)f
V%0sL5!R_=)P
&QC"+U+G')Ԗ7zD+=ͩMܬAܑ.FK=x=&}0[!!
+~&SPԿ]6✑^;9FSho4u.
D`^UF+DL^\{,F6ALJ3Z0`n_=.zU#I<}K8˫hAk^K=) 8Z1UcaHAvT
FQՒ68[0Ah{vݾ:kNjJD>U`OvṚ:ڽ{hUn<%cAȁMePtSG&'3(@YȺE6a{6{%މR%fȅ1) f]ֶa+2Puۀl˾-Z2ndS
!p^ }VQY)z;?ޜmb;[Gc
3&}$EGt,d
k4K:i
5%I`ՖMoQ5Ǽº!%}r
ƩIlhDxj[%Nzyͻ7چE\I,o~n839<Z';0d5#F
hRCILAm
Y~ Xa\܍KƄ@^Ij34IZ9W#(~\/>z?p¢50 _j:s Y?O4f~af͗Qh1ͥp`DSrQ YQ73Y`8Eo+c$bc71:x"u~:pcj7эM:^}≽Nc)-Pz.;v('+KkG Wy,B2 qUq%CnXn\Y\Cj)y,]>QWO8E#|Ee)̪^WmeF57Z;;ZLXv,VE[ZB=_r5i6~91, ߴΠqhtw6|~^'nG%|rn^gccFɺ?C6ý`D7hK~Z""j(+R:
;%R/ ; ^1!Fk0aF]*Xdmf|:hRy'nht;e>J ; _0a
=Zum
V4nbN18D0!-6}%KgrAT~mA5H&ڼfj3>17/ޝ1ZeP~8 4wyT1Lc\G$C$c\|rj*F]A7.&2~O7wdQVf:ͩTH)!M# 7N2[燪z$-,=Gb{z7חMuh\uRԏ"FR(+(=GqUTbsp=o(!/誉,"GAK\RDCQJ
FGY,\-&!+:I*;_e
)M; )'VLlSt/Oi9,r
tՃv