Temporal Data: Time and Relational Databases. Bjørn Skjellaug. Research Report 246 ISBN ISSN - PDF

Description
UNIVERSITY OF OSLO Department of Informatics Temporal Data: Time and Relational Databases Bjørn Skjellaug Research Report 246 ISBN ISSN April Temporal Data: Time and Object

Please download to get full document.

View again

of 26
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information
Category:

Leadership & Management

Publish on:

Views: 17 | Pages: 26

Extension: PDF | Download: 0

Share
Transcript
UNIVERSITY OF OSLO Department of Informatics Temporal Data: Time and Relational Databases Bjørn Skjellaug Research Report 246 ISBN ISSN April 1997 Temporal Data: Time and Object Databases Bjørn Skjellaug 1 Institutt for informatikk Universitetet i Oslo P.O.Box 1080 Blindern, 0316 Oslo, Norway Research Report 246 ISBN April The author is also part time at Department of Distributed Information Systems, SINTEF Telecom and Informatics, Oslo. Contents 1 Introduction `What, then, is time?' Time and databases About this Report Report Structure Acknowledgments Temporal Data Basics Perception and Construction of Time Some basic denitions Time Dimensions and Denitions Valid Time Transaction Time Bi- and Multi-Temporal Dimensions NOW and other variables Variables and Semantics Formal Issues on Variables Databases Application of Variables Time and the Relational Model Introduction The Conventional Relational Model Approaches to Support Time Temporal Extensional Support Temporal Intentional Support User dened time Adding Data Types Adding a `Temporal' Layer Use of a Conventional System Tuple timestamping Basic Approaches Event-based models Ariav'smodel i ii CONTENTS Interval-event based models Jensen's Model Interval-based models Snodgrass' model Ben-Zvi's model First Normal Form and Object Identity Attribute timestamping Basic Approaches Transaction-time Indexed Models McKenzie's Model Bi-Temporal Multi-Value Models Gadia and Yeung's Model Valid-Time Multi-Value Models Gadia's Model Tansel's Model Cliord and Croker's Model Non-First Normal Form and Object Identity Query Language Introduction Time Reference in Queries Denitions and other Properties Temporal Algebras - Their Objects and Operators Objects Operators Conventional vs Temporal Queries Optimization and Eciency Uniform Data Access Point- or Interval-based Query Languages Summary 43 Bibliography 45 Chapter 1 Introduction What, then, is time? I know well enough what it is, provided that nobody asks me; but if I am asked what it is and try to explain, I am baed. Saint Augustine in the `Confessions', Book XI, Section 14. [7, page 36]. Most computerized information systems are formed from general purpose components, such as databases, GUIs, etc. Whenever properties of, and operations on, these components are generic they are in principle reusable for dierent purposes and in dierent contexts. Time and time support may also be regarded as a generic information system component. In fact, most applications have requirements that involve dynamics, and a time-varying nature of both data and processes used by these applications. Temporal databases are means to capture some aspects of the required time support, and are mainly used to manage historic data, present data, and predictive data within the same framework and model. To be more specic, in our context time acts as an intrinsic part of objects denoting when these objects are dened related to the built-in time dimension(s) support of the system. A common name of such objects is temporal objects, i.e., objects capturing, besides other properties, time and time dependencies of their values, e.g. an address history of a person. 1.1 `What, then, is time?' Time has been a topic of philosophical and natural scientic study since the ancient Greeks (including Plato, Aristotle, and Diodorus Cronus), through Saint Augustine in the Middle Ages and many later Medieval logicians, to Newtonian physics, Einstein's theory of relativity, and on to present [49]. In the second half of our century logicians, computer scientists, and others have 1 2 CHAPTER 1. INTRODUCTION showed signicant interest in the task of understanding time in both more formalized, linguistic, mathematical, and technical terms. The material presented in this report is founded on the above results, in particular, and not surprisingly, mainly of those results utilized and developed by computer scientists. Time is a human construct. Although it is useful for describing and prescribing changes to the systems and objects under study, aswe will see later on, time is in the day today life most often understood as something which isever increasing, or is continuously moving in one direction into the future. This perception of time is more (or only) reecting human memory. That is, we are able of memorizing the past, e.g. as facts and experiences, but we know nothing about a given time in the future. Still, we mayhave expectations for and predictions about the future. But, it is only when we reach that time in the future, which in the past was a future time, we can say anything, for example, about the validness of our predictions at the time when the predictions were rst stated. Another model presented by Rucker [57] incorporates time and space into a 4-dimensional space where all points are predened. In such a model we are not moving in any specic directions; humans and things are objects dened within the hyperspace. Hence, each 4D object is always showing us when and where we were, are, and (possibly) will be. So, both past, present and future exist simultaneously. Although some points may be regarded as facts and others are predictions, we are within that hyperspace all the time going nowhere because all entities are dened by their extent in this 4D-space. Rucker elaborates on this 4D view most elegantly in his book: Geometry, relativity and the fourth dimension [57]. 1.2 Time and databases In this report we are aiming at an understanding of time as an integral part of properties of data objects. Basically this reduces to understand how properties (or objects) change and behave over time. A common name of such objects is temporal objects, i.e., objects denoting, besides other properties, time and time dependencies. There are dierent times, and dierent notions of time for data managementmay denote whether phenomena in reality are regarded as events, facts, or processes. An intuitive interpretation of time objects in a system would be to let events be represented by time points, facts by time periods (or intervals) and processes with time functions. Why these interpretations? To follow this more or less common sense notion of time a bit further: An event is often taken as happening at a time instant, i.e., a point in time with no duration. A fact is a truth about some static aspects of reality but does not last for ever, i.e. a valid-time period dening when the fact was, is, or is 1.3. ABOUT THIS REPORT 3 believed to be dened (i.e., valid) in reality. A process like anevent denotes or refers to a dynamic aspect of reality, and which, unlike anevent, does have a duration. Thus, a process may be a function describing some cyclic or repeating behavior like a tide or a continuous behavior like an expanding desert or disease. A process and a fact may for example be dened to last forever, or until terminated or changed, respectively. We will primarily treat time related to facts because our concern is temporal data and how such data could be used to integrate facts of dierent kind and/or of dierent databases. We easily see that if an object changes its value(s) this is in the rst place caused by an external/real event triggering some action to do the change (e.g. database update operation). The event itself may have been initiated by a process object. So in a overall setting objects of facts, events and processes are inter-linked. We deal only with the former of these objects, i.e., data management of facts, but will treat the other two whenever they relate to issues discussed. We also present time and temporal data in a broader sense than is usually the case with temporal databases. We dene the notions of schema versioning/evolution, object versioning and conguration managementtobe part of a broad scope of temporal data. Denitions and examples of these notions are given and we show how they are related to times such asvalid times and transaction times, respectively. For denitions of concepts and glossaries related to temporal databases see Jensen et al. [31]. 1.3 About this Report This report is one out of two reports describing the approaches, proposals and other issues within the eld of temporal database research. This report deals with temporal relational databases, and the other deals with temporal object-oriented databases [61]. The reports give a survey of their respective subelds, and they classify the proposed models according to structural characteristics and present representatives of every class in more detail. However, equally important is that the fundamental concepts dened by the eld is presented, therefore, this introduction chapter and the next chapter are included in both reports to give all potential readers an introduction and hopefully a sound understanding of the fundamental temporal concepts as dened and utilized within the temporal database eld. After fteen years of active research in the eld of temporal databases, about 800 papers published, the rst international workshop was held in Arlington, Texas, 1993 [62, 51]. This workshop showed the diversity of issues and topics covered by the eld, and the same tendency is documented by the follow-up workshop held in Zurich, Switzerland, 1995 [16, 60]. We are not aiming at covering all the research related to temporal database, and will, 4 CHAPTER 1. INTRODUCTION of course, only refer to those research publications that are relevant for our purpose. The reader who are interested in temporal database bibliographies is referred to Tsotras and Kumar's bibliography [70], and also the electronic bibliography, authored by Kline, containing nearly 1100 entries as of January 1996 [35] Report Structure In Chapter 2 we presents some basic concepts that are generic to most temporal database models. Chapter 3 presents a survey of temporal relational databases, i.e. models and languages, with a classication of the dierent approaches presented in the literature. We end this report with a short summary in Chapter Acknowledgments I would like to thank Amela Karahasanovic, Ragnar Normann and Dag Sjøberg for comments and suggestions to a previous version of this report. This researchwas supported by the Norwegian Research Council through grant MOI Chapter 2 Temporal Data Basics In this chapter we introduce some generic properties and denitions which are relevant in most settings dealing with temporal data. 2.1 Perception and Construction of Time A philosophical view of time will probably pin point that an event isnot (or necessarily not) an instant oforpoint in time, and could never be an instant of time because an event happens and something that happens has to have some sort of duration. Otherwise, it would not happen. In natural languages the term event is (in an informal sense) a homonym because it may denote the implicit semantics of time dierently: 1) `the concert was quite an event', e.g. meaning an experienced duration of joy and pleasure, and 2) `at the event he sat down he had a stroke', e.g. meaning that something happened at a sudden (or an instant). So, what is an instant oforpoint in time? In life and thought we often regard time as continuous say like a river. Thus, a point in time is nonexisting or is not an appropriate notion if we want to grasp what continuous time is. However, a point in time is a (mathematical) construct and a notion that gives a sucient structure of time when it comes to formal reasoning, data management, etc. With proper models and operations we may suciently approximate or describe phenomena by computer systems by time points or other constructs derived from time points, e.g. intervals and periods. Euclidean geometry does the same with natural spatial primitives like for example an extended body that could be approximated by means of theoretical notions like points and lines. That is, the notion of extended body is described in terms of points and lines. See van Benthem [7, chapter I.1] for a more in depth presentation of the above problems, including a discussion of The Fleeting Now. 5 6 CHAPTER 2. TEMPORAL DATA BASICS 2.2 Some basic denitions Before presenting the dierent subjects and issues raised and discussed we will clarify some concepts which are used throughout the text (and without any further explanations if not the context denes them separately or relates them to more specic structures). The term temporal data means the concept where data or say an object is dened to have some time related information associated with it, e.g. a built-in timestamp 1. For example, in a person object with an property attribute address, and whenever the person changes his/her address the new address value is timestamped. More important, though, is that the previous address values are still accessible, in the sense that an application (or user) may retrieve the whole or a part of the address history of a person. Thus, an address contains both the current and previous addresses (and possibly a future address), as well as the time information associated with each address value. Hence, by means of a temporal data model we may get an integrated knowledge of both where a person lived and when this was. The time (or periods) when a person has addresses is called the lifespan of the address object (see below). The relationship between facts, e.g. a person's addresses, and times is shown in Figure 2.1. current facts historic facts predicted facts time now Person s Addresses Addr. i 1 Addr. i Addr. i+1 Figure 2.1: Facts and Times The time information may be given dierent semantics depending on the time dimensions a particular system supports. For example, temporal database models usually dene one or two of the following time dimensions: the valid-time dimension (see Section 2.3.1) supports information on when a fact was, is, or is believed to be valid (true) in reality, on the other hand the transaction-time dimension (see Section 2.3.2) supports information on when a fact was or is stored/current in the database. The transactiontime dimension has always its upper bound set to the (moving) time now and its lower bound is always set to the time when the system was rst in operation, i.e., the time when the database was created. Whereas the 1 A timestamp is a time value (point in time, time period, or time interval) associated with an object [31]. It is the key time representation in temporal databases. But, qualitatively dierent timestamps represent dierent notions of time. Hence, an object may have several orthogonal timestamps. 2.2. SOME BASIC DEFINITIONS 7 valid-time dimension's upper and lower bounds are set by the application, such bounds for the transaction-time are independent of applications. These two dimensions constitute an object's real world history and registration history respectively. In addition several database systems support primitive data types such asdate, TIME, DATE-TIME, which are used to model what is called user-dened time, and its semantics is dened and only known by the application. For example, an object of type DATE is used to model the property of a person's date of birth, whereas a valid-time timestamp on that persons address property is used to handle the dierent times a person is associated with dierent addresses in the modeled reality. Thus, the built-in semantics of valid-time and transaction-time bound objects to the respective dimensions. That is, a time dimension provides more information of being only a value domain, i.e., a time related order of an objects values is maintained and this ordering is utilized, for example, by query processing. Our concern is valid- and transaction-times and modeling their semantics as part of the database, and not only as structures and semantics of one particular application. Although valid and transaction-times are orthogonal temporal concepts there exist several applications where these two dimensions collapse into one dimension. Many (if not all) real-time database (RTDB) applications have this characteristic. For example, in a cash-line application a bank account is the temporal object of interest. A customer's withdrawal of an amount of money from his/her account means that the registration of this database transactions happens (approximately) at the same (instant of) time as the customers account ischanged in reality, i.e. the time when the real money is withdrawn from the account and the time when this withdrawal is registered coincide, and only one (say valid-transaction-)time dimension may suce for recording both times. Such an database is called degenerated if both valid- and transactions times are captured by one time value [32]. On the other hand when using an ordinary check the times when money is spent and when usage is registered, respectively, could vary form days to weeks, i.e., the valid-time (when spent) and transaction-time (when registered) do not coincide. Further, a temporal data object is said to have a lifespan, and the time periods or intervals constituting the lifespan are not necessary contiguous. In the address example above, there could be a period when a person does not have a known address. Hence, the address object for this person was not dened for this period of time. Thus, the person had no address (or possibly an unknown address) for a period of time, e.g. see the gap between the address values i-1 and i in Figure 2.1. So, the lifespan captures the time when an object is dened. That is, a valid-time lifespan is the time when the object is dened to exist in the modeled reality. On the other hand a transaction-time lifespan is the time when the object is dened to be current and accessible in the database [68, page 625]. We have referred to the concepts point in time and instant as synonyms. 8 CHAPTER 2. TEMPORAL DATA BASICS Another important concept is chronon. A chronon, which is the shortest duration of time supported, for example, by a database is a non-decomposable unit of time or the smallest granule of time. Based on the notion of a chronon a time period is a set of (total) ordered time values, of which each is separated by a chronon. If a time dimension is discrete and linear the concepts of point in time, time period, and time interval are equivalent constructs for representing time [7]. Although this is true for the semantics of time, one construct may be preferred because applications interpret these semantics in context of the modeled reality. We return to this issue in a later chapter. In most temporal models the chosen time dimension is discrete [42, 50], and therefore it is isomorphic to (some subset of) the integers, or isomorphic to (some subset of) the natural numbers when it has an exact lower bound. 2.3 Time Dimensions and Denitions Time dimensions are (usually) classied into valid-time and transaction-time dimensions. Both dimensions can be dened separately, and, hence, they are orthogonal Valid Time The valid-time dimension supports not only management of histories and current data, but also planned or predicted data. Histories are data dened for previous times compared to the time now. Current data are data valid at the time now (i.e., present time), as opposed to predictive data which is data believed to be valid in the future. Figure 2.2 illustrates these properties of valid-time data. Thus, valid-time of some fact is the time when the fact was/is (believed to be) true in reality. Thus, a fact may have several instances, each with an associated timestamp recording changes of that fact [31]. now Object salary: t1 t2 t3 t4 t time t Figure 2.2: Valid-Time Data Figure 2.2 shows an object salary. It could be an object recording the salary evolution of an employee of a company or a general salary object dening the salary of a particular professional category of a company, e.g. an assistant researcher, an engineer. Despite the dierence in possible interpretation of the actual object say by an employee or a professional category application, the temporal semantics of this object remain the sa
Related Search
Similar documents
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks