Diego Calvanese

AAAI Conference 2023 Conference Paper

SMT Safety Verification of Ontology-Based Processes

• Diego Calvanese
• Alessandro Gianola
• Andrea Mazzullo
• Marco Montali

In the context of verification of data-aware processes, a formal approach based on satisfiability modulo theories (SMT) has been considered to verify parameterised safety properties. This approach requires a combination of model-theoretic notions and algorithmic techniques based on backward reachability. We introduce here Ontology-Based Processes, which are a variant of one of the most investigated models in this spectrum, namely simple artifact systems (SASs), where, instead of managing a database, we operate over a description logic (DL) ontology. We prove that when the DL is expressed in (a slight extension of) RDFS, it enjoys suitable model-theoretic properties, and that by relying on such DL we can define Ontology-Based Processes to which backward reachability can still be applied. Relying on these results we are able to show that in this novel setting, verification of safety properties is decidable in PSPACE.

IJCAI Conference 2022 Conference Paper

Verification and Monitoring for First-Order LTL with Persistence-Preserving Quantification over Finite and Infinite Traces

• Diego Calvanese
• Giuseppe De Giacomo
• Marco Montali
• Fabio Patrizi

We address the problem of model checking first-order dynamic systems where new objects can be injected in the active domain during execution. Notable examples are systems induced by a first-order action theory, e. g. , expressed in the Situation Calculus. Recent results have shown that, under the state-boundedness assumption, such systems, in spite of having a first-order representation of the state, admit decidable model checking for full first-order mu-calculus. However, interestingly, model checking remains undecidable in the case of first-order LTL (LTL-FO). In this paper, we show that in LTL-FOp, which is the fragment of LTL-FO in which quantification is over objects that persist along traces, model checking state-bounded systems becomes decidable over finite and infinite traces. We then employ this result to show how to handle monitoring of LTL-FOp properties against a trace stemming from an unknown state-bounded dynamic system, simultaneously considering the finite trace up to the current point, and all its possibly infinite future continuations.

IJCAI Conference 2020 Conference Paper

Counting Query Answers over a DL-Lite Knowledge Base

• Diego Calvanese
• Julien Corman
• Davide Lanti
• Simon Razniewski

Counting answers to a query is an operation supported by virtually all database management systems. In this paper we focus on counting answers over a Knowledge Base (KB), which may be viewed as a database enriched with background knowledge about the domain under consideration. In particular, we place our work in the context of Ontology-Mediated Query Answering/Ontology-based Data Access (OMQA/OBDA), where the language used for the ontology is a member of the DL-Lite family and the data is a (usually virtual) set of assertions. We study the data complexity of query answering, for different members of the DL-Lite family that include number restrictions, and for variants of conjunctive queries with counting that differ with respect to their shape (connected, branching, rooted). We improve upon existing results by providing PTIME and coNP lower bounds, and upper bounds in PTIME and LOGSPACE. For the LOGSPACE case, we have devised a novel query rewriting technique into first-order logic with counting.

IJCAI Conference 2019 Conference Paper

Enriching Ontology-based Data Access with Provenance

• Diego Calvanese
• Davide Lanti
• Ana Ozaki
• Rafael Penaloza
• Guohui Xiao

Ontology-based data access (OBDA) is a popular paradigm for querying heterogeneous data sources by connecting them through mappings to an ontology. In OBDA, it is often difficult to reconstruct why a tuple occurs in the answer of a query. We address this challenge by enriching OBDA with provenance semirings, taking inspiration from database theory. In particular, we investigate the problems of (i) deciding whether a provenance annotated OBDA instance entails a provenance annotated conjunctive query, and (ii) computing a polynomial representing the provenance of a query entailed by a provenance annotated OBDA instance. Differently from pure databases, in our case, these polynomials may be infinite. To regain finiteness, we consider idempotent semirings, and study the complexity in the case of DL-LiteR ontologies. We implement Task (ii) in a state-of-the-art OBDA system and show the practical feasibility of the approach through an extensive evaluation against two popular benchmarks.

TIME Conference 2019 Conference Paper

Two-Dimensional Rule Language for Querying Sensor Log Data: A Framework and Use Cases

• Sebastian Brandt 0001
• Diego Calvanese
• Elem Güzel Kalayci
• Roman Kontchakov
• Benjamin Mörzinger
• Vladislav Ryzhikov
• Guohui Xiao 0001
• Michael Zakharyaschev

Motivated by two industrial use cases that involve detecting events of interest in (asynchronous) time series from sensors in manufacturing rigs and gas turbines, we design an expressive rule language DslD equipped with interval aggregate functions (such as weighted average over a time interval), Allen’s interval relations and various metric constructs. We demonstrate how to model events in the uses cases in terms of DslD programs. We show that answering DslD queries in our use cases can be reduced to evaluating SQL queries. Our experiments with the use cases, carried out on the Apache Spark system, show that such SQL queries scale well on large real-world datasets.

IJCAI Conference 2018 Conference Paper

Ontology-Based Data Access: A Survey

• Guohui Xiao
• Diego Calvanese
• Roman Kontchakov
• Domenico Lembo
• Antonella Poggi
• Riccardo Rosati
• Michael Zakharyaschev

We present the framework of ontology-based data access, a semantic paradigm for providing a convenient and user-friendly access to data repositories, which has been actively developed and studied in the past decade. Focusing on relational data sources, we discuss the main ingredients of ontology-based data access, key theoretical results, techniques, applications and future challenges.

AAAI Conference 2016 Conference Paper

Beyond OWL 2 QL in OBDA: Rewritings and Approximations

• Elena Botoeva
• Diego Calvanese
• Valerio Santarelli
• Domenico Savo
• Alessandro Solimando
• Guohui Xiao

Ontology-based data access (OBDA) is a novel paradigm facilitating access to relational data, realized by linking data sources to an ontology by means of declarative mappings. DL-LiteR, which is the logic underpinning the W3C ontology language OWL 2 QL and the current language of choice for OBDA, has been designed with the goal of delegating query answering to the underlying database engine, and thus is restricted in expressive power. E. g. , it does not allow one to express disjunctive information, and any form of recursion on the data. The aim of this paper is to overcome these limitations of DL-LiteR, and extend OBDA to more expressive ontology languages, while still leveraging the underlying relational technology for query answering. We achieve this by relying on two well-known mechanisms, namely conservative rewriting and approximation, but significantly extend their practical impact by bringing into the picture the mapping, an essential component of OBDA. Specifically, we develop techniques to rewrite OBDA specifications with an expressive ontology to “equivalent” ones with a DL-LiteR ontology, if possible, and to approximate them otherwise. We do so by exploiting the high expressive power of the mapping layer to capture part of the domain semantics of rich ontology languages. We have implemented our techniques in the prototype system ONTOPROX, making use of the state-of-theart OBDA system ONTOP and the query answering system CLIPPER, and we have shown their feasibility and effectiveness with experiments on synthetic and real-world data.

AIJ Journal 2016 Journal Article

Knowledge base exchange: The case of OWL 2 QL

• Marcelo Arenas
• Elena Botoeva
• Diego Calvanese
• Vladislav Ryzhikov

In this article, we define and study the problem of exchanging knowledge between a source and a target knowledge base (KB), connected through mappings. Differently from the traditional database exchange setting, which considers only the exchange of data, we are interested in exchanging implicit knowledge. As representation formalism we use Description Logics (DLs), thus assuming that the source and target KBs are given as a DL TBox+ABox, while the mappings have the form of DL TBox assertions. We define a general framework of KB exchange, and study the problem of translating the knowledge in the source KB according to the mappings expressed in OWL 2 QL, the profile of the standard Web Ontology Language OWL 2 based on the description logic DL-Lite R. We develop novel game- and automata-theoretic techniques, and we provide complexity results that range from NLogSpace to ExpTime.

KR Conference 2016 Conference Paper

On First-Order Mu-Calculus over Situation Calculus Action Theories

• Diego Calvanese
• Giuseppe De Giacomo
• Marco Montali
• Fabio Patrizi

These results are concerned with verification logics that In this paper we study verification of situation calculus action theories against first-order μ-calculus with quantification across situations. Specifically, we consider μLa and μLp, the two variants of μ-calculus introduced in the literature for verification of data-aware processes. The former requires that quantification ranges over objects in the current active domain, while the latter additionally requires that objects assigned to variables persist across situations. Each of these two logics has a distinct corresponding notion of bisimulation. In spite of the differences we show that the two notions of bisimulation collapse for dynamic systems that are generic, which include all those systems specified through a situation calculus action theory. Then, by exploiting this result, we show that for bounded situation calculus action theories, μLa and μLp have exactly the same expressive power. Finally, we prove decidability of verification of μLa properties over bounded action theories, using finite faithful abstractions. Differently from the μLp case, these abstractions must depend on the number of quantified variables in the μLa formula.

EAAI Journal 2016 Journal Article

Ontology-based data integration in EPNet: Production and distribution of food during the Roman Empire

• Diego Calvanese
• Pietro Liuzzo
• Alessandro Mosca
• José Remesal
• Martin Rezk
• Guillem Rull

Semantic technologies are rapidly changing the historical research. Over the last decades, an immense amount of new quantifiable data have been accumulated, and made available in interchangeable formats, in social sciences and humanities, opening up new possibilities for solving old questions and posing new ones. This paper introduces a framework that eases the access of scholars to historical and cultural data about food production and commercial trade system during the Roman Empire, distributed across different data sources. The proposed approach relies on the Ontology-Based Data Access (OBDA) paradigm, where the different datasets are virtually integrated by a conceptual layer (an ontology) that provides to the user a clear point of access and a unified and unambiguous conceptual view.

IJCAI Conference 2016 Conference Paper

Plan Synthesis for Knowledge and Action Bases

• Diego Calvanese
• Marco Montali
• Fabio Patrizi
• Michele Stawowy

We study plan synthesis for a variant of Knowledge and Action Bases (KABs), a rich, dynamic framework, where states are description logic (DL) knowledge bases (KBs) whose extensional part is manipulated by actions that possibly introduce new objects from an infinite domain. We show that plan existence over KABs is undecidable even under severe restrictions. We then focus on state-bounded KABs, a class for which plan existence is decidable, and provide sound and complete plan synthesis algorithms, which combine techniques based on standard planning, DL query answering, and finite-state abstraction. All results hold for any DL with decidable query answering. We finally show that for lightweight DLs, plan synthesis can be compiled into standard ADL planning.

KR Conference 2016 Conference Paper

Regular Open APIs

• Diego Calvanese
• Giuseppe De Giacomo
• Maurizio Lenzerini
• Moshe Vardi

Open APIs are software intermediaries that make it possible for application programs to interact with data and processes, which can both be viewed as forms of services. In many scenarios, when one wants to obtain or publish a new service, one would like to check whether the new functionality can simply be obtained by suitably composing existing services. In this paper we study this problem by distinguishing between the two forms of services, that we call data-centric and process-centric, respectively. In the former, each API is an abstraction of a query specified on a data source, and composition amounts to building a new query by using the available APIs as views over the data. In the latter, each API abstracts a process made up by sequences of atomic actions, and composition means realizing a new process by suitably using the APIs exposed by the available services. We make the assumption that the semantics of services is specified by means of one of the most basic formalisms used in Computer Science, namely, regular languages. As a result, we get a rich analysis framework, where composition shows similarities to conformant and conditional planning. We describe composition principles and automated synthesis techniques for each of the two settings. 1 Moshe Y. Vardi Department of Computer Science Rice Univ., Houston, TX, U. S. A. vardi@cs. rice. edu

IJCAI Conference 2015 Conference Paper

Data Complexity of Query Answering in Description Logics (Extended Abstract)

• Diego Calvanese
• Giuseppe De Giacomo
• Domenico Lembo
• Maurizio Lenzerini
• Riccardo Rosati

We study the data complexity of answering conjunctive queries over Description Logic knowledge bases constituted by a TBox and an ABox. In particular, we are interested in characterizing the FOrewritability and the polynomial tractability boundaries of conjunctive query answering, depending on the expressive power of the DL used to express the knowledge base. What emerges from our complexity analysis is that the Description Logics of the DL-Lite family are essentially the maximal logics allowing for conjunctive query answering through standard database technology.

IJCAI Conference 2015 Conference Paper

Description Logic Based Dynamic Systems: Modeling, Verification, and Synthesis

• Diego Calvanese
• Giuseppe De Giacomo
• Marco Montali
• Fabio Patrizi

In this paper, we overview the recently introduced general framework of Description Logic Based Dynamic Systems, which leverages Levesque’s functional approach to model systems that evolve the extensional part of a description logic knowledge base by means of actions. This framework is parametric w. r. t. the adopted description logic and the progression mechanism. In this setting, we discuss verification and adversarial synthesis for specifications expressed in a variant of first-order µ-calculus, with a controlled form of quantification across successive states and present key decidability results under the natural assumption of state-boundedness.

IJCAI Conference 2015 Conference Paper

On the Undecidability of the Situation Calculus Extended with Description Logic Ontologies

• Diego Calvanese
• Giuseppe De Giacomo
• Mikhail Soutchanski

In this paper we investigate situation calculus action theories extended with ontologies, expressed as description logics TBoxes that act as state constraints. We show that this combination, while natural and desirable, is particularly problematic: it leads to undecidability of the simplest form of reasoning, namely satisfiability, even for the simplest kinds of description logics and the simplest kind of situation calculus action theories.

IJCAI Conference 2015 Conference Paper

Verification of Generalized Inconsistency-Aware Knowledge and Action Bases

• Diego Calvanese
• Marco Montali
• Ario Santoso

Knowledge and Action Bases (KABs) have been put forward as a semantically rich representation of a domain, using a DL KB to account for its static aspects, and actions to evolve its extensional part over time, possibly introducing new objects. Recently, KABs have been extended to manage inconsistency, with ad-hoc verification techniques geared towards specific semantics. This work provides a twofold contribution along this line of research. On the one hand, we enrich KABs with a high-level, compact action language inspired by Golog, obtaining so called Golog-KABs (GKABs). On the other hand, we introduce a parametric execution semantics for GKABs, so as to elegantly accomodate a plethora of inconsistency-aware semantics based on the notion of repair. We then provide several reductions for the verification of sophisticated first-order temporal properties over inconsistency-aware GKABs, and show that it can be addressed using known techniques, developed for standard KABs.

AAAI Conference 2015 Conference Paper

Verification of Relational Multiagent Systems with Data Types

• Diego Calvanese
• Giorgio Delzanno
• Marco Montali

We study the extension of relational multiagent systems (RMASs), where agents manipulate full-fledged relational databases, with data types and facets equipped with domainspecific, rigid relations (such as total orders). Specifically, we focus on design-time verification of RMASs against rich firstorder temporal properties expressed in a variant of first-order µ-calculus with quantification across states. We build on previous decidability results under the state-bounded assumption, i. e. , in each single state only a bounded number of data objects is stored in the agent databases, while unboundedly many can be encountered over time. We recast this condition, showing decidability in presence of dense, linear orders, and facets defined on top of them. Our approach is based on the construction of a finite-state, sound and complete abstraction of the original system, in which dense linear orders are reformulated as non-rigid relations working on the active domain of the system only. We also show undecidability when including a data type equipped with the successor relation.

AAAI Conference 2014 Conference Paper

Capturing Relational Schemas and Functional Dependencies in RDFS

• Diego Calvanese
• Wolfgang Fischl
• Reinhard Pichler
• Emanuel Sallinger
• Mantas Simkus

Mapping relational data to RDF is an important task for the development of the Semantic Web. To this end, the W3C has recently released a Recommendation for the so-called direct mapping of relational data to RDF. In this work, we propose an enrichment of the direct mapping to make it more faithful by transferring also semantic information present in the relational schema from the relational world to the RDF world. We thus introduce expressive identification constraints to capture functional dependencies and define an RDF Normal Form, which precisely captures the classical Boyce-Codd Normal Form of relational schemas.

AAAI Conference 2014 Conference Paper

Managing Change in Graph-Structured Data Using Description Logics

• Shqiponja Ahmetaj
• Diego Calvanese
• Magdalena Ortiz
• Mantas Simkus

In this paper, we consider the setting of graph-structured data that evolves as a result of operations carried out by users or applications. We study different reasoning problems, which range from ensuring the satisfaction of a given set of integrity constraints after a given sequence of updates, to deciding the (non-)existence of a sequence of actions that would take the data to an (un)desirable state, starting either from a specific data instance or from an incomplete description of it. We consider an action language in which actions are finite sequences of conditional insertions and deletions of nodes and labels, and use Description Logics for describing integrity constraints and (partial) states of the data. We then formalize the above data management problems as a static verification problem and several planning problems. We provide algorithms and tight complexity bounds for the formalized problems, both for an expressive DL and for a variant of DL-Lite.

KR Conference 2014 Conference Paper

Nested Regular Path Queries in Description Logics

• Meghyn Bienvenu
• Diego Calvanese
• Magdalena Ortiz
• Mantas Simkus

Institute of Information Systems Vienna Univ. of Technology, Austria it is typically assumed that the data is incomplete and additional domain knowledge is provided by the DL ontology (or TBox). Hence query answering amounts to the more complex task of computing certain answers, i. e., those answers that are obtained from all databases that both contain the explicit facts in the ABox and satisfy the TBox constraints. This difference has driven research in different directions. In databases, expressive query languages for querying graph-structured data have been studied, which are based on the requirement of relating objects by flexibly navigating the data. The main querying mechanism that has been considered for this purpose is that of one-way and two-way regular path queries (RPQs and 2RPQs) (Cruz, Mendelzon, and Wood 1987; Calvanese et al. 2003), which are queries returning pairs of objects related by a path whose sequence of edge labels belongs to a regular language over the (binary) database relations and their inverses. Conjunctive 2RPQs (C2RPQs) (Calvanese et al. 2000) are a significant extension of such queries that add to the navigational ability the possibility of expressing arbitrary selections, projections, and joins over objects related by 2RPQs, in line with conjunctive queries (CQs) over relational databases. Two-way RPQs are present in the property paths in SPARQL 1. 1 (Harris and Seaborne 2013), the new standard RDF query language, and in the XML query language XPath (Berglund and others 2010). An additional construct that is present in XPath is the possibility of using existential test operators, also known as nesting, to express sophisticated conditions along navigation paths. When an existential test hEi is used in a 2RPQ E 0, there will be objects along the main navigation path for E 0 that match positions of E 0 where hEi appears; such objects are required to be the origin of a path conforming to the (nested) 2RPQ E. It is important to notice that existential tests in general cannot be captured even by C2RPQs, e. g., when tests appear within a transitive closure of an RPQ. Hence, adding nesting effectively increases the expressive power of 2RPQs and of C2RPQs. In the DL community, query answering has been investigated extensively for a wide range of DLs, with much of the work devoted to CQs. With regards to the complexity of query answering, attention has been paid on the one hand to combined complexity, i. e., the complexity measured considering as input both the query and the DL knowledge base (constituted by TBox and ABox), and on the other Two-way regular path queries (2RPQs) have received increased attention recently due to their ability to relate pairs of objects by flexibly navigating graph-structured data. They are present in property paths in SPARQL 1. 1, the new standard RDF query language, and in the XML query language XPath. In line with XPath, we consider the extension of 2RPQs with nesting, which allows one to require that objects along a path satisfy complex conditions, in turn expressed through (nested) 2RPQs. We study the computational complexity of answering nested 2RPQs and conjunctions thereof (CN2RPQs) in the presence of domain knowledge expressed in description logics (DLs). We establish tight complexity bounds in data and combined complexity for a variety of DLs, ranging from lightweight DLs (DL-Lite, EL) up to highly expressive ones. Interestingly, we are able to show that adding nesting to (C)2RPQs does not affect worst-case data complexity of query answering for any of the considered DLs. However, in the case of lightweight DLs, adding nesting to 2RPQs leads to a surprising jump in combined complexity, from P-complete to E XP-complete. 1 Magdalena Ortiz Mantas Šimkus

JELIA Conference 2014 Invited Paper

Query Answering over Description Logic Ontologies

• Diego Calvanese

Abstract Description Logics (DLs) provide the formal foundation for ontology languages, and they have been advocated as formalisms for modeling the domain of interest in various settings, including the Semantic Web, data and information integration, and ontology-based data access. An important requirement there is the ability to answer complex database-like queries, while taking into account both extensional and intensional domain knowledge. The task of answering queries has been investigated intensively in the last years for a variety of DLs, and considering both data complexity, i. e. , the complexity measured in the size of the extensional information only, and combined complexity. On the one hand, it has been shown to be in general (exponentially) more difficult than the standard reasoning tasks of concept satisfiability and subsumption; on the other hand a broad range of techniques have been developed. We overview here some of the key techniques developed in the last years for query answering over DL ontologies, ranging from rewriting based approaches for lightweight DLs, to tableaux algorithms, and techniques based on automata on infinite trees for very expressive DLs. The associated results, accompanied by matching lower bounds, have contributed to shaping the computational complexity picture for ontology-based query answering.

KR Conference 2014 Conference Paper

State-Boundedness in Data-Aware Dynamic Systems

• Babak Bagheri Hariri
• Diego Calvanese
• Marco Montali
• Alin Deutsch

verification turns out to be undecidable even for propositional reachability properties (Deutsch et al. 2009; Belardinelli, Lomuscio, and Patrizi 2012; Bagheri Hariri et al. 2013b; 2013a). To mitigate this problem, an extensive amount of research has been devoted to find suitable classes of data-aware dynamic systems for which verification of first-order temporal properties becomes decidable. In particular, a plethora of recent works has shown that verification of data-aware dynamic systems working over unboundedly many data is decidable even for very rich temporal logics, provided that the system is state-bounded. For example, Belardinelli, Lomuscio, and Patrizi (2012) show decidability of verification of state-bounded (there called b-bounded) artifact centric multiagent systems (ACMASs) for a first-order, epistemic variant of CTL, with active domain quantification that applies across time points. Bagheri Hariri et al. (2013b) give a key decidability result for the verification of state-bounded Data-Centric Dynamic Systems (DCDSs) against a first-order variant of the µ-calculus with a limited form of quantification across time. Within the research line of reasoning about actions, De Giacomo, Lesperance, and Patrizi (2012) show that (state-)bounded Situation Calculus theories can be verified against a first-order variant of the µ-calculus, without quantification across states. Notably, in all these cases stateboundedness guarantees the existence of a faithful (sound and complete) finite-state abstraction of the system, paving the way for the application of standard model checking tools. Verification of dynamic systems that manipulate data, stored in a database or ontology, has lately received increasing attention. A plethora of recent works has shown that verification of systems working over unboundedly many data is decidable even for very rich temporal properties, provided that the system is state-bounded. This condition requires the existence of an overall bound on the amount of data stored in each single state along the system evolution. In general, checking stateboundedness is undecidable. An open question is whether it is possible to isolate significant classes of dynamic systems for which state-boundedness is decidable. In this paper we provide a strong negative answer, by resorting to a novel connection with variants of Petri nets. In particular, we show undecidability for systems whose data component contains unary relations only, and whose action component queries and updates such relations in a very limited way. To contrast this result, we propose interesting relaxations of the sufficient conditions proposed in the concrete setting of Data-Centric Dynamic Systems, building on recent results on chase termination for tuple-generating dependencies.

JELIA Conference 2014 Conference Paper

Verification of Context-Sensitive Knowledge and Action Bases

• Diego Calvanese
• Ismail Ilkan Ceylan
• Marco Montali
• Ario Santoso

Abstract Knowledge and Action Bases (KABs) have been recently proposed as a formal framework to capture the dynamics of systems which manipulate Description Logic (DL) Knowledge Bases (KBs) through action execution. In this work, we enrich the KAB setting with contextual information, making use of different context dimensions. On the one hand, context is determined by the environment using context-changing actions that make use of the current state of the KB and the current context. On the other hand, it affects the set of TBox assertions that are relevant at each time point, and that have to be considered when processing queries posed over the KAB. Here we extend to our enriched setting the results on verification of rich temporal properties expressed in μ -calculus, which had been established for standard KABs. Specifically, we show that under a run-boundedness condition, verification stays decidable and does not incur in any additional cost in terms of worst-case complexity. We also show how to adapt syntactic conditions ensuring run-boundedness so as to account for contextual information, taking into account context-dependent activation of TBox assertions.

AIJ Journal 2013 Journal Article

Data complexity of query answering in description logics

• Diego Calvanese
• Giuseppe De Giacomo
• Domenico Lembo
• Maurizio Lenzerini
• Riccardo Rosati

In this paper we study data complexity of answering conjunctive queries over description logic (DL) knowledge bases constituted by a TBox and an ABox. In particular, we are interested in characterizing the FOL-rewritability and the polynomial tractability boundaries of conjunctive query answering, depending on the expressive power of the DL used to express the knowledge base. FOL-rewritability means that query answering can be reduced to evaluating queries over the database corresponding to the ABox. Since first-order queries can be expressed in SQL, the importance of FOL-rewritability is that, when query answering enjoys this property, we can take advantage of Relational Data Base Management System (RDBMS) techniques for both representing data, i. e. , ABox assertions, and answering queries via reformulation into SQL. What emerges from our complexity analysis is that the description logics of the DL-Lite family are essentially the maximal logics allowing for conjunctive query answering through standard database technology. In this sense, they are the first description logics specifically tailored for effective query answering over very large ABoxes.

IJCAI Conference 2013 Conference Paper

Exchanging OWL 2 QL Knowledge Bases

• Marcelo Arenas
• Elena Botoeva
• Diego Calvanese
• Vladislav Ryzhikov

Knowledge base exchange is an important problem in the area of data exchange and knowledge representation, where one is interested in exchanging information between a source and a target knowledge base connected through a mapping. In this paper, we study this fundamental problem for knowledge bases and mappings expressed in OWL 2 QL, the profile of OWL 2 based on the description logic DL-LiteR. More specifically, we consider the problem of computing universal solutions, identified as one of the most desirable translations to be materialized, and the problem of computing UCQrepresentations, which optimally capture in a target TBox the information that can be extracted from a source TBox and a mapping by means of unions of conjunctive queries. For the former we provide a novel automata-theoretic technique, and complexity results that range from NP to EXPTIME, while for the latter we show NLOGSPACE-completeness.

IJCAI Conference 2013 Conference Paper

Verification of Inconsistency-Aware Knowledge and Action Bases

• Diego Calvanese
• Evgeny Kharlamov
• Marco Montali
• Ario Santoso
• Dmitriy Zheleznyakov

Description Logic Knowledge and Action Bases (KABs) have been recently introduced as a mechanism that provides a semantically rich representation of the information on the domain of interest in terms of a DL KB and a set of actions to change such information over time, possibly introducing new objects. In this setting, decidability of verification of sophisticated temporal properties over KABs, expressed in a variant of first-order µcalculus, has been shown. However, the established framework treats inconsistency in a simplistic way, by rejecting inconsistent states produced through action execution. We address this problem by showing how inconsistency handling based on the notion of repairs can be integrated into KABs, resorting to inconsistency-tolerant semantics. In this setting, we establish decidability and complexity of verification.

KR Conference 2012 Short Paper

Exchanging Description Logic Knowledge Bases

• Marcelo Arenas
• Elena Botoeva
• Diego Calvanese
• Vladislav Ryzhikov
• Evgeny Sherkhonov

mappings are sets of DL inclusions. In such a setting, in order to minimize the exchange (and hence transfer and materialization) of explicit (i. e., ABox) information, we are interested in computing translations, from now on referred to as solutions, that contain as much implicit knowledge as possible. This leads us to define the novel notion of representability, which helps us in understanding the capacity of solutions to transfer implicit knowledge. Checking representability and computing a representation of a source TBox under a mapping turn out to be crucial problems in the context of knowledge base exchange. Furthermore, we argue that the right notion of solution, on which to base our investigations, should not be the standard one based on the correspondence between models of source and target KBs. Indeed, we show that such solutions present severe limitations since, on the one hand, they do not allow for the use of implicit target information to represent implicit source information, and on the other hand, they may lead to exponentially large target ABoxes. To overcome these drawbacks, we introduce the weaker notion of Q-solution, for a query language Q, which is based on the correspondence between answers to queries in Q over source and target KBs. Notice that such a notion, though weaker, is in line with the objective of (data and) knowledge base exchange of providing in the target sufficient information to answer queries in Q that could also be posed over the source. We then develop results and techniques for KB exchange and for the Q-representability problem in the case where Q are unions of conjunctive queries (UCQs), and where KBs are expressed in DL-LiteRDFS, a member of the DL-Lite family (Calvanese et al. 2007) that corresponds to the FOL fragment of RDFS (Brickley and Guha 2004), the widely adopted standard Semantic Web language. In this paper, we study the problem of exchanging knowledge between a source and a target knowledge base (KB), connected through mappings. Differently from the traditional database exchange setting, which considers only the exchange of data, we are interested in exchanging implicit knowledge. As representation formalism we use Description Logics (DLs), thus assuming that the source and target KBs are given as a DL TBox+ABox, while the mappings have the form of DL TBox assertions. We study the problem of translating the knowledge in the source KB according to these mappings. We define a general framework of KB exchange, and address the problems of representing implicit source information in the target, and of computing different kinds of solutions, i. e., target KBs with specified properties, given a source KB and a mapping. We develop first results and study the complexity of KB exchange for DL-LiteRDFS, a DL corresponding to the FOL fragment of RDFS, and for DL-LiteR.

KR Conference 2012 Conference Paper

High Performance Query Answering over DL-Lite Ontologies

• Mariano Rodriguez-Muro
• Diego Calvanese

Current techniques for query answering over DL-Lite ontologies have severe limitations in practice, since they either produce complex queries that are inefficient during execution, or require expensive data pre-processing. In light of this, we present two complementary sets of results that aim at improving the overall peformance of query answering systems. We show how to create ABox repositories that are complete w. r. t. a significant portion of DL-Lite TBoxes, including those expressed in RDFS, but where the data is not explicitly expanded. Second, we show how to characterize ABox completeness by means of dependencies, and how to use these and equivalence to optimize DL-Lite TBoxes. These results allow us to reduce the cost of query rewriting, often dramatically, and to generate highly efficient queries. We have implemented a novel system for query answering over DL-Lite ontologies that incorporates these techniques, and we present a series of data-intensive evaluations that show their effectiveness.

ECAI Conference 2012 Conference Paper

Introducing Datatypes in DL-Lite

• Ognjen Savkovic
• Diego Calvanese

In Description Logics (DLs) and in the ontology-based data access (OBDA) scenario, the use of actual datatypes (such as those adopted in DBMSs) has received only limited attention, although datatypes, with their predefined semantics, might have a substantial impact on the computational complexity of inference in ontology systems. In this work we aim at overcoming these limitations, and study the impact of adding datatypes to the OBDA scenario. To this aim, we introduce a language for datatypes and we define the notion of a datatype hierarchy, constituted by a set of datatypes that depend on each other. We classify hierarchies in three classes according to their distinguishing properties, and we establish a theoretical framework for datatypes in the OBDA scenario, based on three major components: a DL, a class of datatype hierarchies, and a query language. We establish the computational complexity of query answering for various significant instantiations of this framework, as ranging from FOL-rewritable to coNP in data complexity.

KR Conference 2012 Short Paper

The Complexity of Explaining Negative Query Answers in DL-Lite

• Diego Calvanese
• Magdalena Ortiz
• Mantas Simkus
• Giorgio Stefanoni

In order to meet usability requirements, most logic-based applications provide explanation facilities for reasoning services. This holds also for DLs, where research has focused on the explanation of both TBox reasoning and, more recently, query answering. Besides explaining the presence of a tuple in a query answer, it is important to explain also why a given tuple is missing. We address the latter problem for (conjunctive) query answering over DL-Lite ontologies, by adopting abductive reasoning, that is, we look for additions to the ABox that force a given tuple to be in the result. As reasoning tasks we consider existence and recognition of an explanation, and relevance and necessity of a certain assertion for an explanation. We characterize the computational complexity of these problems for subset minimal and cardinality minimal explanations. For this reason, we formalize the problem of explaining the absence of a tuple in the context of query answering over DL ontologies. We adopt abductive reasoning [Eiter and Gottlob, 1995; Klarman, Endriss, and Schlobach, 2011], that is, we consider which additions need to be made to the ABox to force the given tuple to be in the result. More precisely, given a TBox T, an ABox A, and a query q, an explanation for a given tuple ~c is a new ABox E such that the answer to q over hT, A ∪ Ei contains ~c. An important aspect in explanations is to provide users with explanations that are simple to understand and free of redundancy, hence as small as possible. To address this requirement, we study various restrictions on explanations, in particular, we focus on subset minimal and cardinality minimal ones. We consider standard decision problems associated to logic-based abduction: (i) existence of an explanation; (ii) recognition of a given ABox as being an explanation; (iii) relevance and (iv) necessity of an ABox assertion, i. e., whether it occurs in some or all explanations. Additionally, it is important to allow one to restrict the signature of explanations. This can be used to consider only solutions that do not extend the ABox vocabulary: an important property in the context of accessing relational databases through ontologies, where database instances are defined over a small, fixed, vocabulary, and the terminological component is used to enrich that vocabulary. The idea of restricting the explanation signature is an adaptation of a concept introduced in [Baader et al., 2010], which studies among others the CQ-emptiness problem. That is, given a query q

ECAI Conference 2012 Conference Paper

Verification of Description Logic Knowledge and Action Bases

• Babak Bagheri Hariri
• Diego Calvanese
• Giuseppe De Giacomo
• Riccardo De Masellis
• Paolo Felli
• Marco Montali

We introduce description logic (DL) Knowledge and Action Bases (KAB), a mechanism that provides both a semantically rich representation of the information on the domain of interest in terms of a DL KB and a set of actions to change such information over time, possibly introducing new objects. We resort to a variant of DL-Lite where UNA is not enforced and where equality between objects may be asserted and inferred. Actions are specified as sets of conditional effects, where conditions are based on epistemic queries over the KB (TBox and ABox), and effects are expressed in terms of new ABoxes. We address the verification of temporal properties expressed in a variant of first-order μ -calculus where a controlled form of quantification across states is allowed. Notably, we show decidability of verification, under a suitable restriction inspired by the notion of weak acyclicity in data exchange.

IJCAI Conference 2011 Conference Paper

A Practical Automata-Based Technique for Reasoning in Expressive Description Logics

• Diego Calvanese
• Domenico Carbotta
• Magdalena Ortiz

In this work we describe the theoretical foundations and the implementation of a new automata-based technique for reasoning over expressive Description Logics that is worst-case optimal and lends itself to an efficient implementation. In order to show the feasibility of the approach, we have realized a working prototype of a reasoner based upon these techniques. An experimental evaluation of this prototype shows encouraging results.

IJCAI Conference 2011 Conference Paper

Containment of Regular Path Queries under Description Logic Constraints

• Diego Calvanese
• Magdalena Ortiz
• Mantas Simkus

Query containment has been studied extensively in KR and databases, for different kinds of query languages and domain constraints. We address the longstanding open problem of containment under expressive description logic (DL) constraints for two-way regular path queries (2RPQs) and their conjunctions, which generalize conjunctive queries with the ability to express regular navigation. We show that, surprisingly, functionality constraints alone make containment of 2RPQs already ExpTime-hard. By employing automata-theoretic techniques, we also provide a matching upper bound that extends to very expressive DL constraints. For conjunctive 2RPQs we prove a further exponential jump in complexity, and provide again a matching upper bound for expressive DLs. Our techniques provide also a solution to the problem of query entailment over DL knowledge bases in which individuals in the ABox may be related through regular role-paths.

AAAI Conference 2010 Conference Paper

Node Selection Query Languages for Trees

• Diego Calvanese
• Giuseppe De Giacomo
• Maurizio Lenzerini
• Moshe Vardi

The study of node-selection query languages for (finite) trees has been a major topic in the recent research on query languages for Web documents. On one hand, there has been an extensive study of XPath and its various extensions. On the other hand, query languages based on classical logics, such as first-order logic (FO) or monadic second-order logic (MSO), have been considered. Results in this area typically relate an Xpath-based language to a classical logic. What has yet to emerge is an XPath-related language that is expressive as MSO, and at the same time enjoys the computational properties of XPath, which are linear query evaluation and exponential query-containment test. In this paper we propose µXPath, which is the alternation-free fragment of XPath extended with fixpoint operators. Using two-way alternating automata, we show that this language does combine desired expressiveness and computational properties, placing it as an attractive candidate as the definite query language for trees.

IJCAI Conference 2009 Conference Paper

• Diego Calvanese
• Thomas Eiter
• Magdalena Ortiz

Reasoning over complex queries in the DLs underlying OWL 2 is of importance in several application domains. We provide decidability and (tight) upper bounds for the problem of checking entailment and containment of positive regular path queries under various combinations of constructs used in such expressive DLs; specifically: regular expressions and (safe) Booleans over roles, and allowing for the combination of any two constructs among inverse roles, qualified number restrictions, and nominals. Our results carry over also to the DLs of the SR family, and thus have a direct impact on OWL 2.

KR Conference 2008 Conference Paper

Path-Based Identification Constraints in Description Logics

• Diego Calvanese
• Giuseppe De Giacomo
• Domenico Lembo
• Maurizio Lenzerini
• Riccardo Rosati

In spite of the importance of identification mechanisms in ontology engineering, the Description Logics at the basis of current reasoners do not include modeling features for expressing identification constraints. In this paper, we consider a powerful class of identification constraints, which allow for using roles, inverses, and paths, thus capturing sophisticated forms of identifications often needed in real-world applications. We show that, when used with no limitations, such path-based identification constraints are problematic with respect to effectiveness/efficiency of reasoning. We then propose a restricted form of these constraints, called local, requiring that at least one of the component paths of the concept identifier is a direct property of the concept. We argue that such a restriction is not a severe limitation in practice, and we show that local path-based identification constraints do not increase the complexity of reasoning both in very expressive Description Logics and in the tractable DL-Lite family.

KR Conference 2008 Conference Paper

View-Based Query Answering over Description Logic Ontologies

• Diego Calvanese
• Giuseppe De Giacomo
• Maurizio Lenzerini
• Riccardo Rosati

View-based query answering is the problem of answering a query based only on the answers precomputed for a set of views. While this problem has been widely investigated in databases, it is largely unexplored in the context of Description Logic ontologies. Differently from traditional databases, Description Logics may express several forms of incomplete information, and this poses challenging problems in characterizing the semantics of views. In this paper, we first present a general framework for view-based query answering, where we address the above semantical problems by defining a spectrum of notions of view-based query answering over ontologies, all based on the idea that the precomputed answers to views are the certain answers to the corresponding queries. We also relate such notions to relevant issues in ontology management, in particular ontology access authorization. Then, we provide decidability results, algorithms, and data complexity characterizations for view-based query answering in several Description Logics, ranging from the DL-Lite family to very expressive Description Logics.

IJCAI Conference 2007 Conference Paper

• Diego Calvanese
• Giuseppe De Giacomo
• Domenico Lembo
• Maurizio Lenzerini
• Riccardo Rosati

Querying Description Logic knowledge bases has received great attention in the last years. In such a problem, the need of coping with incomplete information is the distinguishing feature with respect to querying databases. Due to this feature, we have to deal with two conflicting needs: on the one hand, we would like to query the knowledge base with sophisticated mechanisms provided by full first-order logic (FOL); on the other hand, the presence of incomplete information makes query answering a much more difficult task than in databases. In this paper we advocate the use of a nonmonotonic epistemic FOL query language as a means for expressing sophisticated queries over Description Logic knowledge bases. We show that through a controlled use of the epistemic operator, resulting in the language called EQL-Lite, we are able to formulate full FOL queries over Description Logic knowledge bases, while keeping computational complexity of query answering under control. In particular, we show that EQL-Lite queries over DL-Lite knowledge bases are FOL reducible (i. e. , compilable into SQL) and hence can be answered in LOGSPACE through standard database technologies.

AAAI Conference 2007 Conference Paper

Answering Regular Path Queries in Expressive Description Logics: An Automata-Theoretic Approach

• Diego Calvanese

Expressive Description Logics (DLs) have been advocated as formalisms for modeling the domain of interest in various application areas. An important requirement is the ability to answer complex queries beyond instance retrieval, taking into account constraints expressed in a knowledge base. We consider this task for positive existential path queries (which generalize conjunctive queries and unions thereof), whose atoms are regular expressions over the roles (and concepts) of a knowledge base in the expressive DL ALCQIbreg. Using techniques based on two-way tree-automata, we first provide an elegant characterization of TBox and ABox reasoning, which gives us also a tight EXPTIME bound. We then prove decidability (more precisely, a 2EXPTIME upper bound) of query answering, thus significantly pushing the decidability frontier, both with respect to the query language and the considered DL. We also show that query answering is EXP- SPACE-hard already in rather restricted settings.

TCS Journal 2007 Journal Article

View-based query processing: On the relationship between rewriting, answering and losslessness

• Diego Calvanese
• Giuseppe De Giacomo
• Maurizio Lenzerini
• Moshe Y. Vardi

As a result of the extensive research in view-based query processing, three notions have been identified as fundamental, namely rewriting, answering, and losslessness. Answering amounts to computing the tuples satisfying the query in all databases consistent with the views. Rewriting consists in first reformulating the query in terms of the views and then evaluating the rewriting over the view extensions. Losslessness holds if we can answer the query by solely relying on the content of the views. While the mutual relationship between these three notions is easy to identify in the case of conjunctive queries, the terrain of notions gets considerably more complicated going beyond such a query class. In this paper, we revisit the notions of answering, rewriting, and losslessness and clarify their relationship in the setting of semistructured databases, and in particular for the basic query class in this setting, i. e. , two-way regular path queries. Our first result is a clean explanation of the relationship between answering and rewriting, in which we characterize rewriting as a “linear approximation” of query answering. We show that applying this linear approximation to the constraint-satisfaction framework yields an elegant automata-theoretic approach to query rewriting. As for losslessness, we show that there are indeed two distinct interpretations for this notion, namely with respect to answering, and with respect to rewriting. We also show that the constraint-theoretic approach and the automata-theoretic approach can be combined to give algorithmic characterization of the various facets of losslessness. Finally, we deal with the problem of coping with loss, by considering mechanisms aimed at explaining lossiness to the user.

KR Conference 2006 Conference Paper

Data Complexity of Query Answering in Description Logics

• Diego Calvanese
• Giuseppe De Giacomo
• Domenico Lembo
• Maurizio Lenzerini
• Riccardo Rosati

In this paper we study data complexity of answering conjunctive queries over Description Logic knowledge bases constituted by an ABox and a TBox. In particular, we are interested in characterizing the FOL-reducibility and the polynomial tractability boundaries of conjunctive query answering, depending on the expressive power of the Description Logic used to specify the knowledge base. FOL-reducibility means that query answering can be reduced to evaluating queries over the database corresponding to the ABox. Since first-order queries can be expressed in SQL, the importance of FOL-reducibility is that, when query answering enjoys this property, we can take advantage of Data Base Management System (DBMS) techniques for both representing data, i. e., ABox assertions, and answering queries via reformulation into SQL. What emerges from our complexity analysis is that the Description Logics of the DL-Lite family are the maximal logics allowing conjunctive query answering through standard database technology. In this sense, they are the first Description Logics specifically tailored for effective query answering over very large ABoxes.

TCS Journal 2005 Journal Article

Decidable containment of recursive queries

• Diego Calvanese
• Giuseppe De Giacomo
• Moshe Y. Vardi

One of the most important reasoning tasks on queries is checking containment, i. e. , verifying whether one query yields necessarily a subset of the result of another one. Query containment is crucial in several contexts, such as query optimization, query reformulation, knowledge-base verification, information integration, integrity checking, and cooperative answering. Containment is undecidable in general for Datalog, the fundamental language for expressing recursive queries. On the other hand, it is known that containment between monadic Datalog queries and between Datalog queries and unions of conjunctive queries are decidable. It is also known that containment between unions of conjunctive two-way regular path queries, which are queries used in the context of semistructured data models containing a limited form of recursion in the form of transitive closure, is decidable. In this paper, we combine the automata-theoretic techniques at the base of these two decidability results to show that containment of Datalog in union of conjunctive two-way regular path queries is decidable in 2EXPTIME. By sharpening a known lower bound result for containment of Datalog in union of conjunctive queries we show also a matching lower bound.

AAAI Conference 2005 Conference Paper

DL-Lite: Tractable Description Logics for Ontologies

• Diego Calvanese
• Domenico Lembo

We propose a new Description Logic, called DL-Lite, specifically tailored to capture basic ontology languages, while keeping low complexity of reasoning. Reasoning here means not only computing subsumption between concepts, and checking satisfiability of the whole knowledge base, but also answering complex queries (in particular, conjunctive queries) over the set of instances maintained in secondary storage. We show that in DL-Lite the usual DL reasoning tasks are polynomial in the size of the TBox, and query answering is polynomial in the size of the ABox (i. e. , in data complexity). To the best of our knowledge, this is the first result of polynomial data complexity for query answering over DL knowledge bases. A notable feature of our logic is to allow for a separation between TBox and ABox reasoning during query evaluation: the part of the process requiring TBox reasoning is independent of the ABox, and the part of the process requiring access to the ABox can be carried out by an SQL engine, thus taking advantage of the query optimization strategies provided by current DBMSs.

AIJ Journal 2005 Journal Article

Reasoning on UML class diagrams

• Daniela Berardi
• Diego Calvanese
• Giuseppe De Giacomo

UML is the de-facto standard formalism for software design and analysis. To support the design of large-scale industrial applications, sophisticated CASE tools are available on the market, that provide a user-friendly environment for editing, storing, and accessing multiple UML diagrams. It would be highly desirable to equip such CASE tools with automated reasoning capabilities, such as those studied in Artificial Intelligence and, in particular, in Knowledge Representation and Reasoning. Such capabilities would allow to automatically detect relevant formal properties of UML diagrams, such as inconsistencies or redundancies. With regard to this issue, we consider UML class diagrams, which are one of the most important components of UML, and we address the problem of reasoning on such diagrams. We resort to several results developed in the field of Knowledge Representation and Reasoning, regarding Description Logics (DLs), a family of logics that admit decidable reasoning procedures. Our first contribution is to show that reasoning on UML class diagrams is EXPTIME-hard, even under restrictive assumptions; we prove this result by showing a polynomial reduction from reasoning in DLs. The second contribution consists in establishing EXPTIME-membership of reasoning on UML class diagrams, provided that the use of arbitrary OCL (first-order) constraints is disallowed. We get this result by using DLR ifd, a very expressive EXPTIME-decidable DL that has been developed to capture typical features of conceptual and object-oriented data models. The last contribution has a more practical flavor, and consists in a polynomial encoding of UML class diagrams in the DL ALCQI, which essentially is the most expressive DL supported by current state-of-the-art DL-based reasoning systems. Though less expressive than DLR ifd, the DL ALCQI preserves enough semantics to keep reasoning about UML class diagrams sound and complete. Exploiting such an encoding, one can use current DL-based reasoning systems as core reasoning engines for a next generation of CASE tools, that are equipped with reasoning capabilities on UML class diagrams.

KR Conference 2004 Conference Paper

What to Ask to a Peer: Ontology-based Query Reformulation

• Diego Calvanese
• Giuseppe De Giacomo
• Domenico Lembo
• Maurizio Lenzerini
• Riccardo Rosati

In the recent years, the issue of cooperation, integration, and coordination between information peers in a networked environment has been addressed in different contexts, including data integration, the Semantic Web, Peer-to-Peer and Grid computing, service-oriented computing and distributed agent systems. One of the main problems that arises in such systems is how to exploit the mappings between peers in order to answer queries posed to one peer. The goal of this paper is to present some basic, fundamental results on this problem. In particular, we focus on a simplified setting based on just two interoperating peers and we investigate how to solve the so-called ``What-To-Ask'' problem: find a way to answer queries posed to a peer by relying only on the query answering service available at the queried peer and at the other peer. We show that a solution to this problem exists in the case of peers based on a basic ontology language and provide an algorithm to compute it. We also show that, by slightly enriching the ontology language, the problem may become unsolvable.

KR Conference 2002 Conference Paper

Reasoning about Actions and Planning in LTL Action Theories

• Diego Calvanese
• Giuseppe De Giacomo
• Moshe Y. Vardi

AAAI Conference 2000 Conference Paper

Answering Queries Using Views over Description Logics Knowledge Bases

• Diego Calvanese
• and Maurizio Lenzerini

Answering queries using views amounts to computing the answer to a query having information only on the extension of a set of precomputed queries (views). This problem is relevant in several fields, such as information integration, query optimization, and data warehousing, and has been studied recently in different settings. In this paper we address answering queries using views in a setting where intensional knowledge about the domain is represented using a very expressive Description Logic equipped with n-ary relations, and queries are nonrecursive datalog queries whose predicates are the concepts and relations that appear in the Description Logic knowledge base. We study the problem under different assumptions, namely, closed and open domain, and sound, complete, and exact information on view extensions. We show that under the closed domain assumption, in which the set of all objects in the knowledge base coincides with the set of objects stored in the views, answering queries using views is already intractable. We show also that under the open domain assumption the problem is decidable in double exponential time.

IJCAI Conference 1999 Conference Paper

Reasoning in Expressive Description Logics with Fixpoints based on Automata on Infinite Trees

• Diego Calvanese
• Giuseppe De Giacomo
• Maurizio Lenzerini

In the last years, the investigation on Description Logics (DLs) has been driven by the goal of applying them in several areas, such as, software engineering, information systems, databases, information integration, and intelligent access to the web. The modeling requirements arising in the above areas have stimulated the need for very rich languages, including fixpoint constructs to represent recursive structures. We study a DL comprising the most general form of fixpoint constructs on concepts, all classical concept forming constructs, plus inverse roles, n-ary relations, qualified number restrictions, and inclusion assertions. We establish the EXPTIME decidability of such logic by presenting a decision procedure based on a reduction to nonemptiness of alternating automata on infinite trees. We observe that this is the first decidability result for a logic combining inverse roles, number restrictions, and general fixpoints.

AAAI Conference 1998 Conference Paper

What Can Knowledge Representation Do for Semi-Structured Data?

• Diego Calvanese

The problem of modeling semi-structured data is important in many application areas such as multimedia data management, biological databases, digital libraries, and data integration. Graph schemas (Buneman et al. 1997) have been proposed recently as a simple and elegant formalism for representing semistructured data. In this model, schemas are represented as graphs whose edges are labeled with unary formulae of a theory, and the notions of conformance of a database to a schema and of subsumption between two schemas are defined in terms of a simulation relation. Several authors have stressed the need of extending graph schemas with various types of constraints, such as edge existence and constraints on the number of outgoing edges. In this paper we analyze the appropriateness of various knowledge representation formalisms for representing and reasoning about graph schemas extended with constraints. We argue that neither First Order Logic, nor Logic Programming nor Frame-based languages are satisfactory for this purpose, and present a solution based on very expressive Description Logics. We provide techniques and complexity analysis for the problem of deciding schema subsumption and conformance in various interesting cases, that differ by the expressive power in the specification of constraints.

ECAI Conference 1996 Conference Paper

Reasoning with Inclusion Axioms in Description Logics: Algorithms and Complexity

• Diego Calvanese