Chrono: A Conceptual Design Framework for Temporal Entities

Chrono: a conceptual design framework for temporal entities? Sonia Bergamaschi1,3 and Claudio Sartori2 ,3 DSI - University of Modena, Italy

1 2

[email protected]

DEIS - University of Bologna, Italy [email protected]

CSITE - CNR, Bologna, Italy Viale Risorgimento, 2 - 40136 Bologna, Italy 3

Abstract. Database applications are frequently faced with the necessity of representing time varying information and, particularly in the management of information systems, a few kinds of behavior in time can characterize a wide class of applications. A great amount of work in the area of temporal databases aiming at the de nition of standard representation and manipulation of time, mainly in relational database environment, has been presented in the last years. Nevertheless, conceptual design of databases with temporal aspects has not yet received sucient attention. The purpose of this paper is twofold: to propose a simple temporal treatment of information at the initial conceptual phase of database design; to show how the chosen temporal treatment can be exploited in time integrity enforcement by using standard DBMS tools, such as referential integrity and triggers. Furthermore, we present a design tool implementing our data model and constraint generation technique, obtained by extending a commercial design tool.

1 Introduction and motivations Database applications are frequently faced with the necessity of representing time varying information and, particularly in management information systems, a few kinds of behavior in time can characterize a wide class of applications. In the last years we observed a great amount of work in the area of temporal databases, aiming at the de nition of standard representation and manipulation of time, mainly with reference to the relational model. Nevertheless, in our opinion, the design of databases with temporal aspects has not yet received suf cient attention: the decisions about the temporal treatment of information are matter of the conceptual database design phase and, starting from there, a set of related design choices is strictly consequent. For instance, if we consider two related pieces of information and we decide that temporal treatment is needed only for the rst one, can we assume that the decision of temporal treatment for ?

With the contribution of Gruppo Formula S.p.A. - Bologna, Italy, http://www.formula.it

the second one is completely independent or are there necessary clear constraints to preserve information integrity? In order to obtain an answer to the above question, we have to start facing the problem of supporting referential integrity constraints in this more complex scenario. In fact, when we add temporal treatment to an information we limit the validity of this information in time and a reference to it can be done only during this validity interval, therefore the kind of allowed/required temporal treatment for related information is strictly inter-dependent. As a consequence, in order to support temporal treatment we must extend the referential integrity concept, which plays a central role in databases: a reference is valid if the referenced object is valid through all the valid time of the referencing object. Another assumption of our work is related to the general framework of database design: when we are faced with the design of non-trivial application we cannot avoid the usage of methodologies and tools to support some design phases [1]. The Entity-Relationship (ER) model and its extensions has been proved to be useful in the conceptual design phase, and many design tool allow the user to draw conceptual schemata and to automatically generate relational database schemata. In addition, some design tools are also able to generate code for constraint enforcement, such as referential integrity and triggers for dierent relational DBMS. For this reason, if we design temporal treatment directly at the conceptual level and extend a design tool in this direction we obtain two major advantages:

{ temporal treatment is documented at a high level as a rst class feature and it is dealt with in a standard fashion, { the integrity constraints deriving from temporal treatment can be automatically translated into constraint enforcement code at the DBMS level.

The rst choice we have to make is the selection of the conceptual model to be extended. In order to obtain a general approach and to easily come to the implementation of temporal treatment on top of an existing design tool, we refer to an industry-standard conceptual model, the IDEF1X model [23]. IDEF1X is an accepted standard for the USA government and is adopted by some conceptual database design tools [18,17]. The second choice is which kind of time is to be supported. The past decade of research on temporal databases led to the presentation of a high number of temporal data models and the book [25] gives a comprehensive account and systematization of this activity. In particular, many extension of the relational model have been proposed to represent the time dimension with dierent meanings and complexity. At present, there exists a general consensus on the bi-temporal models, such as BCDM [14], where two orthogonal temporal dimensions are considered: valid time (i.e. the time when the fact is true in the modelled reality) and transaction time (i.e. the time when the fact is current in the database and may be retrieved). According to the assumption that supporting the referential integrity is a major issue, it is mandatory for us to support at least the valid time dimension. 2

In this work we restrict to consider only the valid time, since the transaction time dimension does not aect the enforcement of referential integrity. In other words, if an application requires both the temporal dimensions, it is possible to perform the conceptual design with respect to the valid time dimension, and then add independently the transaction time representation. The third choice refers to the granularity of detail to which conceptual elements have temporal treatment, ranging from a single attribute value to an entire entity instance. Our choice is in favor of the entity level granularity: all the attributes of an entity have the same temporal treatment, and this applies to all its instances. This apparently coarse granularity is well suited for most practical applications, and does not constitute a severe limitation, since a dierent temporal treatment for two subsets of attributes of the same entity can be easily modeled with vertical partitioning. The fourth choice is the type of time modeling suitable for in a database application. The most intuitive notions are that of event, which happens in a time point and state, which holds during a time interval, described by its starting and ending time points. The research community has reached a quite wide consensus on the notion of temporal element, which is a nite union of n-dimensional time intervals [9]1. Special cases of temporal elements include valid-time elements, transaction-time elements and bi-temporal elements. As explained above, we consider only one-dimension temporal elements, i.e. valid-time elements. The straightforward modeling of such a temporal element as a non normalized entity attribute would lead to not ecient implementation in relational environment. Being aimed to produce a practical design tool, our choice is to constrain a given entity to have normalized time attributes, i.e. only one of the following kinds of temporal elements: single chronon, nite set of chronons, single interval, nite set of intervals. This means that the designer has to decide in advance which type of temporal treatment is best suited for the modeling of a given entity. On the basis of the above choices on the temporal treatment of information, we de ne an extension of an industry standard conceptual model, IDEF1X, and develop the necessary set of integrity constraint at the conceptual schema level to preserve information consistency. The result of these extensions is a uniform way to deal with time at the conceptual schema level. Since some design tools provide the automatic mapping of a conceptual schema into a relational one and generate code for constraint enforcement, an eective architectural choice is the extension of a tool like this at the conceptual level. The logical schema and the integrity constraints and triggers to ensure a correct evolution of the database contents with respect to time attributes will thus be automatically generated at the database level. In order to prove the feasibility and the usefulness of our approach, we developed a software layer, called Chrono, on top of the database design case tool ErWin [18]. With Chrono, the conceptual design activity is modi ed as follows: 1. design the conceptual schema abstracting from the temporal aspects 1

The simple notion of time interval would not guarantee the closure property with respect to usual operation on time intervals, such as union, intersection, etc..

3

2. select the appropriate temporal treatment for the entities 3. Chrono automatically converts the schema obtained into a standard IDEF1X schema, adding the temporal attributes and the necessary set of integrity constraints. The paper is organized as follows: section 2 introduces the Chrono conceptual data model as an extension of IDEF1X with temporal modeling features. Section 3 discusses the design constraints generated by the dependencies between related temporal entities. Sections 4 examines the integrity constraints that rule temporal entities. Section 3 discusses the design constraints generated by the dependencies between related temporal entities. Section 5 shows the architecture of the design tool based on Chrono. Finally, section 6 discusses some related works.

2 The Chrono conceptual data model Let us brie y recall the modeling principles of the IDEF1X model, partly drawn from the ocial F.I.P.S. documents [23]. The IDEF1X model is derived from the Entity-Relationship (E/R) model [3] and its well known extensions[1]. The main dierence with respect to E/R is the proposal of a conceptual model \closer" to the logical relational data view. The main extension is the distinction between independent and dependent entity, the latter being identi ed with the contribution of another entity via an identifying relationship. The relationships are either connection or categorization relationship. Connection relationship (also referred as parent-child relationships ) are the standard way to express semantic relationships between entities and can be identifying, non-identifying without nulls and non-identifying with nulls. The cardinality is one to one or one to many. The model allows also the non-speci c relationship, corresponding to the many to many relationship, but its usage is intended only for the initial development of the schema, to be re ned in later development phases and substituted by entities and connection relationships, as explained at the end of this section. A categorization relationship represents a generalization hierarchy and is a relationship between one entity, referred to as the generic entity, and another entity, referred to as a category entity (i.e. the specialization). A category cluster is a set of one or more categorization relationships and represents an exclusive hierarchy. The Chrono conceptual data model is a temporal extension of IDEF1X. In analogy with the Entity{Relationship model, it assumes that each entity instance must be uniquely identi ed. By way of some internal attributes if the entity is independent, and by other connected entities if the entity is dependent. We will consider the identi er of an entity as time-invariant, while the other attributes can be time variant. Entities are either absolute, if they do not require temporal treatment, or temporal, if they are subject to time support, with explicit representation of its time attributes. Absolute entities will eventually be subject 4

to insertions, deletions and updates, as is usual in database environment. In contrast, insertions, deletions and updates of temporal entities will be subject to particular rules and restrictions, as will be shown in the following. According to [12], we assume that all the non-key attributes of an entity have the same kind of behavior in time: in this way, temporal treatment can be done at the entity level and not at the attribute level. This is not a real limitation, since if the assumption does not hold for an entity E, attributes can be clustered according to a uniform behavior in time and the entity can be vertically partitioned into entities, say E1 and E2 linked by a one{to{one identifying relationship. In a way similar to the extension of the relational model with time proposed in [22], we translate the temporal treatment proposed for relations to entities: a temporal entity instance e of the entity type E is associated with a temporal element T (e), giving the lifespan of e. In addition, to simplify the integrity constraint enforcement, we accept the notion of temporal normal form proposed in [13] and consider only conceptual schema in third normal form, by an easy extension of the well-known notion of relational normal forms to the conceptual level, as suggested in [19]. Instead of allowing temporal elements composed by any possible mix of chronons and intervals, we consider four kinds of temporal elements: single chronon, nite set of chronons, single interval, nite set of intervals. For a given temporal entity type only one kind of temporal element is allowed. This led us to extend the IDEF1X model with ve kinds of temporal entities representing either events, when the allowed temporal element is chronon or a set of chronons, or states, when the allowed temporal element is an interval or a set of intervals. An entity instance can have a single lifespan or an history when its temporal element is a set. The semantics of states is that the state is true during its interval, therefore, when state history is represented, the database must satisfy the constraint that the intervals of states of the same entity with dierent attributes cannot overlap. To conclude, an additional constraint is available to the designer: if the instance of an entity must always exist inside a given interval, but its state is allowed to change and the history is relevant, then the intervals of the various states of the same entity must always be contiguous. On the basis of the above discussion, we can say that the possible types of entities with temporal treatment are the following ve: SP, CMP, MP, E, EV. In the following, the ve Chrono types are explained together with their mapping into IDEF1X entities, as shown in Table 1. The mapping consists into the addition of attributes for the representation of time, possibly extending the identi er. Section 4 will discuss the integrity constraints added by this mapping.

SP single period: the entity represents a single state and has an associated

time interval; the time interval is represented as a couple of chronons, say Ts (Tstart) and Te (Tend). CMP consecutive multi-period: the entity is continuously valid during a period, but some of its aspects change over time, in connection with speci c 5

time points; therefore, the evolution of the entity can be seen as a succession of states valid during consecutive periods; its temporal element is a set of contiguous time intervals, and a single, absolute, entity instance generates many entity state instances; in order to represent the entity in terms of attributes and keys as required by the underlying conceptual model, we change the entity identi er, say I to include an extreme of the time interval, say Ts ; in this way, the instances of the temporal entity are dierent versions of the instances of the original absolute entity. MP non-consecutive multi-period: the entity is valid during a set of periods, without any constraint of being consecutive; the representation is the same as the consecutive multi-period type. E event: the entity represents an event which took place in a speci c time point; its time element is a single time point and can be represented by a single attribute Ts. EV event with versions: the entity represents an event which resulted in a tuple of values of its attributes; the history of the changes to the attribute values is maintained, each change being identi ed by its speci c time point; the time element is a set of chronons and the representation is obtained, as for the consecutive multi-period case, by including the time attribute Ts in the identi er. Let us consider a set of short examples about the classi cation above. A human being, from the registry oce point of view, is \valid" from his birth, and can be classi ed as type SP, while a living person, which is a specialization of human being, ends his validity with his death and is of type SP too. A company's employee changes over time his description, including salary, duties, address, and so on. Each change starts at a speci c time and holds up to the following change, therefore the employee description requires a time representation of type CMP. A patient can be hospitalized many times, each time with a speci c starting and ending time point, and can be represented with a type MP entity. The documents for the management of an organization usually are marked with a time (for instance when an ocier wrote the document). Provided that the application requires that no historical record of the document changes is needed, it can be represented as a type E entity. On the other hand, if the application needs to record the dierent versions of such documents, the type EV temporal treatment can be used. Up to now we considered an entity in isolation, but in practical cases we always have many entities linked with various semantic relationships, such as aggregation and generalization hierarchy. In this case the following question arise: is the temporal treatment of an entity independent from that of the entities related to it? And more, which integrity constraints, if any, govern the time values of a single entity and of related entities? In order to give an answer to the above questions, let us examine the relationships expressed in IDEF1X. In the categorization relationships and identifying 6

Temporal treatment of entity E

Chrono representation E

IDEF1X representation E

SP

Single Period (SP)

Id

Id Ts Te

E

Consecutive Multi{Period (CMP)

E CMP

Id

Id Ts Te

E

E MP

Multi-Period (MP)

Id

Id Ts Te

E

E E

Event (E) Event with Versions (EV) Same Validity Period identifying relationship (SVP)

Id

Id Ts

E

E EV

Id

Id Ts

=

Table 1. Mapping from the Chrono concepts to the IDEF1X concepts relationships a child makes a mandatory reference to the parent and therefore when it is be valid the parent must be valid as well. In summary, the validity of both categorization and identifying relationships is the same as the validity of the child and therefore they cannot have any temporal treatment on their own. On the other hand, in principle it is acceptable that a parent instance has a validity period wider than that of its child instances. Therefore, the choice of the constraints to be enforced depends also on whether the validity period of the child instance can be contained in that of its parent instance or it must be forced to be the same as its corresponding parent instance. We consider as default case the less constrained, that is when the validity period can be contained, and introduce, as a new design element the SVP identifying relationship (same validity period ), as shown in the last row of table 1. In IDEF1X the constraint is simply removed at the graphical level, being translated into a constraint at the extensional level. The only constraint on a general non-identifying relationship is that the child instance must be valid inside the validity of its parent instance. Consider, for 7

Employee Emp# Employee Emp#

occupancy

Occupancy Emp#

MP

Room# Room Room# Room Room#

a. IDEF1X representation

b. Chrono representation

Fig. 1. Example of relationship with temporal treatment instance, the cyclic relationship \parent-ospring" This case, can be represented as a non-identifying relationship between human beings, and the constraint of parent birth-date lower than ospring birth-date must be enforced, while the end of the validity perdiod is in nite and does not give rise to any problem. Non-identifying relationships, either with or without nulls, can hold during an arbitrary interval, included in the intersection of the validity intervals of the related entities. Thus the relationship can have a kind of temporal treatment on its own. On the other hand, when complex aspects of a relationship need to be described, such as generalization between relationships, the standard conceptual design procedure is rei cation. A rei ed relationship is promoted to an entity which is the child in a couple of relationships with the two original entities2 . Let us consider, for example, how employees are associated to their oce rooms. In a snapshot view, the employee is assigned to exactly one room, as shown in the schema of Figure 1.a. If we want to model the fact that an employee can change his room over the time, and we want to keep track of this history, we have to modify the schema as follows: 1. reify the relationship occupancy producing the dependent entity Occupancy 2. select for Occupancy one of the Chrono temporal entities, say MP to specify that an employee in a given time period is assigned to at most one room 3. specify the proper cardinality for the relationships of Occupancy: the relationship with Employee derives from the child side and is identifying, while the relationship with Room is non-identifying. The the modi ed schema is shown in Figure 1.b. For the intensional level we will de ne the allowed temporal treatment combination for related entities, and for the extensional level we will state the constraints that rule the insert, update and delete operations on entities. These constraints can be translated into constraints on relational database operations by many design tools. 2

This choice could be considered pertaining the logical level, rather than the conceptual level, but it is coherent with the philosophy of IDEF1X, which is a compromise between a conceptual and a logical data model.

8

3 Design constraints on temporal entities When multiple versions of an entity instance are allowed (i.e. for Chrono entities of types CMP,MP and EV) the mapping from a Chrono entity into an IDEF1X entity gives rise to an extension of the entity identi er Id with one of the time attributes (say the starting time), thus obtaining the key K=(Id,Ts). In this way the entity instance uniqueness is preserved by the uniqueness of the identi er, which is supposed to be time invariant, and of the times in which versions are valid: it is not allowed to have dierent versions starting from the same time point. In the following we will refer to the Chrono representation of entities and also to their corresponding IDEF1X representation. In particular, we de ne version of an entity instance (or brie y version) an instance of an IDEF1X entity. In particular, an instance of an entity of type CMP, MP and EV may correspond to more versions, sharing the same Id, but with dierent time elements. In a standard snapshot database, a foreign key constraint has a straightforward implication: an instance of a child entity must have a valid reference to an instance of a parent entity (or a null reference if it is allowed). In a temporal database the validity of a reference must take into account also the time. Therefore it is necessary to extend the notion of referential integrity, by ensuring that the validity times of two instances of related entities have an overlapping.

Otherwise, it would be the case that, in some time point, a child instance refers to a parent instance which is not valid in that time point. A relationship between two entities implies two major consequences: { at the intensional level, the allowed temporal treatment of the entities is constrained: the constraints take into account the relationship type and the compatibility between the dierent temporal treatments; { at the extensional level, the temporal interaction between two instances of connected entities is subject to additional integrity constraints, which have to be enforced. The following subsections will examine the constraints to be enforced for each kind of IDEF1X relationship; the constraints to be enforced when insert, update and delete operations are performed are a consequence of the ones of this section and will be examined in Section 4.

3.1 Categorization relationship

A complete category cluster speci es that each instance of the parent is related to exactly one instance of one of the childs in the cluster and vice-versa. When time is considered, this constraint must hold for any snapshot. Let be  2 fSP, CMP, MP, E, EVg a type of temporal treatment, Ep the parent entity and Ec the i{th child entity. At the intensional level, the following constraints hold: 1. if Ep is of type  , then all of its childs Ec must be of the same type  ; i

i

9

P C SP CMP MP E EV

SP yes yes yes yes yes

CMP MP

E

EV

SP

yes yes yes yes yes

CMP MP

E

yes no no yes yes yes no yes no no yes yes yes no yes no no no no yes no yes yes yes no no no yes yes no yes no no no no Case a Case b Table 2. Identifying parent-child relationship: allowed combinations

EV no no no yes yes

2. if Ep is absolute, then at least one of its childs must be absolute, since otherwise there could exist a snapshot and an instance ep 2 Ep such that does not exist a valid instance ec 2 Ec for any i3 . i

i

When the category cluster is incomplete the constraint 2 above does not hold.

3.2 Identifying relationship Each child instance ec 2 Ec is completely dependent on a parent instance ep 2 Ep . Thus, the validity period of a ec must be contained in the validity i

i

i

period of its related parent ep . Otherwise, there would exist at least one point in time where the child instance violates the referential integrity. On the other hand, in principle it is acceptable that a parent instance has a validity period wider than that of its child instances. Therefore, the choice of the constraints to be enforced depends also on an application-dependent requirement: a) the validity period of the child instance can be contained in that of its parent instance b) the validity period of the child instance must be forced to be the same as its corresponding parent instance.

Case a - validity period of child instance included in validity period of parent instance In this case, the child can have temporal treatment even

if the parent is an absolute entity. On the contrary, if the parent has a temporal treatment then the child too must have one (for a less restrictive choice see footnote 2). Table 2 case a shows the allowed combinations: let us comment shortly some of them. When the parent entity is of type SP, a single parent instance can be connected to many dierent versions of child instances, and since child validity can be included in parent validity, every kind of temporal treatment is allowed for childs. Vice-versa, when the parent is of type E, there is no room for dierent versions of a child or for child validity spanning over an interval. 3

A less restrictive choice could be to move this constraint at the extensional level, ensuring that the lifespan of a parent instance be covered by the union of the lifespans of all its childrens.

10

Case b - same validity period In this case it is not possible that one entity

is absolute and the other has a temporal treatment. Nevertheless, the temporal treatment of parent and child entities is not constrained to be of the same type, even though combination of types is not arbitrary. Table 2 Case b shows the allowed combinations: let us comment shortly some of them. When the parent is of type SP, its child can be either of type SP or CMP. In fact, a single parent instance ep[ 1 3] with validity [t1; t3] can correspond to two versions of child instances, say ec[ 1 2] and ec[ 2 3 ] , which together cover the parent validity interval. When the parent is of type CMP, its child can be either of type SP or CMP. The second case is straightforward, while the rst one is analogous to that of the previous paragraph, by exchanging parent and child. When the parent is an event with versions time entity, a parent is represented by many versions with dierent validity intervals and can be related to one or more child instances. Therefore, the child must be of type E or EV, since the \period" types could not ensure the coincidence of validity intervals. t ;t

t ;t

t ;t

3.3 Non-identifying relationship without nulls

The only dierence of this case with respect to identifying relationship is that the child key is now independent from the parent key. Apart from that, Child instances must be related to parent instances, therefore their validity must span inside the parent validity and the same constraints of Section 3.2 apply.

3.4 Non-identifying relationship with nulls

In this case, child instances can have a null reference to parent. Vice-versa, when the reference is not null, we require it is valid, i.e. child validity is included in parent validity4. The allowed combination of temporal treatment are the same discussed for case a.

4 Constraints on temporal entity instances This section examines the intra-entity and the inter-entity constraints which must be enforced to guarantee the consistent evolution of a database deriving from a Chrono conceptual schema. In the following we refer, indierently, to a Chrono conceptual schema and to its IDEF1X mapped representation. The constraints considered include both rules on the values of the time attributes and pre-requisite and integrity maintenance actions for the insert, delete and update operations. As a necessary premise, we must consider the in uence of time-related operations. We will consider separately the constraints related to single entities and those deriving from referential integrity. In particular, let us consider the following two basic time related operations [24]: 4

Because of the weaker parent-child relationship it is not worth considering the equality case as in Section 3.2 case b.

11

coalesce given n value equivalent instances of the same entity and with adja-

cent time intervals generate a single entity instance with the maximal time interval split given an entity instance and a time point inside its time interval, generate a couple of value equivalent entity instances with adjacent time intervals. We assume that the above operations be allowed and that the database is always kept in a coalesced state (i.e. no coalescing is possible). Therefore insertions and updates on the database will trigger correction actions when necessary.

4.1 Single period In this case, we have only the obvious intra-instance constraint that it must always be Ts  Te, i.e. its time interval is non-empty. The constraint is to be enforced when attempting an insert or update operation.

4.2 Consecutive multi-period The constraints which rule instances of this kind of temporal entities depend on the kind of operations that are accepted at the application level. In particular, we consider the impact of the availability of the operations of coalescing and splitting (or split). If these operations are allowed, then the following constraints are enforced:

Insert if the time interval of the new entity instance is non-empty and there not

exist an instance with the same value in Id, the insert is accepted, otherwise only the following cases are acceptable: 1. if the new instance starting time Ts meets the ending time of the most recent version of the same instance, the insert represents a new version of an existing instance and is accepted 5 ; 2. if the new instance ending time meets the starting time of the oldest version of the same instance, the insert constitutes an extension of the validity in the past and is accepted; 3. if the new instance ending time Te meets the ending time of an existing version, but the new starting time is greater than the old one, the insert corresponds to a splitting operation and is accepted; as a consequence, the starting and ending time of the new and old versions are updated, to preserve adjacency. Update if the time interval of the new entity instance is non-empty and there not exist an instance with the same value of Id, the update is accepted, otherwise only the following cases are acceptable: 1. if the update does not aect time attributes the update is valid; 2. if the update modi es the starting time Ts of the oldest version or the ending time of the most recent version it is accepted; 5

As an alternative, the most recent version could be open-ended.

12

3. if the update modi es the time interval to cover exactly the time intervals of two or more consecutive versions of the same instance, these versions have to be eliminated (coalescing). Delete for each instance selected for deletion with identi er component Idi, the are two possible cases: 1. there exist only one instance with Idi or the deleted instance is the oldest or the most recent version and the deletion is accepted 2. the instance is deleted for coalescing. If the application logic does not allow automatic coalescing and splitting, the cases requiring such operations, namely the last presented for each of the above operation, are not accepted.

4.3 Non-consecutive multi-period

In this case, we lose the constraint of having the ending time of a version meeting the starting time of the consecutive version and the only requirement is that the versions must be non-overlapping. Given an instance to be inserted, if the time interval of the new instance is non-empty and there not exists an instance with the same value of the entity identi er component Id, the insert is accepted, otherwise the insert is acceptable only if the time interval of the new instance does not overlap the time intervals of the already existing instances with the same identi er Id. For the update and delete operations, the constraints are the same as for the insert.

4.4 Event and event with versions

In this case, a single time attribute is sucient for the temporal representation. Single event entities do not need any special constraint checking, while multiple event entities extend the key with the time attribute, therefore the key uniqueness must be veri ed on insert and update operations.

4.5 Categorization relationship

When Ep is of type  , each instance ec 2 Ec is related to an instance ep and the two instances must be valid at the same time. Therefore, at the extensional level the following constraints hold: 1. the time attribute Ts (and Te if  2 fSP, CMP, MPg), together with the parent identi er component Id, have the semantics of foreign key from Ec to Ep ; 2. for each parent instance ep there must exist a single instance ec in exactly one Ec with the same value of Id, Ts (and Te if  2 fSP, CMP, MPg). The above constraints hold for any  . Insert, update and delete operations, both on the parent and child, must be done according with them. When the category cluster is incomplete the constraint 2 above does not hold and only the parent update and delete, child insert and update are subject to constraint enforcement. i

i

i

i

i

13

4.6 Identifying relationship In this case, parent insert, child insert and child update must check the inclusion of the validity period of the child with respect to that of parent. The attributes (Id, Ts, Te) have the semantics of foreign key, from the child to the parent, and the operations parent update, parent delete, child insert and child update must enforce it.

4.7 Non-identifying relationship The constraints take into account the possibility of null reference from child to parent, and check the validity interval when the reference is not null.

5 Implementation of Chrono The most direct method for the implementation of Chrono would be to extend a case tool for the conceptual design in order to deal with time attributes and to generate the appropriate integrity constraints. At present it was not possible either to build a case tool from the scratch, or to access the source code of an existing tool. For this reason we had to build an additional software layer on top of a case tool, but this was sucient to prove the feasibility and the usefulness of the project. We chose the case tool ERwin (from LogicWorks) which works in MS Windows environment and is based on the IDEF1X model. ERwin has a graphic interface to support conceptual schema design and is able to automatically generate relational schemata and triggers for many popular RDBMSs. The triggers are generated starting from trigger templates, with some peculiarities for the various supported DBMSs. Some trigger templates are added by Chrono to perform time-related checks and actions. Chrono operates by reading and modifying the les generated by ERwin describing a conceptual schema. The ow of the design activity is constituted by the following steps: 1. 2. 3. 4.

the designer prepares a usual IDEF1X conceptual schema with ERwin; the schema is stored in a le with extension .ERX; Chrono reads the .ERX le and interprets the schema description the designer adds the temporal treatment to the entities of the conceptual schema 5. Chrono writes a modi ed .ERX le including the schema modi cations necessary for the representation of time and the triggers for the preservation of data integrity for time related attributes; 6. ERwin imports the modi ed .ERX les for possible schema re nement. Report [2] shows more details on the architecture of Chrono. 14

6 Discussion and conclusions We introduced a conceptual data model extending IDEFIX for the representation of time and discussed both the conceptual design constraints and the integrity constraint introduced by the representation of time. The conceptual design constraints introduce limitations on the possible kinds of temporal treatment for related entities, while the integrity constraint are used to guarantee consistent database states with reference to temporal treatment. The idea of extending conceptual models in order to support time representation received some attention in the literature. The report [10] provides a comprehensive survey on the topic and identi es nineteen design criteria to compare the eectiveness of the surveyed models [8,15,16,21,6,7,4,5,26,20, 11]. All the models above are extensions of the Entity-Relatonship model, but can be easily compared to Chrono, since IDEF1X too is strictly related to the Entity-Relationship model. Report [2] compares Chrono with the models above. To summarize , we can say that Chrono couples a signi cant expressive power with the reuse of the existing available technology, obtaining a feasible and low cost approach to the eective representation of time in a database. The most signi cant evolution of our work would be a deep analysis of the design and constraint issues deriving from a more sophisticated time model, for instance the bi-temporal conceptual model.

Acknowledgements Thanks to Gruppo Formula S.p.A. for the support, to Paolo Pellizzardi for the suggestions and discussions and to Giorgio Ferrara for the programming eort.

References 1. C. Batini, S. Ceri, and S. B. Navathe. Conceptual Database design: an EntityRelationship Approach. The Benjamin/Cummings Publishing Company, 1992. 2. S. Bergamaschi and C. Sartori. Chrono: a conceptual design framework for temporal entities. Technical Report CSITE-011-98, CSITE - CNR, 1998. ftp://wwwdb.deis.unibo.it/pub/reports/CSITE-011-98.pdf. 3. P. Chen. The Entity-Relationship model - towards a uni ed view of data. ACM Trans. on Database Systems, 1(1):9{36, 1976. 4. R. Elmasri, I. El-Assal, and V. Kouramajian. Semantics of temporal data in an extended ER model. In 9th Int. Conf. on the Entity{Relationship Approach, pages 239{254, Lausanne, Switzerland, 1990. 5. R. Elmasri and V. Kouramajian. A temporal query language for a conceptual model. Lecture Notes in Computer Science, 759:175{??, 1993. 6. R. ElMasri and G. Wuu. A temporal model and query language for ER databases. In Proc. IEEE CS Intl. Conf. No. 6 on Data Engineering, Feb. 1990. 7. R. Elmasri, G. T. J. Wuu, and V. Kouramajian. A temporal model and query language for EER databases. In Tansel et al. [25], chapter 9, pages 212{229.

15

8. S. Ferg. Modeling the time dimension in an entity-relationship diagram. In 4th International Conference on the Entity-Relationship Approach, pages 280{286, Silver Spring, MD, 1985. ieee, Computer Society Press. 9. S. K. Gadia and C. S. Yeung. A generalized model for a relational temporal database. In ACM SIGMOD, pages 251{259, 1988. 10. H. Gregersen and C. S. Jensen. Temporal entity{relationship models { a survey. Technical Report TR-3, Time Center, January 1997. http://www.cs.auc.dk/research/DBS/tdb/TimeCenter/publications.html. 11. J. L. Guynes, V. S. Lai, and J. P. Kuilboer. Temporal Databases: Model Design and Commercialization Prospects. Database, 25(3), Aug. 1994. 12. C. S. Jensen and R. T. Snodgrass. Semantics of time-varying information. Information Systems, 21(4):311{352, 1996. 13. C. S. Jensen, R. T. Snodgrass, and M. D. Soo. Extending existing dependency theory to temporal databases. IEEE Transactions on Knowledge and Data Engineering, 8(4):563{582, 1996. 14. C. S. Jensen, M. D. Soo, and R. T. Snodgrass. Unifying temporal models via a conceptual model. Information Systems, 19(7):513{547, 1994. 15. M. R. Klopprogge. TERM: An approach to include the time dimension in the entity-relationship model. In Proceedings of the Second International Conference on the Entity Relationship Approach, pages 477{512, Washington, DC, Oct. 1981. 16. M. R. Klopprogge and P. C. Lockemann. Modelling information preserving databases: Consequences of the concept of time. In M. Schkolnick and C. Thanos, editors, vldb, pages 399{416, Florence, Italy, 1983. 17. I. Knowledge Based Systems. SmartER - information and data modeling and database design. Technical report, Knowledge Based Systems, Inc. - Austin, USA, 1997. http://www.kbsi.com/products/smarter.html. 18. I. Logic Works. Erwin/erx. Technical report, Logic Works, Inc., 1997. http://www.logicworks.com/products/erwinerx/index.asp. 19. H. Mannila and K.-J. Raiha. The design of relational databases. Addison-Wesley, 1993. 20. P. McBrien, A. H. Selveit, and B. Wangler. An entity-relationship model extended to describe historical information. In International Conference on Information Systems and Management of Data (CISMOD'92), pages 244{260, Bangalore, India, July 1992. 21. A. Narasimhalu. A data model for object-oriented databases with temporal attributes and relationships. Technical report, National University of Singapore, 1988. 22. S. Navathe and R. Ahmed. Temporal extensions to the relational model and SQL. In Tansel et al. [25], chapter 4, pages 92{109. 23. F. I. P. S. Publication. Integration de nition for function modeling (idef1x). Technical Report 183, National Institute of Standards and Technology, Gaithersburg, Md. 20899, 1993. 24. R. T. Snodgrass. The temporal query language TQel. ACM Trans. Database Syst., 12(2):247{298, 1987. 25. A. U. Tansel et al., editors. Temporal databases: theory, design and implementations. Benjamin Cummings, 1993. 26. C. Theodoulidis, P. Loucopoulos, and B. Wangler. A conceptual modelling formalism for temporal database applications. Information Systems, 16(4):401{416, 1991.

16