TIME'99 Accepted Papers

Full Papers

Title: A System for Reasoning with Nonconvex Intervals

Author(s): M. Almeida

Title: Symbolic representation of user-defined time granularities

Author(s): Claudio Bettini, Roberto De Sibi

E-mail(s): bettini@dsi.unimi.it, rdesibi@it.oracle.com

Abstract: A recent effort has been done in the literature to formally characterize the notion of time granularity and the relationships between granularities, in order to have a common framework for their specification and to allow the interoperability of systems adopting different time granularities. This paper considers the mathematical characterization of finite and periodical time granularities, and it identifies a user-friendly symbolic formalism which captures exactly that class of granularities. This is achieved by a formal analysis of the expressiveness of well-known symbolic representation formalisms.

Title: A Constraint-Based Specification of Periodic Patterns in Time-Oriented Data

Author(s): Shubha Chakravarty and Yuval Shahar

E-mail(s): {schakrav, shahar}@smi.stanford.edu

Abstract: We use a constraint-based language to specify periodic temporal patterns. The Constraint-based Pattern Specification Language (CAPSUL) is simple to use, but allows a wide variety of patterns to be expressed. CAPSUL solves problems such as (1) how to use calendar-based constraints to define repetition of a periodic event, (2) what temporal relations must exist between consecutive repeats of a pattern, and (3) how expressivity is limited if the same temporal relations must hold between each pair of intervals in the pattern. We implemented CAPSUL in a temporal-abstraction system called Résumé, and used it in a graphical knowledge-acquisition tool to acquire domain-specific knowledge from experts about patterns to be found in large databases. We summarize the results of preliminary experiments using the pattern-specification and pattern-detection tools on data about patients who have cancer and have been seen at the University of Chicago bone-marrow-transplantation center.

Title: A Geometric Framework for Specifying Spatiotemporal Objects

Author(s): Jan Chomicki, Peter Z. Revesz

E-mail(s): chomicki@monmouth.edu, revesz@cse.unl.edu

Abstract: We present a framework for specifying spatiotemporal objects using spatial and temporal objects, and geometric transformations. We define a number of classes of spatiotemporal objects and study their closure properties.

Title: TALplanner: An Empirical Investigation of a Temporal Logic-based Forward Chaining Planner

Author(s): P. Doherty, J.Kvarnström

Title: A Graph-Theoretic Approach to Efficiently Reason about Partially Ordered Events in the Event Calculus

Author(s): M. Franceschet, A. Montanari

Title: Generating Scenarios for Periodic Events with Binary Constraints

Authors: Lina Khatib and Robert A. Morris

E-mail(s): {lina,morris}@cs.fit.edu

Abstract: Reasoning with repeating events differs from reasoning about single events primarily in the fact that with the former the available information about aspects such as the number and period of the events may be indefinite. Much useful knowledge about repeating events takes the form of relationships between "successive" occurrences of the same event, or "proximate" occurrences of pairs of repeating events. The formulation presented here focuses on such knowledge. A backtracking algorithm for solving reasoning problems involving repeating events is presented and its complexity evaluated.

Title: A Temporal Object-Oriented Data Model with Multiple Granularities

Author(s): Isabella Merlo, Elisa Bertino, Elena Ferrari, Giovanna Guerrini,

E-mail(s): merloisa@disi.unige.it, guerrini@disi.unige.it, bertino@dsi.unimi.it, ferrarie@dsi.unimi.it

Abstract: In this paper we investigate some issues arising from the introduction of multiple temporal granularities in an object-oriented data model. Although issues concerning temporal granularities have been investigated in the context of temporal relational database systems, no comparable amount of work has been done in the context of the object-oriented model. Moreover, the main drawback of the existing proposals is the lack of a formal basis -- which we believe is essential to manage the inherent complexity of the object-oriented data model. In this paper, we provide a complete temporal object-oriented type system supporting multiple temporal granularities and we formally define the set of legal values for our type system. We then address issues related to inheritance, type refinement and substitutability.

Title: Optimization in Constraint Reasoning about Repeating Events

Author(s): Robert A. Morris and Lina Khatib

E-mail(s): {morris,lina}@cs.fit.edu

Abstract: The effective manipulation of temporal information about periodic events is required for solving complex problems such as long range scheduling or querying temporal information. Further more, many problems involving repeating events require the optimization of temporal aspects of these events, e.g., minimizing makespan in job-shop scheduling. This paper contains a framework for representing and solving reasoning problems in which temporal aspects of repeating events are to be optimized. This framework rests upon three foundations: recent work on the characterization of repeating events, the temporal CSP framework for processing constraints, and the semiring generalization of CSPs. The semiring allows values to be associated with consistent solutions generated from the specification; the values are computed from functions that provide interpretations of the optimizing constraints.

Title: Study and Comparison of Schema Versioning and Database Conversion Techniques for Bi-temporal Databases

Author(s): Han-Chieh Wei, Ramez Elmasri

E-mail(s): wei@cse.uta.edu, elmasri@cse.uta.edu

Abstract: Schema evolution and schema versioning are two techniques used for managing database evolution. Schema evolution keeps only the current version of a schema and database after applying schema changes. Schema versioning creates new schema versions and converts the corresponding data while preserving the old schema versions and data. To provide the most generality, bi-temporal databases can be used to realized schema versioning, since they allow both retroactive and proactive updates to the schema and database. In this paper we first study two proposed database conversion approaches for supporting schema evolution and schema versioning: single table version approach and multiple table version approach. We then propose the partial table version approach to solve the problems encountered in these approaches when applied to bi-temporal databases.

Short Papers

Title: Using Interval Temporal Logic to Model Cognitive Behaviour

Author(s): H.Bowman, G.Faconti

Title: A Temporal Relational Algebra Based on Multiple Time-Lines

Author(s): Mehmet A. Orgun

E-mail(s): mehmet.orgun@mq.edu.au

Abstract: A clocked temporal relational algebra, called R, which supports temporal relations based on multiple time-lines is proposed. Temporal relations are defined over clocks which are subsequences of an assumed global time-line. The algebra is uniform, it is a consistent extension of the relational algebra, and it includes a number of temporal operators to combine data based on different time-lines. The meaning of an operation of R depends on the clocks of the relations involved in the operation as well as the relations. We outline a formal interpretation of expressions of R, and sketch a naive expression evaluation method.