时间是自然界无处不在的属性。时态信息处理已经成为现代信息系统的重要组成部分。本书系统研究时态信息处理技术及其应用，内容包括：（1）时间模型、时间演算和时态逻辑方法；（2）时态数据库基本概念、时态数据模型、时间算子now的语义和时态数据索引；（3）时态数据查询语言，以TempDB为例介绍时态数据库管理系统的设计和实现；（4）XML、工作流时态扩展和时态知识模型；（5）时态应用模式，并给出一个典型的时态应用实例。

本书读者对象为高等院校计算机专业的师生，科研机构及相关领域的研发人员等。

Time is a natural attribute of everything. With the explosive growth of computer and network systems, temporal information has received extensive attention in both academia and industry. It plays an increasingly important role in the new generation information systems and also a key role in some applications. The use of temporal information modeling and processing technology in these applications can make them more useful and more convenient.

Temporal database and application problems have been mentioned during the 1970s. The groundbreaking study in this area was conducted by J. Ben Zvi, who proposed the bitemporal concept and a temporal database model in his dissertation, submitted to the University of California, Los Angeles, in 1982. In subsequent years, the temporal database theory research has grown vigorously and hundreds of temporal models have been proposed. James Clifford, Christian S. Jensen, Richard T. Snodgrass and Andreas Steiner made important contributions to temporal database models, theory and technology. In the recent years, along with information technology that can meet the increasing requirement for new applications, the temporal database theory and application technologies have made remarkable progress. However, there are many problems in temporal information processing, e.g., weakness in temporal calculus theory, low efficiency of temporal storage and access, complex temporal information processing and lack of the software development tools. There are three main trends in temporal technologies: model standardization, middleware development and application diversification.

We began to pay special attention to research on temporal database when we undertook the software application project: Intelligent Decision Support System of Salary (SIDSS), in 1998. The main concept behind SIDSS is that an employee's wage is paid according to information related to the employee and to the policies of the salary management department. SIDSS is a typical temporal system, in which the employee information that influences his or her salary is the typical temporal data and the salary policies that can be changed by the management department which also are time-varying knowledge. In the SIDSS, we used a temporal database model to design the employee database. We proposed a rule-based temporal knowledge model to represent the time-varying salary policies, and implemented a reasoning mechanism to realize the employee's salary determination and change based on the employee's temporal information and the salary policies based on temporal rule knowledge. The SIDSS has been used by more than ten thousands of agencies and millions of employees since 2000. In the past decade, we have undertaken more than 20 research projects on temporal database systems and associated software that involved the temporal data/knowledge base middleware, extension temporal to workflow, XML and role-based cooperative software, and others. Remarkably, TempDB 2.01, a temporal database management middleware developed by us, has been downloaded by hundreds of users from more than 10 countries since its release on July 2008.

This book is a collection of main study and research results that we obtained in the past years. There are five parts in this book. Part Ⅰ gives the time models, basic types of time data and their calculation methods. In Part Ⅱ, we introduce the basic concepts of temporal database. We then discuss the complex semantics of temporal variables and the basic problems of temporal database. In Part Ⅱ, we introduce database systems based on temporal information, such as spatio-temporal database systems and temporal XML database. Part Ⅲ discusses some temporal index technologies and proposes some new temporal indexing methods, such as bitemporal index, spatio-temporal data indexes and temporal XML index. These are key problems in the implementation of temporal database systems and applications. Part Ⅳ introduces the basic concepts of Temporal Database Management Systems (TDBMS) and the main techniques for the implementation of TempDB 2.1. Part Ⅴ discusses some temporal application technologies, such as temporal knowledge representation and reasoning mechanism, temporal extension to workflow and role management systems. In Part Ⅴ, as a case study, we introduce temporal data model, temporal knowledge reasoning and their implementations on a typical temporal application of SIDSS.

The aim of this book is to provide a basic understanding on calculation methods of time data and on temporal information modeling, as well as the implementation technologies of temporal applications. Researchers, graduate students and information technology professionals who are interested in the information systems and software involving temporal attributes, will find a starting point and a reference 

for their study, research and development from this book.

We would like to acknowledge all of the researchers in the area of temporal database modeling and applications. Based on their publications, their influence on this book is profound. We would like to thank all of the colleagues and students in the Co-soft Research and Development Center at Sun Yat-Sen University, China. We wish to express thanks to them for their valuable suggestions, discussions and assistance. We would also like to thank Dr. Jing Xiao, Dr. Gansen Zhao and Mr. Aaron Tang for their valuable suggestions and kind help.

The work described in this book was supported by The National Natural Science Foundation of China under Grant Nos. 60373081, 60673135, 60736020, and 60970044; The Natural Science Foundation of Guangdong Province of China under Grant Nos. 4105503, 7003721, 5003348, and 9151027501000054; and the Program for New Century Excellent Talents at the University of China under 

Grant No. NCET-04-0805.

Yong Tang, Xiaoping Ye and Na Tang

April, 2009

Contents

Preface i

List of Figures and Tables xiii

Part Ⅰ　Temporal Models and Calculation Methods 1

1　From Time Data to Temporal Information 3

1.1　Application Requirement 3

1.2　What Is Time Data 4

1.2.1　Time Point 5

1.2.2　Time Interval 6

1.2.3　Time Span 7

1.2.4　Complex Time Data 7

1.3　Temporal Information, Temporal Database and Temporal System 8

1.3.1　What Is Temporal Information 8

1.3.2　Temporal Database 8

1.3.3　Temporal System 9

1.4　Origin and Development of Temporal Information Technologies 9

1.4.1　Founding Phase 10

1.4.2　Development Phase 11

1.4.3　Application Phase 11

1.5　Current Situation, Problems and Trends 13

1.5.1　Current Situation 13

1.5.2　Existent Problems in Temporal Database Research 15

1.5.3　Trends 16

References 17

2　Time Calculation and Temporal Logic Method 21

2.1　Time Model 22

2.1.1　Continuous Model 22

2.1.2　Stepwise Model 23

2.1.3　Discrete Model 23

2.1.4　Non Temporal Model 24

2.2　Properties of Time Structure 24

2.2.1　Order Relations of Time Sets 24

2.2.2　First Order Properties of Time Flow 24

2.3　Point-Based Temporal Logic 26

2.3.1　Temporal Extensions Based Snapshot Model 26

2.3.2　Temporal Extensions Based Timestamp Model 28

2.4　Interval-Based Temporal Logic 29

2.4.1　From Interval to Point 30

2.4.2　From Point to Point 31

2.4.3　Temporal Predict 32

2.5　Calculation Based on Span 33

2.6　Other Temporal Calculations in Common Use 34

2.7　Time Granularity and Conversion Calculation 34

2.7.1　Time Granularity and Chronon 35

2.7.2　State of Existence of Time Granularity 35

2.7.3　Operations of Time Granularity 36

2.7.4　Relational Chart of Time Granularity Conversion 38

2.8　Tense Logic 38

2.8.1　Syntax and Semantics of Tense Logic 39

2.8.2　Axiomatics and Properties 40

References 42

3　Temporal Extension of Relational Algebra 43

3.1　Regular Relational Operations 44

3.1.1　Basic Notions 44

3.1.2　Relational Algebra 45

3.1.3　Relational Calculus 47

3.2　Relational Algebra of Historical Database 47

3.2.1　Basic Notions and Terminologies 48

3.2.2　HRDM Model 48

3.2.3　Historical Relational Algebra of HRDM 49

3.3　Bitemporal Relational Algebra of BCDM 55

3.3.1　Basic Notions and Terminologies 55

3.3.2　Bitemporal Relational Algebra 59

3.4　Snapshot Reducibility and Temporal Completeness 62

3.4.1　Snapshot Reducibility 62

3.4.2　Temporal Semi-Completeness 64

3.4.3　Temporal Completeness 65

References 65

Part Ⅱ　Database Based on Temporal Information 67

4　Temporal Data Model and Temporal Database Systems 69

4.1　Time-Dimensions 69

4.1.1　User-Defined Time 69

4.1.2　Valid Time 70

4.1.3　Transaction Time 71

4.1.4　Two Temporal Variables: Now and UC 71

4.1.5　An Illustration 72

4.2　Temporal Database Types 75

4.2.1　Snapshot Database 75

4.2.2　Historical Database 76

4.2.3　Rollback Database 78

4.2.4　Bitemporal Database 81

4.3　Temporal Data Models 82

4.3.1　Bitemporal Time Stamps 82

4.3.2　BCDM 85

4.3.3　Temporal Entity-Relationship Data Model 86

4.4　Difference from Real-Time Database 87

References 88

5　Spatio-Temporal Data Model and Spatio-Temporal Databases 91

5.1　Introduction 91

5.2　Spatio-Temporal Data Model 92

5.2.1　Spatio-Temporal Object 92

5.2.2　Basic Considerations of Spatio-Temporal Modeling 93

5.2.3　Version Based Data Model 96

5.2.4　Event-Based Data Model 100

5.2.5　Constraint-Based Data Model 103

5.2.6　Moving Objects Data Model 103

5.3　Query on Spatio-Temporal Data 106

5.3.1　Spatio-Temporal Data Query 107

5.3.2　Moving Data Query 107

5.3.3　Spatio-Temporal Database Language 108

5.4　Structure of Spatio-Temporal Database System 109

5.4.1　Structure of Complete Type 109

5.4.2　Structure of Layered Type 110

5.4.3　Structure of Extended Type 110

Reference 111

6　Temporal Extension of XML Data Model 113

6.1　Motivation 114

6.1.1　XML Temporal Driven 114

6.1.2　Commercial-Driven Temporal Database 116

6.2　Temporal Research of the Semi-Structured Data 119

6.3　Temporal XML Model and Query Mechanism 120

References 123

7　Data Operations Based on Temporal Variables 125

7.1　Introduction 125

7.2　Data Model Based on Temporal Variables 127

7.2.1　Order and Temporal Variables 127

7.2.2　Main Body Instances 129

7.2.3　Bitemporal Relation Model Based on Variables 131

7.3　Data Updating 132

7.3.1　Data Inserting 132

7.3.2　Data Deleting 135

7.3.3　Data Modifying 136

7.4　Data Querying 138

7.4.1　Now in Current Versions 138

7.4.2　Now in Non-Current Version 141

7.4.3　Temporal Querying Algorithms 142

References 147

Part Ⅲ　Temporal Index Technologies 149

8　Temporal Indexes Supporting Valid Time 151

8.1　Introduction 151

8.2　Summary of Temporal Index 152

8.2.1　Temporal Index Based on Transaction Time 153

8.2.2　Index Based on Valid Time 154

8.2.3　Bitemporal Index 155

8.3　TRdim 159

8.3.1　Relative Temporal Data Model 159

8.3.2　Temporal Relation Index Model 160

8.4　Data Querying and Index Updating 166

8.4.1　Index Querying 166

8.4.2　Index Updating 167

8.5　Simulation 171

8.5.1　Index Constructing 171

8.5.2　Query Based on Probability 172

8.5.3　Query Based on the Number of Data 172

References 173

9　Indexes for Moving-Objects Data 175

9.1　Introduction 175

9.2　Data Model for Moving Objects 181

9.2.1　Data Model Modm 182

9.2.2　Temporal Summary 184

9.3　Index for Moving Object Data 189

9.3.1　Linear Order Division 189

9.3.2　Index Model Modim 192

9.4　Data Query 195

9.5　Index Update 198

References 201

10　Temporal XML Index Schema 203

10.1　Introduction 203

10.2　Linear-Order Relation 205

10.2.1　Linear-Order Matrix 206

10.2.2　Linear-Order Equivalence Relation 207

10.3　Temporal Summary and Temporal Indexing 210

10.3.1　Data Model 210

10.3.2　Temporal Summary 211

10.3.3　Temporal Indexing 213

10.4　Data Query 214

10.4.1　Query Based on Absolute Paths 215

10.4.2　Query Based on Relative Paths 215

10.5　Simulation and Evaluation 217

10.5.1　Environment and Data Design 217

10.5.2　Simulation and Evaluation 217

References 223

Part Ⅳ　Temporal Database Management Systems 225

11　Implementation of Temporal Database Management Systems 227

11.1　Introduction 227

11.2　TimeDB 228

11.2.1　Installation 228

11.2.2　TimeDB 2.0 Beta 4's User Interface 230

11.2.3　Examples 232

11.3　TempDB 234

11.3.1　Installation 234

11.3.2　TempDB's User Interface 235

11.3.3　Examples 238

11.4　Comparing TimeDB with TempDB 241

References 242

12　Improvement and Extension to ATSQL2 245

12.1　Introduction 245

12.2　Study on ATSQL2 246

12.2.1　Requirements and Expatiation 246

12.2.2　Properties of ATSQL2 247

12.3　Interpretation of ATSQL2 Semantics 249

12.3.1　Data Definition Statement 249

12.3.2　Data Manipulation Statement 250

12.3.3　Data Query Statement 251

12.4　Improved ATSQL2 255

12.4.1　Clear Regulation to the Semantic Operator 255

12.4.2　Re-Definition of Scalar Expression 256

12.4.3　Clearly Regulate the Usage of Common Operators and 

Temporal Operators in Conditional Statements 257

References 258

13　Design and Implementation of TempDB 261

13.1　Introduction 261

13.2　Framework of TempDB 262

13.2.1　Middleware Architecture 262

13.2.2　Platform of Implementation 263

13.2.3　Architecture of TempDB 263

13.3　Implementation of TempDB 266

13.3.1　Temporal DDL 266

13.3.2　Temporal DML 267

13.3.3　Temporal Query 269

13.4　Processing Mechanism of Temporal Integrity Constraints 270

13.4.1　Basic Concepts 271

13.4.2　Temporal Insertion 271

13.4.3　Temporal Deletion 272

13.4.4　Temporal Modification 273

13.5　Optimization of Performance 275

13.5.1　Temporal Indexes and MAP21 275

13.5.2　Binding on Now 275

13.5.3　MAP21-B 276

References 278

Part Ⅴ　Temporal Application and Case Study 281

14　Research on Temporal Extended Role Hierarchy 283

14.1　Introduction 283

14.2　Related Works 284

14.3　Extended Role Hierarchy 285

14.4　Temporal Role Hierarchy 287

14.4.1　Time Constraint on the Inheritance of Restricted 

Special Permission 287

14.4.2　Temporal Inheritance Character 289

14.4.3　Space and Time Efficiency Analysis 290

References 292

15　Temporal Workflow Modeling and Its Application 293

15.1　Introduction 293

15.2　Related Works 294

15.3　A Modified Workflow Meta-Model and Temporal Attributes 295

15.3.1　Build-Time Meta-Model 296

15.3.2　Run-Time Meta-Model 299

15.3.3　A Formal Model of Temporal Workflow 300

15.4　Fuzzy Temporal Workflow Nets (FTWF-Nets) 301

15.4.1　Fuzzy Time Point 301

15.4.2　Formal Definition for FTWF-Nets 302

15.4.3　Time Related Calculation in FTWF-Nets 303

15.5　Time Modeling and Time Possibility Analysis 304

15.6　An Illustration 306

References 308

16　Temporal Knowledge Representation and Reasoning 311

16.1　Introduction 311

16.2　Temporal Production System 313

16.2.1　Basic Definitions 313

16.2.2　Temporal Reasoning 315

16.3　Prototype Implementation in a Salary System 318

16.3.1　Global Database 318

16.3.2　Data Structures of Temporal Production Rules 

in Database 319

16.3.3　Data Structures of Facts in Database 320

16.3.4　Details in Reasoning 320

16.3.5　Binding Semantics of Now Variable 322

References 322

17　Temporal Application Modes and Case Study 325

17.1　Temporal Application Modes 326

17.1.1　Entire Temporal Application Mode 326

17.1.2　Embedding Temporal Application Mode 327

17.1.3　Mix Temporal Application Mode 327

17.2　Temporal Data/Knowledge View 327

17.2.1　Temporal Data View 327

17.2.2　Temporal Data/Knowledge Model 328

17.2.3　Links of Temporal Knowledge and Temporal Data 328

17.3　Temporal Application in Cooperative Software 330

17.3.1　Three Basic Elements of Cooperative Software 330

17.3.2　Temporal Relation of Collaborative Roles 331

17.3.3　Temporal Extension in the Collaboration Information 332

17.3.4　Temporal Extension of Workflow 332

17.3.5　Case Study 333

17.4　SIDSS: A Typical Example of Temporal Application 334

17.4.1　Introduction 334

17.4.2　Temporal Data in SIDSS 335

17.4.3　Temporal Knowledge in SIDSS 337

17.4.4　Implementation of SIDSS 340

References 341

Appendix 343

A.1　Extension ATSQL of TempDB 2.1 343

A.2　API of TempDB 2.1 345

Index 347

List of Figures and Tables

Figure 1.1　Representation of time intervals 6

Figure 2.1　Information about a teacher 23

Figure 2.2　Allen's temporal relations 30

Figure 2.3　Temporal relationships between time intervals and points 31

Figure 2.4　Temporal relationships between time points 31

Figure 2.5　Granularity in Gregorian calendar system 38

Figure 2.6　Conversion chart of multi-calendar 39

Figure 3.1(a)　A normal bitemporal element 56

Figure 3.1(b)　Not a normal bitemporal element  56

Figure 3.2(a)　u and v 58

Figure 3.2(b)　uv 58

Figure 3.2(c)　uv 58

Figure 3.2(d)　uv 58

Figure 3.3　Snapshot reducibility 63

Figure 4.1　An additional illustration of a faculty salary temporal relation 73

Figure 4.2　The state of snapshot relation concerning valid time and 

transaction time 76

Figure 4.3　The states of the historical database concerning valid time and 

transaction time 77

Figure 4.4　Relation of attribute, tuple and valid time dimension in 

a coordinate system 78

Figure 4.5　The states of the transaction database concerning valid time and 

transaction time 80

Figure 4.6　The relation of attribute, tuple and transaction time dimension in 

a coordinate system 81

Figure 4.7　An illustration of the valid time and the transaction time of a fact 81

Figure 4.8　The bitemporal states concerning the valid time and 

the transaction time 82

Figure 4.9　The bitemporal information of Alice's title and salary 85

Figure 4.10　Simple values and time structure in TERM 86

Figure 4.11　Entity definition in TERM 87

Figure 5.1　Spatio-temporal relationship 95

Figure 5.2　Modeling layers of spatio-temporal data 95

Figure 5.3　Sequential snapshots model 97

Figure 5.4　Base state with amendments model 97

Figure 5.5　Space-time cube model 98

Figure 5.6　Space-time composite model 99

Figure 5.7　Object-oriented spatio-temporal model 100

Figure 5.8　Event-based spatio-temporal data model 101

Figure 5.9　ESTDM's pointer structure 102

Figure 5.10　Three domains model 103

Figure 5.11　Summarization of spatio-temporal database 104

Figure 5.12　Layered architecture of STDBMS 110

Figure 5.13　Extending architecture of STDBMS 111

Figure 7.1　Past semantics and uncertainty 140

Figure 7.2　Future semantics and binding 141

Figure 8.1　HR-tree 153

Figure 8.2　ST-tree 154

Figure 8.3　Interval tree 155

Figure 8.4　Time index 156

Figure 8.5　2LBIT 156

Figure 8.6　M-IVTT 157

Figure 8.7　4R-tree 158

Figure 8.8　TRqdm model 160

Figure 8.9　Temporal summary 162

Figure 8.10　Temporal preorder (Γ) 163

Figure 8.11　Open complementary submatrix relative to 23 164

Figure 8.12　Linear order branch of (Γ) 165

Figure 8.13　Temporal index 166

Figure 8.14　Reconstruction of LOB based on inserting the nodes 168

Figure 8.15　Reconstruction of the LOB based on deleted nodes 170

Figure 8.16　Space cost of constructing the index 171

Figure 8.17　Time cost of constructing the index 172

Figure 8.18　Query based on the change of the probability 

with the same time 172

Figure 8.19　Query based on the number of data 173

Figure 9.1　Trajectories of moving object 184

Figure 9.2?Data mode for moving objects 186

Figure 9.3?Mode for temporal summary 188

Figure 9.4?Time order matrix 189

Figure 9.5?UL(23) and DR(23) 190

Figure 9.6?HLOM(D) 192

Figure 9.7?Index mode for moving object 194

Figure 9.8?Example for the index mode of moving objects 200

Figure 9.9?Index mode of moving objects after the inserting of segments 200

Figure 10.1?Linear matrix LOM(D) 206

Figure 10.2?UL(23) and DR(23) 207

Figure 10.3?HLOM(D) 209

Figure 10.4?Least-TOER and longest-TOER are mutually not contained 

in each other 210

Figure 10.5?Instance of temporal XML data 211

Figure 10.6?Temporal summary 213

Figure 10.7?Temporal indexing 214

Figure 10.8?Comparison on the space between data and indexing file 218

Figure 10.9?Time consumed in building index 219

Figure 10.10?Relation between XML data and index document 219

Figure 10.11?Comparisons on time consuming to Q3 220

Figure 10.12?Comparison on time consuming to Q6 220

Figure 10.13?Comparison on span of periods in Q3 220

Figure 10.14?Comparison on span of periods in Q6 221

Figure 10.15?Visited nodes in the same querying process 221

Figure 10.16?Comparison in path-querying 222

Figure 10.17?Relation between time span and nodes needed to view 222

Figure 11.1?TimeDB's user interface 229

Figure 11.2?Attributes setting interface 229

Figure 11.3?TimeDB menu 230

Figure 11.4?Transaction menu 231

Figure 11.5?File menu 231

Figure 11.6?Help menu 232

Figure 11.7?Welcome interface 235

Figure 11.8?User interface 235

Figure 11.9?Connection configuration dialog 236

Figure 11.10?Create database (schema) 237

Figure 11.11?Toolbar 237

Figure 11.12?ATSQL command editor 237

Figure 13.1　Architecture of TempDB 263

Figure 13.2　Transformation of overlaps' parse tree 265

Figure 14.1　Role hierarchies of adding private roles 285

Figure 14.2　Role permission of extended role hierarchy 286

Figure 14.3　Role hierarchy of extended inheritance mode 287

Figure 14.4　Up-transferring of time constraint on PermissionRS 288

Figure 14.5　Space comparisons of the two models 291

Figure 15.1　Organization meta-model 297

Figure 15.2　Information meta-model 297

Figure 15.3　Application meta-model 298

Figure 15.4　Process meta-model 299

Figure 15.5　Run-time meta-model 300

Figure 15.6　Trapezoid function of a fuzzy time point 302

Figure 15.7　ab (b is a fuzzy time point) 304

Figure 15.8　ab (b is a precise time point) 305

Figure 15.9　FTWF-net representation 306

Figure 15.10　(?o(?)?f(?)) of the determining process 307

Figure 16.1　Resolution process 316

Figure 16.2　The reasoning process 317

Figure 16.3　Architecture of salary system 318

Figure 16.4　Relation between data tables 319

Figure 16.5　Physical structure of a rule in rule base 321

Figure 17.1　Various temporal application modes 326

Figure 17.2　Temporal data view 328

Figure 17.3　Framework of temporal information processing 329

Figure 17.4　Temporal data knowledge model 330

Figure 17.5　Three basic elements of cooperative application 331

Figure 17.6　Three aspects of TRR diagram 331

Figure 17.7　Roles and relationship in SCHOL@ 334

Figure 17.8　Basic elements in SIDSS 335

Figure 17.9　Metafile of NTER model 336

Figure17.10　Example of NTER model in SIDSS 337

Figure 17.11　Temporal character of salary policy 338

Figure 17.12　Structure of SIDSS 341

Table 1.1　Employees' information with time point attribute 6

Table 1.2　Employees' information with time interval attribute 7

Table 1.3　Departure information of bus with time point set 7

Table 1.4　Employees' information with time interval set 7

Table 1.5　Temporal information of academic title 8

Table 1.6　Temporal query languages 14

Table 2.1a　Relation of workplace 28

Table 2.1b　Relation of duty 28

Table 2.2　Allen's relationships of temporal intervals 29

Table 2.3　Temporal relationships between time intervals and points 31

Table 2.4　Temporal relationships between time points 31

Table 2.5a　Flight departures 36

Table 2.5b　Vacations 36

Table 2.6　Time axis of dynamic granularity 36

Table 3.1　Changes in employees' salary 48

Table 3.2　Relation r1 50

Table 3.3　Relation r2 50

Table 3.4　Relation r3 51

Table 3.5　Relation r4 51

Table 3.6　Relation r5 52

Table 3.7　Relation R 52

Table 3.8　Relation S 52

Table 3.9　Relation TRS 53

Table 3.10　Select_IFemployee's number=929502288(r1) 54

Table 3.11　Select_WHENemployee's number=929502288[2003, 2005] (r1) 54

Table 3.12　Relation r1 59

Table 3.13　Relation r2 59

Table 3.14　r1 BT r2 60

Table 3.15　r1 BT r2 60

Table 3.16　r1 -BT r2 60

Table 3.17　Relation r1 on schema R 61

Table 3.18　Relation r2 on schema S 61

Table 3.19　r1 BT r2 61

Table 3.20　ΠX(r) 62

Table 3.21　σBT(Employee's number="92950228")∧([2008,UC), [2005,Now])(r1) 62

Table 3.22　Employee's information 63

Table 3.23　Slice of employee's information 63

Table 3.24　Result of implementing query on temporal relation 64

Table 3.25　Result of implementing query on regular relation 64

Table 4.1　A faculty salary relation 76

Table 4.2　A faculty salary historical relation 77

Table 4.3　A faculty salary rollback relation 79

Table 4.4　A way to store bitemporal data 83

Table 4.5　Bitemporal time stamp representation of a faculty salary 

bitemporal relation 84

Table 4.6　Improved bitemporal time stamp representation of a faculty 

salary bitemporal relation 84

Table 6.1　Temporally ungrouped employee table 118

Table 6.2　Temporally grouped employee table 118

Table 6.3　Comparison of data structure 118

Table 6.4　Comparison of query language 118

Table 7.1　Bitemporal relation "Employees" 130

Table 7.2　MI White of inserting new tuple 131

Table 7.3　Black's record(1) 133

Table 7.4　Black's record (2) 133

Table 7.5　Black's record (3) 133

Table 7.6　Black's recording (4) 134

Table 7.7　New relation after deleting 135

Table 7.8　Relation in processing of modification (1) 136

Table 7.9　Relation in processing of modification (2) 136

Table 7.10　Deleted temporal relation propagating backward 137

Table 7.11　John's temporal recording 139

Table 7.12　Black's temporal recording 139

Table 7.13　Temporal records of Raul (1) 141

Table 7.14　Temporal records of Raul (2) 142

Table 7.15　Temporal recording of Raul (3) 142

Table 7.16　Temporal relation MI1 143

Table 7.17　Temporal relation MI2 143

Table 7.18　Temporal connection of MI1 and MI2 144

Table 7.19　Projecting on attributes "Name" and "Dept" 144

Table 7.20　Projection on "Title" 145

Table 7.21　Projecting on "Salary" 145

Table 8.1　Temporal relation data instance personnel 160

Table 8.2　Summary nodes 162

Table 8.3　Index nodes 166

Table 9.1　Concrete information of trajectories 185

Table 9.2　Data of summary nodes 187

Table 9.3　Data of index node 193

Table 10.1　Data for building index 218

Table 11.1　Employee 233

Table 11.2　Temporal data before inserting 239

Table 11.3　Temporal data after inserting 239

Table 11.4　Temporal data after deleting 240

Table 11.5　Employee table 241

Table 11.6　Result of the historical non-sequenced query 241

Table 11.7　Comparing TempDB 2.01 with TimeDB 2.0 Beta 4 241

Table 12.1　Before record insertion 251

Table 12.2　After record insertion 251

Table 12.3　Relation r1 252

Table 12.4　Relation r2 252

Table 12.5　Relation r3r1r2 253

Table 12.6　Relation r4r1r2 253

Table 12.7　Relation R 254

Table 12.8　Relation S 254

Table 12.9　Relation TRS 254

Table 12.10　Before merging 255

Table 12.11　After merging 255

Table 12.12　Operations between improved data types 257

Table 14.1　Extended role inheritance rule 286

Table 14.2　Role comparison of two models 290

Table 17.1　Rule table of promotion 339

Table 17.2　Condition expression table of skipping promotion 339

Table 17.3　Skipping action table 339

xviii

xvii