KRDB Research Centre
for Knowledge and Data

KRDB PhD Students Workshop

For more information, please contact:

Lina Lubyte
lubyte at
(+39) 0471 016 226
Marijke Keet
keet at
(+39) 0471 016 128

After the workshop we will have a dinner (more information will follow soon).


Time SpeakerTitleAbstractSlides
16:00-16:25 Evgeny Kharlamov A Proof Theory for DL-Lite Abstract
16:25-16:40 Vlad Ryzhikov Complexity of Reasoning in Entity Relationship Models Abstract
16:40-16:55 Lina Lubyte Extracting Ontologies from Relational Databases Abstract
16:55-17:10 Marijke Keet Prospects for and issues with mapping the Object-Role Modeling language into DLRifd Abstract
17:10-17:30 Break
17:30-17:55 Camilo Thorne Expressing DL-Lite Ontologies with Controlled English Abstract
17:55-18:20 Paolo Dongilli From Conjunctive Queries to Text Plans Abstract
18:20-18:35 Mariano Rodriguez An Extension of DIG 2.0 for Handling Bulk Data Abstract
18:35-18:50 Christina Tziviskou Semantic Personalization of Web Portal Contents Abstract


A Proof Theory for DL-Lite.
Evgeny Kharlamov

In this work we propose an alternative approach to inference in DL-Lite, based on a reduction to reasoning in an extension of function-free Horn Logic (EHL). We develop a calculus for EHL and prove its soundness and completeness. We will also show how to achieve decidability by means of a specific strategy, and how alternative strategies can lead to improved results in specific cases. On the one hand, we will mimic the query-answering technique based on first computing a rewriting and then evaluating it. On the other hand, we discuss a strategy that allows one to anticipate the grounding of atoms, and that might lead to better performance in the case where the size of the TBox is not dominated by the size of the data.

Complexity of Reasoning in Entity Relationship Models.
Vlad Ryzhikov

In this work we investigate the complexity of reasoning over various fragments of the Extended Entity Relationship (EER) language, which include different combinations of the constructs for isa between concepts and relationships, disjointness, covering, cardinality constraints, including their refinement. Specifically, we show that reasoning over ER diagrams with I S A between relationships is EXPTIME-hard, even when we drop relationship covering. Surprisingly, when we drop also ISA between relations, reasoning becomes NP-complete. If we further remove boolean constructs, reasoning becomes polynomial. Our lower-bound results are established through direct reductions, while the upper-bounds follow from correspondences with expressive variants of the DL DL-Lite.

Extracting Ontologies from Relational Databases.
Lina Lubyte

The use of a conceptual model (or an ontology) to describe relational data sources has been proved to be extremely useful to overcome many important data access problems. However, the task of wrapping relational data sources by means of an ontology is mainly done manually. In this paper we introduce an automatic procedure for extracting a conceptual view from a relational database. The semantic mapping between the database schema and its conceptualisation is captured by associating views over the data source to elements of the extracted conceptual model. To represent the conceptual model we use an ontology language, rather that a graphical notation, in order to provide a precise formal semantics. In particular we adopt a variant of the DLR-Lite description logic because of its nice computational properties, and ability to express the mostly used modelling constraints. In order to uncover the connections between relational schema and the conceptual model, the heuristics underlying the ontology extraction process are based on ideas of standard relational schema design and normalisation. In fact, we assume that the relational source is in third normal form. Under this assumption we can formally prove that the conversion preserves the semantics of the constraints in the relational database. Therefore, there is no data loss, and the extracted model constitutes a faithful wrapper of the relational database.

Prospects for and issues with mapping the Object-Role Modeling language into DLRifd.
Marijke Keet

Object-Role modellers miss the advantages of automated reasoning over their ORM conceptual models, which could be addressed by DL reasoners. DLs are not considered user-friendly and could benefit from the easy to use ORM diagrammatic and verbalization interfaces and modelling methodologies. Relating the two would greatly expand the scope for automated reasoning with additional scenarios to improve quality of software systems. Given that none of the extant DL languages are as expressive as ORM or its successor ORM2, the ‘best-fit’ DLRifd was chosen to map the formal conceptual modelling language ORM2. For the non-mappable constraints, pointers to other DL languages are provided, which could serve as impetus for research into DL language extensions or interoperability between existing DL languages.

Expressing DL-Lite Ontologies with Controlled English.
Camilo Thorne

In this work we deal with the problem of providing natural language front-ends to databases upon which an ontology layer has been added. Specifically, we are interested in expressing ontologies formalized in Description Logics in a controlled language, i.e., a fragment of natural language tailored to compositionally translate into a knowledge representation (KR) language. As KR language we have chosen DL-Lite R , a representative of the well-known DL-Lite family, and we aim at understanding the kind of English constructs the controlled language can and cannot have to correspond to DL-Lite R . Hence, we compare the expressive power of DL-Lite R to that of various fragments of English studied by I. Pratt and A. Third, which compositionally translate into fragments of first order logic. Our analysis shows that DL-Lite R , though polynomial, is incomparable in expressive power with respect to intractable fragments of English. Interestingly, it allows one to represent a restricted form of relative clauses, which lead to intractability when used without restrictions.

From Conjunctive Queries to Text Plans.
Paolo Dongilli

In this talk I will present our efforts in terms of building a bridge between an Intelligent Query Interface and Natural Language Generation technologies. The current version of our query interface enables users to access data sources by means of an ontology representing the knowledge of a domain in a well defined formal semantics. The main challenge we are facing now is that the underlying conjunctive query is to be presented to the user in natural language. I will explain the steps needed to translate a conjunctive query into a text plan, focusing primarily on the problem of maximizing the local referential coherence of the natural language query that will be generated given the text plan. This is done by seeing this problem as a topological sort of a directed acyclic tree (the query), more precisely finding the linear ordering of the predicates that will maximize the local coherence and therefore the readability of the generated text, according to the coherence measures offered by Centering Theory.

An Extension of DIG 2.0 for Handling Bulk Data.
Mariano Rodriguez

The research community has noted the need to retrieve the instance level of an ontology from bulk data stored in external data sources (e.g., a relational database), and to delegate to the external source all aspects of the actual management of the data. To achieve this, several methodologies have been recently developed to represent and reason about what we call here Ontologies with Linking Axioms. However, existing DL reasoners cannot properly deal with such ontologies. Indeed, including the instance level in the communication with a DL reasoner can be a heavy burden on the communication line, and goes against the requirement of delegating data management to the external source. To overcome these problems, we present here an extension to the DIG 2.0 Interface that allows for the specification and management of Ontologies with Linking Axioms. The extension is a general framework which can accommodate any type of data source and linking axiom through specific implementations. We present one such specific implementation aiming at representing axioms linking RDBMS data sources to ontologies handled in DIG.

Semantic Personalization of Web Portal Contents.
Christina Tziviskou

Enriching Web applications with personalized data is of major interest for facilitating the user access to the published contents, and therefore, for guaranteeing successful user navigation. We propose a conceptual model for extracting personalized recommendations based on user profiling, ontological domain models, and semantic reasoning. The approach offers a high-level representation of the designed application based on a domain- specific metamodel for Web applications called WebML.

W3C member