Transcript Paper Contents (Cont.)

Temporal Database
Paper Reading Report
資工所 在職碩一
P96922001
莊浚銘
Reporting Contents
1. Paper Subject & Author
2. Study Motivation
3. Paper Contents
4. Conclusion
Paper Subject & Author
• Subject：Temporal Aggregates and Temporal Universal
Quantification in Standard SQL
• Published Date： 2006/06
• Author：Esteban Zimanyi, Dept. of Computer &
Network Engineering, Universite Libre de Bruxelles
• Web Site：
http://www.sigmod.org/sigmod/record/issues/0606/p16article-zimanyi.pdf
Study Motivation
To understand :
• How a SQL database is extended with temporal
functionality support
• How temporal operations are implemented in standard
SQL
• What problems can be solved by temporal operations
Paper Contents
•No consensus on TSQL standard : Several proposed
temporal extensions of SQL, such as “TSQL2” and
“SQL/Temporal”, have NOT reached acceptance in the
standardization committees.
•Standard SQL dominant : Nowadays, database
practitioners MUST STILL use standard SQL for
manipulating time-varying information. Querying and
updating time-varying data using standard SQL is STILL a
challenging task.
Paper Contents (Cont.)
•Little temporal support : Current Database Management
Systems, like SQL, provide little support for dealing with
time-varying data. They only provide standard data types
for encoding dates or timestamps.
•What this paper aims for : With regard to using standard
SQL to manipulate temporal data, there has been studies
showing how to define temporal join, projection and
difference, but NOT how to deal with temporal aggregates
as well as temporal universal quantifiers, this paper is
devoted to the later issue.
Paper Contents (Cont.)
•Temporal DB Schema : Temporal database design in
standard SQL
Non-temporal
temporal
temporal
temporal
temporal
All circled columns are with the same data-type named “date” !
That means it’s hard to distinguish temporal tables simply by DB data-type.
Paper Contents (Cont.)
•Temporal DB Schema(Cont.) :
A closed-open
representation
is used!
即 [ d1 , d2 )
Note that a special date ‘3000-01-01’ is used to denote currently-valid
rows ! Also, data redundancy is inevitable before we coalesce it.
Paper Contents (Cont.)
•Temporal Join : A temporal join is needed when the tables
to be combined are temporal.
•Question1: How do the salary and the affiliation of
employees affect each other?
?
We need to temporal join both tables because they are all
temporal!
Paper Contents (Cont.)
•Solution for Question1: To express a temporal join in SQL,
we need FOUR select statements and complex inequality
predicates verifying that the validity periods of the rows to
be combined intersect.
Should be FIVE?
via Temporal Join
Paper Contents (Cont.)
To get all intersected (即inter運算) intervals
S
DURING
A
S
OVERLAP
A
S
OVERLAP
A
S
DURING
A
S
(3) UNION
instead?
(1) “=”
Missing?
(2) EQUIVALENT
Missing?
A
via Temporal Join
Paper Contents (Cont.)
To get all intersected (即inter運算) intervals
Incorrect ? for …
via Temporal Join
Paper Contents (Cont.)
To get all intersected (即inter運算) intervals
•Another solution for Question1: Note that temporal join
can be written in a single statement, either using a Case
statement or using functions.
Get the intersection of
the validity periods by
calling predefined SQL
functions!
Ensure the two validity
periods overlap
Paper Contents (Cont.)
•Temporal Coalescing : A complex and costly operation in
SQL, similar to temporal Folding,Nesting and Packing
proposed by other researchers.
DNumber is projected out
to get employees’ total
service life span!
Both can be coalesced!
020101
Paper Contents (Cont.)
030601 030801
000101
Gaps = Tuples’ date differences before performing joining
•Temporal Coalescing Realization : Can be implemented in
The Gaps are all 0 in this case, so
SQL as follows:
the 3rd tuple is what we want. But
how to erase unwanted tuples?
1st Filtering
2nd Filtering
020101
020601
030601 030801
790101
Gap>0!
Gap
Paper Contents (Cont.)
•Temporal Coalescing Realization(Cont.) : Try the SQL
1st “Not Exists”
Filtering (to erase
tuples containing
the Gap period!)
2nd “Not Exists”
Filtering (to erase
tuples following or
preceding the
original ones!)
Final Result !
Paper Contents (Cont.)
•Temporal Aggregation : We need a three-step process to
implement temporal aggregation. That process is :
(i) Identifying the periods of time in which all values are
constant.
(ii) Computing the aggregation over these periods.
(iii) Coalescing the result.
(i)
Identifying the periods of time in
which all values are constant.
(ii)
Computing the aggregation over
these periods.
Paper Contents (Cont.)
(iii) Coalescing the result.
•Temporal Aggregation(Cont.) : Suppose we want to find
maximum salary among employees. Then the computing
way will depend on whether the target table is temporal or
not.
The temporal way
time
Employee1
The non-temporal way
Employee2
Employee3
Salary
Employee
Paper Contents (Cont.)
(i)
Identifying the periods of time in
which all values are constant.
(ii)
Computing the aggregation over
these periods.
(iii) Coalescing the result.
•Temporal Aggregation(Cont.) : Implementation of the
temporal way to solve the “Maximum Salary Question”.
1.Create a view named “SalChanges”
So that we can gather
the days in which a
salary change may
occur !
2.Create a view named “SalPeriods”
So that we can construct
all “atomic” periods for
later processing ! Note
that there is no gap
between any two of these
day periods.
(i)
Identifying the periods of time in
which all values are constant.
(ii)
Computing the aggregation over
these periods.
Paper Contents (Cont.)
(iii) Coalescing the result.
•Temporal Aggregation(Cont.) : Implementation of the
temporal way to solve the “Maximum Salary Question”.
3.Create a view named “TempMax”
So that we can get
maximum salary for every
atomic period ! Like this…
from step (i)
Note that there could be a
gap between any two of these
periods !(No people on jobs)
4.Create a view named “TempCount”
Given a zero
count when no
salary found !
So that we can get
employee count for every
atomic period ! Like this…
Paper Contents (Cont.)
(i)
Identifying the periods of time in
which all values are constant.
(ii)
Computing the aggregation over
these periods.
(iii) Coalescing the result.
•Temporal Aggregation(Cont.) : Implementation of the
temporal way to solve the “Maximum Salary Question”.
To get maximum salary
for each period, we can
coalesce the view
“TempMax”.
Using the SQL in previous
section to Coalesce !
Final result !
Paper Contents (Cont.)
(i)
Identifying the periods of time in
which all values are constant.
(ii)
Computing the aggregation over
these periods.
(iii) Coalescing the result.
•Temporal Aggregation(Cont.) : Similar way to solve the
“Maximum Salary by Department Question”.
Divided into 2 layers: Affiliation & Salary
Evolve
Time
Paper Contents (Cont.)
(i)
Identifying the periods of time in
which all values are constant.
(ii)
Computing the aggregation over
these periods.
(iii) Coalescing the result.
•Temporal Aggregation(Cont.) : Similar way to solve the
“Maximum Salary by Department Question”.
1.Create a view named “Aff_Sal”
So that we can get a
temporal join of affiliation
and salary, which yields the
days in which a change of
max salary of a department
may occur !
Intersected periods only
2.Create a view named “SalChangesDep”
from step 1
So that we can gather
the days by department ,
in which a salary change
may occur !
(i)
Identifying the periods of time in
which all values are constant.
(ii)
Computing the aggregation over
these periods.
Paper Contents (Cont.)
(iii) Coalescing the result.
•Temporal Aggregation(Cont.) : Similar way to solve the
“Maximum Salary by Department Question”.
3.Create a view named “SalPeriodsDep”
from step 2
So that we can construct
all “atomic” periods by
department for later
processing ! Note that
there is no gap between
any two of these day
periods. Like this..
Paper Contents (Cont.)
(i)
Identifying the periods of time in
which all values are constant.
(ii)
Computing the aggregation over
these periods.
(iii) Coalescing the result.
•Temporal Aggregation(Cont.) : Similar way to solve the
“Maximum Salary by Department Question”.
4.Create a view named “TempMaxDep”
5. Query the view
Final Result !
from step 1
from step 3
Paper Contents (Cont.)
•Temporal Universal Quantifier : Needed in many usual
queries, such as “List the employees that work in all projects
controlled by the department to which they are affiliated”.
That’s, finding supermen!
The non-temporal version of above query
Recall that we’ve seen the
“Not Exists,Not Exits”
pattern before. It’s mainly
used to erase tuples
containing any “GAP” period.
Based on the DB schema at the top-right corner,we can construct an E-R model as follows:
Employee
1
has
n
Salary
1
has
1
Key table
Affiliation
n
has
1
Department
1
has
n
1
has
n
Key table
WorksOn
n
has 1
Project
1
n
Key table
Controls
has
:inferred entity
Temporal ?
Temporal ?
Paper Contents (Cont.)
Temporal ?
•Temporal Universal Quantifier(Cont.) : Considering
whether the tables WorksOn,Affiliation, and Controls are
temporal or not. Four cases arise when doing previous query.
Employee 1 has N? Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Paper Contents (Cont.)
•Temporal Universal Quantifier(Cont.) :
The view below:
Pattern found again!
Superman
found by
using..
Employee 1 has 1 Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Paper Contents (Cont.)
•Temporal Universal Quantifier(Cont.) :
construct all “atomic” periods for later processing !
Employee 1 has 1 Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Paper Contents (Cont.)
•Temporal Universal Quantifier(Cont.) :
Pattern found again!
Employee 1 has 1 Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Paper Contents (Cont.)
•Temporal Universal Quantifier(Cont.) :
Temporal join
Project independent !
Employee 1 has n Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Paper Contents (Cont.)
•Temporal Universal Quantifier(Cont.) :
Project independent !
Employee 1 has n Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Paper Contents (Cont.)
•Temporal Universal Quantifier(Cont.) :
1st Temporal Join
2nd Temporal Join
Employee 1 has n Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Paper Contents (Cont.)
•Temporal Universal Quantifier(Cont.) :
Employee 1 has n Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Paper Contents (Cont.)
•Temporal Universal Quantifier(Cont.) :
Employee 1 has n Affiliation
1has
1 has
n
n
Salary
WorksOn
n has
n
1 Department
has 1
Project
1
1
has
n
has n
Controls
Conclusion
1. The cost to implement temporal queries in standard
SQL is high due to the adoption of constructing
various complex “Views”, both in coding and
execution time.
2. To reduce execution time, this paper suggest using TSQL procedures with cursors instead. But the detail
belongs to the future work of this paper.
3. The best solution, however, is to have the DBMS
provide such time-varying facilities in a native way,
since that would increase both database performance
and application development productivity.
The End