Data and Knowledge-base Systems

The Knowledge Representation Language Telos

In the M.Sc. thesis of Manolis Koubarakis (University of Toronto, 1988) the knowledge representation language Telos was defined, formalized and implemented. Knowledge in Telos is represented by classes of structured objects, integrity constraints and deductive rules. Temporal knowledge can also be organized along two dimensions: history time (i.e., the time when an event happens in the world) and belief time (i.e., the time when an event is recorded by the system). Telos is based on simple primitive concepts, emphasizes uniformity of modelling (e.g., objects and their attributes have the same status) and supports higher-order concepts (e.g., meta-classes and meta-attributes can be easily defined).

Telos was originally used for the modelling of requirements arising in the early stages of information systems development. It has also been used as a general purpose object-centered knowledge representation language in several applications. The conceptual framework of Telos, described in an ACM TOIS publication by John Mylopoulos, Alex Borgida, Matthias Jarke and Manolis Koubarakis had a big impact in all research projects where it has been used. These projects include the ESPRIT projects DAIDA, ITHACA and NATURE, and several projects funded by the Canadian government. A very nice implementation of Telos is ConceptBase.

Telos is so much related to RDF/RDFS; it is a pity only the people that defined RQL and O-Telos-RDF have noticed!!!

The Scheme of Indefinite Constraint Databases

In the Ph.D. thesis of Manolis Koubarakis (National Technical University of Athens, 1994) we developed the scheme of indefinite constraint databases and concentrated on instances of this scheme where the constraints are temporal. Our work starts from the premise that an important requirement of advanced temporal applications (e.g., planning and scheduling) is the ability to deal with definite, indefinite, finite and infinite temporal information. We proposed that a combination of classical relational databases and temporal constraint networks offers a powerful framework which addresses the database needs of these applications. The main technical contributions of this Ph.D. thesis are the following:

• We studied a hierarchy of parameterized database models: ML-relational databases, L-constraint databases and indefinite L-constraint databases. The first order language L, the parameter, defines the constraint vocabulary and ML is the structure over which L-constraints are interpreted. This work is essentially an extension of the constraint database framework of Kanellakis, Kuper and Revesz to include indefinite information. The models of temporal constraint databases and indefinite temporal constraint databases were studied as instances of the last two of the above parameterized models.
• We developed quantifier elimination and decision algorithms for several theories of temporal constraints. These results go beyond what has been achieved in the area of temporal constraint networks by Dechter, van Beek, Ladkin, Meiri, Kautz and others. Because the most important theories we considered are subtheories of Presburger arithmetic (in the case of discrete time) and real addition with order (in the case of dense time), Manolis Koubarakis' results are of independent interest for the theoretical computer science community.
• We analyzed the complexity of query evaluation in temporal constraint databases and indefinite temporal constraint databases. Our analysis shows that there is no change in the worst-case data/combined complexity when we go from relational databases to temporal constraint databases (with or without indefinite information). This work complements and extends previous research by Kanellakis, Kuper, Revesz, van der Meyden, van Beek and others.

Spatial and Temporal Database Management

Our goal is to develop models, query languages and efficient implementation techniques for spatiotemporal databases. A spatiotemporal database is a database that captures the evolution over time of two kinds of data: administrative data as they are found in today's DBMS, and spatial relations (or constraints) as they are represented in current specialized systems (for example, Geographical Information Systems or Image Database Management Systems). With Spiros Skiadopoulos we have worked on models and algorithms for cardinal direction information and its use in spatial database management systems. This work was funded by the European Union's 4th Framework project CHOROCHRONOS and the Greek General Secretariat for Research and Technology.