CoopIS’01
Università di Ancona
Istituto di Informatica - Università degli studi di Ancona
COOPERATION STRATEGIES FOR
INFORMATION INTEGRATION
Maurizio Panti, Luca Spalazzi, Loris Penserini
{panti,spalazzi,[email protected]
September 6, 2001
1
CoopIS’01
Università di Ancona
Talk Overview
 Motivations and Goals
 Local strategies
 Cooperation strategies
the choice of partners
the choice of queries
the choice of answers
 Discussion
September 6, 2001
2
CoopIS’01
Università di Ancona
Motivation
 Information systems are collections of
information sources and information consumers:
 Distributed
 Heterogeneous
 at physical level
 at logical level
 at conceptual level (names and schemas)
 Dynamic
 changes of information sources or their schemas
 changes of information consumers or their needs
September 6, 2001
3
CoopIS’01
Università di Ancona
Goal
Rewriting a consumer’s query into queries to
specific information sources
when we have
a distributed, heterogeneous, and strongly
dynamic information system.
September 6, 2001
4
CoopIS’01
Università di Ancona
Related Work
Usually query rewriting and
integration systems adopt the
information
Mediator Architecture:
[TSIMMIS, Squirrel, WHIPS, Carnot, SIMS, Information
Manifold, Infomaster]
dynamic sources: systems are overloaded with
expensive updating operations;
dynamic consumers: systems do not perform
user profiling.
September 6, 2001
5
CoopIS’01
Università di Ancona
Information Source
wrapper source: w
a description logic as data modelling
and query language
1
Wrapper
publicati on
jour nal
confer ence
...
acm_trans
[e.g. C-Classic]
...
ieee_trans
...
publicati on =
ti tle.String
bookti tle .Str ing
publisher.Str ing
keyword.String
people =
pub.publ icati on
name.String
affil iation.Str ing





source query processing is based on
rewriting query using views over the
local source
DBMS
publicati on
ti tle bookti tle publisher
people
keyword
pub name affil iation
[adapted by Beeri, Levy, Rousset]
September 6, 2001
6
CoopIS’01
Università di Ancona
Mediator
mediated schema
a description
logic
as
data
modelling
mediator
and query
language
Thesaurus
[e.g. C-Classic]
Schema
query Mediated
processing
is based on
rewriting query using views
over the distributed sources
[adapted by Beeri, Levy, Rousset]
September 6, 2001
7
CoopIS’01
Università di Ancona
Rewriting query using views
Rewriting:
Composition
of rewriting
Retrieval:
Conjunction
of concepts
that
of retrieved
concepts
are maximally
contained
in the query
T
acm
journal
”}
acm_journal type.{“Trans
acm_trans
db
H= pub.(journal 
db)
ai
agents
J= pub.ai
pub.acm
pub.(ai db) I=pub..acm_journal
pub.(agents
db)
H J =pub.(ai db journal) K=pub.(agen
db
ts
)
rewrite:
retrieved
concepts:
{K, ∏
(Hdb)
∏ J)}
{I}
query: (view(K)∏view(I))U(view(H)∏view(J)∏view(I))
Q = pub.(ai
∏ pub.acm
September 6, 2001
8
CoopIS’01
Università di Ancona
Query Execution
source: w
source: w
2
db
object-oriented
active
...
ai
federated
...
.
planning
...
db = title.String
booktitle.String
type.String
year.Integer

people = pub.db
name.String
degree.String

.
3
cbr
...
...
.
ai = title.String
agents
...
booktitle.String
type.{“Trans”,”Magazine”}
publisher.String
year.Integer


.
people = pub.ai
name.String
position.String

...






...
#id pub
#id pub
…
…
…..
…..
#id pub
…
…..
Mediator M
rewrite:
rewrite:(view(K)∏view(I))U(view(H)∏view(J)∏view(I))
(view(K)∏view(I))U(view(H)∏view(J)∏view(I))
data:
#id pub
…
…..
…
… …..
…..
September 6, 2001
9
CoopIS’01
Università di Ancona
Local Failures
 In query rewriting:
the mediator is not able to rewrite (some or all
the components) of the input query.
 In query execution:
the mediator is not able to execute (some or
all the components) of the rewrited query.
September 6, 2001
10
CoopIS’01
Università di Ancona
Cooperation Strategies
all the
mediators
new
whole
mediators
mediator
original
single
failing
component
mediators
mediator
whole
succeeding
query Thesaurus
mediators
selected
rewriting
partner
single
answer concepts
component
data all the sources
whole
Mediated Schema
new sources
rewriting
single
source
component
failing
sources
succeeding
sources
September 6, 2001
11
CoopIS’01
Università di Ancona
Cooperation with Mediators
Asking for Rewriting
1: request
Mediator M
2: rewrite
Mediator N
3: query
4: data
W1
September 6, 2001
W2
W3
12
CoopIS’01
Università di Ancona
Cooperation with Mediators
Asking for Data
1: request
Mediator M
Mediator N
4: data
2: query
3: data
W1
September 6, 2001
W2
W3
13
CoopIS’01
Università di Ancona
Cooperation with Sources
Mediator M
Mediator N
1: request
2: rewrite
3: data
W1
September 6, 2001
W2
W3
14
CoopIS’01
Università di Ancona
Strategy Comparison
Partner
Type of
Answer
Efficiency
Effectiveness
No. of Messages
Redund. Recall Prec.
st
1 . time
Next time
Source (Sj) Rewriting
4s
2s
No
1
1
“
Data
2s
2s
No
1
1
Mediator (Ni) Rewriting 2m+2s’
2s’
Yes
No
1
“
Data
2m+2ms’ 2m+2ms’
No
No
1
m: number of mediators
s: number of sources
s’: number of sources that cooperate with Ni
September 6, 2001
15
CoopIS’01
Università di Ancona
Strategy Comparison
Query
Original Query
Q
Selected Concepts
Q’
Rewriting of selected concepts view(Q’)
SolN(view(Q’))
September 6, 2001
SolN(Q’)
Rewriting
Sol N(Q)
Sol N(Q’)
Sol N(view(Q’))
SolN(Q)
16
CoopIS’01
Università di Ancona
Conclusion
1st scenario (s ≈ m+s’)
 mediators can be used for user profiling,
 mediators can be used to solve name
heterogeneity and integrate data,
 in order to solve schema heterogeneity, for a
mediator the most efficient and effective
strategy is to directly cooperate with sources,
 in order to update its schemas, for a mediator
a “lazy” approach can be not appropriate.
September 6, 2001
17
CoopIS’01
Università di Ancona
Conclusion
2nd scenario (s >> m+s’)
 mediators can be used for user profiling,
 the most efficient strategy is the cooperation
with other mediators,
 cooperation with wrappers is useful only
when mediators are not able to rewrite a
given query,
 in order to update its schemas, for a mediator
a “lazy” approach is appropriate.
September 6, 2001
18
CoopIS’01
September 6, 2001
Università di Ancona
19
CoopIS’01
Università di Ancona
M’s Mediated Schema
Problem
Solution
(Query)
Rewriting
Information Sources
H=pub.
(pub.journal Π pub.db),
(pub.journal, w1),
(journalΠdb) (pub.ai Π pub.db)
(pub.db,w2),
(pub.ai,w3)
I=pub.
(pub.acm_trans),
(pub.acm_trans, w1),
acm_journal (pub.type.{“Trans”} Π
(pub.type.{“Trans”}, w3),
pub.publisher.{“ACM”}) (pub.publisher.{“ACM”}, w3)
J=pub.ai
(pub.keyword.{“AI”}),
(pub.keyword.{“AI”}, w1),
(pub.ai)
(pub.ai, w3)
K=pub.
(pub.keyword.{“Agents”} (pub.keyword.{“Agents”}, w1)
(agentsΠdb) Π pub.db),
(pub.db, w2),
(pub.agents Π pub.db)
(pub.agents, w3 )
September 6, 2001
20
CoopIS’01
Università di Ancona
Rewriting query using views
Composition of rewriting of retrieved concepts
view( pub.(ai ∏ db) ∏ pub.acm ) =
= view( pub.(ai ∏ db) ) ∏ view( pub.acm )
= (view(K)∏view(I))U(view(H)∏view(J)∏view(I))
= … ...
September 6, 2001
21
CoopIS’01
Università di Ancona
Rewriting query using views
=(view(K) ∏ view(I)) U (view(H) ∏ view(J) ∏ view(I))
={ (pub. keyword.{“Agents”} ∏ pub.db ∏
pub.acm_trans) ,
(pub.keyword.{“Agents”}∏pub.db ∏
pub.type.{“Trans”}∏pub.publisher.{“ACM”}),
(pub.agents ∏ pub.db ∏ pub.acm_trans) ,
(pub.agents ∏ pub.db ∏
pub.type.{“Trans”}∏pub.publisher.{“ACM”}),
(pub.journal ∏ pub.db ∏ pub. keyword.{“AI”} ∏
pub.acm_trans) ,
…}
September 6, 2001
22
CoopIS’01
Università di Ancona
Local Failure in Query Rewriting
T
acm
journal
”}
acm_journal type.{“Trans
acm_trans
db
H= pub.(journal 
db)
ai
agents
affiliation.{“Stanford”}
J= pub.ai
pub.(ai db) I=pub..acm_journal
pub.(agents
db)
H J =pub.(ai db journal) K=pub.(agen
db
ts
)
retrieved
Ø
rewrite
: concepts:
failure{K, (H ∏ J)}
query:
Q=pub.(ai∏db)∏affiliation.{“Stanford”}
September 6, 2001
23
CoopIS’01
Università di Ancona
Local Failure in Query Execution
source: w
source: w
2
db
object-oriented
active
...
ai
federated
...
.
planning
...
db = title.String
booktitle.String
type.String
year.Integer

people = pub.db
name.String
degree.String

.
3
cbr
...
...
.
ai = title.String
agents
...
booktitle.String
type.{“Trans”,”Magazine”}
publisher.String
year.Integer


.
people = pub.ai
name.String
position.String

...






...
#id pub
…
…..
#id pub
…
…..
Mediator M
rewrite:
rewrite:(view(K)∏view(I))U(view(H)∏view(J)∏view(I))
(view(K)∏view(I))U(view(H)∏view(J)∏view(I))
data: failure
September 6, 2001
24
CoopIS’01
Università di Ancona
Cooperation with Mediators
Asking for Rewriting
T
Mediator N
retrieved concepts:{pub.acm_tocl,
pub.ac
m
acm
acm_tods
pub.acm_tods}
acm_tocl
pub.acm_tocl
pub.acm_tod
s
Mediator M
rewrite:{view(pub.acm
query:
_tocl),view(pub.acm
pub.acm
_tods)}
September 6, 2001
25
CoopIS’01
Università di Ancona
Cooperation with Mediators
Asking for Rewriting
source: w
source: w
2
db
object-oriented
active
...
.
ai
federated
...
...
db = title.String
booktitle.String
type.String
year.Integer

people = pub.db
name.String
degree.String

.
...
3
planning
agents
...
booktitle.String
type.{“Trans”,”Magazine”}
publisher.String
year.Integer



cbr
...
...
.
ai = title.String
.
people = pub.ai
name.String
position.String






...
Mediator M
rewrite:{view(pub.acm_tocl),view(pub.acm_tods)}
rewrite:{view(pub.acm_tocl),view(pub.acm_tods)}
data:
#id pub
…
…..
…
… …..
…..
September 6, 2001
26
CoopIS’01
Università di Ancona
Cooperation with Mediators
Asking for Data
T
Mediator N
retrieved
rewriteconcepts
:{view(pub.acm
:{pub.acm_tocl,
_tocl),view(pub.acm
pub.acm_tods}
_tods)}
pub.ac
m
acm
acm_tods
acm_tocl
pub.acm_tocl
pub.acm_tod
s
Mediator M
query:
September 6, 2001
pub.acm
27
CoopIS’01
Università di Ancona
Cooperation with Mediators
Asking for Data
T
Mediator N
rewrite:{view(pub.acm_tocl),view(pub.acm_tods)}
rewrite:{view(pub.acm_tocl),view(pub.acm_tods)}
data:
#id acm
pub
pub.ac
…
…..
m
…
…..
… …..
acm_tods
pub.acm_tocl
acm_tocl
source: w
pub.acm_tod
s
source: w
2
db
object-oriented
active
...
.
federated
...
...

people = pub.db
name.String
degree.String

...
September 6, 2001
ai
db = title.String
booktitle.String
type.String
year.Integer
.
3
planning
agents
...
booktitle.String
type.{“Trans”,”Magazine”}
publisher.String
year.Integer



cbr
...
...
.
ai = title.String
.
people = pub.ai
name.String
position.String






...
28
CoopIS’01
Università di Ancona
Cooperation with Mediators
Asking for Data
T
Mediator N
rewrite:{view(pub.acm_tocl),view(pub.acm_tods)}
rewrite:{view(pub.acm_tocl),view(pub.acm_tods)}
data:
#id acm
pub
pub.ac
…
…..
m
…
…..
… …..
acm_tods
acm_tocl
pub.acm_tocl
pub.acm_tod
s
Mediator M
rewrite:{view(pub.acm_tocl),view(pub.acm_tods)}
query:
pub.acm
data:
#id pub
…
…..
…
… …..
…..
September 6, 2001
29
CoopIS’01
Università di Ancona
Cooperation with Sources
source: w
source: w
source: w
2
object-oriented
active
...
.
.
people = pub.db
...
name.String
degree.String
source: w
conference
ai
federated
...
db = title.String
booktitle.String
type.String
year.Integer
4
3
db
...





conference
...
...
planning
cbr
...
.
ai = title.String
booktitle.String
type.{“Trans”,”Magazine”}
publisher.String
year.Integer
acm_ccs
.

acm

journal
journal
...
acm_ccs
acm_jacm acm_trans
...
.

acm_tods
acm_ccs = acm
booktitle.{“CCS”}
type.{“Proc”}
acm_jacm = acm

booktitle.{“JACM”}
...acm_tocl


acm_jacm acm_trans
.

...
people = pub.ai
name.String
position.String
...
acm
agents
4


...
.
acm_tods = acm

journal
acm_trans


booktitle.{“TODS”}
.
acm_tocl = acm_trans
acm_tods ... booktitle.{“TOCL”}
acm_tocl

...
.
acm_ccs = acm

retrieved:{pub.acm_ccs,pub.acm_jacm,pub.acm_tods}
booktitle.{“CCS”}

Mediator M
type.{“Proc”}
acm_jacm = acm

booktitle.{“JACM”}
.
journal

.
rewrite:{view(pub.acm_ccs),view(pub.acm_jacm),
acm_tods = acm  acm_trans 
view(pub.acm_tods)} booktitle.{“TODS”}
.
acm_tocl = acm_trans

data:
Mediator M#id pub
... booktitle.{“TOCL”}
…
…..
…
query:
pub.acm
… …..
…..
September 6, 2001
30
CoopIS’01
Università di Ancona
Redundancy
Cn(M)
mediated schema of M
after n interactions with N
C(N)
mediated schema of N
card (Cn( M )  C ( N ))
card (C ( N ))
September 6, 2001
31
CoopIS’01
Università di Ancona
Recall
Cn(M)
mediated schema of M
after n interactions with S1, … Sn
n
information need of a consumer
(a view of S1, … Sn )
card(Cn( M ) n )
card(n )
September 6, 2001
32
CoopIS’01
Università di Ancona
Precision
Cn(M)
mediated schema of M
after n interactions with S1, … Sn
n
information need of a consumer
(a view of S1, … Sn )
card(Cn( M ) n )
card(Cn( M ))
September 6, 2001
33
CoopIS’01
Università di Ancona
N’s Mediated Schema
Problem
Solution
(Query)
Rewriting
Information Sources
pub.
(pub.booktitle.{“TODS”} Π (pub.booktitle.{“TODS”}, w4),
acm_tods pub.acm)
(pub.acm , w4)
pub.
(pub.booktitle.{“TOCL”} Π (pub.booktitle.{“TODS”}, w4),
acm_tocl
pub.acm_trans)
(pub.acm_trans , w1)
September 6, 2001
34
CoopIS’01
Università di Ancona
M’s Mediated Schema
(updated)
Problem
Solution
(Query)
Rewriting
Information Sources
H
(pub.journal Π pub.db),
(pub.journal, w1),
(pub.ai Π pub.db)
(pub.db,w2),
(pub.ai,w3)
I
(pub.acm_trans),
(pub.acm_trans, w1),
(pub.type.{“Trans”} Π
(pub.type.{“Trans”}, w3),
pub.publisher.{“ACM”}) (pub.publisher.{“ACM”}, w3)
J
(pub.keyword.{“AI”}),
(pub.keyword.{“AI”}, w1),
(pub.ai)
(pub.ai, w3)
K
(pub.keyword.{“Agents”} Π (pub.keyword.{“Agents”}, w1)
pub.db),
(pub.db, w2),
(pub.agents Π pub.db)
(pub.agents, w3 )
pub.acm (pub.booktitle.{“TODS”} Π (pub.booktitle.{“TODS”}, w4),
pub.acm)
(pub.acm , w4)
September 6, 2001
35
CoopIS’01
Università di Ancona
M’s Mediated Schema
(updated)
Problem
Solution
(Query)
Rewriting
Information Sources
H
(pub.journal Π pub.db),
(pub.journal, w1),
(pub.ai Π pub.db)
(pub.db,w2),
(pub.ai,w3)
I
(pub.acm_trans),
(pub.acm_trans, w1),
(pub.type.{“Trans”} Π
(pub.type.{“Trans”}, w3),
pub.publisher.{“ACM”}) (pub.publisher.{“ACM”}, w3)
J
(pub.keyword.{“AI”}),
(pub.keyword.{“AI”}, w1),
(pub.ai)
(pub.ai, w3)
K
(pub.keyword.{“Agents”} Π (pub.keyword.{“Agents”}, w1)
pub.db),
(pub.db, w2),
(pub.agents Π pub.db)
(pub.agents, w3 )
pub.acm (pub.acm_tods)
(pub.acm_tods , N)
September 6, 2001
36
CoopIS’01
Università di Ancona
M’s Mediated Schema
(updated)
Problem
Solution
(Query)
Rewriting
Information Sources
H
(pub.journal Π pub.db),
(pub.journal, w1),
(pub.ai Π pub.db)
(pub.db,w2),
(pub.ai,w3)
I
(pub.acm_trans),
(pub.acm_trans, w1),
(pub.type.{“Trans”} Π
(pub.type.{“Trans”}, w3),
pub.publisher.{“ACM”}) (pub.publisher.{“ACM”}, w3)
J
(pub.keyword.{“AI”}),
(pub.keyword.{“AI”}, w1),
(pub.ai)
(pub.ai, w3)
K
(pub.keyword.{“Agents”} Π (pub.keyword.{“Agents”}, w1)
pub.db),
(pub.db, w2),
(pub.agents Π pub.db)
(pub.agents, w3 )
pub.acm (pub.acm_ccs) ,
(pub.acm_ccs , w4) ,
(pub.acm_jacm) ,
(pub.acm_jacm , w4) ,
(pub.acm_tods)
(pub.acm_tods , w4)
September 6, 2001
37
CoopIS’01
Università di Ancona
Cooperation with Mediators
Theorem.
Cn(M)
mediated schema of M
after n interactions with N
C(N)
mediated schema of N
redundancy:
September 6, 2001
card (Cn(M) C(N))
lim
=1
n 
card (C(N))
38
CoopIS’01
Università di Ancona
Cooperation with Mediators
Theorem.
Cn(M)
mediated schema of M
after n interactions with N
n
information need of
(a view of S1, … Sn )
recall:
a
consumer
card (Cn(M) n )
lim
1
n 
card (n )
card (Cn(M) n )
precision: lim
n 
card(Cn(M))
September 6, 2001
indeterminate
39
CoopIS’01
Università di Ancona
Cooperation with Sources
Theorem.
Cn(M)
mediated schema of M
after n interactions with S1, … Sn
n
information need of a consumer
(a view of S1, … Sn )
recall:
card (Cn(M) n )
lim
=1
n 
card (n )
card (Cn(M) n )
=1
precision: lim
n 
card(Cn(M))
September 6, 2001
40
Descargar

Metodologie OO