Search

The analysis of the semantics of temporal data and queries plays a central role in the area of temporal databases. Although many different algebrae and models have been proposed, almost all of them are based on a point-based (snapshot) semantics for data. On the other hand, in the areas of linguistics, philosophy, and, recently, artificial intelligence, an oft-debated issue concerns the use of an interval-based versus a point-based semantics. In this paper, we first show some problems inherent in the adoption of a point-based semantics for data, then argue that these problems arise because there is no distinction drawn in the data between telic and atelic facts. We then introduce a three-sorted temporal model and algebra including coercion functions for transforming relations of one sort into relations of the other at query time which properly copes with these issues. Index Terms--Temporal databases, database semantics, data models.

Calendars and periodicity play a fundamental role in many applications. Recently, some commercial databases started to support user-defined periodicity in the queries in order to provide 'a human-friendly way of handling time' (see, e.g., TimeSeries in Oracle 8). On the other hand, only few relational data models support user-defined periodicity in the data, mostly using 'mathematical' expressions to represent periodicity. In this paper, we propose a high-level 'symbolic' language for representing user-defined periodicity which seems to us more human-oriented than mathematical ones, and we use the domain of Gadia's temporal elements in order to define its properties and its extensional semantics. We then propose a temporal relational model which supports user-defined 'symbolic' periodicity (e.g., to express 'on the second Monday of each month') in the validity time of tuples and also copes with frame times (e.g., 'from 1/1/98 to 28/2/98'). We define the temporal counterpart of the standard operators of the relational algebra, and we introduce new temporal operators and functions. We also prove that our temporal algebra is a consistent extension of the classical (atemporal) one. Moreover, we define both a fully symbolic evaluation method for the operators on the periodicities in the validity times of tuples, which is correct but not complete, and semisymbolic one, which is correct and complete, and study their computational complexity. Index Terms--Temporal relational model and algebra, user-defined symbolic periodicity in the validity time, high-level 'symbolic' language, symbolic (intensional) evaluation method, semisymbolic evaluation method, user-friendly treatment of periodicity, integration and extension of artificial intelligence and temporal databases techniques.

Generating abductive explanations is the basis of several problem solving activities such as diagnosis, planning, and interpretation. Temporal abduction means generating explanations that do not only account for the presence of observations, but also for temporal information on them, based on temporal knowledge in the domain theory. We focus on the case where such a theory contains temporal constraints that are required to be consistent with temporal information on observations. The aim of this paper is to propose efficient algorithms for computing temporal abductive explanations. Temporal constraints in the theory and in the observations can be used actively by an abductive reasoner in order to prune inconsistent candidate explanations at an early stage during their generation. However, checking temporal constraint satisfaction frequently generates some overhead. In the paper, we analyze two incremental ways of making this process efficient. First we show how, using a specific class of temporal constraints (which is expressive enough for many applications), such an overhead can be reduced significantly, yet preserving a full pruning power. In general, the approach does not affect the asymptotic complexity of the problem, but it provides significant advantages in practical cases. We also show that, for some special classes of theories, the asymptotic complexity is also reduced. We then show how, compiled knowledge based on temporal information, can be used to further improve the computation, thus, extending to the temporal framework previous results in the case of atemporal abduction. The paper provides both analytic and experimental evaluations of the computational advantages provided by our approaches. Index Terms--Abductive reasoning, temporal reasoning, computing explanations, efficient algorithms, knowledge-based systems, knowledge compilation.

The paper describes a framework for representing and reasoning with periodic events. In particular, it proposes a temporal formalism which deals with both 1) quantitative information concerning the frame of time (e.g., between 1990 and 1993) and the user-defined calendar-dates (e.g., on the first Mondays of April) in which periodic events are located and 2) the qualitative relations between periodic events (e.g., Sam visits the branch office X01 before going to his office). The meaning of the temporal specifications in our formalism is described in logical terms. The paper defines the basic operations of inversion, intersection and composition of temporal specifications. These operations are correct (with respect to the logical definition of the specifications) and do not lose information. Finally, the paper also describes a correct algorithm which takes advantage of these operations for performing temporal reasoning, and analyses its complexity. An application of the temporal framework to the scheduling in an office is shown in an example. Index Terms - Knowledge representation and reasoning; temporal information about periodic events; representation and treatment of user-defined calendar dates; representation and treatment of qualitative temporal relations between periodic events; integration of user-defined calendar dates and qualitative information; inversion, intersection and composition of temporal specifications about periodic events; temporal reasoning for amalgamating a knowledge base of temporal information about periodic events and checking its consistency.