The issue of periodicity is generally understood to be a desirable property of temporal data that should be supported by temporal database models and their query languages. Nevertheless, there has so far not been any systematic examination of how to incorporate this concept into a temporal DBMS. In this paper we describe two concepts of periodicity, which we call strong periodicity and near periodicity, and discuss how they capture formally two of the intuitive meanings of this term. We formally compare the expressive power of these two concepts, relate them t o existing temporal query languages, and show how they can be incorporated into temporal relational database query languages, such as the proposed temporal extension t o SQL, in a clean and straightforward manner. i Introduction Periodicity is a feature of temporal phenomena t h a t has received relatively little attention in the literature of temporal databases. T h e work t h a t has been done related t o periodicity, which we survey in Section 1.1, has been either mostly of a theoretical nature or is related t o t h e notion of a calendar [26, 23, 61. However, there has been no comprehensive treatment of the subject of periodicity in the temporal database literature t h a t thoroughly addresses both the meaning of periodicity in t h e database context as well as how this aspect of time can be supported in commercial temporal database systems. As a result of t h e limited attention t o this concept, periodicity is not supported in t h e TSQL2 standard [25] and no periodic queries were included in t h e test suite of temporal queries [15]. This situation is unfortunate since many of the existing temporal query language proposals cannot express periodic queries, as we shall discuss in Section 3. For example, they cannot express even such a simple periodic query as "Find the names and attendance times of people who attended any of the Tuesday meetings." The goal of this paper is twofold: we explore the meaning of the concept of periodicity in the context of temporal databases, and we show how it can be supported in commercial temporal query languages and in the TSQL2 standard in particular. Our objective is mainly pragmatic: we want to add periodicity in a practical way to temporal query languages, including TSQL2. However, it is impossible to do this in a comprehensive and theoretically sound way without a proper understanding on the conceptual level of what periodicity means and how it can be formally represented. Therefore, we study periodicity both on the theoretical and the pragmatic levels. To understand what periodicity means intuitively, a good place to start is in the dictionary. The entry in the American Heritage Dictionary [I] gives the following three meanings for the term periodic: 1. having periods or repeated cycles 2. happening or appearing at regular intervals 3. taking place now and then; intermittent. The first of these meanings for the term periodic says that the events occur at such moments of time that the distance between these moments is the same. For example, a class might be scheduled to meet periodically, say, once a week on Wednesdays at 11 am. Note that the time between two successive occurrences in this case is always exactly seven days. The second meaning says that the events occur at regular intervals, meaning that the events do not necessarily occur at equally distant moments of time. However, there is a certain degree of "regularity" in their occurrence: they are "regularly" distanced and thus occur within a certain limit from each other. For example, assume that the head of a state of some country has t o travel once every week on some business but at the same time is concerned about security because of the recent increase in the terrorist activities in that country. To make the trips safer, the schedule of trips is kept secret and is organized so Center for Digital Economy Research Stern School of Business Working Paper IS-95-06 that the day of the week when the politician travels appears to be totally random. In this example, the set of trips is "regular" in the sense that they occur once a week. On the other hand, they are not "regular" in the first sense of the word: they are not equally distanced from each other, nor can this set of trips be obtained as a union of equal-distance sequences (as will be shown later in the paper). This concept of periodicity is clearly a weaker concept than the first one. The third meaning for the term periodic says that the events occur "intermittently," meaning that if one event occurred then the next will follow some time in the future, but it is not clear when. For example, a person may visit a pub "periodically," meaning that the visits can be quite irregular but the person will keep going to the pub. Clearly, this is the weakest concept of periodicity among the three. In this paper, we provide formalizations for the first two concepts of periodicity in the context of querying a database along the valid time or transaction time dimensions of its data. We do not study the third notion of periodicity because we feel that it is "too weak" to be formally supported by temporal query languages: technically, all that it says is that periodic sets are unbounded in the future. After we formalize the two notions of periodicity described above and study their properties and the relationship between them, we address the pragmatic question of how to add periodicity in a practical way to commercially oriented temporal query languages. In this paper, we concentrate on the ungrouped temporal data models (81 and, therefore, consider ungrouped temporal query languages, and in particular the TSQL2 standard. However, we believe that the ideas presented in the paper can be extended to the grouped temporal data models (81 as well. In the process of studying of how periodicity can be added to commercially oriented temporal query languages, we rely on the theoretical results about periodicity described earlier in the paper. When studying periodicity, one has to address two questions. The first question is how to define periodic sets of times. For example, one might want to define the set consisting of "every Wednesday," or "the first day of each month," or a "set of visits of the head of a state.'' The second question is how to define periodic queries, such as a query to find people who attended every meeting held on Wednesdays, or people that came to the meetings once a week. This distinction between periodic sets of time and periodic queries corresponds to the distinction between data expressiveness and query expressiveness discussed in [5]. The data expressiveness of a formalism specifies what types of infinite temporal databases can be defined with the formalism. It arises only in the context of infinite temporal databases because in the finite case all the finite databases can be represented explicitly. The query expressiveness of a formalism specifies what types of queries can be expressed in the formalism and is more akin to the standard notion of expressiveness of query languages. Therefore, in order to understand how periodicity can be added to TSQL2 in the best possible way, we will study the data and query expressiveness of different periodic extensions studied in this paper. Perhaps the first approach to analyzing the notion of "time" and its relationship to conceptual modeling of data was proposed in [4] . Among the many aspects of time that are discussed here is the notion of periodicity. A periodic set is defined here in a set-theoretic framework in terms of its "period, duration, and cover interval." Periodic sets, along with all of the time aspects discussed in the paper, are all interrelated via a concept network similar to a semantic net. While this work is of pioneering importance in the temporal database literature by having explored so many aspects of the temporal dimension of data, it did not study the properties of periodic sets of times, nor did it address the issue of a language for expressing queries about the periodic nature of data. It does so by allowing the user to associate multiple valid-time time stamps with a given fact. For example, a tuple such as < john, d5, d9, h8, h12 > on relation scheme GUARDS(NAME, Fdate, TDate, Fhour, Thour) is said to represent that "John works as a guard during the hours h8-h12 (h12 excluded), for every day in the interval [d5, d9)." However, the semantics of such relations with multiple valid-time timestamps is not fully explored. Moreover, the query language does not support queries about periodic events. is called "regularity." For example, a temporal relation is said to be "transaction time event regular with time unit A t > 0" if the transaction times of any two items stored in the database is always an integral multiple of some specified duration A t . Variations of this type of consideration lead to some additional characterizations of relations related to temporal regularity. As the authors point out, regularity is related to, but is different from, periodicity. In fact, as we shall see, regularity can be defined in terms of our notion of periodicity by starting with a periodic set of times and subtracting any arbitrary, but recursively defined, set of times from it. Finally, the issues of a language for querying such databases with properties of regularity, or for expressing these regularity constraints on the temporal dimensions, are not considered. Classical work in temporal logic (18, 201 is concerned with truth and validity of temporal logic formulae, which are defined in terms of temporal structures [18] The language pTL, as defined in 1331, is a propositional temporal calculus, although Vardi points out that it can be easily extended to the predicate case [33] . Calculus pTL is obtained from the propositional temporal logic with operators n e x t , and two types of "previous" operators, previousl and previousz' by the addition of the operators least and greatest fixpoint. The formula pX.$(X) (respectively vX.$(X)) denotes the least (respectively greatest) fixpoint solution to the equation X = $(X), where X is a temporal proposition. Calculus pTL can express temporal operators until and since and can also define periodic sets. For example, it can define the set of even numbers as h he difference between them is that p r e v i o u s 1 is always true and p r e v i o u s z is always false when applied to an arbitrary formula a t time t = 0. where init is defined as previousl false and is equal t o true at time t = 0 and false elsewhere. Vardi [33] studies the expressive power of pTL and shows that it a quite expressive language: it has the expressive power of w-regular languages [29] . This means that p T L is "too powerful" to express periodicity alone: intuitively, pTL does not capture the "essence" of periodicity, but supports other concepts in addition to periodicity. Since in this paper we are interested in the question of what mechanism is needed t o add periodicity, and only periodicity, t o existing temporal query languages and calculi, we want to study languages that are less powerful than pTL. Periodicity has also been studied in the context of infinite temporal databases in [16, 71 and surveyed in [5]. In [16, 51 a generalized relation is defined as a set of generalized tuples of the form {tl, . . . , tm, dl,. . . ,dl I ti 6 (alnl + bl), . . . , t , E (a,n, + b, ) and constraints on ( t l , . . . , t,) are satisfied) where tl, . . . , t, are temporal variables, d l , . . . , dl are non-temporal constants, and the constraints imposed on tl, . . . , t, are linear. The expressions a;n; + b; are called linear repeating points (LRPs), and they form periodic sets. If we restrict the notion of a generalized tuple t o only one attribute and make it temporal, then a generalized relation would consist of a set of LRP's with some linear constraints imposed on them. This representation would correspond to the first notion of periodicity above, i.e., "having periods or repeated cycles." The union of LRP's would also capture the second notion of periodicity, i.e., "happening or appearing at regular intervals," but only to some extent. For example, as will be shown later in the paper, a finite union of LRP's cannot represent the set of "visits of the head of a state" described in the introduction. We will call the sets defined by unions of LRP's strongly periodic sets to distinguish them from the more general notion of nearly periodic. We will show in the paper that the concept of near periodicity subsumes strong periodicity and captures the second meaning of periodicity, i.e. "happening or appearing at regular intervals.)' Also, certain aspects of periodicity are studied,in [7]
Many approaches only focused on the treatment of periodicity in the query (see, e.g., REF and Oracle8; see www.oracle.com\databases\ timeseries.html).
On Periodicity in Temporal Databases
Information Systems
Computer Science