Constraints for migrating relations over time

Migrating objects in a database is nothing new—employees become managers, MSc students PhD students and so forth—and this has been investigated and implemented widely in temporal databases. But imagine a scenario for an airline company’s passenger RDBMS and a passenger who books a flight, hence we have a relation ⟨John, AZ123⟩ ∈ Booking with John ∈ Passenger and AZ123 ∈ Flight, which is normally followed by the events that John also checks in and boards the plane afterward, i.e., ⟨John, AZ123⟩ ∈ CheckIn and then ⟨John, AZ123⟩ ∈ Boarding. While the booking relation holds even after the tuple extended to the check-in relation, i.e., ⟨John, AZ123⟩ is a member of both Booking and CheckIn relations, this is not the case for the step from check-in to boarding which causes the tuple ⟨John, AZ123⟩ to be moved from one table to another in the operational database. In addition, for any tuple that is member of the Boarding relation, we know that it must have been a member of CheckIn relation sometime earlier. Clearly, airline companies implement some code to keep track of such changes, but how to represent this in a conceptual data model?

Or take a simple change in relation between two objects can be caused by the fact that a is structurally a part of b but a gets loose so after that a becomes spatially contained in b; e.g., a component in a medical device breaks loose due to wear and tear. Then it would be nice if a fault detection system can send such a message back to control, compared to the imprecise “there’s something wrong over there”.

A related issue is keeping track of the status of the same relation. Take, for instance, the issues with subquantities with, say, a bottle of wine and pouring a subquantity of the wine into a wineglass so that this subquantity in the glass used to be—but not is—a subquantity of the wine in the bottle and one wants to maintain traceability of quantities over time. This is important especially in the food industry for food safety in the food processing chain, hence, the data management has to be able to deal with such cases adequately and transparently.

Perhaps surprisingly, there is no conceptual data modelling language that lets you model the business knowledge where relations migrate during the conceptual analysis stage.  By relation migration, I mean the change of membership of a tuple from one relation to another. Thus, relation migration is distinct from state transition diagrams that concern states of single objects, from activity diagrams that concern processes but do not explicitly consider the participating entities, and from interaction diagrams for modelling use cases. Here we focus explicitly on the migration of facts/tuples/relation instances and the corresponding temporal behaviour of fact types/relations. So, in analogy to object migration, there is a usefulness of a similar set of constraints for relations that can be called relation migration.

Alessandro Artale and I specified the basic constraints that hold for relation migration, which recently got accepted for the ORM’10 workshop co-located with the OTM conference. The paper’s [1] abstract is as follows:

Representing and reasoning over evolving objects has been investigated widely. Less attention has been devoted to the similar notion of relation migration, i.e., how tuples of a relation (ORM facts) can evolve along time. We identify different ways how a relation can change over time and give a logic-based semantics to the notion of relation migration to capture its behaviour. We also introduce the notion of lifespan of a relation and clarify the interactions between object migration and relation migration. Its use in graphical conceptual data modelling is illustrated with a minor extension to ORM2 so as to more easily communicate such constraints with domain experts.

We distinguish between evolution constraints—specifying how elements of a relation can possibly migrate to another relation—persistence constraints—specifying persistent states for a relation—and quantitative evolution constraints—specifying the exact amount of time for the relation migration to happen. In addition, one has to consider the lifespan of relations. Together, they result in 15 axioms for the evolution and persistence constraints, and 3 propositions concerning the logical implications with respect to subsumption and relation migration, relation migration vs. lifespan, and objects vs. a relation’s lifespan.

Concerning the interaction object and relation migration, we found two types, one where an object migration forces a relation to migrate, and one where a relation migration forces an object migration. For instance, take a company where, at some point in time, each employee will be promoted within the same department he or she works for (for simplicity: the employee works for exactly one department) and such that demotion does not occur. This means an object migration of type PEX (Persistent Extension) between Employee and Manager (see figure, below). This forces a relation migration of type RPEX between worksFor and manages in order to maintain consistency of the conceptual data model (see figure below).

Example of an object migration (dashed purple arrow) that forces a relation migration (dashed green arrow)

The last word has not been said yet about incorporating rigidity fully in this framework, nor tractable reasoning with relation migration, but at least the foundational aspects of relation migration have been identified and characterized formally, which already can be added to conceptual data modelling languages, as illustrated for the Object-Role Modeling language in [1].

References

[1] Keet, C.M. and Artale, A. A basic characterization of relation migration. International Workshop on Fact-Oriented Modeling (ORM’10), Crete, Greece, October 27-29, 2010. Meersman, R., Herrero, P. (Eds.), OTM Workshops, Springer, Lecture Notes in Computer Science LNCS. (to appear)