Temporal Databases: Topics

Introduction Time Ontology Temporal Conceptual Modeling Manipulating Temporal Databases with SQL-92 Summary

Temporal DBMS
Provide mechanisms to store and query time-varying information Example: Media Planning 3 Which advertisements are to appear? 3 When should the advertisements appear? 3 What is the advertising budget for the dierent media? Applications with temporal aspects abound

Applications
Academic 3 Register the courses taken by students in previous and current semesters, the grades for previous semesters

Temporal Databases: Introduction

Examples of applications Case study Summary

Accounting 3 What bills were sent out and when, what payments were received and when? 3 Cash ow over time 3 Money-management software show, e.g., account balance over time Budget 3 Previous and projected budgets Data warehousing 3 Historical trend analysis for decision support

Temporal DBs: Introduction 1

Temporal DBs: Introduction 2

Applications, cont.
Financial 3 Stock market data 3 Audit analysis: why were nancial decisions made, and with what information available? Geographical Information Systems 3 Land use over time: boundary of parcels change over time, as parcels get partitioned and merged 3 Road planning 3 Deforestation trends Insurance 3 Which police was in eect at each point in time, and what time periods did that police cover? Planning

Applications, cont.
3 Use of present and past schedules for designing new schedules 3 Network management Process monitoring 3 Chemical, electrical, nuclear power installations Reservation systems 3 Hotels, trains, airlines 3 Conguration of new routes Scientic databases 3 Recording experiments 3 Dating archeological ndings 3 Timestamping satellite images

Applications, cont.
Inventory 3 Inventory over time, for analysis, accounting Law 3 Validity period for laws Medical Records 3 Patient records, drug regimes, lab tests 3 Tracking course of disease 3 Epidemiology Payroll 3 Past employees, employee salary history, salaries for future months, records of withholding requested by employees Planning 3 Attribution of tasks, schedules

Applications: Conclusion
Dicult to identify applications not needing management of temporal data These applications would benet from built-in temporal support in the DBMS 3 More ecient application development 3 Potential increase of performance

Temporal DBs: Introduction 3

Temporal DBs: Introduction 4

Case Study
Personnel management in a database Employee(Name, Salary, Title) It is easy to know the salary of an employee SELECT Salary FROM Employee WHERE Name = John It is necessary to add date of birth Employee(Name, Salary, Title, BirthDate DATE) It is also easy to know the date of birth of an employee SELECT BirthDate FROM Employee WHERE Name = John

Determine the Salary

To know the employees current salary, things are more dicult SELECT Salary FROM Employee WHERE Name = John AND FromDate <= CURRENT TIMESTAMP AND CURRENT TIMESTAMP <= ToDate Determine the salary history 3 Result: for each person, the maximal intervals of each salary Name Salary FromDate ToDate John 60.000 1/1/95 1/6/95 John 70.000 1/6/95 1/1/97 3 An employee could have arbitrarily many title changes between salary changes

11

Determine the Salary, cont. Converting to a Temporal Database

We want to keep the employment history Employee(Name, Salary, Title, BirthDate, FromDate DATE, ToDate DATE) Name John John John John Salary 60.000 70.000 70.000 70.000 Title Assistant Assistant Lecturer Professor BirthDate 9/9/60 9/9/60 9/9/60 9/9/60 FromDate 1/1/95 1/6/95 1/10/95 1/2/96 ToDate 1/6/95 1/10/95 1/2/96 1/1/97 Alternative 1 3 Give the user a printout of Salary and Title information, and have the user determine when his/her salary changed Alternative 2 3 Use SQL as much as possible 3 Find those intervals that overlap or are adjacent and that should be merged

For the data model, new columns are identical to attribute BirthDate

10

12

Temporal DBs: Introduction 5

Temporal DBs: Introduction 6

SQL Code
CREATE TABLE Temp(Salary, FromDate, ToDate) AS SELECT Salary, FromDate, ToDate FROM Employee WHERE Name = John UPDATE Temp T1 SET (T1.ToDate) = (SELECT MAX(T2.ToDate) FROM Temp AS T2 WHERE T1.Salary = T2.Salary AND T1.FromDate < T2.FromDate AND T1.ToDate >= T2.FromDate AND T1.ToDate < T2.ToDate) WHERE EXISTS ( SELECT * FROM Temp as T2 WHERE T1.Salary = T2.Salary AND T1.FromDate < T2.FromDate AND T1.ToDate >= T2.FromDate AND T1.ToDate < T2.ToDate) until no tuples updated repeat

SQL Code, cont.

Loop is executed logN times in the worst case, where N is the number of tuples in a chain of overlapping or adjacent value-equivalent tuples Then delete extraneous, non-maximal intervals DELETE FROM Temp T1 WHERE EXISTS ( SELECT * FROM Temp AS T2 WHERE T1.Salary = T2.Salary AND ( (T1.FromDate > T2.FromDate AND T1.ToDate <= T2.ToDate) OR (T1.FromDate >= T2.FromDate AND T1.ToDate < T2.ToDate) )

13

15

SQL Code, cont.

Initial table

Same functionality entirely in SQL

CREATE VIEW Temp(Salary, FromDate, ToDate) AS SELECT Salary, FromDate, ToDate FROM Employee WHERE Name = John SELECT DISTINCT F.Salary, F.FromDate, L.ToDate FROM Temp AS F, Temp AS L WHERE F.FromDate < L.ToDate AND F.Salary = L.Salary AND NOT EXISTS ( SELECT * FROM Temp AS T WHERE T.Salary = F.Salary AND F.FromDate < T.FromDate AND T.FromDate < L.ToDate AND NOT EXISTS ( SELECT * FROM Temp AS T1 WHERE T1.Salary = F.Salary AND T1.FromDate < T.FromDate AND T.FromDate <= T1.ToDate) ) AND NOT EXISTS ( SELECT * FROM Temp AS T2 WHERE T2.Salary = F.Salary AND ( (T2.FromDate < F.FromDate AND F.FromDate <= T2.ToDate) OR (T2.FromDate < L.ToDate AND L.ToDate < T2.ToDate)))

After one pass

After two passes

14

16

Temporal DBs: Introduction 7

Temporal DBs: Introduction 8

Same Query in Calculus

f t1 t l

Another Possibility, cont.

Original table

t2

%
Linked list is not necessary in this case if cursor is ORDER BY Salary, FromDate Alternative 4: Use the transitive closure or triggers in SQL3 TSQL2 SELECT Salary FROM Employee WHERE Name = Bob

t2

{f.FromDate, l.ToDate | Temp(f ) Temp(l) f.FromDate < l.ToDate f.Salary = l.Salary (t)(Temp(t) t.Salary = f.Salary f.FromDate < t.FromDate t.FromDate < l.ToDate (t1 )(Temp(t1 ) t1 .Salary = f.Salary t1 .FromDate < t.FromDate t.FromDate <= t1 .ToDate)) (t2 )(t2 .Salary = f.Salary ( (t2 .FromDate < f.FromDate f.FromDate <= t2 .ToDate) (t2 .FromDate < l.ToDate l.ToDate < t2 .ToDate)) ) }

17

19

Another Possibility
Alternative 3: Use SQL to open a cursor in the table
Maintain a linked list of intervals, for each salary; Initialize this linked list to empty; DECLARE emp_cursor CURSOR FOR SELECT Salary, FromDate, ToDate FROM Employee WHERE Name = Bob OPEN emp_cursor; loop: FETCH emp_cursor INTO :salary, :FromDate, :ToDate; if no-data returned, then go to finish; find position in list to insert this information go to loop; finish: CLOSE emp_cursor iterate through linked list for printing dates and salary

More Drastic Alternatives

Reorganize the schema: separate the information on Salary, Title, and BirthDate Employee1(Name, Salary, FromDate DATE, ToDate DATE) Employee2(Name, Title, FromDate DATE, ToDate DATE) Determine the information about the salary is easy now SELECT Salary, FromDate, ToDate FROM Employee1 WHERE Name = John However, how to obtain a table of salary, title intervals?

18

20

Temporal DBs: Introduction 9

Temporal DBs: Introduction 10

Example of Temporal Join

Name John John Name John John John Name John John John John Employee1 Salary FromDate 60.000 1/1/95 70.000 1/6/95 Employee2 Title FromDate Assistant 1/1/95 Lecturer 1/10/95 Professor 1/2/96 ToDate 1/6/95 1/1/97 ToDate 1/10/95 1/2/96 1/1/97 ToDate 1/6/95 1/10/95 1/2/96 1/1/97

Temporal Join in SQL

SELECT Employee1.Name, Salary, Title, Employee1.FromDate, FROM Employee1, Employee2 WHERE Employee1.Name = Employee2.Name AND Employee2.FromDate <= Employee1.FromDate AND Employee1.ToDate <= Employee2.ToDate UNION ALL SELECT Employee1.Name, Salary, Title, Employee1.FromDate, FROM Employee1, Employee2 WHERE Employee1.Name = Employee2.Name AND Employee1.FromDate > Employee2.FromDate AND Employee2.ToDate < Employee1.ToDate AND Employee1.FromDate < Employee2.ToDate UNION ALL SELECT Employee1.Name, Salary, Title, Employee2.FromDate, FROM Employee1, Employee2 WHERE Employee1.Name = Employee2.Name AND Employee2.FromDate > Employee1.FromDate AND Employee1.ToDate < Employee2.ToDate AND Employee2.FromDate < Employee1.ToDate UNION ALL SELECT Employee1.Name, Salary, Title, Employee2.FromDate, FROM Employee1, Employee2 WHERE Employee1.Name = Employee2.Name AND Employee2.FromDate >= Employee1.FromDate AND Employee2.ToDate <= Employee1.ToDate Employee1.ToDate Employee1 Employee2 Employee2.ToDate Employee1 Employee2 Employee1.ToDate Employee1 Employee2 Employee2.ToDate Employee1 Employee2

Employee1 1 Employee2 Salary Title FromDate 60.000 Assistant 1/1/95 70.000 Assistant 1/6/95 70.000 Lecturer 1/10/95 70.000 Professor 1/2/96

21

23

Evaluation of Temporal Join

Alternative 1: print the two tables and leave the user make the combinations Alternative 2: Use SQL entirely Employee1 Employee2 Result
SELECT Employee1.Name, Salary, Title, Employee1.FromDate, Employee1.ToDate FROM Employee1, Employee2 WHERE Employee1.Name = Employee2.Name AND Employee2.FromDate <= Employee1.FromDate AND Employee1.ToDate < Employee2.ToDate

Temporal Join, cont.

Alternative 3: Use embedded SQL TSQL2: Give the salary and title history of employees SELECT Employee1.Name, Salary, Title FROM Employee1, Employee2 WHERE Employee1.Name = Employee2.Name

22

24

Temporal DBs: Introduction 11

Temporal DBs: Introduction 12

Introduction: Summary
Applications managing temporal data abound Classical DBMS are not adequate If a temporal DBMS is used 3 Schemas are simpler 3 SQL queries are much simpler 3 Much less procedural code is necessary Benets 3 Application code is less complex Easier to understand, to produce, to ensure correctness, to maintain 3 Performance may be increased by relegating functionality to DBMS Notions of time 3 Structure 3 Density 3 Boundedness TSQL2 time ontology Time data types Clocks Times and facts

Time Ontology

25

27

Time Structure
Linear: total order on instants  -

Temporal Databases: Topics

6 now

y Time Ontology
Temporal Conceptual Modeling Manipulating Temporal Databases with SQL-92

Introduction

Hypothetical (possible futures): tree rooted on now :  : -

6 now

Directed Acyclic Graph Periodic/cyclic time: weeks, months, . . ., for recurrent processes

26

28

Temporal DBs: Time Ontology 13

Temporal DBs: Time Ontology 14

Boundedness of Time
Assume a linear time structure Boundedness 3 Unbounded 3 Time origin exists (bounded from the left) 3 Bounded time (bounds on two ends) Nature of bound 3 Unspecied 3 Specied Physicists believe that the universe is bounded by the Big Bang (12-18 billions years ago) and by the Big Crunch (? billion years in the future)

TSQL2: Time Ontology

Structure 3 TSQL2 uses a linear time structure Boundedness 3 TSQL2 time line is bounded on both ends, from the start of time to a point far in the future Density 3 TSQL2 do not dierentiate between discrete, dense, and continuous time ontologies 3 No questions can be asked that give dierent answers E.g., instant a precedes instant b at some specied granularity. Dierent granularities give dierent answers 3 Distance is dened in terms of numbers of chronons

29

31

Time Density
Discrete 3 Time line is isomorphic to the integers 3 Time line is composed of a sequence of non-decomposable time periods, of some xed minimal duration, termed chronons 3 Between each pair of chronons is a nite number of other chronons Dense 3 Time line is isomorphic to the rational numbers 3 Innite number of instants between each pair of chronons Continuous 3 Time line is isomorphic to the real numbers 3 Innite number of instants between each pair of chronons Distance may optionally be dened

Ontological Temporal Types

Instant: chronon in the time line 3 Event: instantaneous fact, something occurring at an instant 3 Event occurrence time: valid-time instant at which the event occurs in the real world Instant Set: set of instants Time period: time between two instants 3 Also called interval, but conicts with SQL data type INTERVAL Time interval: a directed duration of time. Duration: amount of time with a known length, but no specic starting or ending instants 3 positive interval: forward motion time 3 negative interval: backward motion time Temporal element: nite union of periods

30

32

Temporal DBs: Time Ontology 15

Temporal DBs: Time Ontology 16

Representing Time in TSQL2

TSQL2 supports a bounded discrete representation of the time line Time line composed of chronons, which is the smallest granularity Consecutive chronons may be grouped together into granules, yielding multiple granularities Dierent granularities are available, and it is possible to convert from one granularity to another (via scaling)

Clocks
A clock is a physical process coupled with a method of measuring that process Units of measurement are the chronons of the clock Examples 3 Year clocks 3 Day clocks 3 Second clocks 3 Other clocks

33

35

Time and Facts

Valid time of a fact: when the fact is true in the modeled reality 3 Independently of its recording in the database 3 Past, present, future Transaction time of a fact: when the fact is current in the database and may be retrieved 3 Identify the transactions that inserted and deleted the fact Two dimensions are orthogonal Four kinds of tables 3 Snapshot 3 Valid time 3 Transaction time 3 Bitemporal

Temporal Data Types in SQL-92 and TSQL2

SQL92 3 DATE (YYYY-MM-DD) 3 TIME (HH:MM:SS) 3 DATETIME (YYYY-MM-DD HH:MM:SS) 3 INTERVAL (no default granularity) TSQL2 3 PERIOD: DATETIME - DATETIME

34

36

Temporal DBs: Time Ontology 17

Temporal DBs: Time Ontology 18

Transaction Time Tables Snapshot Tables

transaction time

May be modied Used for static queries What is Johns title? SELECT Title FROM Faculty WHERE Name = John

Append-only: correction to previous snapshot states is not permitted Allow retrospective queries (rollback) What did we believe Johns rank was on October 1st, 1984? SELECT Title FROM Faculty WHERE Name = John AND TRANSACTION(Faculty) OVERLAPS DATE 01-10-1984

37

39

Snapshot Tables, cont.

Analogy: Nameplate on door John Assistant John 1st Assistant John 1st Assistant John Lecturer

Transaction Time Tables, cont.

Analogy: Pay stubs

John Assistant 1-1-84

...
John Assistant 1-11-87 John 1st Assistant 1-12-87

Jan. 84

Dec. 87

March 89

July 89

On January 1st, 1984, John is hired as assistant On December 1st, 1987, John nishes his doctorate and is promoted as 1st Assistant retroactively on July 1st, 1987 On March 1st, 1989, John is promoted as Lecturer, proactively on July 1st, 1989

...

John 1st Assistant 1-6-89 John Lecturer 1-7-89

38

40

Temporal DBs: Time Ontology 19

Temporal DBs: Time Ontology 20

Valid Time Tables

Bitemporal Tables

Valid Time

Transaction Time

Append-only May be modied Allow historical queries What was Johns title on October 1st, 1984 (as best known)? SELECT Title FROM Faculty WHERE Name = John AND VALID(Faculty) OVERLAPS DATE 01-10-1984 41 Transaction and valid time Allow coupled historical and retrospective queries On October 1st, 1984, what did we think Johns rank was at that date?
SELECT Title FROM Faculty AS E WHERE Name = John AND VALID(E) OVERLAPS DATE 01-10-1984 AND TRANSACTION(E) OVERLAPS DATE 01-10-1984

43

Bitemporal Tables, cont. Valid Time Tables, cont.

Analogy: Curriculum Vit John Titles Lecturer 1st Assistant Assistant Analogy: Stack of CVs
John Titles Assistant January 1984

January 1984 Version December 1987 Version

July 1989 July 1987 January 1984

John Titles 1st Assistant July 1987 Assistant January 1984 John Titles Lecturer July 1989 1st Assistant July 1987 Assistant January 1984

March 1989 Version

42

44

Temporal DBs: Time Ontology 21

Temporal DBs: Time Ontology 22

Temporal Data Models: What is Timestamped? Time Ontology: Summary

Several dierent structures of time 3 Linear is simplest and most common 5 fundamental temporal data types Many dierent physical clocks 3 TSQL2 uses a baseline clock composed of 4 physical clocks related at synchronization points Several dimensions of time 3 TSQL2 supports transaction and valid time Individual attribute values Groups of attribute values: heterogeneous data model Tuples: homogeneous data model Set of tuples 3 Generally used for transaction time, to timestamp a set of tuples inserted or modied by a transaction Object Object graph 3 E.g., to associate a connected set of modules (a conguration) with a particular version identier Schema item

45

47

Temporal Conceptual Modeling

Current setting in temporal databases Modeling requirements The conceptual manifesto Temporal objects Temporal attributes Temporal generalization Temporal relationships Dynamic relationships Conclusion

Temporal Databases: Topics

Introduction Time Ontology

y Temporal Conceptual Modeling

Manipulating Temporal Databases with SQL-92

46

48

Temporal DBs: Temporal Conceptual Modelling 23

Temporal DBs: Temporal Conceptual Modelling 24

Current Setting in Temporal DBs

Towards an Infrastructure for Temporal Databases a workshop report, SIGMOD Record, March 1994 No marketed temporal DBMS Many research results (about 1000 papers) No commonly accepted data model or query language 3 about 25 relational model extensions 3 about 12 ER model extensions 3 about 15 OO models extensions 3 about as many query languages

Temporal Requirements
Valid time, transaction time, user-dened time Imprecise, future, relative, branching time Time series Integration of DBs with dierent granularities Coexistence with non-temporal data Legacy applications Open architecture Temporal reasoners

49

51

Major Conclusions
there seems to be a gap between the goals assumed by the temporal DB community and the needs... users could not say what a temporal database is the glossary was couched in the language of temporal DB researchers the time-varying semantics is obscured in the representation schemes by other considerations of presentation and implementation we therefore advocate a separation of concerns, i.e. adopting a very simple conceptual data model ....

Interaction Requirements
Graphical information 3 information visualization 3 graphical queries Multiple users, multiple needs, multiple functions

50

52

Temporal DBs: Temporal Conceptual Modelling 25

Temporal DBs: Temporal Conceptual Modelling 26

The Conceptual Manifesto (1)

Semantically powerful data structures

Practical Requirements
Huge data sets 3 Collecting new data is expensive 3 Reusing highly heterogeneous existing data sets is a must ... but is very dicult ! Integration requires understanding, hence a conceptual model

Simple (understandable) data model 3 few clean concepts, with standard, well-known semantics No articial time objects Time orthogonal to data structures Various granularities, Clean, visual notations Intuitive icons / symbols

53

55

Why Conceptual Modeling ?

Focuses on the application Technology independent 3 portability, durability User oriented Formal, unambiguous specication Supports visual interfaces 3 data denition and manipulation Best vehicle for information exchange/integration
ENDstamp ID Employee

Counter Examples
ENDstamp Works for Id Project

BEGIN stamp Salary

Salary

Employee

54

56

Temporal DBs: Temporal Conceptual Modelling 27

Temporal DBs: Temporal Conceptual Modelling 28

Orthogonality
Employee EName WorksOn Project P# EmpDep Department D#

Temporal information describes ...

Life cycles of objects and relationships Validity of information values 3 timestamps

Employee EName lifecycle department projects

Temporal relationships 3 transformation / generation of objects 3 temporal links 3 time-based aggregations 3 Temporal integrity constraints

Employee EName projects

EmpDep

Department D#

57

59

Temporal Schema: Example The Conceptual Manifesto (2)

Explicit temporal relationships and integrity constraints Support of valid time and transaction time Past to future Co-existence of temporal and traditional data Query languages Complete and precise denition of the model
name presentations speaker venue duration salary WorkOn Project Runs budget Employee Works for Department Person name birthdate address telephones number street name city zip country name budget

58

60

Temporal DBs: Temporal Conceptual Modelling 29

Temporal DBs: Temporal Conceptual Modelling 30

Temporal Objects
name birthdate address salary projects [7/94-6/96] [7/97-6/98] active [7/96-6/97] suspended

Non-Temporal Objects ?
No life cycle, or Default life cycle 3 ( active, [0, now] ) 3 ( active, [now, now] ) 3 ( active, [0, ] ) Coexistence 3 temporal non temporal (snapshot) 3 non-temporal temporal (default life cycle)

Employee

e221

Peter 8/9/64 Rue de la Paix 5000 {MADS, HELIOS}

life cycle information

61

63

Object / Relationship Life Cycle

Continuous create ? Discontinuous create ? suspend ? reactivate ? kill ? kill ?

TSQL2 Policy
Temporal operators not allowed on non-temporal relations 3 no life cycle Joins between temporal and non-temporal relations are allowed 3 default life cycle = ( active, [0, ] ) SELECT Department.Name, COUNT (PID) FROM Department, Employee WHERE Employee.dept # = Department.dept # AND VALID(Employee) OVERLAPS PERIOD [1/1/96-31/12/96] GROUP BY dept #

62

64

Temporal DBs: Temporal Conceptual Modelling 31

Temporal DBs: Temporal Conceptual Modelling 32

Temporal Attributes
o2 Peter 8/9/64 Bd St Germain Bd St Michel Rue de la Paix 4000 5000 [7/94-7/98] [1/85-12/87] [1/88-12/94] [1/95-now]

Temporal Complex Attributes (2)

Employee

name birthdate address salary projects

Laboratory

labName projName project manager

Updating manager add element to manager history Updating projName (name of project has changed) update name

[7/94-7/95] [8/95-now] [7/94-8/95] [9/95-now]

{MADS} {MADS, HELIOS}

Updating project (laboratory changed project) update name, start new history for manager

65

67

Temporal Complex Attributes (1)

Laboratory lab1 name name projects manager budget LBD lab1 name projects budget name manager { MADS, Stef [x/x/x -- x/x/x] , 1500) , Chris [x/x/x -- x/x/x] (Helios, Martin [x/x/x -- x/x/x] , 2000) } John [x/x/x -- x/x/x] LBD {(MADS, Chris,1500)} [1/1/95 -31/12/95] {(MADS, Chris,1500), [1/1/95 -now] (Helios, Martin,2000)}

Attribute Timestamping Properties

Attribute types / timestamping 3 none, irregular, regular, instants, durations, ... Cardinalities

Laboratory

3 snapshot and DBlifespan Identiers 3 snapshot or DBlifespan

66

68

Temporal DBs: Temporal Conceptual Modelling 33

Temporal DBs: Temporal Conceptual Modelling 34

Attribute Timestamping Issues

Constraints ? 3 the validity period of an attribute must be within the life cycle of the object it belongs to 3 the validity period of a complex attribute is the union of the validity periods of its components MADS : no implicit constraint

Static Temporal Generalization

Employee

Temporary

Permanent

Temporary and Permanent are implicitly temporal 3 they inherit their life cycle from Employee

69

71

Temporal Generalization
Person name birthdate address salary projects o2 Peter 8/9/64 East Terrace Flinders Street Person

Dynamic Temporal Generalization

Person

Employee o1 John 3/7/55 High Street Victoria Street

Temporary Student

Permanent Faculty

[3/93-2/95] [3/95-now]

[1/87-6/94] [7/94-now]

Student and Faculty have two life cycles: 3 an inherited one (the one of Person) 3 a redened one (the one of Student/Faculty )

[7/94-now] 4000 [7/94-7/95] 5000 [8/95-now] {MADS} [7/94-8/95] {MADS, HELIOS} [9/95-now]

Employee

The redened life cycle has to be included in the one of the corresponding Person 3 lifespan and active periods

70

72

Temporal DBs: Temporal Conceptual Modelling 35

Temporal DBs: Temporal Conceptual Modelling 36

Temporal Relationships (1)

name birthdate address Employee WorksOn hours/week [x/x/x - x/x/x] e1 John 3/7/55 Bd Haussman Peter [x/x/x - x/x/x] e2 8/10/64 Rue de la Paix [x/x/x - x/x/x] (e1, p2, 30 [x/x/x -- x/x/x] ) [x/x/x - x/x/x] 25 [x/x/x - x/x/x] (e1, p1, ) 35 [x/x/x - x/x/x] [x/x/x - x/x/x] 25 [x/x/x - x/x/x] (e2, p2, ) 35 [x/x/x - x/x/x] MADS [x/x/x - x/x/x] p1 Christine 5000 HELIOS [x/x/x - x/x/x] Yves p2 6000 Project pname manager budget

Temporal Relationships (2)

name birthdate address Employee WorksOn hours/week [x/x/x - x/x/x] e1 John 3/7/55 Bd Haussman Peter [x/x/x - x/x/x] e2 8/10/64 Rue de la Paix (e1, p2, 30 (e1, p1, [x/x/x -- x/x/x] ) MADS [x/x/x - x/x/x] p1 Christine 5000 HELIOS [x/x/x - x/x/x] Yves p2 6000 Project pname manager budget

25 [x/x/x - x/x/x] ) 35 [x/x/x - x/x/x] 25 [x/x/x - x/x/x] ) 35 [x/x/x - x/x/x]

(e2, p2,

Only currently valid couples are kept in the relationship

73

75

Temporal Relationships (3)

name birthdate address Employee WorksOn hours/week e1 John 3/7/55 Bd Haussman Peter 8/10/64 Rue Haute (e1, p2, 30 [x/x/x - x/x/x] [x/x/x -- x/x/x] ) [x/x/x - x/x/x] MADS Christine 5000 HELIOS Yves 6000 p1 p2 Project pname manager budget

Relationship Timestamping Issues

Constraints ? 3 the validity period of a relationship must be within the intersection of the life cycles of the objects it links 3 a temporal relationship can only link temporal objects MADS : no implicit constraint

e2

25 [x/x/x - x/x/x] (e1, p1, 35 ) [x/x/x - x/x/x] [x/x/x - x/x/x] 25 [x/x/x - x/x/x] (e2, p2, ) 35 [x/x/x - x/x/x]

Only currently valid objects participate in the relationship

74

76

Temporal DBs: Temporal Conceptual Modelling 37

Temporal DBs: Temporal Conceptual Modelling 38

Dynamic Relationships
Express processes or time links Transformation of an object 3 a student becomes an alumnus Generation of objects 3 a parcel is split into several parcels Temporal relationships between objects 3 ancestor Coalescence 3 an object and its versions / snapshots

Transition Relationships (2)

Their temporality records when it happened 3 life cycle = one instant or one interval They are relationships 3 they bear cardinalities 3 they can have attributes, methods, and constraints (temporal or not) Peculiarity: linked objects have the same oid Also apply to non-temporal objects

77

79

Transition Relationship (1)

Person

Generation Relationship (1)

0:n Parcel 0:n source 1:n A active S suspended D dead ? not existing target 1:n Generates G

Student

Promoted T A A|S|D S|? A

Alumnus

Student.status Alumnus.status

A active S suspended D dead ? not existing

source Parcel.status target Parcel.status

A|S|D

S|? A

Migration of objects in a dynamic generalization hierarchy: becomes a

A (set of) source object(s) generates a (set of) target object(s): yields

78

80

Temporal DBs: Temporal Conceptual Modelling 39

Temporal DBs: Temporal Conceptual Modelling 40

Synchronization Relationships (2) Generation Relationships (2)

Their temporality records when it happened 3 life cycle = one instant or one interval They are peculiar relationships : they bear 2 kinds of cardinalities 3 how many generation instances can be linked to an object 3 how many objects can be linked to a generation instance : multi-roles Also apply to non-temporal objects
Person desc. 0:n before ( anc.life, desc.life) anc. 0:n Ancestor during ( Landslide.life, Typhoon.life) Typhoon 0:n Causes 0:1 Landslide

81

83

Synchronization Relationships (1)

Describe temporal constraints between the life cycles of two objects Expressed with Allens operator extended for temporal elements before meets overlaps during starts nishes

Synchronization Relationships (3)

Express a temporal constraint between 3 the whole life cycles, or 3 the active periods Temporal constraint dened with 3 extended Allens operators 3 application-dened operators, e.g., 9 months later They are relationships 3 may have attributes, cardinalities

82

84

Temporal DBs: Temporal Conceptual Modelling 41

Temporal DBs: Temporal Conceptual Modelling 42

Coalescence (1)
0:n River name flowrate name flowrate Versions C 1:1 RiverBed name year averageflow name year averageflow

Temporal Conceptual Models: Conclusion

Existing temporal models are weak candidates for conceptual modeling Uneasy issues remain to be solved Orthogonality is the answer Consensus is hardly foreseable if criteria are not discussed

River.lifecycle.active.temp_elt = SET(Versions.RiverBed.year) River.flowrate = TIMESET(Versions.RiverBed.averageflow, Versions.RiverBed.year)

A temporal object linked to its (non-temporal) versions: has versions Attributes may be derived

85

87

Coalescence (2)
They are not temporal They are aggregation relationships 3 they bear cardinalities 3 they can have attributes (temporal or not) Introduction Time Ontology

Temporal Databases: Topics

y Manipulating Temporal Databases with SQL-92

Temporal Conceptual Modeling

86

88

Temporal DBs: Temporal Conceptual Modelling 43

Temporal DBs: Manipulating Temporal DBs with SQL 44

Temporal Keys Dening Valid-Time Tables in SQL

Employees SSN FirstName LastName BirthDate Salary SSN Amount Positions PCN JobTitle FromDate ToDate Incumbents SSN PCN 111223333 900225 111223333 900225 FromDate 1996-01-01 1996-04-01 ToDate 1996-06-01 1996-10-01

Incumbents SSN PCN FromDate

ToDate

Constraint: Employees have only one position at a point in time In the corresponding non-temporal table the key is (SSN,PCN)

Incumbents is a valid-time table 3 FromDate indicates when the information in the row is valid, i.e. when the employee was assigned to that position 3 ToDate indicates when the information in the row was no longer valid Data type for periods is not available in SQL-92 a period is simulated with two Date columns

Candidate keys on Incumbents: (SSN,PCN,FromDate), (SSN,PCN,ToDate), and (SSN,PCN,FromDate,ToDate) None captures the constraint: there are overlapping periods associated with the same SSN What is needed: sequenced constraint, applied at each point in time All constraints specied on a snapshot table have sequenced counterparts, specied on the analogous valid-time table

89

91

Example of a Valid-Time Table

Incumbents SSN 111223333 111223333 111223333 111223333 111223333

Sequenced Primary Key

PCN 900225 900225 900225 900225 900225 FromDate 1996-01-01 1996-06-01 1996-08-01 1996-10-01 1997-01-01 ToDate 1996-06-01 1996-08-01 1996-10-01 3000-01-01 3000-01-01 Constraint: Employees have only one position at a point in time CREATE TRIGGER Seq_Primary_Key ON Incumbents FOR INSERT, UPDATE AS IF EXISTS ( SELECT * FROM Incumbents AS I1 WHERE 1 < ( SELECT COUNT(I2.SSN) FROM Incumbents AS I2 WHERE I1.SSN = I2.SSN AND I1.PCN = I2.PCN AND I1.FromDate < I2.ToDate AND I2.FromDate < I1.ToDate ) ) OR EXISTS ( SELECT * FROM Incumbents AS I WHERE I.SSN IS NULL OR I.PCN IS NULL ) BEGIN RAISERROR(Violation of sequenced constraint,1,2) rollback transaction END

Special date 3000-01-01 denotes currently valid Closed-open periods used, e.g., validity of rst tuple is [1996-01-01,1996-06-01) Table can be viewed as a compact representation of a sequence of snapshot tables, each valid on a particular day Constraint: Employees does not have gaps in their position history Last two rows may be replaced with a single row valid at [1996-06-01,3000-10-01)

90

92

Temporal DBs: Manipulating Temporal DBs with SQL 45

Temporal DBs: Manipulating Temporal DBs with SQL 46

 I1.FromDate < I2.ToDate AND I2.FromDate < I1.ToDate: test overlaping on two periods If a closed-closed representation for the period of validity is used, the predicate must be changed by I1.FromDate <= I2.ToDate AND I2.FromDate <= I1.ToDate: COUNT: ensure that I1 and I2 are not the same row 1 2 3 4 5

Types of Duplicates
Incumbents SSN 111223333 111223333 111223333 111223333 111223333 PCN 120033 120033 120033 120033 120033 FromDate 1996-01-01 1996-04-01 1996-04-01 1996-10-01 1997-12-01 ToDate 1996-06-01 1996-10-01 1996-10-01 1998-01-01 1998-01-01

Handling Now
What should the timestamp be for current data ? One alternative: using NULL Allows to indentify current records: WHERE Incumbents.ToDate IS NULL Disadvantages 3 users get confused with a data of NULL 3 in SQL any comparision with a null value returns false rows with null values will be absent from the result of many queries 3 other uses of NULL are not available Another approach: set the end date to largest value in the timestamp domain, e.g., 3000-01-01 Disadvantages 3 DB states that something will be true in the far future 3 represent now and forever in the same way 93

Two rows are value equivalent if the values of their nontimestamp columns are equivalent Two rows are sequenced duplicates if they are duplicates at some instant: 1+2 employee has to Positions for the months of April and May of 1996 Two rows are current duplicates if they are sequenced duplicates at the current instant: 4+5 in December 1997 a current duplicate will suddenly appear Two rows are nonsequenced duplicates if the values of all columns are identical: 2+3 94

Preventing Duplicates (1)

Preventing value-equivalent rows: dene secondary key using UNIQUE(SSN,PCN) Preventing nonsequenced duplicates: UNIQUE(SSN,PCN,FromDate,ToDate) Preventing current duplicates: No employee can have two identical Positions at the current time CREATE TRIGGER Current_Duplicates ON Incumbents FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT I1.SSN FROM Incumbents AS I1 WHERE 1 < ( SELECT COUNT(I2.SSN) FROM Incumbents AS I2 WHERE I1.SSN = I2.SSN AND I1.PCN=I2.PCN AND I1.FromDate <= CURRENT_DATE AND CURRENT_DATE < I1.ToDate AND I2.FromDate <= CURRENT_DATE AND CURRENT_DATE < I2.ToDate ) ) BEGIN RAISERROR(Transaction allows current duplicates,1,2) rollback transaction END

95

Temporal DBs: Manipulating Temporal DBs with SQL 47

Temporal DBs: Manipulating Temporal DBs with SQL 48

Preventing Duplicates (2)

Preventing current duplicates, asumming no future data: current data will have the same ToDate (3000-01-01) UNIQUE(SSN,PCN,ToDate) Preventing sequenced duplicates, asumming no future data: since a primary key is a combination of UNIQUE and NOT NULL, remove the NOT NULL portion of code for keys CREATE TRIGGER Seq_Primary_Key ON Incumbents FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT I1.SSN FROM Incumbents AS I1 WHERE 1 < ( SELECT COUNT(I2.SSN) FROM Incumbents AS I2 WHERE I1.SSN = I2.SSN AND I1.PCN=I2.PCN AND I1.FromDate < I2.ToDate AND I2.FromDate < I1.ToDate ) ) BEGIN RAISERROR(Transaction allows sequenced duplicates,1,2) rollback transaction END Preventing sequenced duplicates, asumming only current modications: UNIQUE(SSN,PCN,ToDate) 96

Uniqueness (2)
Nonsequenced constraint: an employee cannot have more than one position over two identical periods, i.e., Incumbents.SSN is nonsequenced unique: UNIQUE(SSN,FromDate,ToDate) Current constraint: an employee has at most one position, i.e., Incumbents.SSN is current unique: CREATE TRIGGER Seq_Primary_Key ON Incumbents FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT I1.SSN FROM Incumbents AS I1 WHERE 1 < ( SELECT COUNT(I2.SSN) FROM Incumbents AS I2 WHERE I1.SSN = I2.SSN AND I1.FromDate < I2.ToDate AND I2.FromDate < I1.ToDate ) ) BEGIN RAISERROR(Transaction violates sequenced constraint,1,2) rollback transaction END

98

Uniqueness (1)
Constraint: Each employee has at most one position Snapshot table: UNIQUE(SSN) Sequenced constraint: At any time each employee has at most one position, i.e., Incumbents.SSN is sequenced unique CREATE TRIGGER Seq_Primary_Key ON Incumbents FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT I1.SSN FROM Incumbents AS I1 WHERE 1 < ( SELECT COUNT(I2.SSN) FROM Incumbents AS I2 WHERE I1.SSN = I2.SSN AND I1.FromDate < I2.ToDate AND I2.FromDate < I1.ToDate ) ) OR EXISTS ( SELECT * FROM Incumbents AS I WHERE I.SSN IS NULL ) BEGIN RAISERROR(Transaction violates sequenced constraint,1,2) rollback transaction END

Referential Integrity (1)

Incumbents.PCN is a foreign key for Positions.PCN Case 1: Neither table is temporal CREATE TABLE Incumbents ( ... PCN CHAR(6) NOT NULL REFERENCES Positions,

... )

Case 2: Both tables are temporal The PCN of all current incumbents must be listed in the current Positions CREATE TRIGGER Current_Referential_Integrity ON Incumbents FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT * FROM Incumbents AS I WHERE I.ToDate = 3000-01-01 AND NOT EXISTS ( SELECT * FROM Positions AS P WHERE I.PCN = P.PCN AND P.ToDate = 3000-01-01 ) ) BEGIN RAISERROR(Violation of current referential integrity,1,2) ROLLBACK TRANSACTION END

97

99

Temporal DBs: Manipulating Temporal DBs with SQL 49

Temporal DBs: Manipulating Temporal DBs with SQL 50

Referential Integrity (2)

Incumbents.PCN is a sequenced foreign key for Positions.PCN
CREATE TRIGGER Sequenced_Ref_Integrity ON Incumbents FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT * FROM Incumbents AS I WHERE NOT EXISTS ( SELECT * FROM Positions AS P WHERE I.PCN = P.PCN AND P.FromDate <= I.FromDate AND I.FromDate < P.ToDate ) P P OR NOT EXISTS ( SELECT * FROM Positions AS P  I R  WHERE I.PCN = P.PCN AND P.FromDate < I.ToDate R AND I.ToDate <= P.ToDate ) OR EXISTS ( Pz  SELECT * FROM Positions AS P WHERE I.PCN = P.PCN AND I.FromDate < P.ToDate  R AND P.ToDate < I.ToDate AND NOT EXISTS ( P2 SELECT * FROM Positions AS P2 WHERE P2.PCN = P.PCN AND P2.FromDate <= P.ToDate AND P.ToDate < P2.ToDate ) ) ) BEGIN RAISERROR(Violation of sequenced referential integrity,1,2) ROLLBACK TRANSACTION END

Referential Integrity (3)

Incumbents.PCN is a sequenced foreign key for Positions.PCN, and Incumbents.PCN denes a contiguous history CREATE TRIGGER Sequenced_Ref_Integrity ON Incumbents FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT * FROM Incumbents AS I WHERE NOT EXISTS ( SELECT * FROM Positions AS P WHERE I.PCN = P.PCN AND P.FromDate <= I.ToDate AND I.FromDate < P.ToDate ) OR NOT EXISTS ( SELECT * FROM Positions AS P WHERE I.PCN = P.PCN AND P.FromDate < I.ToDate AND I.ToDate <= P.ToDate ) ) BEGIN RAISERROR(Violation of sequenced referential integrity,1,2) ROLLBACK TRANSACTION END

100

102

Contiguous History
Incumbents.PCN denes a contiguous history CREATE TRIGGER Contiguous_History ON Positions FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT * FROM Positions AS P1, Positions AS P2 WHERE P1.PCN = P2.PCN AND P1.ToDate < P2.FromDate AND NOT EXISTS ( SELECT * FROM Positions AS P3 P1 P2 WHERE P3.PCN = P1.PCN  R  R AND ( ( P3.FromDate <= P1.ToDate P3 P3 AND P1.ToDate < P3.ToDate ) OR ( P3.FromDate < P2.FromDate AND P2.FromDate <= P3.ToDate ) ) ) ) BEGIN RAISERROR(Transaction violates contiguous history,1,2) ROLLBACK TRANSACTION END This is a nonsequenced constraint: it require examining the table at multiple points of time

Referential Integrity (4)

Case 4: Only the referenced table is temporal Incumbents.PCN is a current foreign key for Positions.PCN, CREATE TRIGGER Current_Referential_Integrity ON Incumbents FOR INSERT, UPDATE, DELETE AS IF EXISTS ( SELECT * FROM Incumbents AS I WHERE NOT EXISTS ( SELECT * FROM Positions AS P WHERE I.PCN = P.PCN AND P.ToDate = 3000-01-01 ) ) BEGIN RAISERROR(Violation of current referential integrity,1,2) ROLLBACK TRANSACTION END

101

103

Temporal DBs: Manipulating Temporal DBs with SQL 51

Temporal DBs: Manipulating Temporal DBs with SQL 52

Querying Valid-Time Tables

Employees SSN FirstName LastName BirthDate Salary SSN Amount Positions PCN JobTitle

Incumbents SSN PCN FromDate

Extracting Current State (2)

FromDate ToDate What employees currently have no position? SELECT FirstName FROM Employees WHERE NOT EXISTS ( SELECT * FROM Incumbents WHERE Employees.SSN = Incumbents.SSN AND FromDate <= CURRENT_DATE AND CURRENT_DATE < ToDate )

ToDate

As for constraints, queries and modications can be of three kinds: current, sequenced, and nonsequenced Extracting the current state: What is Bobs current position SELECT JobTitle FROM Employees, Incumbents, Positions WHERE FirstName = Bob AND Employees.SSN = Incumbents.SSN AND Incumbents.PCN = Positions.PCN AND ToDate = 3000-01-01

104

106

Extracting Current State (1)

Another alternative for obtaining Bobs current position SELECT JobTitle FROM Employees, Incumbents, Positions WHERE FirstName = Bob AND Employees.SSN = Incumbents.SSN AND Incumbents.PCN = Positions.PCN AND FromDate <= CURRENT_DATE AND CURRENT_DATE < ToDate Current joins over two temporal tables are not too dicult What is Bobs current position and salary ? SELECT JobTitle, Amount FROM Employees, Incumbents, Positions, Salary WHERE FirstName = Bob AND Employees.SSN = Incumbents.SSN AND Incumbents.PCN = Positions.PCN AND Salary.SSN = Employees.SSN AND FromDate <= CURRENT_DATE AND CURRENT_DATE < ToDate AND Salary.FromDate <= CURRENT_DATE AND CURRENT_DATE < Salary.ToDate

Extracting Prior States

Timeslice queries: extracts a state at a particular point in time Timeslice queries over a previous state requires an additional predicate for each temporal table What was Bobs position at the beginning of 1997? SELECT JobTitle FROM Employees, Incumbents, Positions WHERE FirstName = Bob AND Employees.SSN = Incumbents.SSN AND Incumbents.PCN = Positions.PCN AND FromDate <= 1997-01-01 AND 1997-01-01 < ToDate

105

107

Temporal DBs: Manipulating Temporal DBs with SQL 53

Temporal DBs: Manipulating Temporal DBs with SQL 54

Sequenced Queries
Queries whose result is a valid-time table Use sequenced variants of basic operations: selection, projection, union, sorting, join, dierence, and duplicate elimination Sequenced selection: no change is necessary Who makes or has made more than 50K annually SELECT * FROM Salary WHERE Amount > 50000 Sequenced projection: include the timestamp columns in the select list List the social security numbers of current and past employees SELECT SSN, FromDate, ToDate FROM Salary Duplications resulting from the projection are retained To eliminate them coalescing is needed (see next)

Coalescing while Removing Duplicates

SELECT DISTINCT F.SSN, F.FromDate, L.ToDate FROM Salary F, Salary L WHERE F.FromDate < L.ToDate AND F.SSN = L.SSN AND NOT EXISTS ( SELECT * FROM Salary AS M WHERE M.SSN = F.SSN AND F.FromDate < M.FromDate AND M.FromDate <= L.ToDate AND NOT EXISTS ( SELECT * FROM Salary AS T1 WHERE T1.SSN = F.SSN AND AND T1.FromDate < M.FromDate AND M.FromDate <= T1.ToDate ) ) AND NOT EXISTS ( SELECT * FROM Salary AS T2 WHERE T2.SSN = F.SSN AND AND ( (T2.FromDate < F.FromDate AND F.FromDate <= T2.ToDate) OR (T2.FromDate <= L.ToDate AND L.ToDate < T2.ToDate) ) )

108

110

Coalescing entirely in SQL

F
)

L T1
)

Sequenced Sort
Requires the result to be ordered at each point in time This can be accomplished by appending the start and end time columns in the ORDER BY clause Sequenced sort Incumbents on the position code (rst version) SELECT * FROM Incumbents ORDER BY PCN, FromDate, ToDate Sequenced sorting can also be accomplished by omitting the timestamp columns SELECT * FROM Incumbents ORDER BY PCN

Select those start and end dates such that 3 there are not gaps between these dates 3 no value-equivalent row overlaps the period between the selected start and end dates and has an earlier start date or a later end date Search two value-equivalent rows F(irst) and L(ast) dening the start and end points of a coalesced row First NOT EXISTS ensures that there are no gaps between F.ToDate and L.FromDate Second NOT EXIST ensures that only maximal periods result, i.e. F and L cannot be part of a larger value-equivalent row T2

109

111

Temporal DBs: Manipulating Temporal DBs with SQL 55

Temporal DBs: Manipulating Temporal DBs with SQL 56

Sequenced Join (2) Sequenced Union

A UNION ALL (retaining duplicates) over temporal tables is automatically sequenced if the timestamp columns are kept Who makes or has made annually more than 50,000 or less than 10,000? SELECT * FROM Salary WHERE Amount > 50000 UNION ALL SELECT * FROM Salary WHERE Amount < 10000 A UNION without ALL eliminates duplicates but is dicult to express in SQL (see later)
SELECT S.SSN, Amount, PCN, S.FromDate, S.ToDate FROM Salary S, Incumbents I WHERE S.SSN = I.SSN AND I.FromDate < S.FromDate AND S.ToDate <= I.ToDate UNION ALL SELECT S.SSN, Amount, PCN, S.FromDate, I.ToDate FROM Salary S, Incumbents I WHERE S.SSN = I.SSN AND S.FromDate >= I.FromDate AND S.FromDate < I.ToDate AND I.ToDate < S.ToDate UNION ALL SELECT S.SSN, Amount, PCN, I.FromDate, S.ToDate FROM Salary S, Incumbents I WHERE S.SSN = I.SSN AND I.FromDate >= S.FromDate AND I.FromDate < S.ToDate AND S.ToDate < I.ToDate UNION ALL SELECT S.SSN, Amount, PCN, I.FromDate, I.ToDate FROM Salary S, Incumbents I WHERE S.SSN = I.SSN AND I.FromDate > S.FromDate AND I.ToDate < S.ToDate S I

S I

S I

S I

112

114

Sequenced Join using CASE Sequenced Join (1)

Example: determine the salary and position history for each employee Implies a sequenced join between Salary and Incumbents It is supposed that there are no duplicate rows in the tables: at each point in time an employee has one salary and one position In SQL a sequenced join requires four select statements and complex inequality predicates The following code does not generates duplicates For this reason UNION ALL is used which is more ecient than UNION, which does a lot of work for remove the nonocccurring duplicates SELECT S.SSN, Amount, PCN, "Start Date"= CASE WHEN S.FromDate > I.FromDate THEN S.FromDate ELSE I.FromDate END, "End Date"= CASE WHEN S.ToDate > I.ToDate THEN I.ToDate ELSE S.ToDate END FROM Salary S, Incumbents I WHERE S.SSN = I.SSN AND (CASE WHEN S.FromDate > I.FromDate THEN S.FromDate ELSE I.FromDate END) < (CASE WHEN S.ToDate > I.ToDate THEN I.ToDate ELSE S.ToDate END) CASE allows to write this query in a single statement First CASE simulates a maxDate function of the two arguments, the second one a minDate function Condition in the WHERE ensures that the period of validity is well formed 113 115

Temporal DBs: Manipulating Temporal DBs with SQL 57

Temporal DBs: Manipulating Temporal DBs with SQL 58

Sequenced Join using Functions

create function minDate (@one smalldatetime, @two smalldatetime) returns smalldatetime as begin return CASE WHEN @one < @two then @one else @two end end create function maxDate (@one smalldatetime, @two smalldatetime) returns smalldatetime as begin return CASE WHEN @one > @two then @one else @two end end SELECT S.SSN, Amount, PCN, "Start Date"=maxDate(S.FromDate,I.FromDate), "End Date"=minDate(S.ToDate,I.ToDate) FROM Salary S, Incumbents I WHERE S.SSN = I.SSN AND maxDate(S.FromDate,I.FromDate) < minDate(S.ToDate,I.ToDate) Result Case 1 Case 2 Case 3 Case 4

Sequenced Dierence (1)

)

Department head Professor Department head Professor Professor

) )

Department head Professor

)

Department head

Four possible cases should be taken into account Each of these cases requires a separate SELECT statement in the sequenced version

116

118

Dierence
Implemented in SQL with EXCEPT, NOT EXISTS, or NOT IN List the employees who are department heads (PCN=455332) but are not also professors (PCN=821197): nontemporal version SELECT SSN FROM Incumbents I1 WHERE I1.PCN = 455332 AND NOT EXISTS ( SELECT * FROM Incumbents I2 WHERE I1.SSN = I2.SSN AND I2.PCN = 821197 ) Using EXCEPT (not available in SQL Server) SELECT SSN FROM Incumbents WHERE PCN = 455332 EXCEPT SELECT SSN FROM Incumbents WHERE PCN = 821197 Sequenced version: Identify when the department heads were not professors

Sequenced Dierence (2)

List the employees who are or were department heads (PCN=455332) but were not also professors (PCN=821197)
SELECT I1.SSN, I1.FromDate, I2.FromDate AS ToDate FROM Incumbents I1, Incumbents I2 WHERE I1.PCN = 455332 AND I2.PCN = 821197 AND I1.SSN = I2.SSN AND I1.FromDate < I2.FromDate AND I2.FromDate < I1.ToDate AND NOT EXISTS ( SELECT * FROM Incumbents I3 WHERE I1.SSN = I3.SSN AND I3.PCN = 821197 AND I1.FromDate < I3.ToDate AND I3.FromDate < I2.FromDate ) UNION SELECT I1.SSN, I2.ToDate AS FromDate, I1.ToDate FROM Incumbents I1, Incumbents I2 WHERE I1.PCN = 455332 AND I2.PCN = 821197 AND I1.SSN = I2.SSN AND I1.FromDate < I2.ToDate AND I2.ToDate < I1.ToDate AND NOT EXISTS ( SELECT * FROM Incumbents I3 WHERE I1.SSN = I3.SSN AND I3.PCN = 821197 AND I2.ToDate < I3.ToDate AND I3.FromDate < I1.ToDate ) UNION ... I1 DH I2 Pr.

I1 DH I2 Pr. )

117

119

Temporal DBs: Manipulating Temporal DBs with SQL 59

Temporal DBs: Manipulating Temporal DBs with SQL 60

Sequenced Dierence (3)

... SELECT I1.SSN, I2.ToDate AS FromDate, I3.FromDate AS ToDate FROM Incumbents I1, Incumbents I2, Incumbents I3 WHERE I1.PCN = 455332 AND I2.PCN = 821197 AND I3.PCN = 821197 AND I1.SSN = I2.SSN AND I1.SSN = I3.SSN AND I2.ToDate < I3.FromDate I1 DH AND I1.FromDate < I2.ToDate AND I3.FromDate < I1.ToDate I2 Pr. ) I3 Pr. AND NOT EXISTS ( SELECT * FROM Incumbents I4 WHERE I1.SSN = I4.SSN AND I4.PCN = 821197 AND I2.ToDate < I4.ToDate AND I4.FromDate < I3.FromDate ) UNION SELECT SSN, FromDate, ToDate I1 DH FROM Incumbents I1 ) WHERE I1.PCN = 455332 AND NOT EXISTS ( SELECT * FROM Incumbents I4 WHERE I1.SSN=I4.SSN AND I4.PCN = 821197 AND I1.FromDate < I4.ToDate AND I4.FromDate < I1.ToDate )

Eliminating Duplicates
Remove nonsequenced duplicates from Incumbents SELECT DISTINCT * FROM Incumbents Remove value-equivalent rows from Incumbents SELECT DISTINCT SSN,PCN FROM Incumbents Remove current duplicates from Incumbents SELECT DISTINCT SSN,PCN FROM Incumbents WHERE ToDate = 3000-01-01

120

122

Nonsequenced Variants
Nonsequenced operators (selection, join , . . .) are straightforward: they ignore the time-varying nature of tables List all the salaries, past and present, of employees who had been a hazardous waste specialist at some time SELECT Amount FROM Incumbents, Positions, Salary WHERE Incumbents.SSN = Salary.SSN AND Incumbents.PCN = Positions.PCN AND JobTitle = 20730 When did employees receive raises? SELECT S2.SSN, S2.FromDate AS RAISE_DATE FROM Salary AS S1, Salary AS S2 WHERE S2.Amount > S1.Amount AND S1.SSN = S2.SSN AND S1.ToDate = S2.FromDate

Sequenced Aggregation Functions

Affiliation SSN DNumber Salary SSN Amount FromDate FromDate ToDate ToDate

SQL provides aggregation functions: COUNT, MIN, MAX, AVG, . . . List the maximum salary: non-temporal version SELECT MAX(Amount) FROM Salary List by department the maximum salary: non-temporal version SELECT DNumber, MAX(Amount) FROM Affiliation A, Salary S WHERE A.SSN = S.SSN GROUP BY DNumber

121

123

Temporal DBs: Manipulating Temporal DBs with SQL 61

Temporal DBs: Manipulating Temporal DBs with SQL 62

Number of Employees: Temporal Version Maximum Salary: Temporal Version (1)

E1 E2 E3 MAX 20 25 30 35 20 25 30 30 35 35 30 30 35 35 30 E1 E2 E3 COUNT 1 2 3 20 25 30 3 3 35 2 0 2 30 30 35 1

First step: Compute the periods on which a maximum must be calculated CREATE VIEW SalChanges(Day) as SELECT DISTINCT FromDate FROM Salary UNION SELECT DISTINCT ToDate FROM Salary CREATE VIEW SalPeriods(FromDate, ToDate) as SELECT P1.Day, P2.Day FROM SalChanges P1, SalChanges P2 WHERE P1.Day < P2.Day AND NOT EXISTS ( SELECT * FROM SalChanges P3 WHERE P1.Day < P3.Day AND P3.Day < P2.Day )

Second step: Compute the number of employees for these periods CREATE VIEW TempCount(NbEmp, FromDate, ToDate) as SELECT COUNT(*), P.FromDate, P.ToDate FROM Salary S, SalPeriods P WHERE S.FromDate<=P.FromDate AND P.ToDate<=S.ToDate GROUP BY P.FromDate, P.ToDate UNION ALL SELECT 0, P.FromDate, P.ToDate FROM SalPeriods P WHERE NOT EXISTS ( SELECT * FROM Salary S WHERE S.FromDate<=P.FromDate AND P.ToDate<=S.ToDate ) Third step: Coalesce the above view (as seen before)

124

126

Maximum Salary: Temporal Version (2)

E1 E2 E3 MAX 20 25 30 35 20 25 30 30 35 35 30 30 35 35 30

Maximum Salary by Department: Temporal Version (1)

E1 E2 E3 MAX(D1) MAX(D2) D1 20 D2 D2 30 D1

Second step: Compute the maximum salary for these periods CREATE VIEW TempMax(MaxSalary, FromDate, ToDate) as SELECT MAX(E.Amount), I.FromDate, I.ToDate FROM Salary E, SalPeriods I WHERE E.FromDate <= I.FromDate AND I.ToDate <= E.ToDate GROUP BY I.FromDate, I.ToDate Third step: Coalesce the above view (as seen before)

25 D2 30

D1 35

20 25 35 35 25 30 30 30

Hypothesis: Employees have salary only while they are aliated to a department

125

127

Temporal DBs: Manipulating Temporal DBs with SQL 63

Temporal DBs: Manipulating Temporal DBs with SQL 64

Sequenced Division Maximum Salary by Department: Temporal Version (2)

First step: Compute by department the periods on which a maximum must be calculated
CREATE VIEW Aff_Sal(DNumber, Amount, FromDate, ToDate) as SELECT DISTINCT A.DNumber, S.Amount, maxDate(S.FromDate,A.FromDate), minDate(S.ToDate,A.ToDate) FROM Affiliation A, Salary S WHERE A.SSN=S.SSN AND maxDate(S.FromDate,A.FromDate) < minDate(S.ToDate,A.ToDate) CREATE VIEW SalChanges(DNumber, Day) as SELECT DISTINCT DNumber, FromDate FROM Aff_Sal UNION SELECT DISTINCT DNumber, ToDate FROM Aff_Sal CREATE VIEW SalPeriods(DNumber, FromDate, ToDate) as SELECT P1.DNumber, P1.Day, P2.Day FROM SalChanges P1, SalChanges P2 WHERE P1.DNumber = P2.DNumber AND P1.Day < P2.Day AND NOT EXISTS ( SELECT * FROM SalChanges P3 WHERE P1.DNumber = P3.DNumber AND P1.Day < P3.Day AND P3.Day < P2.Day )

Affiliation SSN DNumber

FromDate

ToDate ToDate

Controls PNumber DNumber WorksOn SSN PNumber

FromDate

FromDate

ToDate

Implemented in SQL with two nested NOT EXISTS List the employees that work in all projects of the department to which they are aliated: non-temporal version SELECT SSN FROM Affiliation A WHERE NOT EXISTS ( SELECT * FROM Controls C WHERE A.DNumber = C.DNumber AND NOT EXISTS ( SELECT * FROM WorksOn W WHERE C.PNumber = W.PNumber AND A.SSN = W.SSN ) )

128

130

Sequenced Division: Case 1

Only WorksOn is temporal First step: Compute the division

Maximum Salary by Department: Temporal Version (3)

Second step: Compute the maximum salary for these periods CREATE VIEW TempMaxDep(DNumber, MaxSalary, FromDate, ToDate) as SELECT P.DNumber, MAX(Amount), P.FromDate, P.ToDate FROM Aff_Sal A, SalPeriods P WHERE A.DNumber = P.DNumber AND A.FromDate <= P.FromDate AND P.ToDate <= A.ToDate GROUP BY P.DNumber, P.FromDate, P.ToDate Third step: Coalesce the above view (as seen before)

W2 W1 Result

E,P1

%!%

E,P2

Affiliation(E,D) Controls(D,P1) Controls(D,P2)

CREATE VIEW TempUnivQuant(SSN, FromDate, ToDate) as SELECT DISTINCT W1.SSN, W1.FromDate, W2.ToDate FROM WorksOn W1, WorksOn W2, Affiliation A WHERE W1.SSN = W2.SSN AND W1.SSN = A.SSN AND W1.FromDate < W2.ToDate AND NOT EXISTS ( SELECT * FROM Controls C WHERE A.DNumber = C.DNumber AND NOT EXISTS ( SELECT * FROM WorksOn W WHERE C.PNumber = W.PNumber AND A.SSN = W.SSN AND W.FromDate <= W1.FromDate AND W2.ToDate <= W.ToDate ) )

Second step: Coalesce the above view 129 131

Temporal DBs: Manipulating Temporal DBs with SQL 65

Temporal DBs: Manipulating Temporal DBs with SQL 66

Sequenced Division: Case 2 (1)

Only Controls and WorksOn are temporal Employees may work in projects controlled by departments dierent from the department to which they are aliated First step: Construct the periods on which the division must be computed C1 C2 W1 W2 Result E,P1 D,P1 D,P2 Affiliation(E,D) E,P2

Sequenced Division: Case 2 (3)

Second step: Compute the division of these periods
CREATE VIEW TempUnivC2(SSN,FromDate,ToDate) as SELECT DISTINCT P.SSN,P.FromDate,P.ToDate FROM ProjPeriodsC2 P, Affiliation A WHERE P.SSN=A.SSN AND NOT EXISTS ( SELECT * FROM Controls C WHERE A.DNumber=C.DNumber AND C.FromDate<=P.FromDate AND P.ToDate<=C.ToDate AND NOT EXISTS ( SELECT * FROM WorksOn W WHERE C.PNumber=W.PNumber AND P.SSN=W.SSN AND W.FromDate<=P.FromDate AND P.ToDate<=W.ToDate ) )

!!%!!%

Third step: Coalesce the above view

132

134

Sequenced Division: Case 2 (2)

CREATE VIEW ProjChangesC2(SSN,Day) as SELECT DISTINCT SSN,FromDate FROM Affiliation A, Controls C WHERE A.DNumber=C.DNumber UNION SELECT DISTINCT SSN,ToDate FROM Affiliation A, Controls C WHERE A.DNumber=C.DNumber UNION SELECT DISTINCT SSN,FromDate FROM WorksOn UNION SELECT SSN,ToDate FROM WorksOn CREATE VIEW ProjPeriodsC2(SSN,FromDate,ToDate) as SELECT P1.SSN,P1.Day,P2.Day FROM ProjChangesC2 P1, ProjChangesC2 P2 WHERE P1.SSN=P2.SSN AND P1.Day<P2.Day AND NOT EXISTS ( SELECT * FROM ProjChangesC2 P3 WHERE P1.SSN=P3.SSN AND P1.Day<P3.Day AND P3.Day<P2.Day )

Sequenced Division: Case 3 (1)

Only Affiliation and WorksOn are temporal Employees may work in projects controlled by departments dierent from the department to which they are aliated First step: Construct the periods on which the division must be computed E,D E,P1 E,P2 Controls(D,P1) Controls(D,P2)

A W W ProjChanges

%%!%

133

135

Temporal DBs: Manipulating Temporal DBs with SQL 67

Temporal DBs: Manipulating Temporal DBs with SQL 68

Sequenced Division: Case 3 (2)

CREATE VIEW Aff_WO(SSN, DNumber, PNumber, FromDate, ToDate) as SELECT DISTINCT A.SSN, A.DNumber, W.PNumber, maxDate(A.FromDate,W.FromDate), minDate(A.ToDate,W.ToDate) FROM Affiliation A, WorksOn W WHERE A.SSN=W.SSN AND maxDate(A.FromDate,W.FromDate) < minDate(A.ToDate,W.ToDate) CREATE VIEW ProjChangesC3(SSN, DNumber, Day) as SELECT DISTINCT SSN, DNumber, FromDate FROM Aff_WO UNION SELECT DISTINCT SSN, DNumber, ToDate FROM Aff_WO UNION SELECT SSN, DNumber, FromDate FROM Affiliation UNION SELECT SSN, DNumber, ToDate FROM Affiliation CREATE VIEW ProjPeriodsC3(SSN, DNumber, FromDate, ToDate) as SELECT P1.SSN, P1.DNumber, P1.Day, P2.Day FROM ProjChangesC3 P1, ProjChangesC3 P2 WHERE P1.SSN = P2.SSN AND P1.DNumber = P2.DNumber AND P1.Day < P2.Day AND NOT EXISTS ( SELECT * FROM ProjChangesC3 P3 WHERE P1.SSN = P3.SSN AND P1.DNumber = P3.DNumber AND P1.Day < P3.Day AND P3.Day < P2.Day )

Sequenced Division: Case 4 (1)

Affiliation, Controls, and WorksOn are all temporal First step: Construct the periods on which the division must be computed E,D D,P1 D,P2 E,P1 E,P2

A C1 C2 W1 W2 Result

!%!%! ! %

136

138

Sequenced Division: Case 4 (2)

CREATE VIEW Aff_Cont(SSN, DNumber, PNumber, FromDate, ToDate) as SELECT DISTINCT A.SSN, A.DNumber, C.PNumber, maxDate(A.FromDate,C.FromDate), minDate(A.ToDate,C.ToDate) FROM Affiliation A, Controls C WHERE A.DNumber=C.DNumber AND maxDate(A.FromDate,C.FromDate) < minDate(A.ToDate,C.ToDate) CREATE VIEW Aff_Cont_WO(SSN, DNumber, PNumber, FromDate, ToDate) as SELECT DISTINCT A.SSN, A.DNumber, W.PNumber, maxDate(A.FromDate,W.FromDate), minDate(A.ToDate,W.ToDate) FROM Aff_Cont A, WorksOn W WHERE A.PNumber=W.PNumber AND A.SSN=W.SSN AND maxDate(A.FromDate,W.FromDate) < minDate(A.ToDate,W.ToDate) CREATE VIEW ProjChangesC4(SSN, DNumber, Day) as SELECT DISTINCT SSN, DNumber, FromDate FROM Aff_Cont UNION SELECT DISTINCT SSN, DNumber, ToDate FROM Aff_Cont UNION SELECT DISTINCT SSN, DNumber, FromDate FROM Aff_Cont_WO UNION SELECT DISTINCT SSN, DNumber, ToDate FROM Aff_Cont_WO UNION SELECT SSN, DNumber, FromDate FROM Affiliation UNION SELECT SSN, DNumber, ToDate FROM Affiliation CREATE VIEW ProjPeriodsC4(SSN, DNumber, FromDate, ToDate) as SELECT P1.SSN, P1.DNumber, P1.Day, P2.Day FROM ProjChangesC4 P1, ProjChangesC4 P2 WHERE P1.SSN = P2.SSN AND P1.DNumber = P2.DNumber AND P1.Day < P2.Day AND NOT EXISTS ( SELECT * FROM ProjChangesC4 P3 WHERE P1.SSN = P3.SSN AND P1.DNumber = P3.DNumber AND P1.Day < P3.Day AND P3.Day < P2.Day )

Sequenced Division: Case 3 (3)

Second step: Compute the division of these periods
CREATE VIEW TempUnivQuant(SSN, FromDate, ToDate) as SELECT DISTINCT P.SSN, P.FromDate, P.ToDate FROM ProjPeriodsC3 P WHERE NOT EXISTS ( SELECT * FROM Controls C WHERE P.DNumber=C.DNumber AND NOT EXISTS ( SELECT * FROM WorksOn W WHERE C.PNumber=W.PNumber AND P.SSN=W.SSN AND W.FromDate<=P.FromDate AND P.ToDate<=W.ToDate ) )

Third step: Coalesce the above view

137

139

Temporal DBs: Manipulating Temporal DBs with SQL 69

Temporal DBs: Manipulating Temporal DBs with SQL 70

Sequenced Division: Case 4 (3)

Second step: Compute the division of these periods
CREATE VIEW TempUnivQuant(SSN, FromDate, ToDate) as SELECT DISTINCT P.SSN, P.FromDate, P.ToDate FROM ProjPeriodsC4 P WHERE NOT EXISTS ( SELECT * FROM Controls C WHERE P.DNumber = C.DNumber AND C.FromDate <= P.FromDate AND P.ToDate <= C.ToDate AND NOT EXISTS ( SELECT * FROM WorksOn W WHERE C.PNumber = W.PNumber AND P.SSN=W.SSN AND W.FromDate <= P.FromDate AND P.ToDate <= W.ToDate ) )

Third step: Coalesce the above result

140

Temporal DBs: Manipulating Temporal DBs with SQL 71