Arrow Research search

Author name cluster

Maurizio Lenzerini

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

40 papers
2 author rows

Possible papers

40

AAAI Conference 2026 Conference Paper

Expressive Recursive Answers for Ontological Knowledge Bases

  • Luca Andolfi
  • Gianluca Cima
  • Marco Console
  • Maurizio Lenzerini

A fundamental use of knowledge bases (KBs) is query answering, i.e., retrieving the information entailed by the KB in response to a user query. When both the KB and the query are specified as logical formulae, the standard form of answer provided to users is the set of all certain answers (CAs): tuples of constants that satisfy the formula defining the query in every model of the logical theory defining the KB. Despite their wide adoption, CAs are known to be just a lossy representation of the information that a KB and a query provide. While several alternative answer languages have been proposed in the literature, no general consensus has emerged on the most suitable approach to query answering over ontological KBs, as each language comes with its own limitations. To address some of these issues, we introduce Regularly Recurrent Answers (RRAs), a novel answer language for queries over ontological KBs based on regular expressions. RRAs support the representation of infinite sets of tuples of constants via a simple (and arguably well understood) generation mechanism. We show that RRAs can capture a fundamental fragment of the certain information entailed by union of conjunctive queries and DL-Lite KBs, making them a strong candidate for informative query answering settings. Our contribution includes the formal definition of RRAs, a proof of their informativeness, and a study of the computational complexity of query answering problem using RRAs.

PDF Details DOI

AAAI Conference 2025 Conference Paper

Answering Conjunctive Queries with Safe Negation and Inequalities over RDFS Knowledge Bases

  • Gianluca Cima
  • Marco Console
  • Roberto Maria Delfino
  • Maurizio Lenzerini
  • Antonella Poggi

Expressing negative conditions is a crucial feature of query languages for knowledge bases (KBs). Answering such queries over ontological KBs, however, is a very challenging task that becomes undecidable even for lightweight Description Logic (DL) ontologies. Such negative results hold even for Conjunctive Queries (CQs) equipped with basic forms of negative conditions such as the so-called safe negation or inequality atoms. One ontology language that is seemingly unaffected by these results is (the DL counterpart of) RDFS even if equipped with disjointness axioms. Answering CQs with inequalities over such ontologies is known to be Pi^p_2-complete, if the number of inequality atoms is unbounded, and NP-complete if we limit this number to one. Notably, these results leave open the cases of CQs with a fixed number greater than two of inequality atoms. Additionally, such a thorough analysis is missing for CQs with safe negation. In this paper, we embark in a refined analysis of the combined complexity of answering CQs with inequality atoms and safe negation over RDFS ontologies augmented with disjointness axioms. Firstly, we provide a unified Pi^p_2 query answering algorithm for the general problem. Secondly, we confirm the generally held conjecture according to which answering CQs with two inequality atoms over such ontologies is already Pi^p_2-hard. This result closes an important gap in the current literature and has an impact on the widely influential problem of query containment. Lastly, for CQs with safe negation, we prove a behavior similar to that of CQs with inequality atoms. Specifically, we show that answering CQs with at most one negated atom can be done in NP, while allowing at most two negated atoms is sufficient to obtain Pi^p_2-hardness.

PDF Details DOI

ECAI Conference 2025 Conference Paper

RDFS Knowledge Graphs Through the Lens of Logic: Semantics and Query Answering

  • Roberto Maria Delfino
  • Maurizio Lenzerini
  • Antonella Poggi

We propose a semantic characterization for a simple and yet sufficiently expressive kind of Knowledge Graphs based on RDFS, which we call RKGs. In doing so, we address some of the issues deriving from the standard RDFS semantics and then proceed by defining a semantics for RKGs based on formal logic which is also able to properly capture the metamodeling capabilities of RDFS. We prove that RKGs, in general, do not exhibit a universal model, and thus query answering cannot rely on the well-known techniques based on the use of it. Then, by highlighting the connection between the lack of a universal model for an RKG and the presence of a form of indefiniteness in its elements, we introduce the class of definite RKGs, and prove that definiteness is both a sufficient and necessary condition for an RKG to admit a universal model. Also, based on such result, we propose an algorithm for query answering for both definite and general RKGs and we characterize the computational complexity for the two cases.

Details

AAAI Conference 2024 Conference Paper

What Does a Query Answer Tell You? Informativeness of Query Answers for Knowledge Bases

  • Luca Andolfi
  • Gianluca Cima
  • Marco Console
  • Maurizio Lenzerini

Query answering for Knowledge Bases (KBs) amounts to extracting information from the various models of a KB, and presenting the user with an object that represents such information. In the vast majority of cases, this object consists of those tuples of constants that satisfy the query expression either in every model (certain answers) or in some model (possible answers). However, similarly to the case of incomplete databases, both these forms of answers are a lossy representation of all the knowledge inferable from the query and the queried KB. In this paper, we illustrate a formal framework to characterize the information that query answers for KBs are able to represent. As a first application of the framework, we study the informativeness of current query answering approaches, including the recently introduced partial answers. We then define a novel notion of answers, allowing repetition of variables across answer tuples. We show that these answers are capable of representing a meaningful form of information, and we also study their data complexity properties.

PDF Details DOI

AAAI Conference 2023 Conference Paper

Epistemic Disjunctive Datalog for Querying Knowledge Bases

  • Gianluca Cima
  • Marco Console
  • Maurizio Lenzerini
  • Antonella Poggi

The Datalog query language can express several powerful recursive properties, often crucial in real-world scenarios. While answering such queries is feasible over relational databases, the picture changes dramatically when data is enriched with intensional knowledge. It is indeed well-known that answering Datalog queries is undecidable already over lightweight knowledge bases (KBs) of the DL-Lite family. To overcome this issue, we propose a new query language based on Disjunctive Datalog rules combined with a modal epistemic operator. Rules in this language interact with the queried KB exclusively via the epistemic operator, thus extracting only the information true in every model of the KB. This form of interaction is crucial for not falling into undecidability. The contribution provided by this paper is threefold. First, we illustrate the syntax and the semantics of the novel query language. Second, we study the expressive power of different fragments of our new language and compare it with Disjunctive Datalog and its variants. Third, we outline the precise data complexity of answering queries in our new language over KBs expressed in various well-known formalisms.

PDF Details DOI

AAAI Conference 2022 Conference Paper

Monotone Abstractions in Ontology-Based Data Management

  • Gianluca Cima
  • Marco Console
  • Maurizio Lenzerini
  • Antonella Poggi

In Ontology-Based Data Management (OBDM), an abstraction of a source query q is a query over the ontology capturing the semantics of q in terms of the concepts and the relations available in the ontology. Since a perfect characterization of a source query may not exist, the notions of best sound and complete approximations of an abstraction have been introduced and studied in the typical OBDM context, i. e. , in the case where the ontology is expressed in DL-Lite, and source queries are expressed as unions of conjunctive queries (UCQs). Interestingly, if we restrict our attention to abstractions expressed as UCQs, even best approximations of abstractions are not guaranteed to exist. Thus, a natural question to ask is whether such limitations affect even larger classes of queries. In this paper, we answer this fundamental question for an essential class of queries, namely the class of monotone queries. We define a monotone query language based on disjunctive Datalog enriched with an epistemic operator, and show that its expressive power suffices for expressing the best approximations of monotone abstractions of UCQs.

PDF Details

IJCAI Conference 2021 Conference Paper

Intensional and Extensional Views in DL-Lite Ontologies

  • Marco Console
  • Giuseppe De Giacomo
  • Maurizio Lenzerini
  • Manuel Namici

The use of virtual collections of data is often essential in several data and knowledge management tasks. In the literature, the standard way to define virtual data collections is via views, i. e. , virtual relations defined using queries. In data and knowledge bases, the notion of views is a staple of data access, data integration and exchange, query optimization, and data privacy. In this work, we study views in Ontology-Based Data Access (OBDA) systems. OBDA is a powerful paradigm for accessing data through an ontology, i. e. , a conceptual specification of the domain of interest written using logical axioms. Intuitively, users of an OBDA system interact with the data only through the ontology's conceptual lens. We present a novel framework to express natural and sophisticated forms of views in OBDA systems and introduce fundamental reasoning tasks for these views. We study the computational complexity of these tasks and present classes of views for which these tasks are tractable or at least decidable.

PDF Details DOI

AAAI Conference 2020 Conference Paper

Answering Conjunctive Queries with Inequalities in DL-Lite ℛ

  • Gianluca Cima
  • Maurizio Lenzerini
  • Antonella Poggi

In the context of the Description Logic DL-Lite = R, i. e. , DL-LiteR without UNA and with inequality axioms, we address the problem of adding to unions of conjunctive queries (UCQs) one of the simplest forms of negation, namely, inequality. It is well known that answering conjunctive queries with unrestricted inequalities over DL-LiteR ontologies is in general undecidable. Therefore, we explore two strategies for recovering decidability, and, hopefully, tractability. Firstly, we weaken the ontology language, and consider the variant of DL-Lite = R corresponding to RDFS enriched with both inequality and disjointness axioms. Secondly, we weaken the query language, by preventing inequalities to be applied to existentially quantified variables, thus obtaining the class of queries named UCQ =, b s. We prove that in the two cases, query answering is decidable, and we provide tight complexity bounds for the problem, both for data and combined complexity. Notably, the results show that answering UCQ =, b s over DL-Lite = R ontologies is still in AC0 in data complexity.

PDF Details

AAAI Conference 2020 Conference Paper

Epistemic Integrity Constraints for Ontology-Based Data Management

  • Marco Console
  • Maurizio Lenzerini

Ontology-based data management (OBDM) is a powerful knowledge-oriented paradigm for managing data spread over multiple heterogeneous sources. In OBDM, the data sources of an information system are handled through the reconciled view provided by an ontology, i. e. , the conceptualization of the underlying domain of interest expressed in some formal language. In any information systems where the basic knowledge resides in data sources, it is of paramount importance to specify the acceptable states of such information. Usually, this is done via integrity constraints, i. e. , requirements that the data must satisfy formally expressed in some specific language. However, while the semantics of integrity constraints are clear in the context of databases, the presence of inferred information, typical of OBDM systems, considerably complicates the matter. In this paper, we establish a novel framework for integrity constraints in the OBDM scenarios, based on the notion of knowledge state of the information system. For integrity constraints in this framework, we define a language based on epistemic logic, and study decidability and complexity of both checking satisfaction and performing different forms of static analysis on them.

PDF Details

KR Conference 2020 Conference Paper

Non-Monotonic Ontology-based Abstractions of Data Services

  • Gianluca Cima
  • Maurizio Lenzerini
  • Antonella Poggi

In Ontology-Based Data Access (OBDA), a domain ontology is linked to the data sources of an organization in order to query, integrate and manage data through the concepts and relations of the domain of interest, thus abstracting from the technical details of the data layer implementation. While the great majority of contributions in OBDA in the last decade have been concerned with the issue of computing the answers of queries expressed over the ontology, recent papers address a different problem, namely the one of providing suitable abstractions of data services, i. e. , characterizing or explaining the semantics of queries over the sources in terms of queries over the domain ontology. Current works on this subject are based on expressing abstractions in terms of unions of conjunctive queries (UCQs) over the ontology. In this paper we advocate the use of a non-monotonic language for this task. As a first contribution, we present a simple extension of UCQs with non-monotonic features, and show that non-monotonicity provides more expressive power in characterizing the semantics of data services. A second contribution is to prove that, similarly to the case of monotonic abstractions, depending on the expressive power of the languages used to specify the various components of the OBDA system, there are cases where neither perfect nor approximated abstractions exist for a given data service. As a third contribution, we single out interesting special cases where the existence of abstractions is guaranteed, and we present algorithms for computing such abstractions in these cases.

PDF Details DOI

IJCAI Conference 2019 Conference Paper

Semantic Characterization of Data Services through Ontologies

  • Gianluca Cima
  • Maurizio Lenzerini
  • Antonella Poggi

We study the problem of associating formal semantic descriptions to data services. We base our proposal on the Ontology-based Data Access paradigm, where a domain ontology is used to provide a semantic layer mapped to the data sources of an organization. The basic idea is to explain the semantics of a data service in terms of a query over the ontology. We illustrate a formal framework for this problem, based on the notion of source-to-ontology (s-to-o) rewriting, which comes in three variants, called sound, complete and perfect, respectively. We present a thorough complexity analysis of two computational problems, namely verification (checking whether a query is an s-to-o rewriting of a given data service), and computation (computing an s-to-o rewriting of a data service).

PDF Details

IJCAI Conference 2016 Conference Paper

Answering Metaqueries over Hi (OWL 2 QL) Ontologies

  • Maurizio Lenzerini
  • Lorenzo Lepore
  • Antonella Poggi

Hi(OWL 2 QL) is a new ontology language with the OWL2QL syntax and a specific semantics designed to support metamodeling and meta-querying. In this paper we investigate the problem of answering metaqueries in Hi(OWL 2 QL), which are unions of conjunctive queries with both ABox and TBox atoms. We first focus on a specific class of ontologies, called TBox-complete, where there is no uncertainty about TBox axioms, and show that query answering in this case has the same complexity (both data and combined) as in OWL2QL. We then move to general ontologies and show that answering metaqueries is coNP-complete with respect to ontology complexity, Π 2 p -complete with respect to combined complexity, and remains AC0 with respect to ABox complexity. Finally, we present an optimized query answering algorithm that can be used for TBox-complete ontologies.

PDF Details

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.

PDF Details

AAAI Conference 2014 Conference Paper

Data Quality in Ontology-based Data Access: The Case of Consistency

  • Marco Console
  • Maurizio Lenzerini

Ontology-based data access (OBDA) is a new paradigm aiming at accessing and managing data by means of an ontology, i. e. , a conceptual representation of the domain of interest in the underlying information system. In the last years, this new paradigm has been used for providing users with abstract (independent from technological and system-oriented aspects), effective, and reasoning-intensive mechanisms for querying the data residing at the information system sources. In this paper we argue that OBDA, besides querying data, provides the right principles for devising a formal approach to data quality. In particular, we concentrate on one of the most important dimensions considered both in the literature and in the practice of data quality, namely consistency. We define a general framework for data consistency in OBDA, and present algorithms and complexity analysis for several relevant tasks related to the problem of checking data quality under this dimension, both at the extensional level (content of the data sources), and at the intensional level (schema of the data sources).

PDF Details

ECAI Conference 2014 Conference Paper

Reducing global consistency to local consistency in Ontology-based Data Access

  • Marco Console
  • Maurizio Lenzerini

Ontology-based data access (OBDA) is a new paradigm aiming at accessing and managing data by means of an ontology, i. e. , a conceptual representation of the domain of interest in the underlying information system. In the last years, this new paradigm has been used for providing users with suitable mechanisms for querying the data residing at the information system sources. Most of the research has been concentrating on making query answering efficient. Howeverquery answering is not the only service that an OBDA system must provide. Another crucial service is consistency checking. Current approaches to this problem involves executing expensive queries at run-time. In this paper we address a fundamental problem for OBDA system: given an OBDA specification, can we avoid the consistency check on the whole OBDA system (global consistency check), and rely instead on the constraint checking carried out by the DBMS on the data source (local consistency checking)? We present algorithms and complexity analysis for this problem, showing that it can be solved efficiently for a class of OBDA systems that is very relevant in practice.

Details

AAAI Conference 2012 Conference Paper

Ontology-Based Data Access with Dynamic TBoxes in DL-Lite

  • Floriana Di Pinto
  • Giuseppe De Giacomo
  • Maurizio Lenzerini
  • Riccardo Rosati

In this paper we introduce the notion of mapping-based knowledge base (MKB) to formalize the situation where both the extensional and the intensional level of the ontology are determined by suitable mappings to a set of (relational) data sources. This allows for making the intensional level of the ontology as dynamic as traditionally the extensional level is. To do so, we resort to the meta-modeling capabilities of higher-order Description Logics, which allow us to see concepts and roles as individuals, and vice versa. The challenge in this setting is to design tractable query answering algorithms. Besides the definition of MKBs, our main result is that answering instance queries posed to MKBs expressed in Hi(DL-LiteR) can be done efficiently. In particular, we define a query rewriting technique that produces first-order (SQL) queries to be posed to the data sources.

PDF Details

ECAI Conference 2012 Conference Paper

Updating inconsistent Description Logic knowledge bases

  • Maurizio Lenzerini
  • Domenico Fabio Savo

Finding an appropriate semantics for task of updating an inconsistent knowledge base is a challenging problem. In this paper, we consider knowledge bases expressed in Description Logics, and focus on ABox inconsistencies, i. e. , the case where the TBox is consistent, but the whole knowledge base is not. Our first contribution is the definition of a new semantics for updating an inconsistent Description Logic knowledge base with both the insertion and the deletions of a set of ABox assertions. We then concentrate on the

Details

AAAI Conference 2011 Conference Paper

Higher-Order Description Logics for Domain Metamodeling

  • Giuseppe De Giacomo
  • Maurizio Lenzerini
  • Riccardo Rosati

We investigate an extension of Description Logics (DL) with higher-order capabilities, based on Henkin-style semantics. Our study starts from the observation that the various possibilities of adding higher-order constructs to a DL form a spectrum of increasing expressive power, including domain metamodeling, i. e. , using concepts and roles as predicate arguments. We argue that higher-order features of this type are sufficiently rich and powerful for the modeling requirements arising in many relevant situations, and therefore we carry out an investigation of the computational complexity of satisfiability and conjunctive query answering in DLs extended with such higher-order features. In particular, we show that adding domain metamodeling capabilities to SHIQ (the core of OWL 2) has no impact on the complexity of the various reasoning tasks. This is also true for DL-LiteR (the core of OWL 2 QL) under suitable restrictions on the queries.

PDF Details

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.

PDF Details

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.

PDF Details

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.

AAAI Conference 2005 System Paper

QuOnto: Querying Ontologies

  • Andrea Acciarri
  • Giuseppe De Giacomo
  • Maurizio Lenzerini

In this work, we present QUONTO, a query answering system based on DL-Lite. Our system provides three basic functionalities: (1) specification of the intensional level of the ontology (TBox), (2) specification of the extensional level of the ontology (ABox), and (3) query answering.

PDF Details

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.

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.

PDF

IJCAI Conference 1995 Conference Paper

What's in an Aggregate: Foundations for Description Logics with Tuples and Sets

  • Giuseppe De Giacomo
  • Maurizio Lenzerini

Based on the research done in the last decade, attempts have been made to propose description logics as unifying formalisms for the various class-based representation languages used in different areas. These attempts have made apparent that sound, complete, and decidable description logics still suffer from several limitations, regarding modeling classes of aggregate objects, expressing general inclusion axioms, and the ability of navigating links between classes. In this paper we make description logics accomplish the necessary leap in order to become suitable for the new challenging applications they are faced with. In particular, we propose a powerful description logic overcoming the above limitations and we show that its reasoning tasks are decidable in worst case exponential time.

PDF

AAAI Conference 1991 Conference Paper

Concept Languages as Query Languages

  • Maurizio Lenzerini

We study concept languages (also called terminological languages) as means for both defining a knowledge base and expressing queries. In particular, we investigate on the possibility of using two different concept languages, one for asserting facts about individual objects, and the other for querying a set of such assertions. Contrary to many negative results on the complexity of terminological reasoning, our work shows that, provided that a limited language is used for the assertions, it is possible to employ a richer query language while keeping the reasoning process tractable. We also show that, on the other hand, there are constructs that make query answering inherently intractable.

PDF Details