Databases Reference
In-Depth Information
Schema
Corresponding circuit
r(project) = k
project: tuple
name: string
amount: real
company: string
flat structure
circ(company)
circ(name)
circ(amount)
r(projectDB) = 3 k
projectDB: set
r(project) = 2 k
project: tuple
name : string
amount: real
company: tuple
r(company) = k
cname: string
budget: real
circ(name)
circ(amount)
nested structure
circ(cname)
circ(budget)
Fig. 9.9
Examples of circuits for flat and nested structures
circ
.n
0
/;
circ
.n
1
/;:::
circ
.n
k
/
between ground and an intermediate circuit node
n
top
, and then adding a resistor of value
r.n/
from node
n
top
to the output. Exam-
ples of such transformation are illustrated in Fig.
9.9
. Note that the circuit mapping
function makes the resulting circuits isomorphic to the original trees.
In Spicy, similarly to the
opaque
schema matching [
Kang and Naughton 2003
],
labels are ignored by the circuit mapping function, and values are basically treated
as uninterpreted strings. Furthermore, values correspond to alphanumeric data in
the underlying Spicy data model. The circuit features discussed above reflect this
choice. However, the circuit model is sufficiently flexible to allow the treatment of
special data, like large texts or multimedia, as discussed in other orthogonal usage
of circuits [
Palmer and Faloutsos 2003
].
Given two trees
t
1
and
t
2
, a measure of their similarity can be computed by map-
ping
t
1
and
t
2
to the corresponding circuits,
circ
.t
1
/;
circ
.t
2
/
, as depicted in Fig.
9.9
,
solving the two circuits to determine their currents and voltages, and choosing a
number of descriptive features of the corresponding circuits,
f
0
;f
1
;:::f
i
. A notion
of
comparator
for each feature
f
i
as a module that computes the index of similar-
ity
i
between the two structures with respect to feature
f
i
is defined in Spicy as
follows:
i
D
f
i
.
circ
.t
2
///=f
i
.
circ
.t
1
//
. Finally, the overall sim-
ilarity of the two trees is computed based on the values of
0
;
1
;:::
i
abs
.f
i
.
circ
.t
1
//
[
Bonifati
et al.
2008a
].
