Query Processing in
Multidatabase Systems
Query Processing in Three Steps
1. Global query is
decomposed into local
queries
Local Schema 1 Local Schema 2 Local Schema 3
2. Each local query is Translator 1 Translator 2 Translator 3
translated into
queries over the InS1 InS2 InS3
corresponding local
database system
INTEGRATOR
3. Results of the local
queries are combined
into the answer GCS
Outline
• Overview of major query processing
components in multidatabase systems:
– Query Decomposition
– Query Translation
– Global Query Optimization
• Techniques for each of the above
components
Global Query
Overview
Query decomposition &
global optimization
SQ1 SQ2
... SQn PQ1 … PQ1
Query
translator 1
Query
translator 2
… Query
translator n
SQi - export schema
subquery in global query
language
TQ1 TQ2 ... TQn
TQi - target query (local
subquery) in local query
language
PQi - postprocessing query
used to combine results
DB1 DB2 DBn returned by subqueries
to form the answer
Assumptions
• We use the object-oriented data model to
present a query modification algorithm
• To simplify the discussion, we assume that
there are only two export schemas:
ES1 ES2
Emp1: SSN Emp2: SSN
Name Name
Salary Salary
Age Rank
Definitions
• type: Given a class C, the type of C denoted
by type(C ), is the set of attributes defined
for C and their corresponding domains.
• extension: the extension of C, denoted by
extension(C ), is the set of instances
contained in C.
• world: the world of C, denoted by world(C ),
is the set of real-world objects described by
C.
Review: Outerjoin
The outerjoin of relation R1 and R2 is
the union of three components:
– the join of R1 and R2,
– dangling tuples of R1 padded with null
values, and
– dangling tuples of R2 padded with null
values.
Outerjoin Example
Emp1 EmpO
OID SSN Name Salary Age OID SSN Name Salary Age Rank
3 6789 Smith 90,000 40
1 2222 Ahad 98,000 null S. Mgr.
4 4321 Chang 62,000 30
2 7531 Wang 95,000 mull S. Mgr.
5 8642 Patel 75,000 35
Incon-
3 6789 Smith sistent
40 Mgr.
Emp2 4 4321 Chang 62,000 30 null
OID SSN Name Salary Rank 5 8642 Patel 75,000 35 null
1 2222 Ahad 98,000 S. Mgr.
2 7531 Wang 95,000 S. Mgr.
3 6789 Smith 25,000 Mgr.
Schema Integration - Outerjoin
Two classes C1 and C2 can be integrated
by equi-outerjoining the two classes on
the OID to form a new class C.
– extension(C ) = extension(C1 ) ⋈o extension(C2 )
– type(C ) = type(C1 ) ⋃ type(C2 )
– world(C ) = world(C1 ) ⋃ world(C2 )
Schema Integration - Generalization
Two classes C1 and C2 can be integrated by
generalizing the two classes to form the
superclass C.
• type(C ) = type(C1 ) ⋂ type(C2 )
• extension(C ) = ᅲtype(C) [extension(C1 ) ⋃o extension(C2 )]
• world(C ) = world(C1 ) ⋃ world(C2 )
Generalization Example
Emp1: SSN Emp2: SSN EmpG: SSN
Name Name Name
Salary Salary Salary
Age Rank
• Emp1 and Emp2 will also appear in the
global schema since not all information in
Emp1 and Emp2 is retained in EmpG
EmpG SSN
Name
Salary
Emp1 Age Rank Emp2
Inconsistency Resolution
• The schema integration techniques
work as long as there is no data
inconsistency
• If data inconsistency may exist, then
aggregate functions may be used to
resolve the problem.
Inconsistency Resolution Example
Export Schemas Integrated Schemas
Emp1: SSN Emp2: SSN EmpG: SSN EmpO: SSN
Name Name Name Name
Salary Salary Salary Salary
Age Rank Age
Rank
Sample Aggregate Functions:
[Link] = [Link], if EmpG is in world(Emp1)
= [Link], if EmpG is in world(Emp2) – world(Emp1)
[Link] = [Link], if EmpG is in world(Emp1) – world(Emp2)
= [Link], ifEmpG is in world(Emp2) – world(Emp1)
= Sum([Link], [Link]), if EmpG is in world(Emp1) ⋂ world(Emp2)
[Link] = [Link], if EmpO is in world(Emp1)
= Null, if EmpO is in world(Emp2) – world(Emp1)
[Link] = [Link], if EmpO is in world(Emp2)
= Null, if EmpO is in world(Emp1) – world(Emp2)
Query Modification (1)
Global Select [Link], [Link]
Query From EmpO
Where [Link] > 80,000 AND
[Link] > 35
STEP 1: Obtain a partition of world(EmpO) based on the
function used to resolve the data inconsistency.
Strategy 1 (based on Salary) Strategy 2 (based on Age)
part. 1: world(Emp1) – world(Emp2) part. 1: world(Emp1)
part. 2: world(Emp2) – world(Emp1) part. 2: world(Emp2) –
part. 3: world(Emp1) ⋂ world(Emp2) world(Emp1)
world(Emp1) world(Emp1)
3 2 2
1 1
world(Emp2) world(Emp2)
We use Strategy 1 since it is the finest partition among all the partitions.
Query Modification (2)
Strategy 1: Strategy 2:
world(Emp1) world(Emp1)
2 2
1 1
world(Emp2) world(Emp2)
Use finer partition:
world(Emp1)
3 2
1
world(Emp2)
Query Modification (3)
Global Query: part. 1: Select [Link]
From Emp1
Select [Link], [Link]
Where [Link] > 80,000 AND
From EmpO [Link] > 35 AND
Where [Link] > 80,000 AND [Link] NOT IN
[Link] > 35 (Select [Link]
From Emp2)
Partition:
part. 2: This subquery is discarded because
world(Emp1) [Link] is Null.
3 2 part. 3: Select Emp1. Name, [Link]
1 From Emp1, Emp2
world(Emp2) Where Sum([Link],
[Link]) > 80,000 AND
STEP 2: Obtain a query for [Link] > 35 AND
[Link] = [Link]
each subset in the
chosen partition.
Query Modification (4)
STEP 3: Some resulting query may still reference
data from more than one database. They need to be
further decomposed into subqueries and possibly also
postprocessing queries
Select [Link]
From Emp1
Before STEP 3: Where [Link] > 80,000 and
Select [Link] Emp1. Age > 35 and
From Emp1 [Link] NOT IN X
Where [Link] > 80,000 and
Emp1. Age > 35 and
[Link] NOT IN X
(Select [Link]
From Emp2)
Insert INTO X
Select [Link]
From Emp2)
Query Modification (5)
STEP 4: It may be desirable to reduce
the number of subqueries by
combining subqueries for the same
database.
Query Translation (1)
IF Global Query Language ≠
Local Query Language
THEN Export Local
Schema Translator Query
Subquery Language
Query Translation (2)
IF the source query language has a higher
expressive power THEN EITHER
– Some source queries cannot be translated; or
– they must be translated using both
• the syntax of the target query language, and
• some facilities of a high-level programming language.
Example: A recursive OODB query may not be
translated into a relational query using SQL
alone.
Translation Techniques (1)
CASE 1: A single target query is generated
IF the target database system has a query
optimizer
THEN the query optimizer can be used
to optimize the translated query
ELSE the translator has to consider the
performance issues
Translation Techniques (2)
CASE 2: A set of target queries is needed.
• It might pay to have the minimum number of
queries
– It minimizes the number of invocations of the target
system
– It may also reduce the cost of combining the partial
results
• It might pay for a set to contain target queries
that can be well coordinated
– The results or intermediate results of the queries
processed earlier can be used to reduce the cost of
processing the remaining queries
Relation-to-OO Translation
OODB Schema:
Auto Company People City
OID OID OID OID
Color Name Name Name
Manufacturer Profit Hometown State
Headquarter Automobile
President Age
Equivalent Relational Schema:
Auto(Auto-OID, Color, Company-OID)
Company(Company-OID, Name, Profit, City-OID, People-OID)
People(People-OID, Name, Age, City-OID, Auto-OID)
City(City-OID, Name, State)
Relational-to-OO Example (1)
Global Query: Relational Predicate Graph:
Select Auto1.*
From Auto Auto1, Auto Auto2,
Company, People, Company-OID
City City1, City City2 Auto1 Company
Where [Link]-OID =
Company,Company-OID AND ID
O People-OID
[Link]-OID = ity
-
C
[Link]-OID AND
[Link] = 52 AND
[Link]-OID = City1 People
[Link]-OID AND Age=52
[Link] = “red” AND
[Link]-OID = D
-OI Auto-OID
[Link]-OID AND C ity
[Link] = [Link] AND
[Link]-OID =
[Link]-OID
Auto2
City2 Color=red
Relational-to-OO Example (2)
OO Predicate Graph: Auto1
Company-OID
Company
D
y -OI People-OID
Cit
City1 People
Age=52
D
OI Auto-OID
y-
Cit
Auto2
City2 Color=red
OO Query:
Where [Link] = red AND
[Link] = 52 AND
[Link] =
[Link]
Global Query Optimization (1)
• A query obtained by the query modification
process may still reference data from
more than one database.
Example: part. 3 (i.e., world(Emp1) ⋂ world(Emp2))
on page 108
Select [Link], [Link]
From Emp1, Emp2 /* access two databases
Where sum([Link], [Link]) > 80,000 AND
[Link] > 35 AND
[Link] = [Link]
→ Some global strategy is needed to process such queries
Global Query Optimization (2)
• Select [Link], [Link]
From Emp1, Emp2 /* access two databases
Where sum([Link], [Link]) > 80,000 AND
[Link] > 35 AND
[Link] = [Link]
→ Some global strategy is needed to process such queries
Site 1 Site 2
Emp1 Emp2 Site 1 Site 2
Emp1 Emp2
form form
result result
form
result
Emp1 Emp1
Site 3
Site 2 Site 1
Data Inconsistency
• If C is integrated from C1 and C2 with no
data inconsistency on attribute A, then
бA op a (C) = бA op a (C1) ⋃ бA op a (C2)
• If A has data inconsistency, then the
above equality may no longer hold.
Example: Consider the select operation
б[Link] > 100,000 (EmpO)
the correct answer should have the
record for Smith. However, the above
equation will return an empty set !
Data Inconsistency - Solution
Express an outerjoin (or a generalization) as
outer-unions as follows:
C1 ⋈o C2 = C1-O ⋃o C2-O ⋃o (C1-C ⋈OID C2-C)
C1-O: Those tuples of C1 that have no matching
tuples in C2 (private part)
C1-C: Those tuples of C1 that have matching tuples
in C2 (overlap part)
бA op a (C1 ⋈o C2 ) = бA op a (C1-O) ⋃o бA op a (C2-O)
⋃o бA op a (C1-C ⋈ C2-C)
Distribution of Selections (1)
бA op a (C1 ⋈o C2 ) = бA op a (C1-O) ⋃o бA op a (C2-O)
⋃o бA op a (C1-C ⋈ C2-C)
When can we dustribute
б over ⋈ ? Expensive operation
Distribution of Selection (2)
Four cases were identified when all arguments of the aggregate
function are non-negative
1. f(A1,A2) op a ≡ A1 op a AND A2 op a:
бA op a (C1-C ⋈ C2-C) = бA op a (C1-C) ⋈ бA op a ( C2-C)
Example: max([Link], [Link]) < 30K
≡ [Link] < 30K AND
[Link] < 30K
2. f(A1,A2) op a ≡ f(A1 op a, A2 op a) op a:
бA op a(C1-C ⋈ C2-C) = бA op a(бA1 op a(C1-C) ⋈ бA2 op a(C2-C))
Example: sum([Link], [Link]) < 30K
≡ sum([Link] < 30K,
[Link] < 30K) < 30K
Distribution of Selection (3)
3. f(A1,A2) op a ≡ f(A1 op’ a, A2 op’ a) op a:
бA op a(C1-C ⋈ C2-C) = бA op a(бA1 op’ a(C1-C) ⋈
бA2 op’ a(C2-C))
Example: sum([Link], [Link]) = 30K
≡ sum([Link] ≤ 30K,
[Link] ≤ 30K) = 30K
4. No improvement is possible:
Example: sum([Link], [Link]) > 30K
Distribution Rules for б over ⋈
бA op a(C1-C ⋈ C2-C)
op
A > ≥ ≤ < = ≠ in Not in
sum(A1, A2) 4 4 2 2 3 4 4 4
avg(A1, A2) 4 4 2 2 3 4 4 4
max(A1, A2) 4 4 1 1 3 4 4 4
min(A1, A2) 1 1 4 4 3 4 4 4
Problem in Global Query
Optimization (1)
Important information about local entity sets that is
needed to determine global query processing plans
may not be provided by the local database systems.
– Example: cardinalities
availability of fast access paths
– Techniques:
• Sampling queries may be designed to collect statistics
about the local databases.
• A monitoring system can be used to collect the
completion time for subqueries. This can be used to
better estimate subsequent subqueries.
Problems in Global Query
Optimization (2)
• Different query processing algorithms may have been used in
different local database systems.
→ Cooperation across different systems difficult
Examples: Semijoin may not be supported on some
local systems.
• Data transmission between different local database systems
may not be fully supported.
Examples:
– A local database system may not allow update operations
– For many nonrelational systems, the instances of one entity set are more
likely to be clustered with the instances of other entity sets. Such
clustering makes it very expensive to extract data for one entity set.
→ Need more sophisticated decomposition algorithms.