|
TITLE: Reasoning over (Temporal) Conceptual Models
PRESENTER: Alessandro Artale, http://www.inf.unibz.it/~artale, artale@inf.unibz.it
AFFILIATION:KRDB Research Centre, Faculty of Computer Science, Free University of Bozen-Bolzano, http://www.inf.unibz.it/
DATE: Friday 29th August 2008
TIME: 12:00:00
PLACE: CSE Seminar Room, Level 1, K17
ABSTRACT:
We investigate the computational complexity of reasoning over various
fragments of the Extended Entity-Relationship (EER) language including
reasoning over temporal EER diagrams.
We consider first the atemporal case including a number of constructs:
ISA between entities and relationships, disjointness and covering of
entities and relationships, cardinality constraints for entities in
relationships and their refinements as well as multiplicity
constraints for attributes. We extend the known ExpTime-completeness
result for UML class diagrams [BeCD05] and show that reasoning over
EER diagrams with ISA between relationships is ExpTime-complete even
without relationship covering. Surprisingly, reasoning becomes
NP-complete when we drop ISA between relationships (while still
allowing all types of constraints on entities). If we further omit
disjointness and covering over entities, reasoning becomes
polynomial. These last results show the usefulness on the DL-Lite
language for conceptual modeling.
We also show that reasoning in the temporal conceptual model \ERVT
that only allows Timestamping is complete for 2-\ExpTime. The
membership result is based on an embedding of the conceptual model
into the description logic S5xALCQI. Hardness is obtained by reducing
a fragment of S5xALCQI, allowing just global roles, to \ERVT.
BIOGRAPHY OF SPEAKER:
Alessandro Artale is an Assistant Professor at the Faculty of Computer
Science at the Free University of Bozen-Bolzano (Italy). He got a PhD
in Computer Science from the University of Florence in 1994.
His main research subject concerns the Class-Based knowledge
representation languages and in particular description logics,
temporal logics, automated reasoning, ontologies and conceptual
modelling. The aim is in providing formal theories and efficient
principled systems for expressing and reasoning with structured
knowledge. A particular emphasis is devoted to the formalization of
conceptual modeling tasks in domains with high semantic complexity.
His research activity has been internationally recognized being funded
by the European Community and published by various international
Journals and Conferences. In particular, he has been principal
investigator of a three years EPSRC (the British National Research
Council) project, and he is currently member of various European
funded projects. Furthermore, he is author of more then 50
international publications, chair or program committee member of
international conferences, editor of special issues, acting as referee
for the major journals and conferences.
Host:
Alfredo Gabaldon
Seminar Convenor:
Van Hai Ho
|
