Transcript 14. Interoperability

14. Interoperability
Database interoperability --Is the problem of making the data and queries of
one database system usable to the users of
another database system.
Requires that the data models used in them
have the same data expressiveness.
Data expressiveness --Database written in the data model used in Δ1
can be translated into an equivalent database in
the data model of Δ2
1
14.1.1 Constraint and Extreme Point Data Models
Each database in the rectangles data
model and Worboys’ data model is
equivalent to a constraint database with
some suitable types of constraints.
Theorem:
Any rectangle relation R is equivalent to a
constraint relation C with only inequality
constraints between constants and
variables.
2
House2
ID X
Y
T
1
X
Y
T
2<=x, x<=6, 3<=y, y<=6, 100<=t, t<=200
2
X
Y
T
8<=x, x<=11, 3<=y, y<=7, 150<=t, t<=300
3
X
Y
T
2<=x, x<=4, 5<=y, y<=10, 250<=t, t<=400
3
X
Y
T
2<=x, x<=10, 8<=y, y<=10, 250<=t, t<=400
3
Theorem:
Any Worboys relation W is equivalent to a
constraint relation C with two spatial
variables with linear constraints and one
temporal variable with inequality constraints.
4
Example:
ID
X Y T
Fountain
x
y
t
x = 10, y = 4, 1980 <= t, t <= 1986
Road
x
y
t
5 <= x, x <= 9, y = -x+15, 1995 <= t, t <=1996
Road
x
y
t
x = 9, 3 <= y, y <= 6, 1995 <= t, t <=1996
Tulip
x
y
t
2 <= x, x <= 6 ,y <= 9-x, 3 <= y, y <= 7,
1975 <= t, t <= 1990
Park
x
y
t
1 <= x, x <= 12, 2 <= y, y <= 11, 1974 <= t, t <= 1996
Pond
x
y
t
x >= 3, y >= 5, y >= x-1, y <= x+5, y <= -x+13,
1991 <= t, t <= 1996
5
14.1.2 Constraint and Parametric Extreme Point Data Models
Theorem:
Any parametric rectangle relation R with
m-degree polynomial parametric functions
of t is equivalent to a constraint relation C
with inequality constraints in which the
spatial variables are bound from above or
below by m-degree polynomial functions of
t and t is bounded from above and below
by constants.
6
Bomb2
X
Y
T
x
y
t
t <= x, x <= t+1, t <= y, y <= t+1,
100 - 9.8 t2 <= z, z <= 102 - 9.8t2,
0 <= t, t <= 3.19
7
Theorem:
Any parametric 2-spaghetti relation W with
quotient of polynomial functions of t is
equivalent to a constraint relation C with
polynomial constraints over the variables x, y,
and t such that for each instance of t all the
constraints are linear.
8
Net2
Example:
X
Y
T
x
y
t
y <= x - t,
y (t+2) >= x t - t2 - 2t + 6,
y (t+2) >= x (t-2) – t2 + 16
9
Theorem:
Any periodic parametric 2-spaghetti
relation with periodic parametric functions
of t is equivalent to a constraint database
relation with periodic constraints over the
variables x, y, t such that for each instance
of t all the constraints are linear.
10
Example:
Tide2
X Y
T
x
y
t
1 <= x, x <= 3, 1 <= y, y <= 4, 0 <= t’, t’ <=5.75,
y >= x - t’ + 3
x
y
t
1 <= x, x <= 3, 1 <= y, y <= 4, 5.75 <= t’, t’<=11.5,
y >= x + t’ - 8.5
11
14.1.3 Parametric and Geometric Transformation Models
Theorem:
Let [ai, bi] for 1<=i<=d be any set of d intervals with ai <
bi, Let
R=(Пi=1d[Xi[, Xi]], [from, to]) be any normal form
parametric rectangle. Let G=(Пi=1d[ai, bi], [from, to], f) be
any normal form geometric transformation object where f
is definable as the system of equations xi=gixi + hi where
gi and hi are functions of t for 1<=i<=d. Then R and G are
equivalent if:
12
Theorem:
Any parametric 2-spaghetti relation W with
m-degree polynomial functions of t is
equivalent to a two-dimensional
parametric affine transformation object
relation G with m-degree polynomial
functions of t and a polygonal reference
object.
13
Constraint
(Parametric)
Extreme
Point
(Parametric)
Geometric
Transformation
Inequality
Rectangles
Identity transformation
rectangle reference object
x, y linear t inequality Worboys
Identity transformation
polygon reference object
Each xi bounded by
a function of t
Parametric rectangles
Parametric scaling +translation
rectangle reference object
x, y linear for each t
Parametric 2-spaghetti Parametric affine motion
polygon reference object
14
14.1.4 Constraint and Geometric Transformation Models
Theorem:
Any d-dimensional parametric affine
transformation object relation with mdegree polynomial function soft t can be
represented as a (d+1) dimensional
constraint relation with polynomial
constraints
15
14.2 Query Interoperability
14.2.1 Query interoperability via Query Translation
Figure 14.4.
14.2.2 Query Interoperability via Data Translation
Figure 14.5
16
Theorem:
All the spatiotemporal models appearing in
Figure 14.3 are closed under intersection,
complement, union, join, projection, and
selection with inequality constraints that
contain spatiotemporal variables and
constants.
17
14.2.3 Query Interoperability via a common basis
Figure 14.7
Precise data translation --We can translate each of the spatiotemporal
data models of Chapter 13 into a
syntactically restricted type of constraint
database. We can also easily compare the
expressive power of several different data
models by translating them to restricted
types of constraint databases
18
Advantages of common basis
Easy query translation --Many spatiotemporal query languages
contain numerous spatial operators and
other special language features.
Safety and complexity --By knowing the allowed syntax of the
constraints in the common basis, we can
gain valuable information about the safety
and computational complexity of queries.
19
14.2.4 Intersection of Linear Parametric rectangles
Theorem:
Whether two d-dimensional linear
parametric rectangles intersect can be
checked in O(d) time.
20