The idea of using an ontology to enrich user queries with domain knowledge has attracted considerable attention from the database and KR communities during the last fifteen years or so. The ontology and the user query can be conveniently seen as two components of one composite query, called ontology-mediated query (omq), while an omq language (OL,QL) collects all such omqs where the ontology is expressed using the ontology language OL and the user query comes from the query language QL. The evaluation problem for rule-based omq languages of the form (OL,CQ), where OL is a rule-based ontology language, i.e., it collects ontologies modelled using tuple-generating dependencies (a.k.a. existential rules), and CQ is the language of conjunctive queries, has been extensively studied in the literature. In particular, the notion of first-order rewritability of such languages, i.e., the property of being able to rewrite every omq from the language in question to an equivalent first-order query, has been studied in depth. This research effort led an algorithmic characterization of when a rule-based omq language (OL,CQ) is first-order rewritable. More precisely, there is a uniform algorithm Rewrite such that, for every rule-based ontology language OL, the omq language (OL,CQ) is first-order rewritable iff for every omq O from (OL,CQ), the algorithm Rewrite on input O terminates and constructs a first-order rewriting of O. The question that we are interested in is whether the above algorithmic characterization can be extended to rule-based omq languages of the form (OL,nCQ), where nCQ is the language of conjunctive queries with the useful feature of negation. The goal of this work is to initiate effort towards the settlement of the above highly non-trivial question. To this end, we provide a new algorithm, which is a non-trivial extension of the algorithm Rewrite for positive omqs, and show the following: under the Skolem semantics, a well-established approach for defining the answer to a rule-based omq when the user query can use negation, the proposed algorithm is a first-order rewriter for (OL,nCQ), where OL is the language of linear or acyclic tuple-generating dependencies, two central rule-based ontology languages that ensure first-order rewritability for positive omqs. We strongly believe that the new algorithm can serve as a good starting point towards the full settlement of our main question.

Analyzing and predicting the dynamics of opinion formation in the context of social environments are problems that attracted much attention in literature. While grounded in social psychology, these problems are nowadays popular within the artificial intelligence community, where opinion dynamics are often studied via game-theoretic models in which individuals/agents hold opinions taken from a fixed set of discrete alternatives, and where the goal is to find those configurations where the opinions expressed by the agents emerge as a kind of compromise between their innate opinions and the social pressure they receive from the environments. As a matter of facts, however, these studies are based on very high-level and sometimes simplistic formalizations of the social environments, where the mental state of each individual is typically encoded as a variable taking values from a Boolean domain. To overcome these limitations, the paper proposes a framework generalizing such discrete preference games by modeling the reasoning capabilities of agents in terms of weighted propositional logics. It is shown that the framework easily encodes different kinds of earlier approaches and fits more expressive scenarios populated by conformist and dissenter agents. Problems related to the existence and computation of stable configurations are studied, under different theoretical assumptions on the structural shape of the social interactions and on the class of logic formulas that are allowed. Remarkably, during its trip to identify some relevant tractability islands, the paper devises a novel technical machinery whose significance goes beyond the specific application to analyzing opinion formation and diffusion, since it significantly enlarges the class of Integer Linear Programs that were known to be tractable so far.

Similarities play a pivotal role in diverse real-world scenarios, driving extensive research into methodologies for measuring entity similarity and expanding sets of entities with similar ones. Machines are nowadays adept at performing these tasks by taking in some regard relevant interconnected properties shared by entities, which we term nexus of similarity. To the best of our knowledge, however, there lacks a general logic-based framework for ‘characterizing’ nexus of similarity between (tuples of) entities within a given relational knowledge base represented via some arbitrary formalism. Essentially, there is no way to formally express such nexus in a comprehensive and concise manner, making them understandable to both machines and humans. Moreover, the classical notion of expanding a set of entities overlooks the inherent human tendency to naturally generalize entities in a taxonomic way. In light of what was discussed above, we introduce the novel notion of selective knowledge base, denoted by S=(K,ς), designed to enhance any pre-existing relational knowledge base K with a summary selector ς. For any tuple τ of entities, ς selects a relevant portion of the knowledge entailed by K that describes τ. Subsequently, we design a nexus explanation language, called NCF, with an associated semantics. This allows us to delve into the task of explaining and characterizing the nexus of similarity among (tuples of) entities within a selective knowledge base. Then, we introduce the notions of explanation, characterization, canonical characterization, and core characterization, demonstrating that they always exist and are computable. Furthermore, we introduce the notions of essential expansion and expansion graph, formally generalizing the classical notion of linear expansions by showcasing that expansions are naturally taxonomic. We also study key reasoning tasks related to the computation of characterizations and expansions, and analyze their tractability under various computational assumptions. Finally, we contextualize our framework within the existing literature by exploring related technical problems, analyze our design choices in a critical way, and investigate the adaptability and effectiveness of our approach in real-world scenarios.

Abstract Existential rules form an expressive ${{\textsf{Datalog}}}$ -based language to specify ontological knowledge. The presence of existential quantification in rule-heads, however, makes the main reasoning tasks undecidable. To overcome this limitation, in the last two decades, a number of classes of existential rules guaranteeing the decidability of query answering have been proposed. Unfortunately, only some of these classes fully encompass ${{\textsf{Datalog}}}$ and, often, this comes at the price of higher computational complexity. Moreover, expressive classes are typically unable to exploit tools developed for classes exhibiting lower expressiveness. To mitigate these shortcomings, this paper introduces a novel general syntactic condition that allows us to define, systematically and in a uniform way, from any decidable class $\mathcal{C}$ of existential rules, a new class called ${{\textsf{Dyadic-}\mathcal{C}}}$ enjoying the following properties: (i) it is decidable; (ii) it generalizes ${{\textsf{Datalog}}}$ ; (iii) it generalizes $\mathcal{C}$ ; (iv) it can effectively exploit any reasoner for query answering over $\mathcal{C}$ ; and (v) its computational complexity does not exceed the highest between the one of $\mathcal{C}$ and the one of ${{\textsf{Datalog}}}$ .

We consider the problem of ontological query answering, that is, the problem of answering a database query (typically a conjunctive query) in the presence of an ontology. This means that during the query answering process we also need to take into account the knowledge that can be inferred from the given database and ontology. Building, however, ontology-aware database systems from scratch, with sophisticated optimization techniques, is a highly non-trivial task that requires a great engineering effort. Therefore, exploiting conventional database systems is an important route towards efficient ontological query answering. Nevertheless, standard database systems are unaware of ontologies. An approach to ontological query answering that enables the use of standard database systems is the so-called polynomial combined query rewriting, originally introduced in the context of description logics: the conjunctive query q and the ontology Σ are rewritten in polynomial time into a first-order query qΣ (in a database-independent way), while the database D and the ontology Σ are rewritten in polynomial time into a new database DΣ (in a query-independent way), such that the answer to q in the presence of Σ over D coincides with the answer to qΣ over DΣ. The latter can then be computed by exploiting a conventional database system. In this work, we focus on linear and guarded existential rules, which form robust rule-based languages for modeling ontologies, and investigate the limits of polynomial combined query rewriting. In particular, we show that this type of rewriting can be successfully applied to (i) linear existential rules when the rewritten query can use the full power of first-order queries, (ii) linear existential rules when the arity of the underlying schema is fixed and the rewritten query is positive existential, namely it uses only existential quantification, conjunction, and disjunction, and (iii) guarded existential rules when the underlying schema is fixed and the rewritten query is positive existential. We can show that the above results reach the limits (under standard complexity-theoretic assumptions such as ) of polynomial combined query rewriting in the case of linear and guarded existential rules.

Abstract We introduce a novel logic-based system for reasoning over data streams, which relies on a framework enabling a tight, fine-tuned interaction between Apache Flink and the $${{\mathcal I}^2}$$ -DLV system. The architecture allows to take advantage from both the powerful distributed stream processing capabilities of Flink and the incremental reasoning capabilities of $${{\mathcal I}^2}$$ -DLV, based on overgrounding techniques. Besides the system architecture, we illustrate the supported input language and its modeling capabilities, and discuss the results of an experimental activity aimed at assessing the viability of the approach.

Guarded existential rules form a robust rule-based language for modelling ontologies. The central problem of ontology-based query answering, as well as the notion of polynomial combined rewritability, have been extensively studied during the last years for this formalism. However, the relevant setting where the underlying signature is considered to be fixed is far from being well understood. All the existing results on ontology-based query answering and polynomial combined rewritability assume rule heads with one atom, while existential rules in real ontologies are typically coming with multi-heads consisting of several atoms. We aim to fill this gap.

Abstract Decision support systems play an important role in medical fields as they can augment clinicians to deal more efficiently and effectively with complex decision-making processes. In the diagnosis of headache disorders, however, existing approaches and tools are still not optimal. On the one hand, to support the diagnosis of this complex and vast spectrum of disorders, the International Headache Society released in 1988 the International Classification of Headache Disorders (ICHD), now in its 3rd edition: a 200 pages document classifying more than 300 different kinds of headaches, where each is identified via a collection of specific nontrivial diagnostic criteria. On the other hand, the high number of headache disorders and their complex criteria make the medical history process inaccurate and not exhaustive both for clinicians and existing automatic tools. To fill this gap, we present head-asp, a novel decision support system for the diagnosis of headache disorders. Through a REST Web Service, head-asp implements a dynamic questionnaire that complies with ICHD-3 by exploiting two logical modules to reach a complete diagnosis while trying to minimize the total number of questions being posed to patients. Finally, head-asp is freely available on-line and it is receiving very positive feedback from the group of neurologists that is testing it.

Abstract The W3C Web Ontology Language (OWL) is a powerful knowledge representation formalism at the basis of many semantic-centric applications. Since its unrestricted usage makes reasoning undecidable already in case of very simple tasks, expressive yet decidable fragments have been identified. Among them, we focus on OWL 2 RL, which offers a rich variety of semantic constructors, apart from supporting all RDFS datatypes. Although popular Web resources - such as DBpedia - fall in OWL 2 RL, only a few systems have been designed and implemented for this fragment. None of them, however, fully satisfy all the following desiderata: (i) being freely available and regularly maintained; (ii) supporting query answering and SPARQL queries; (iii) properly applying the sameAs property without adopting the unique name assumption; (iv) dealing with concrete datatypes. To fill the gap, we present DaRLing, a freely available Datalog rewriter for OWL 2 RL ontological reasoning under SPARQL queries. In particular, we describe its architecture, the rewriting strategies it implements, and the result of an experimental evaluation that demonstrates its practical applicability.

Enhancing Datalog with existential quantification gives rise to Datalog ∃ , a powerful knowledge representation language widely used in ontology-based query answering. In this setting, a conjunctive query is evaluated over a Datalog ∃ program consisting of extensional data paired with so-called “existential” rules. Owing to their high expressiveness, such rules make the evaluation of queries undecidable, even when the latter are atomic. Decidable generalizations of Datalog by existential rules have been proposed in the literature (such as weakly acyclic and weakly guarded); but they pay the price of higher computational complexity, hindering the implementation of effective systems. Conversely, the results in this article demonstrate that it is definitely possible to enable fast yet powerful query answering over existential rules that strictly generalize Datalog by ensuring decidability without any complexity overhead. On the theoretical side, we define the class of parsimonious programs that guarantees decidability of atomic queries. We then strengthen this class to strongly parsimonious programs ensuring decidability also for conjunctive queries. Since parsimony is an undecidable property, we single out Shy, an easily recognizable class of strongly parsimonious programs that generalizes Datalog while preserving its complexity even under conjunctive queries. Shy also generalizes the class of linear existential programs, while it is uncomparable to the other main classes ensuring decidability. On the practical side, we exploit our results to implement DLV ∃ , an effective system for query answering over parsimonious existential rules. To assess its efficiency, we carry out an experimental analysis, evaluating DLV ∃ performances for ontology-based query answering on both real-world and synthetic ontologies.

Reasoning with existential rules typically consists of checking whether a Boolean conjunctive query is satisfied by all models of a first-order sentence having the form of a conjunction of Datalog rules extended with existential quantifiers in rule-heads. To guarantee decidability, five basic decidable classes - linear, weakly-acyclic, guarded, sticky, and shy - have been singled out, together with several generalizations and combinations. For all basic classes, except shy, the important property of finite controllability has been proved, ensuring that a query is satisfied by all models of the sentence if, and only if, it is satisfied by all of its finite models. This paper takes two steps forward: (i) devise a general technique to facilitate the process of (dis)proving finite controllability of an arbitrary class of existential rules; and (ii) specialize the technique to complete the picture for the five mentioned classes, by showing that also shy is finitely controllable.

Existential rules generalize Datalog with existential quantification in the head. Natively, Datalog is interpreted under a closed-world semantics, while existential rules typically employ the open-world assumption. The interpretation domain in the latter case is enlarged by infinitely many "anonymous" individuals. Then, in any rule, each variable ranges over all individuals, even if not needed or required. In this paper, we enhance existential rules by closed-world variables to consciously reason on the properties of "known" (non-anonymous) and arbitrary individuals in different ways. Accordingly, we uniformly generalize the basic classes of existential rules that ensure decidability of ontology-based query answering. For them, after observing that decidability is preserved, we prove that a strict increase in expressiveness is gained, and in most cases the computational complexity is not altered.

Two paradigmatic restrictions that have been studied for ensuring the decidability of query answering under existential rules are guardedness and stickiness. With the aim of consolidating these restrictions, a flexible condition, called tameness, has been proposed a few years ago, which relies on hybrid reasoning, i.e., a combination of forward and backward procedures. The complexity of query answering under this hybrid class of existential rules is by now well-understood. However, the complexity of finite query answering, i.e., query answering under finite models, has remained an open problem. Closing this problem is the main goal of this work.

Abstract Ontology-based query answering asks whether a Boolean conjunctive query is satisfied by all models of a logical theory consisting of a relational database paired with an ontology. The introduction of existential rules (i.e., Datalog rules extended with existential quantifiers in rule heads) as a means to specify the ontology gave birth to Datalog+/-, a framework that has received increasing attention in the last decade, with focus also on decidability and finite controllability to support effective reasoning. Five basic decidable fragments have been singled out: linear, weakly acyclic, guarded, sticky, and shy. Moreover, for all these fragments, except shy, the important property of finite controllability has been proved, ensuring that a query is satisfied by all models of the theory iff it is satisfied by all its finite models. In this paper, we complete the picture by demonstrating that finite controllability of ontology-based query answering holds also for shy ontologies, and it therefore applies to all basic decidable Datalog+/- classes. To make the demonstration, we devise a general technique to facilitate the process of (dis)proving finite controllability of an arbitrary ontological fragment.

We perform an in-depth complexity analysis of query answering under guarded-based classes of disjunctive tuple-generating dependencies (DTGDs), focusing on (unions of) conjunctive queries ((U)CQs). We show that the problem under investigation is very hard, namely 2E xp T ime -complete, even for fixed sets of dependencies of a very restricted form. This is a surprising lower bound that demonstrates the enormous impact of disjunction on query answering under guarded-based tuple-generating dependencies, and also reveals the source of complexity for expressive logics such as the guarded fragment of first-order logic. We then proceed to investigate whether prominent subclasses of (U)CQs (i.e., queries of bounded treewidth and hypertree-width, and acyclic queries) have a positive impact on the complexity of the problem under consideration. We show that queries of bounded treewidth and bounded hypertree-width do not reduce the complexity of our problem, even if we focus on predicates of bounded arity or on fixed sets of DTGDs. Regarding acyclic queries, although the problem remains 2E xp T ime -complete in general, in some relevant settings the complexity reduces to E xp T ime -complete. Finally, with the aim of identifying tractable cases, we focus our attention on atomic queries. We show that atomic queries do not make the query answering problem easier under classes of guarded-based DTGDs that allow more than one atom to occur in the body of the dependencies. However, the complexity significantly decreases in the case of dependencies that can have only one atom in the body. In particular, we obtain a P time -completeness if we focus on predicates of bounded arity, and AC 0 -membership when the set of dependencies and the query are fixed. Interestingly, our results can be used as a generic tool for establishing complexity results for query answering under various description logics.

Figure 3 was left out in the article (Gottlob et al. 2013). The figure that is given there as figure 3 should in fact be figure 4. Further, the reference to figure 3 on the 4th line of page 889 should be a reference to figure 4. The correct figure 3 (missing in the paper) is supplied below. We apologise for this error.

Abstract Consistent query answering over a database that violates primary key constraints is a classical hard problem in database research that has been traditionally dealt with logic programming. However, the applicability of existing logic-based solutions is restricted to data sets of moderate size. This paper presents a novel decomposition and pruning strategy that reduces, in polynomial time, the problem of computing the consistent answer to a conjunctive query over a database subject to primary key constraints to a collection of smaller problems of the same sort that can be solved independently. The new strategy is naturally modeled and implemented using Answer Set Programming (ASP). An experiment run on benchmarks from the database world prove the effectiveness and efficiency of our ASP-based approach also on large data sets.

Abstract Existential rules are Datalog rules extended with existential quantifiers in rule-heads. Three fundamental restriction paradigms that have been studied for ensuring decidability of query answering under existential rules are weak-acyclicity, guardedness and stickiness. Towards the identification of even more expressive decidable languages, several attempts have been conducted to consolidate weak-acyclicity with the other two paradigms. However, it is not clear how guardedness and stickiness can be merged; this is the subject of this paper. A powerful and flexible condition, called tameness, is proposed, which allows us to consolidate in an elegant and uniform way guardedness with stickiness.

Abstract A data integration system provides transparent access to different data sources by suitably combining their data, and providing the user with a unified view of them, called global schema. However, source data are generally not under the control of the data integration process; thus, integrated data may violate global integrity constraints even in the presence of locally consistent data sources. In this scenario, it may be anyway interesting to retrieve as much consistent information as possible. The process of answering user queries under global constraint violations is called consistent query answering (CQA). Several notions of CQA have been proposed, e.g., depending on whether integrated information is assumed to be sound, complete, exact, or a variant of them. This paper provides a contribution in this setting: it uniforms solutions coming from different perspectives under a common Answer-Set Programming (ASP)-based core, and provides query-driven optimizations designed for isolating and eliminating inefficiencies of the general approach for computing consistent answers. Moreover, the paper introduces some new theoretical results enriching existing knowledge on the decidability and complexity of the considered problems. The effectiveness of the approach is evidenced by experimental results.

Abstract Datalogis one of the best-known rule-based languages, and extensions of it are used in a wide context of applications. An importantDatalogextension is DisjunctiveDatalog, which significantly increases the expressivity of the basic language. DisjunctiveDatalogis useful in a wide range of applications, ranging from Databases (e.g., Data Integration) to Artificial Intelligence (e.g., diagnosis and planning under incomplete knowledge). However, in recent years an important shortcoming ofDatalog-based languages became evident, e.g. in the context of data-integration (consistent query-answering, ontology-based data access) and Semantic Web applications: The language does not permit any generation of and reasoning with unnamed individuals in an obvious way. In general, it is weak in supporting many cases of existential quantification. To overcome this problem,Datalog∃has recently been proposed, which extends traditionalDatalogby existential quantification in rule heads. In this work, we propose a natural extension of DisjunctiveDatalogandDatalog∃, calledDatalog∃,˅, which allows both disjunctions and existential quantification in rule heads and is therefore an attractive language for knowledge representation and reasoning, especially in domains where ontology-based reasoning is needed. We formally define syntax and semantics of the languageDatalog∃,˅, and provide a notion of instantiation, which we prove to be adequate forDatalog∃,˅. A main issue ofDatalog∃and hence also ofDatalog∃,˅is that decidability is no longer guaranteed for typical reasoning tasks. In order to address this issue, we identify many decidable fragments of the language, which extend, in a natural way, analog classes defined in the non-disjunctive case. Moreover, we carry out an in-depth complexity analysis, deriving interesting results which range from Logarithmic Space to Exponential Time.

Abstract The seaport of Gioia Tauro is the largest transshipment terminal of the Mediterranean coast. A crucial management task for the companies operating in the seaport is team-building: the problem of properly allocating the available personnel for serving the incoming ships. Teams have to be carefully arranged in order to meet several constraints, such as allocation of employees with appropriate skills, fair distribution of the working load, and turnover of the heavy/dangerous roles. This makes team-building a hard and expensive task requiring several hours of manual preparation per day. In this paper we present a system based on Answer Set Programming for the automatic generation of the teams of employees in the seaport of Gioia Tauro. The system is currently exploited in the Gioia Tauro seaport by ICO BLG, a company specialized in automobile logistics.

In this paper we present a successful application of logic programming for e-tourism: the iTravel system. The system exploits two technologies that are based on the state-of-the-art computational logic system DLV: (i) a system for ontology representa

A distributed XML document is an XML document that spans several machines or Web repositories. We assume that a distribution design of the document tree is given, providing an XML tree some of whose leaves are "docking points", to which XML subtrees can be attached. These subtrees may be provided and controlled by peers at remote locations, or may correspond to the result of function calls, e.g., Web services. If a global type τ, e.g. a DTD, is specified for a distributed document T, it would be most desirable to be able to break this type into a collection of local types, called a local typing, such that the document satisfies τ if and only if each peer (or function) satisfies its local type. In this paper we lay out the fundamentals of a theory of local typing and provide formal definitions of three main variants of locality: local typing, maximal local typing, and perfect typing, the latter being the most desirable. We study the following relevant decision problems: (i) given a typing for a design, determine whether it is local, maximal local, or perfect; (ii) given a design, establish whether a (maximal) local, or perfect typing does exist. For some of these problems we provide tight complexity bounds (polynomial space), while for the others we show exponential upper bounds. A main contribution is a polynomial-space algorithm for computing a perfect typing in this context, if it exists.

This work describes a clinical process management system aimed to support a process-centred vision of health care practices. The system is founded on knowledge representation and semantic information extraction approaches allowing medical knowledge modelling and acquisition. At the heart of the system there are formalisms and languages well suited for representing, clinical processes as workflows, medical and domain knowledge as ontologies and rules enabling the recognition of semantic patterns representing ontology concepts. The system acquires and stores clinical process instances into a medical knowledge base which parameters are obtained exploiting a semantic information extraction approach enabling automatic medical knowledge acquisition from unstructured clinical documents. The main goal of the system is to assists health care professional in executing and monitoring clinical processes by providing functionalities for automatic knowledge acquisition. Acquired information can be analyzed for identifying main causes of medical errors, high costs and, potentially, to suggest clinical processes restructuring or improvement able to enhance cost control and patient safety.