Navigational Accesses in a Temporal Object Model.
AbstractA considerable research effort has been devoted in past years to query languages for temporal data in the context of both the relational and the object-oriented model. Object-oriented databases provide a navigational approach for data access based on object references. In this paper, we investigate the navigational approach to querying object-oriented databases. We formally define the notion of temporal path expression, and we address on a formal basis issues related to the correctness of such expressions. In particular, we focus on static analysis and give a set of conditions ensuring that an expression always results in a correct access at runtime.
Introduction
temporal join
-join time-
join
navigational
Path expressions
implicit joins explicit
joins
dangling
The importance of temporal data management has long been recognized by the database community
and many techniques for modeling and managing temporal data have been introduced [19, 21]. Most
research in temporal databases has been developed in the framework of the relational data model
[8, 10, 17, 20]. However, also temporal object-oriented databases have recently received increasing
attention, and several object-oriented data models have been proposed [16]. The reason for this
interest is that most applications for which object-oriented database management systems are
expected to provide support, exhibit some form of temporality. Examples are engineering databases,
multimedia systems, and office information systems. However, as pointed out also by Snodgrass in
[16], in contrast to temporal relational data models, the specification of temporal object-oriented
data models is in most cases informal. To overcome this drawback, we have proposed in [1] a
formal temporal object-oriented data model, and we have addressed on this formal basis several
issues deriving from the introduction of time in an object-oriented context.
A considerable research effort on temporal databases has been devoted to the design of temporal
query languages, for both the relational and the object-oriented data model. In particular, temporal
extensions of relational algebra [8, 18], relational calculus [18], and relational commercial query
languages such as QUEL [15] and SQL [13, 17] have been proposed. In those temporal query
languages, a relevant operation is represented by the . Indeed, in temporal relational
query languages the join relational operator has two different flavors, referred to as 2 and
in [8]. Two different join operators are required because in temporal data models two kinds
of values (ordinary and temporal) are represented. 2-join plays the same role as in nontemporal
relational data models, and allows to compare only attribute values that occur at the same point
in time, whereas temporal join allows to impose conditions on times associated to tuples.
Several temporal object-oriented query languages have also been proposed [16]. Many of these
query languages are extensions of relational query languages, like DAPLEX [14], QUEL [12] and
SQL [9], rather than of existing nontemporal object-oriented query languages. It is however important
to note that object-oriented database systems [3] support a approach for data
access, in addition to traditional query language constructs available in relational database systems.
This modality must be taken into account in designing temporal object-oriented query languages.
The navigational approach is based on object identifiers and aggregation relationships: given an
OID, the system directly accesses the corresponding object and navigates through objects referred
to by its components. This access modality can be combined with a classical (e.g. SQL-like) ac-
cess. Thus, the conditions in a query are imposed on nested attributes of the hierarchy rooted
at the object under examination. allow to conveniently describe joins, aiming at
getting a component from an object. In an object-oriented query language a distinction can be
made between , corresponding to the hierarchical structure of objects, and
, analogous to the relational ones, explicitly comparing two objects. While issues related to
explicit joins are quite similar to those arising in the relational context, implicit joins poses some
new problems. Indeed, when the value of an object attribute is the identifier of another object, the
identifier can be seen as a pointer to the referred object. Obviously, for the access to be correct,
that pointer must not be .
In this paper, we investigate issues related to implicit joins and navigational accesses in a
temporal context. Therefore, the goal of this paper is not to propose a new temporal object-oriented
query language, rather is to investigate the impact of time on the peculiar features of object-oriented
query languages. To this purpose, we first introduce a formal notion of temporal path expression.
Temporal path expressions are obtained as an extension of classical path expressions of object-oriented
languages, in that for each attribute access a time can be specified, in addition to the
Ttype
OI CI AN
temporal T
temporal T
2 The Reference Temporal Object-Oriented Model
integer real bool character string
time
time
time
Function is the identity function on nontemporal types.
referential integrity constraint
structured types
temporal types
now
now
attribute name. The time can be expressed either explicitly, by specifying a time instant or a set of
time instants, or implicitly, by means of a formalism to symbolically denote sets of time instants.
Then, we investigate the notion of path expression correctness. As remarked by Clifford and Croker
in [8], a temporal model must enforce with respect to the temporal
dimension. For example, the information that an employee worked in a division at time , is correct
if both the employee and the division existed in the database at time . This means that some
correctness conditions should be imposed on a database to ensure it satisfies temporal constraints.
We have proposed a notion of consistency for a temporal object-oriented database [1]. However, the
consistency of the database alone is not enough to ensure that all the navigations through objects
are correct. Thus, in this paper we investigate the issue of correctness of navigational accesses, and
whether and how correctness can be statically verified.
To best of our knowledge, this is the first extensive investigation concerning navigational accesses
in a temporal context and addressing the problem of a static analysis of path expressions. One of
the few papers considering navigational access is the one by Cheng and Gadia [7]. Their language
OOTempSQL provides a sublanguage for associative navigation relying on notions very similar to
our concept of temporal expression. However, neither a formal semantics is given for the language
nor correctness conditions have been stated.
The remainder of the paper is organized as follows. Section 2 presents a brief overview of
the Chimera data model. Section 3 describes the formalism we use to symbolically denote a
set of time instants in a temporal path expression. Section 4 formally introduces temporal path
expressions and addresses the problem of path expression correctness. Section 5 deals with the
static analysis of path expressions, whereas path expression equality is considered in Section 6.
Finally, Section 7 concludes the paper. The paper includes two appendixes reporting the syntax
of the language we use to specify boolean expressions and a sketch of the proofs of main results,
respectively.
Chimera is the temporal extension of the Chimera object-oriented data model [11]. Chimera
provides all concepts commonly ascribed to object-oriented data models, such as: object identity,
complex objects, user-defined operations, classes and inheritance. In the following, we denote with
a set of object identifiers, with a set of class identifiers, that is, class names and with
a set of attribute names. Moreover, denotes the set of Chimera legal values.
In Chimera the notion of is supported. The existence of a finite set of basic predefined
value types is postulated, containing the types , , , and . The
type is also a predefined value type, used in the definition of temporal types. Chimera
supports such as sets, lists and records, and allows the use of class names in the
definition of structured types. In addition to the above-mentioned nontemporal types, Chimera
supports a collection of , to handle in a uniform way temporal and nontemporal
domains. For each type , a corresponding temporal type, ( ), is defined. Intuitively,
instances of type ( ) are partial functions from instances of type to instances of type
. In Chimera, temporal types can be used in the definition of structured types. A function
is defined, which takes as argument a temporal type ( ), and returns the corresponding
static type .
We assume as the domain of the type the domain = 0,1,. , isomorphic
to the set of natural numbers IN. Symbol '0' denotes the relative beginning, while denotes the
c c
OI
instance
member
class
Example 1
I
temporal
dom a; c a
c
lifespan
A
dom
dom
dom
dom
dom
lifespan
valid
signature
implementation
lifespan
temporal
immutable
nontemporal
Suppose that . The following are examples of Chimera classes:
class ,
class , with = , subclass of , such that:
According to the usual terminology, an object is an of a class , if is the most specific class, in the
inheritance hierarchy, to which the object belongs. If an object is an instance of a class it is also a of all the
superclasses of this class.
time
employee [10,now]
employee name salary status division manager
name employee temporal(string)
salary employee temporal(integer)
status employee string
division employee temporal(string)
manager employee temporal manager
manager [10,now] employee
manager employee dependents official car
current time. An interval, denoted is a set of consecutive time instants, including
all time instants between and , and included. A single time instant can be represented
as the time interval [ denotes the null interval. The time dimension considered by our
model is time.
A in Chimera consists of two components: the , containing all the information
for the use of the class and its instances, and the , providing an implementation
for the signature. A is associated with each class, representing the time interval during
which the class has existed. We assume the lifespan of a class to be contiguous. The class signature
contains information about the attributes (name and domain) and the methods (name and type of
input and output parameters) of its instances. Attributes in Chimera can be either temporal,
immutable or nontemporal. A (or historical) attribute is an attribute whose value may
change over time, and whose values at different times are recorded in the database. An
attribute is an attribute whose value cannot be modified during the object lifetime, whereas a
(or static) attribute is an attribute whose value can change over time, but whose
past values are not meaningful for the application at hand, and are thus not recorded in the
database. Immutable attributes can be regarded as a particular case of temporal ones, since their
value is a constant function from a temporal domain. Temporal attributes have temporal types as
domains and their values are functions from the temporal domain to the set of legal values
for the attribute. Throughout the paper we represent the value of a temporal attribute of type
as a set of pair . , where . are legal values for type
, and . are time intervals such that the attribute assumes the value
for each time instant in Given a class , ( ) denotes the set of
attributes of instances of that class, whereas ( ) denotes the domain of attribute in class
Finally, since the objects belonging to a class vary over time, each class maintains the history
of the objects instances or members of the class over time. The set of objects members of a
class changes dynamically over time. Thus, to represent the extension of Chimera classes, we
introduce a function : 2 , assigning an extent to each class, for each instant .
For each , ( ) is the set of the identifiers of objects that, at time , belongs to either as
instances or as members.
object
Example 2
fh ig
f fh ig fh ig
fh ig
fh ig
dom
class history
lifespan
class history
lifespan
class history
lifespan
class history
Instances of class contain an immutable attribute , whose value never changes during
the instance lifespans, a static attribute , for which we do not keep track of the history of
changes, and three temporal attributes , and , for which we record the
whole history of changes. Class is a subclass of with the additional attributes
and .
Consider the classes of Example 1, and suppose that . The following
are examples of Chimera objects:
dependents manager temporal(set-of(employee))
official car manager string
manager
employee name
status
salary division manager
manager employee
dependents official car
now
name [20,now] Alan Smith salary [20,60],15k [61,now],30k
status full-time division [20,100],'Disks' [101,now],`Printers'
manager [20,49],i [50,now],i
[20,now],employee
name [50,now] Mary Dole salary [50,now],50k
status full-time division [50,now],'Printers'
manager [50,now],i dependents [50,100]
[50,now],manager
The notion of Chimera is formalized by the following definition.
An object is a 4-tuple ( - ), where
is the oid of ;
( ) is the lifespan of ;
is a record value are the names of the attributes
of , and . are their corresponding values;
is a set . , where . are time inter-
vals, . are class identifiers, such that is the class identifier of the most specific
class to which belongs in , 1 .
Given an oid , we make use of function : to refer the class the object
denoted by belongs at time , that is, ( . Note that
( ) is defined for any .
c
3 Temporal Expressions
first last slice first instant last instant inst slice
th
select the employees that earned more than their managers in
the time interval [10,100]
select the employees
that work in the Printers department when it was headed by Mary Dole
The query:
, is an example of query in which the set of time instants in which the
query condition must be verified is given explicitly. By contrast, the query:
, is an example
of query in which the set of time instants is implicitly specified.
temporal
expression
The consistency of an object is checked only with respect to its most specific class. If an object is consistent with
respect to its most specific class, it is consistent with respect to all its superclasses.
Two intervals are considered disjoint if they cannot be collapsed into a single one (note that [1,2] and [3,4] are
not disjoint).
We require that each object is a consistent instance of all the classes it belongs to. Our notion
of consistency keeps into account that, in a temporal context, both the object state and the class
an object belongs to change over time. Therefore, verifying the consistency of an object requires
two steps. First the set of attributes characterizing the object for each instant of its lifespan must
be determined. Then, the correctness of their values, with respect to the most specific class the
object belongs at time , must be verified. Note that, if we consider an instant lesser than the
current time, we are able to identify only the temporal attributes characterizing the object at time
, since for static attributes we record only their current values. Thus, for instants lesser than the
current time, it only makes sense to check the correctness of the values of the temporal attributes of
the objects. Moreover, at the current time also the correctness of the values of the static attributes,
with respect to the most specific class the object currently belongs, must be checked. We refer the
interested reader to [1] for further details.
Generally, in a nontemporal object-oriented database a query selects objects based on the evaluation
of boolean expressions, involving attribute values, method invocation results, and so on. In a
temporal context, queries must allow the retrieval of objects satisfying a given boolean expression
(or a set of boolean expressions) for a specific set of time instants, that can be defined either
explicitly or implicitly.
To implicitly represent the time with respect to which a boolean expression must be evaluated,
we need a formalism to symbolically denote a set of time instants. The symbolic formalism we
use is similar to the one proposed by Gadia and Nair in [10], based on the notion of
. A temporal expression is a symbolic representation of a set of time instants. The main
difference between our notion of temporal expression and the one in [10] is that we allow the use of
the selection operators: (), (), (), (), (), () in the
definition of temporal expressions (see Defintion 3 introduced later on).
In the following, we use a set of disjoint intervals . as a compact
notation for the set of natural numbers included in these intervals. The operations of union
have the usual
semantics of set operations. Moreover, 7 is true if is one of the natural numbers represented
by 7. Finally, we define a projection operation 5(7 ), that takes as input a set of
disjoint time intervals 7 and a natural number . Function 5() orders the elements in 7 in
increasing order, with respect to their upper bound, and returns the - interval in the or-
dering, if the cardinality of 7 is lesser than or equal to ; it returns otherwise. For ex-
2and
and
Example 4
Example 5
be
be be be
be ; be
te te te te te te te te te
te first te last te slice te; n first instant te last instant te
inst slice te; n
first ?
te
te / te
/ be be be
now
salary 20k division
salary 40k salary
salary 40k
status 'full-time'
now
30k salary 40k manager.name = 'Mary Dole'
The temporal interpretation of the boolean expression
, when the above expression is evaluated on object of Example 2, is ,
whereas the temporal interpretation of is the empty set, as attribute has
never reached this value during lifespan. Note that the temporal interpretation of ,
when it is evaluated on object , is . Finally note that the interpretation of
is the set , on both and , as attribute is static. This does
not imply that attribute has assumed a value different from for the instants
lesser then the current time. However, since we record the value of the attribute only at the current
time, we are able to check the truth of the condition only at .
, are examples of temporal expressions

ample,
In the following denotes the set of boolean expressions. Boolean expressions are specified
using the language described in Appendix A.
Before formally defining the notion of temporal expression, we need to introduce the following
definition.
Let be a boolean expression. The temporal interpretation
of (written is the set of instants in which is true.
The set of Chimera temporal expressions is recursively
defined as follows:
the temporal interpretation of a boolean expression is a temporal expression:
if and are temporal expressions, then , , , are temporal
if is a temporal expression, then (
are temporal expressions.
Each temporal expression uniquely denotes a set of time intervals. The semantics of a temporal
expression, that is, the set of intervals it denotes, is formalized by means of function :
defined as follows.
Let be a temporal expression. The semantics
of , denoted as ( ), is defined as follows:
c
and
or
Example 6
4 Temporal Path Expressions
The usefulness of instant-valued temporal expressions will be made clear in the following section.
Consider objects and of Example 2:
when the expression is
evaluated on . Similarly,
.
instant-valued
manager.salary 40k [101,now] [50,now] [50,now]
manager.salary 40k [50,50] division
now
first te / te ; te
last te /
first instant te ; min / te ; te
last instant te
inst slice te;
first instant ? / last
te
is the n-th instant in . are time
intervals such that (
In the following we refer to temporal expressions denoting a single time instant as
temporal expressions. Formally, a temporal expression is an instant-valued temporal expression
if and only if (
Temporal path expressions are obtained as an extension of classical path expressions of object-oriented
languages [4], in that for each attribute access a time can be specified, in addition to the
attribute name. In such a way, the value of the attribute at a specified time is denoted. The
time can be expressed either explicitly, by specifying a time instant or a set of time instants, or
implicitly, by means of a temporal expression. The language to express path expressions allows
the nesting of attribute accesses expressed by means of postfix dot notation, but the restriction is
imposed that all attribute accesses in the path expression, but the last one, are qualified with a time
instant, and not with a set of time intervals, thus denoting a nontemporal value, on which a further
attribute access can be specified. Alternatively, if a set of time intervals were specified to qualify
an intermediate attribute access in the path expression, that set would be seen as the set of time
instants belonging to the intervals, so that the access would denote a set of nontemporal values,
on which further accesses can be evaluated. The following subsections give a formal treatment of
path expressions in a temporal context, and address the problem of path expression semantics and
correctness.
4.2 Semantics
Example 7
employee
division
salary 'Mary Dole'
manager
ar
e a te
e:a te
e a t
e a e:a
e a te
e:a te
e a
e:a
e a e:a all
X:
last interval
first instant
Consider the classes of Example 1, and let be a variable of type . The
following are examples of path expressions:
In this section we formally define the set of Chimera path expressions. In the following we denote
with a set of object-denoting variables.
The set of Chimera path expressions is recursively defined
as follows:
a simple path expression is defined as follows:
if is an object-denoting variable, then is a simple path expression;
if is a simple path expression, is an attribute name and is an
instant-valued temporal expression, then is a simple path expression;
if is a simple path expression, is an attribute name and is a time
instant, then is a simple path expression;
if is a simple path expression and is an attribute name, then is a simple
path expression;
a terminal path expression is defined as follows:
if is a simple path expression, is an attribute name and is a temporal
expression, then is a terminal path expression;
if is a simple path expression, is an attribute name and 7 2 is
a set of time intervals, then 7 is a terminal path expression;
if is a simple path expression, is an attribute name, then is a terminal
path expression;
simple path expressions and terminal path expressions are path expressions.
The semantics of a path expression (i.e., the value denoted by it) can only be specified starting
from an oid-assignment, that is, a function assigning oids to object-denoting variables. However,
the value denoted by a path expression depends on the temporal specifications it contains.
Consider first the case of a path expression for which a time instant is specified (either implicitly
or explicitly). If the path expression is of the form , that is, a temporal specification occurs
in the terminal part of the path expression, then it denotes the nontemporal value ( ), where
T t now
manager
Definition 6 (Time of a Path Expression)
Example 8
strong
time
Referring to Example 7:
For the sake of simplicity, here and in the following we represent the value of a static attribute of type as a
partial function: , defined only at = .
e e:a
e:a
o:v:a now
a a now
e:a e e:a now
e:a
o:v:a
o:v:a
e:a
e:a all o:v:a
e
e
ar e now
X:
first instant
is the object identified by the oid to which evaluates. Consider now an expression , that is, an
expression with no temporal specification in the terminal part. The most intuitive interpretation
is that, if no time is specified, the expression is evaluated at the current time, that is, is simply
a shorthand for . However, consider a sequence of attribute accesses composing a path,
that is, suppose = . Let be the object identified by the oid to which evaluates.
Because of the consistency of the database, is certainly defined at time and so its attribute
is; by contrast, could be undefined at time . Thus, when a path expression contains a
temporal qualifier, it is evaluated at the time denoted by the qualifier till another explicit temporal
qualifier is encountered. Therefore the path expression
is equivalent to . A path expression
, where does not contain any temporal specification, is simply a shorthand for .
Consider now the terminal path expression 7, where 7 is a set of time intervals (either
explicitly or implicitly denoted). The value associated with this expression is , that is, the
restriction of the function which is the value of to the time intervals in 7. However two
different interpretations of this path expression are possible: according to the interpretation
the denoted function must be defined for each 7, otherwise the path expression denotes no
value. According to the interpretation, the path expression denotes a function which can be
partial on 7. We assume that the default interpretation of a path expression is the weak one.
However, the strong interpretation can also be required by using the alternative syntax 7. A
(terminal) path expression denotes the temporal value whenever it is defined.
We now formalize these notions. First we introduce the associated with a path expression
, denoted as 0( ).
Let be a simple path expression. Its time,
denoted as 0( ), is a time instant in recursively defined as follows:
is an instant-valued temporal expression and
Consider now the restriction of a temporal value to a set of time intervals, as specified by the
following definitions.
Consider the path expressions of Example 7,and suppose that , where is
the object of Example 2:
division
salary 'Mary Dole' [50,60],15k
[61,now],30k
manager
Definition 7 (Temporal Value Weak Restriction)
Definition 8 (Temporal Value Strong Restriction)
Definition 9 (Path Expression Semantics)
Example 9
temporal T
undefined
temporal T v
undefined
e
ar
te / te t; t e:a te e :v:a t
te e:a te e :v:a
te e:a te e :v:a
e:a all e :v:a
X:
last interval
first instant
Let be temporal value of type ( ),
and let 7 2 be a set of time time intervals. The weak restriction of to 7, denoted
as , is a function: such that:
otherwise
Let be a temporal value of type
be a set of time intervals. The strong restriction of
to 7, denoted as , is a function such that:
otherwise
We are now ready to define the semantics (the value denoted by) of a path expression .
Let : be an oid-assignment. The
semantics of a path expression under oid-assignment , denoted as recursively defined
as follows:
if , it is the oid assigned to variable by ;
if ,
if is an instant-valued temporal expression, and (
if is a temporal expression,
if is a temporal expression,
4.3
Proposition 1
Proposition 2
Here and in the following, given a function , ( ) denotes the set of values on which is defined.
e:a all
e:a dom e:a e:a e:a e
e:a
dom
e
ar
e t a
t a t
dom #
Let , , be a path expression. Under the weak semantics,
the following relationship holds:
By contrast, under the strong semantics, relationship (*) holds only if:
A path expression is correct for an oid-
assignment if all the following conditions are satisfied:
for each :
Note that, according to Definition 9, simply a shorthand for
Similarly, equivalent to Therefore in the
remainder of the discussion we do not explicitly consider these cases.
The following proposition relates the semantics of a path expression on a set of time intervals,
either explicitly or implicitly denoted, to the semantics of the path expression on the time instants
composing the set. This proposition thus characterizes nontemporal valued terminal expressions
as derivable from temporal valued ones.
In this subsection we focus on conditions ensuring that a path expression is correct, for a given
assignment . Such conditions ensure that defined, that is, it denotes a value. The
correctness conditions depend on the structure of the path expression. Starting from the basis of
the inductive definition of path expressions, the path expression , with , is correct for
, provided that the oid-assignment assigns an oid to variable . Thus, given a path expression
, we must consider oid-assignments that are defined on variables in . Consider now the case
, with time instant (either implicitly or explicitly denoted). For this expression to denote
a value, the object denoted by must exist at time , and must be an attribute of the class to
which that object belongs at ; finally, the value for at time must be stored. For terminal path
expressions, the correctness conditions differ according to the two different interpretations (strong
and weak) of the path expressions. In particular, the strong interpretation requires the conditions
above to be satisfied for all time instants in the specified set of time intervals, whereas the weak
interpretation only requires the existence of at least an instant in the specified set of intervals, in
which the conditions are satisfied.
The following proposition states the correctness conditions for a path expression.
Corollary 1
Proposition 3
employee
division 5
status 'Mary Dole'
division
dom a ; c
A a t i n
A a t i n
A a t i n
c a a A c
n a e t now
A a t a e t now
A a a e now
A a a e now; now
X:
last interval
first instant
A a dom e t
A a dom e
A a all dom e dom X:a t :a
2. , and ;
3.
4. ;
, and conditions 1 3 above hold (with ), or
, and for which conditions 1 3 above hold (with ), or
, and conditions 1 3 above hold (with ).
Let be a path expression. If,
, such that is a static attribute, then is correct only if . Furthermore:
if , and is a static attribute, then is correct only if ;
if , and is a static attribute, then is correct only if ;
if ,and is a static attribute, then is correct only if .
Referring to objects of Example 2, the path expressions of Example 7 are correct,
whereas the following are examples of incorrect path expressions, given variable of type :
Let be a correct path expression. Then:
if , is
correct
if , .
We remark that the condition of Proposition 2 for terminal expressions under strong semantics
does not require that object never migrated during the
intervals in 7, that is, that (
7. By contrast, it requires that for all the classes - to which
has belonged during 7, - contains attribute , that is, (-).
The following corollary states correctness conditions for path expressions containing static attributes

The correctness test for a path expression can be performed in linear time with respect to the
length of the path expression, where the length of a path expression is the number of attribute
accesses (that is, "dots") appearing in it.
The following proposition specifies the domains of temporal values denoted by correct path
expressions. Their knowledge is relevant in order to check the correctness of subsequent uses of
those values, for instance when path expressions are used in comparison formulas.
(R 2a)
5 Static Analysis of Path Expressions
Rule 1
e X:a t:e X V ar
ar
now
The meaning of the inference rule is the following: if the conditions in the rule premises (the upper part of the
rule) are satisfied, then the rule consequence (the lower part of the rule) can be inferred.
In the previous subsection we have stated conditions ensuring that a temporal path expression is
correct, that is, it denotes a value. However, these conditions can only be checked dynamically,
since they depend on the specific object assigned to the variable appearing in the path expression
by the oid-assignment . In this section, we establish conditions ensuring the correctness of a
path expression for any oid-assignment . The relevance of these conditions is that they can be
checked statically, that is, at program (query) compilation time, thus allowing to ensure, by means
of static checks, that a given path expression will always be correct at run-time. Our approach
is related to static type checking techniques for nontemporal (database) programming languages.
In such database languages, type declarations are exploited to statically check the correctness of a
program, to ensure that no run-time type errors occur [6].
First, consider the problem of determining legal oid-assignments. In a (nontemporal) typed
object-oriented language, a type information is associated with each variable (that is, a type is
declared for the variable). We express the information that type is declared for variable as
. This type declaration implies that at run-time variable can only be instantiated to
an object member of class (that is, instance of or of a subclass of ). Moving to a temporal
context, we need to express information of the form : , to denote that variable can only be
instantiated with an object member of at time , as stated by the following rule.
Let be a path expression. The (temporal) type information : is associated with
in , if has the form and is the type declared for . Formally:
Therefore, given a variable with type information : , an oid-assignment is legal for
if the object assigned to by is an instance of class at time .
Let be a path expression and let : the type
information associated with . An oid-assignment is legal for if ( ) and (

Figure

1 shows the typing rules for path expressions. We denote the type associated with a
path expression as ( ). Rule 1 states that the type of a path expression = is the
type declared for . Rules 2, 3 and 4 deal with path expressions on time instants, thus denoting
nontemporal values, whereas the remaining rules deal with (terminal) path expressions on time
intervals, thus denoting temporal values.
For simplicity, throughout the paper, we have considered static attributes as a particular case
of temporal attributes, whose values are defined only at time instant . To take into account the
distinction between static and temporal attributes, the above rules should be refined. For example,
Rule 2 should be replaced by the following two rules:

Figure

1: Temporal path expression typing rules2
(R
(R
(R
instant-valued
(R
(R
(R
non instant-valued
(R
(R
non instant-valued
(R
ar
type e:a te dom a; T
te
type e:a dom a; T
type e:a dom a; T
type e:a te dom a; T
te
type e:a dom a; T
type e:a te dom a; T
te
type e:a all dom a; T
now
(R 2b)
type e:a now dom a; T
Proposition 4
Example 11
Corollary 2
Example 12
manager
50 division 20
string
employee 50 i division 20
manager 50 division 40 now
manager 50 division
now i division 50 now
now
last instant te first instant te inst slice te; n te n
e
e
e
e X:
:lif espan
Let be a type correct path expression. Then, for any legal
assignment , is correct for . Moreover, if the type deduced for is , then
Referring to classes of Example 1, consider the path expression
, with . The path expression is type correct, and
. Consider the oid assignment such that of Example 2. The oid assignment
is legal, since . However, is undefined, since
Let be a type correct path expression, if , then for
any legal assignment , is correct for .
Referring to classes of Example 1 and to objects of Example 2 it is easy to see that the
path expression is type correct but it is not correct with respect
to the legal oid assignment such that . Indeed,
is undefined, since .
and similar refinements should be done for other rules. However, there is no mean to statically
check whether the only instant denoted by a temporal expression will be . Thus, in the
following, we will focus on temporal attributes.
In order to apply the above typing rules, an important information is whether a temporal expression
is instant-valued. In general, this property cannot be statically decided, since it depends
on the content of the database. However, there are some sufficient syntactic conditions on temporal
expressions ensuring their instant-valuedness. In particular, temporal expressions of the form
are instant-valued, , IN.
We are now able to introduce the notion of type correctness of a path expression and to relate
this notion to the notion of (dynamic) correctness discussed in Section 4.3.
A path expression is said to be type correct if a type for
it can be deduced according to rules in Figure 1.
By contrast, if a path expression contains the specification of two different time instants,
type correctness does not imply the correctness of for any legal oid-assignment, as shown by the
following example.
For path expressions denoting a temporal value, a similar result can be obtained, under the
weak interpretation, as stated by the following corollary.
As a particular case, note that if = is a type correct path expression,
then for any legal assignment , is correct for . By contrast, under a strong interpretation, type
correctness does not imply the correctness for any legal oid-assignment, as shown by the following
example.
6 Path Expression Equality
inst
ins #
ins #
salary 'Mary Dole' salary [50,now]
salary 'Mary Dole' salary
ar
ar
ar
t dom e t dom e e t e t
last interval X
last interval X
ar e e
e e dom e dom e
e e dom e dom e
Definition 14 (Weak-value Equality)
Example 13
Proposition 5
instantaneous-value
equality weak-value equality
Referring to path expressions of Example 9:
. ,
. , and this implies
that the two path expressions are also weak value equal.
Let be an oid-assignment. Let and be two path expressions:
is correct only if .
is correct only if
is correct only if and .
The value a path expression denotes can be compared (by means of a comparison operator such
as =, =, , , etc.) with a value of appropriate type, or with the value denoted by another path
expression. Clearly, for a comparison expression to be correct, several constraints must be satisfied,
involving both the type of the compared values and the time at which the comparison expression
is evaluated. For the sake of simplicity, in this section we focus on the notion of path expression
equality. However, similar considerations apply for other comparison operators.
Path expression equality is formalized by the following definition.
Let : be an oid-assignment. Two
path expressions and are equal
Note that the notion of path expression equality uniformly applies to path expressions denoting
both temporal and static values.
In a temporal context, two further notions of equality can be devised:
and . Two path expressions are instantaneously value equal if there
exists an instant in which they denote the same value. Two path expressions are weakly value
equal there exist two instants, not necessarily the same, in which they denote the same value.
These notions are formalized by the following definitions.
Let : be an oid-assignment. Two
path expressions and are instantaneously value equal there exists an
instant such
Let : be an oid-assignment. Two path
expressions and are weakly value equal there exist two instants and
such
The above notions of equality obviously make sense for path expressions denoting temporal
values. Also a path expression denoting a static value can be compared under these types of
equalities to path expressions denoting either static or temporal values, but only at the current
time. Therefore, several constraints must be satisfied by the values denoted by two path expressions
compared under one of the above types of equality. These constraints are formalized by the following
proposition.
ins
Definition 15 Restricted Equality
Example 14
Proposition 6
salary 'Mary Dole'
salary
ins #
ins #
inst
inst w
inst inst inst inst
We omit the definition of = and = as they are analogous to that of = .
The same results hold for restricted equality.
Given two path expressions and :
if , then ;
if , then ;
if , then:
if (resp. , ), then .
ar e e
e e te te e e
e e te te t / te dom e dom e
e e te te t / te dom e t / te dom e
last interval
e e te te
We can also be interested in comparing two path expressions, under one of the above notions
of equality, only for a specific set of time instants, either implicitly or explicitly denoted. This
possibility is formalized by the following definition.
be an oid-assignment. Let and
be two path expressions:
that
such that
Note that, conditions stated by Proposition 5 can be easily extended to the case of an an
expression involving restricted equalities.
Finally, the following relationships hold between the various types of equality.
snapshot conditions
Conclusions



--R



Submitted for publication.


Semantic Assumptions and Query Evaluation in
On Understanding Types
An Object-Oriented Model for
The Historical Relational Data Model (hrdm) Reviseted.


In this paper we have addressed the problem of querying a temporal object-oriented database through a navigational approach
This work can be extended in several directions.


available via anonymous ftp from as

HSQL: A Historical Query Language.
The Functional Data Model and the Data Language DAPLEX.
The Temporal Query Language TQUEL.
Temporal Object-Oriented Databases: A Critical Comparison
The TSQL2 Temporal Query Language.
A Generalized Relational Framework for Modeling Temporal Data.


Temporal Relational Data Model.
Temporal Database Bibliography Update.
In the following we give the syntax in BNF form for the language provided by Chimera to define boolean expressions.




by Definition 9
The proposition can be proved by induction on the structure of the path expression.




We now prove the correctness of the terminal expression 7 given

If is a static attribute
We consider each case separately:


First of all we recall that is simply a shorthand for
Basis Inductive step i) ii) i) ii) iii) Proof of Corollary 2 Proof of Proposition 5 T T t




Let us consider the first item.
Let us consider the second item.

Let us consider the fourth item.
--TR

--CTR
S. Adali , M. L. Sapino , V. S. Subrahmanian, An algebra for creating and querying multimedia presentations, Multimedia Systems, v.8 n.3, p.212-230, October 2000
Salvatore T. March , Charles A. Wood , Gove N. Allen, Research Frontiers in Object Technology, Information Systems Frontiers, v.1 n.1, p.51-74, July 1999
static analysis and type checking;navigational data accesses;temporal query languages;temporal object-oriented data models