InteLLigence

Research on Data and Knowledge-base Systems

Description

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.

Because Telos is a sophisticated meta-modelling language, it is currently used in the Semantic Web by Wolfgang Nejdl's group at Hannover.

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.

Related Publications

Koubarakis M., Vouros G., Chalkiadakis G., Plagianakos V., Tjortjis C., Kavallieratou E., Vrakas D., Mavridis N., Petasis G., Blekas K., Krithara A.: AI in Greece: The Case of Research on Linked Geospatial Data, AI Magazine, Vol 39, No 2, Summer 2018

Publication Type: Journal Publications [abstract] [link]

Chliaoutakis A., Zervanou K., Petrakis E.: The AMTEx Approach in the Medical Document Indexing and Retrieval Application, Data and Knowledge Engineering (DKE), Volume 68, Issue 3, March 2009, Pages 380-392.

Publication Type: Journal Publications [abstract] [file]

Siskos D.: Ontology - Based Information Retrieval in Medical Document Collections, Diploma Thesis, Department of Electronic and Computer Engineering, Technical University of Crete, Greece, July 2008. (Technical Report TR-TUC-ISL-04-2008)

Publication Type: Technical Reports [abstract] [file]

Koubarakis M.: Query Evaluation in Temporal Constraint Databases, In M. Fischer, D. Gabbay and L. Villa (eds.) Handbook of Temporal Reasoning in Artificial Intelligence. Volume 1 in the series “Foundations of Artificial Intelligence”, B. Nebel, J.Hendler and H. Kitano (eds). Elsevier Science. 2005.

Publication Type: Book Chapters [abstract]

Koubarakis M., Sellis T., Frank A., Grumbach S., Güting R., Jensen C., Lorentzos N., Manolopoulos Y., Nardelli E., Pernici B., Schek H., Scholl M., Theodoulidis B., Tryfona N.: Spatiotemporal Databases: The Chorochronos Approach, Lecture Notes in Computer Science, Vol. 2520, June 2003, Springer.

Publication Type: Books [abstract] [link]

Grumbach S., Koubarakis M., Scholl M., Rigaux P., Skiadopoulos S.: Spatiotemporal models and languages: an approach based on constraints, In M. Koubarakis, T. Sellis et. al. Spatiotemporal Databases: The Chorochronos Approach, Lecture Notes in Computer Science, Vol. 2520, June 2003, Springer.

Publication Type: Book Chapters [abstract]

Koubarakis M.: Querying Temporal Constraint Networks: A Unifying Approach, Applied Intelligence,Vol. 17, No. 3, pages 297-311, November-December 2002.

Publication Type: Journal Publications [abstract] [file]

Skiadopoulos S., Koubarakis M.: Composing Cardinal Direction Relations, Proceedings of the 7th International Symposium on Spatial and Temporal Databases (SSTD-2001), Los Angeles, California, July 12-15, 2001.

Publication Type: Conference Publications [abstract] [file]

Koubarakis M., Skiadopoulos S.: Querying temporal and spatial constraint networks in PTIME, Artificial Intelligence, Vol. 123, No. 1-2, pages 223-263, 2000.

Publication Type: Journal Publications [abstract] [file]

Koubarakis M., Skiadopoulos S.: Querying Temporal Constraint Networks in PTIME, Proceedings of AAAI-99. Orlando, Florida, July 18-22, 1999.

Publication Type: Conference Publications [abstract] [file]

Frank A., Grumbach S., Güting R., Jensen C., Koubarakis M., Lorentzos N., Manolopoulos Y., Nardelli E., Pernici B., Schek H., Scholl M., Sellis T., Theodoulidis B., Widmayer P.: Chorochronos: A Research Network for Spatiotemporal Database Systems, ACM SIGMOD Record, Vol. 28, No. 3, pages 12-21, 1999.

Publication Type: Journal Publications [abstract] [file]

Koubarakis M., Skiadopoulos S.: Tractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatio-Temporal Information In Spatio-Temporal Database Management, (Proceedings of the International Workshop STDBM'99), Lecture Notes in Computer Science, Vol. 1678, Bohlen, M.H. and Jensen, C. and Scholl, M. (eds.), pages 204-223, Springer, 1999.

Publication Type: Workshop Proceedings [abstract]

Koubarakis M., Skiadopoulos S.: Querying Indefinite Temporal and Spatial Information: A New Frontier, Proceedings of the IJCAI-99 Workshop on Hot Topics in Temporal and Spatial Reasoning, Stockholm, Sweden, August 2, 1999.

Publication Type: Workshop Proceedings [abstract] [file]

Koubarakis M., Skiadopoulos S.: Tractable Query Answering in Indefinite Constraint Databases: Basic Results and Applications to Querying Spatio-Temporal Information, In M. H. Bohlen, C.S. Jensen and M.O. Scholl, Spatio-Temporal Database Management (Proceedings of the International Workshop STDBM'99, Edinburgh, Scotland, September 1999), LNCS vol. 1678, Springer, pages 204-223.

Publication Type: Workshop Proceedings [abstract] [file]

Koubarakis M.: The Complexity of Query Evaluation in Indefinite Temporal Constraint Databases, Theoretical Computer Science, Vol. 171, pages 25-60, January 1997. Special Issue on Uncertainty in Databases and Deductive Systems, Editor: L.V.S. Lakshmanan.

Publication Type: Journal Publications [abstract] [file]

Koubarakis M.: Databases and Temporal Constraints: Semantics and Complexity, In Clifford, J. and Tuzhilin, A. (eds.), Recent Advances in Temporal Databases (Proceedings of the International Workshop on Temporal Databases, Zurich, Switzerland, September 1995), Workshops in Computing, Springer, pages 93-109.

Publication Type: Workshop Proceedings [abstract] [file]

Koubarakis M.: Database Models for Infinite and Indefinite Temporal Information, Information Systems, Vol. 19, No. 2, March 1994, pages 141-173.

Publication Type: Journal Publications [abstract] [file]

Papadias D., Frank A., Koubarakis M.: Constraint-Based Reasoning in Geographic Databases: the Case of Symbolic Arrays, Proceedings of the 2nd ICLP Workshop on Deductive Databases and Logic Programming, Santa Margherita Ligure, Italy, June 1994. Published as GMD-Studien Nr. 231, U. Geske, D. Seipel (eds.)

Publication Type: Workshop Proceedings [abstract]

Koubarakis M.: Foundations of Indefinite Constraint Databases, In A. Borning (ed.), Proceedings of the 2nd International Workshop on the Principles and Practice of Constraint Programming (PPCP'94), Lecture Notes in Computer Science vol. 874, pages 266-280, Springer Verlag, 1994.

Publication Type: Workshop Proceedings [abstract] [file]

Koubarakis M.: Representation and Querying in Temporal Databases: the Power of Temporal Constraints, Proceedings of the 9th International Conference on Data Engineering, pages 327-334, April 1993.

Publication Type: Conference Publications [abstract] [file]

Mylopoulos J., Borgida A., Jarke M., Koubarakis M.: Representing Knowledge About Information Systems in Telos, In M. Jarke (ed.), Database Application Engineering with DAIDA, Springer Verlag, 1993, pages 31-64.

Publication Type: Book Chapters [abstract]

Kramer B., Chaudhri V., Koubarakis M., Topaloglou T., Wang H., Mylopoulos J.: Implementing Telos, SIGART Bulletin, Special Issue on Implemented Knowledge Representation and Reasoning Systems, Vol. 2, No. 3, June 1991, pages 77-83.

Publication Type: Journal Publications [abstract]

Mylopoulos J., Borgida A., Jarke M., Koubarakis M.: Telos: Representing Knowledge about Information Systems, ACM Transactions on Information Systems, Vol. 8, No. 4, October 1990, pages 325-362. [gzipped postscript with no figures (sorry!)]

Publication Type: Journal Publications [abstract] [file]