Notes on SAKT’10: Bolzano colloquium on logic for temporal databases

On 16 and 17 December, the KRDB Research Centre at FUB hosted the successful SAKT’10 Symposium in Advances in KRDB Technologies that had as special theme logics for temporal databases, which was organized by Alessandro Artale from the KRDB. As the title suggest, the topics of the presentations and discussions offered various approaches to address the interaction between temporal logics and temporal databases, which I’ll try to summarise here from the notes I took. Note/caution: there are no proceedings to cross-check and to take some of the formal apparatus to illustrate some aspects more precisely, and my note-taking had its ups and downs; so, if you want to know more about the topics, then take a look at the attendees’ respective homepage and publications.

Database-oriented talks

David Toman from the University of Waterloo gave two talks, one about querying temporal databases with temporal SQL and one about data streams and temporal databases. Stream databases can be seen as an append-only temporal database where holistic/bounded synopses (views) have to be made about the glut of past data to be able to effectively manage such ever-growing databases, which can be done policy-driven and query-driven, the latter being a variant of data expiration.

Carlo Combi from the University of Verona and Pietro Sala from the University of Udine gave a joint presentation about temporal functional dependencies in databases with some rather challenging examples taken from the medical domain. It requires a DBMS to deal somehow with fixed intervals as well as moving windows, such as querying if a patient indeed received the right doses at the stipulated times in her chemotherapy treatment (i.e., constraints about the past) and ensuring constraints formulated about treatments that ought to hold in the future, such as (roughly) “a patient should be administered the same quantity of medicine x after each two weeks from the start of the treatment”, for which both a point-based and an interval-based approach was presented. How this is to be presented in a temporal conceptual model is another topic.

Jef Wijssen from Mons University considered temporal patterns (word problems) motivated by certain query answering and pondered about what constitutes a temporal conjunctive query. Mark Reynolds’ work at the University of Western Australia was about reasoning with time stamps and metric temporal logic with real numbers. Paolo Terenziani from the University of Torino reported on his ongoing work towards a unified data model for temporal databases, taking into account both valid time and transaction time, the atelic/telic distinctions (roughly: point-based and interval-based), temporally determinate/indeterminate and some other issues (“now”, granularities).

Logic talks

Roughly in-between ‘just the logic’ and ‘just databases’ was Alessandro Artale’s  presentation about temporal conceptual data modelling with simplified ER and UML Class Diagrams extended with a few temporal operators—those temporal operators that are in TDL-Lite. Vlad Ryzhikov from KRDB presented Marco Gario’s project work about trying to implement a reasoner over temporal ER, which was realized through transformations from the Temporal ER to TDL-Lite, to TFOL over Z to LTL over Z to LTL over N and CTL, the latter two handled with the NuSMV tool. It worked with bounded model checking, but for symbolic model checking there were scalability problems even for very small temporal ER models; so there is room for improvements. There was some immediate feedback from Viktor Schuppan from Fondazione Bruno Kessler where they developed NuSMV, who, in turn, talked in his presentation about the comparison of LTL satisfiability solvers. There are several such solvers that use different techniques, and it appeared that different tools are better at solving different problems, but there is not one that scores best throughout. Michel Ludwig from the University of Liverpool presented his PhD thesis work about TSPASS, a monodic temporal logic prover that builds upon SPASS 3.0.

Roman Kontchakov from Birkbeck College gave a brief overview on how to develop decidable temporal languages, augmented by his joint presenter, Vlad, who talked about TDL-Lite over natural numbers. Being logicians, they invented their own list of what such a decidable temporal language ‘needs’; it would have been nicer if they actually had developed a decidable language that demonstrably contains what is needed from a modelling perspective, such as, to handle essential and immutable parts, relation migration, or demonstrate that one can represent some Relation Ontology relation with a time component, such as the transformation-of relation.

Ian Pratt-Hartmann from the University of Manchester focused on the trials and tribulations of interval temporal logics, where he argued that one should not go the way of restricting the Allen relations but instead restrict quantification to the event-guarded case so as to maintain decidability of the language.

Discussion sessions

Aside from the questions and discussions with each presentation there were two dedicated discussion sessions, one introduced by Vlad on the temporal ER reasoning and chaired by Alessandro Artale, and the second one introduced and moderated by Franz Baader from Dresden University. In addition to the majority of KRDB members and the aforementioned presenters, the other invited attendees—Carsten Lutz from Bremen University, Angelo Montanari from the University of Udine, and Frank Wolter and Boris Konev from the University of Liverpool—also participated.

The first discussion session had as topic the interaction between logic and temporal databases, or: we have al those fancy temporal operators in the logic languages, but how can/do/should/may they translate to the database setting? Take, for instance, an evolution constraint “each employee eventually will be promoted to become a manager”, which seems to ask for the notion of possible/potential satisfiability. Or when we have branching in the future, in which way can there be (certain) query answering that, given a particular state of the database, checks if all branches (possible worlds) lead to some state x or at least some of them, versus that such a state cannot be reached anymore in any possible future state of the database. Can one view the main temporal operators in the logics as database updates in DBMSs? Should one use the CWA for reasoning/querying about the past and OWA for the future? Also, when we represent something in our ontology, and it being a realist ontology, then there is only a single path in the past, but we may revise our understanding and representation of what actually happened; what if that new branch in the past leads to an inconsistency in the system, and how can we keep track of such things (including how valid time and transaction time, whilst being distinct, still interact in data management)? Unsurprisingly, the actual official closing of the discussion was after the scheduled end of the discussion time, and continued informally afterwards.

The discussion session on the second day looked more at applications of temporal logics, such as time-stamped fact bases (ABoxes, if you wish) and how that may interact with (a)temporal TBoxes. If DL knowledge bases may be suitable for it, or perhaps it will be a part of a larger system with some temporal pre-processing before it is entered into the fact base. For the biomed-oriented reader: Franz Baader motivated it with an interesting medical informatics example about management of hospital data in conjunction with knowledge represented in SNOMED CT, having to manage quantitative and qualitative patient data about, e.g., hypertension, patient histories, and projection into the future about likely development of a particular disease, and handling rules, such as (simplified here) “if the measurements of properties x, y, and z are above 1, 2, and 3 at least three times in the past hour in patient1, then classify partient1 as having disease A”.

Overall, it was a stimulating mix of talks and a good ambience for cross-fertilization of topics, problems, and solutions. There is still plenty of research to be done.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s