Base De Datos

Universal Temporal Extensions for Database Languages
Cindy Xinmin Chen and Carlo Zaniolo Computer Science Department University of California at Los Angeles Los Angeles, CA 90095 E-mail: fcchen, zaniolog@cs.ucla.edu

Abstract
Temporal reasoning and temporal query languages present di cult research problems of theoretical interest and practical importance. One problem is the chasm betweenpoint-based temporal reasoning and intervalbased reasoning. Another problem is the lack of robustness and universality in many proposed solutions, whereby temporal extensions designed for one language cannot be easily applied to other query languages| e.g., extensions proposed for SQL cannot be applied to QBE or Datalog. In this paper, we provide a simple solution to both problems by observing thatall query languages support (i) single-value based reasoning and (ii) aggregate-based reasoning, and then showing that these two modalities can be naturally extended to support, respectively, point-based and interval-based temporal queries. We follow TSQL2 insofar as practical requirements are concerned, and show that its functionality can be captured by simpler constructs which can be applieduniformly to Datalog, QBE and SQL. Then, we show that an e cient implementation can be achieved by mapping into a di erent storage representation, and discuss a prototype built along these lines using the LDL++ system with extended aggregates.

1. Introduction
With many applications requiring support for temporal databases, extensive research has focused on temporal queries and reasoning 12]. Acritical issue in all these approaches is the choice of model used to represent valid time: for instance, many approaches represent valid time states by temporal intervals, while point-based models view the database as a sequence of snapshots 3, 13]. The major drawback of the intervalbased data model is the need for coalescing time intervals when a projection is taken, whereas point-based

datamodels are free from this problem. On the other hand, many temporal queries can be expressed naturally using intervals, e.g., using Allen's interval operators. Furthermore, intervals provide an e cient representation for the physical storage of the data, while point-based conceptual models must be mapped into di erent representations for storage e ciency. The language TSQL2 11] introduced a consensusextension to SQL-92 that supports a Bi-temporal Conceptual Data Model 6], which handles both valid time and transaction time. In TSQL2, there is no explicit time column in the relations, and valid time cannot be referred in the query as a tuple attribute; therefore, we say that TSQL2 has an implicit-time data model. By keeping time implicit, TSQL2 eliminates the need for a user to specify thecoalescing of time periods 2]. However, implicit time makes the semantics of TSQL2 more obscure and di cult to formalize. Furthermore, the fact that one cannot work directly with time makes certain queries hard to express and requires the introduction of special temporal constructs to achieve the same goal indirectly. This bring us to the second problem, i.e., said special TSQL2 constructs aredesigned for SQL only, and do not generalize into a universal temporal data model and query language that can be used for, say, QBE and Datalog. We refer to this problem as the lack of universality of TSQL2. In this paper, we rst propose an approach based on a point-based explicit-time model and on temporal aggregates to support interval-based reasoning. We demonstrate the universality of this approach,by proposing parallel designs for SQL, QBE, and Datalog. Then, we tackle the problem of e cient implementation for these languages, by proposing two storage representations, one based on intervals, and the other on events, which avoid the space ine ciency problem of point-based representations. Queries on point-based representations at the conceptual level can be easily mapped into equivalent...