Transcript Temporal Data Models

Temporal and Real-Time
Databases: A Survey
by Gultekin Ozsoyoglu and
Richard T. Snodgrass
Presentation by Didi Yao
Introduction

Survey two areas that can benefit from cross
infusion: temporal and real-time DBs
 Temporal: time-varying info
 Real-time: transactions w/ time constraints
 Both can benefit from one another
Real-Time Databases

Transactions have deadlines and timing
constraints
 Time constraints on: queries, insertions,
deletions, updates, database integrity
 More work has been done on temporal than
real-time DBs (600 temporal papers, 150
real-time papers)
The Time Domain

2 structures: linear and branching
 Densities of the time line:
– Discrete models
– Dense models
– Continuous models

naturals
reals or rationals
reals (no gaps)
Most proposals for adding temporal to
relational data models use discrete
The Time Domain (cont.)

Relative (unanchored): 3PM, Nov 9, 2000
 Relative has direction
 Absolute (anchored): 3 hours
 Absolute, in a way, is also relative
The Time Domain (cont.)

Valid time
– When a fact was true in reality
– Bounded or unbounded

Transaction time
– When a fact was stored
– Grows monotonically

Others: user-defined time, decision time
 Indeterminacy- “don’t know exactly when”
Time in Real-Time DBs

Valid time
– Used for data that have real-world counterparts

Transaction time
– Transactions affecting real-time systems
– Never aborted or rolled back

Does not assume future, linear, bounded
 Does not deal with temporal indeterminacy
Temporal Data Models (relational)

Time support in conventional DBs is only
user-defined time: Date, Time, Timestamp
 Table I (temporal relational data models):
– 14 “valid time” models
– 3 “transaction time” models
– 9 “valid and transaction time” models

“Valid time” wins
Temporal Data Models (OO)

Table II
(temporal OO data models):
– 3 “valid” models
– 5 “transaction” models
– 4 “both” models
Valid Time (Temporal Model)

Single chronon
– Event timestamp

Interval
– Interval timestamp

Valid-time
– Set of intervals
Transaction Time (Temporal Model)

Often used to support versioning which
allows user-supplied identifiers to be
attached to versions.
 Versioning support generally implies OO.

Conclusion to temporal data models: a coordinated suite of
data models can best achieve temporal goals
Real-time Data Models

Relational model is used for real-time DBs
 OO model may benefit real-time DBs:
– rich data semantics, complex objects,
encapsulation, methods, messages

However, the added complexity affects realtimeliness
Temporal Query Languages

User-defined time supported by most DBs
 3 approaches to supporting Valid-time:
– Use relational or OO model directly
– Include general extensions to data model and
query languages (only used on OO query languages)
– add new constructs and temporal operators
Temporal Query Languages

Transaction-time is used for rollbacks and
versioning (extension and schema)
 Extension versioning (tuples, object instances or
attributes are versioned)
– Use model directly, general extensions, or
modify data model and language

Schema versioning (object definition versioned)
– Multiple schemas in effect
Real-Time Data and
Transaction Properties



Hard transaction: missing a deadline is disastrous
Soft transaction: missing a deadline will not kill you
Factors that affect real-time transactions:
– Transaction arrival pattern: periodic, sporadic
– Data access type: random, round-robin
– Knowing whether an item will be accessed beforehand
– Knowing the CPU and I/O usage beforehand
Real-Time Properties (cont.)

It is not possible to have both external
consistency AND integrity constraint sat.
 External consistency may:
– Lead to triggers (more coolant)
– Require aborts (abort objects from furnace)

Internal consistency may need resolution
through new transactions.
 Cooperate, not compete
Conventional vs. Real-Time

Conventional DBs:
– Fair in data and resource allocation
– Use response time and throughput as measures

Real-Time DBs:
–
–
–
–
Timely transaction execution
Fairness is secondary
Use % of non-missed deadlines as a measure
Transactions prioritized on deadlines
Real-Time Consistency

Absolute data consistency
 Relative data consistency
– A set of data items that are relatively consistent
to each other
Real-Time Query Languages

none
Architectural Issues




Temporal query optimization is more involved than
conventional query opt.
Predicates are harder to optimize
– Joins with more inequalities are frequent
Time advances in one direction
– Natural clustering on sort order
Methods to optimize query:
– Replace algebraic expression with a more efficient, equivalent one
– Change access method of an operator
– Change implementation of an operator
Architectural Issues (cont.)

Temporal joins: proposed extensions to
nested loop and merge joins
 Temporal indices are important because of
the size of temporal data but no work has
been done to empirically compare them
Architectural Issues (cont.)

Transaction processing
– Adapt existing concurrency control and
transaction management to support transaction
time
– Timestamp at the end of transaction

Processing transaction with hard deadlines
– Arrival patterns, items to be accessed, CPU, I/O
access times must all be known
Architectural Issues (cont.)

Processing transaction with soft deadlines
– Priority assignment policies:
 Earliest-deadline-first, least-slack-time-first, etc…

Concurrency control protocols
– Lock-based protocols
– Timestamp-ordering protocols (timestamp start)
– Optimistic concurrency control protocols
(timestamp end)
Architectural Issues (cont.)

Lock-based protocols
– Transaction blocks or aborts depending on transactions
priority

Priority inheritance approach
– Lower-priority transaction inherits a higher priority in
order to block

Priority abort approach
– Higher-priority request can cause lower-priority
transaction to abort
Architectural Issues (cont.)

Timestamp-ordering protocols
– Timestamps transaction start
– Early conflict resolution
– Suffers from priority inversion

Optimistic concurrency control protocols
– Timestamps transaction end
– Nonblocking and deadlock-free
– Aborts and restart wastes resources
Architectural Issues (cont.)

Stored data manager structures
– Reverse chaining, accession lists, clustering,
stacking, cellular chaining

Buffering for real-time scheduling
– Priority-LRU, priority-DBMIN

Scheduling disk I/O for real-time processing
– FD-SCAN decides scanning direction by
location I/O request with earliest deadline
Conclusion

Temporal relational database (25 years)
 Temporal OO database (15 years)
 Real-time databases (since 1986)
 Accomplishments
– No data model is good enough, need suite of models
– Real-time and temporal people are interacting and
starting to use the same language

Needs
– Real-time models that capture semantic knowledge
– Too many temporal data models, not many real-time
models and no real-time query language
– Performance is still a challenge