Web Reasoning and Rule Systems

Description logic programs are a declarative approach to access ontological knowledge bases through a query interface, and to combine the query results using rules that can be nonmonotonic. Noticeably, a bidirectional information flow between the rules and the ontology is supported, which opens the possibility of sophisticated data exchange and advanced reasoning tasks on top of ontologies. As it happens, inconsistency may arise from the interplay of the rules and the ontology. We consider this issue and discuss different origins of inconsistency, as well as approaches to deal with it. While recent progress has been made, several issues remain to be explored; among them is inconsistency management for generalizations of description logic programs, and in particular for HEX programs, where this issues is largely unexplored and challenging, the more if distributed or web-based evaluation scenarios are considered.

We survey results about static analysis of pattern-based queries over XML documents. These queries are analogs of conjunctive queries, their unions and Boolean combinations, in which tree patterns play the role of atomic formulae. As in the relational case, they can be viewed as both queries and incomplete documents, and thus static analysis problems can also be viewed as finding certain answers of queries over such documents. We look at satisfiability of patterns under schemas, containment of queries for various features of XML used in queries, finding certain answers, and applications of pattern-based queries in reasoning about schema mappings for data exchange.

Answer Set Programming (ASP) is a powerful language for knowledge representation and reasoning, that has been developed in the field of nonmonotonic reasoning and logic programming. The high knowledge-modeling power of ASP, together with the availability of efficient ASP systems, have implied a renewed interest in this formalism in recent years. ASP has been applied in many scientific applications, ranging from Artificial Intelligence, to Knowledge Management and Information Integration. The big challenge now is to show that ASP can be profitably used for real-world applications, and can attract much interest also in industry.

In this paper, we report on our on-the-field experience on the development of real-world applications in ASP. We have employed the DLV system, the first ASP system which is undergoing an industrial exploitation by a spin-off company, and is very well-suited for applications development, thanks also to the endowment of powerful development tools, supporting the activities of researchers and implementors. In particular, we describe a couple of real-world ASP applications for work-force management and e-tourism, and we focus on two advanced development tools for DLV: ASPIDE and JDLV. ASPIDE is an extensible integrated development environment for ASP; while JDLV is a plug-in for Eclipse, integrating ASP in a well-assessed development platform which enables a bilateral interaction between ASP and Java.

We present an algorithm for query evaluation given a logic program consisting of function-free Datalog rules. The algorithm is based on Earley Deduction [7,10], but uses explicit states to eliminate rules which are no longer needed, and partial evaluation to minimize the work at runtime. At least in certain cases, the new method is more efficient than our SLDMagic-method [2], and also beats the standard Magic set method. It is also theoretically interesting, because it consumes one EDB fact in each step. Because of its origin, it is especially well suited for parsing applications, e.g. for extracting data from web pages. However, it has the potential to speed up basic Datalog reasoning for many semantic web applications.

In this paper, we devise a general framework for formalizing Description Logic Based Dynamic Systems that is parametric w.r.t. the description logic knowledge base and the progression mechanism of interest. Using this framework we study verification and adversarial synthesis for specifications expressed in a variant of first-order μ-calculus, with a controlled form of quantification across successive states. We provide key decidability results for both verification and synthesis, under a “bounded-state” assumption. We then study two instantiations of this general framework, where the description logic knowledge base is expressed in DL-Lite and \(\mathcal{ALCQI}\), respectively

Extending description logics with so-called nominal schemas has been shown to be a major step towards integrating description logics with rules paradigms. However, establishing efficient algorithms for reasoning with nominal schemas has so far been a challenge. In this paper, we present an algorithm to reason with the description logic fragment \(\mathcal{ELROV}_{n}\), a fragment that extends \(\mathcal{EL}^{++}\) with nominal schemas. We also report on an implementation and experimental evaluation of the algorithm, which shows that our approach is indeed rather efficient.

Recent developments in ontology learning research have made it possible to generate significantly more expressive ontologies. Novel approaches can support human ontology engineers in rapidly creating logically complex and richly axiomatized schemas. Although the higher complexity increases the likelihood of modeling flaws, there is currently little tool support for diagnosing and repairing ontologies produced by automated approaches. Off-the-shelf debuggers based on logical reasoning struggle with the particular characteristics of learned ontologies. They are mostly inefficient when it comes to detecting modeling flaws, or highlighting all of the logical reasons for the discovered problems. In this paper, we propose a reasoning approach for discovering unsatisfiable classes and properties that is optimized for handling automatically generated, expressive ontologies. We describe our implementation of this approach, which we evaluated by comparing it with state-of-the-art reasoners.

Because of the semantic conflicts, the exchange of information between heterogeneous applications remains a complex task. One way to address this problem is to use ontologies for the identification and association of semantically corresponding information concepts. In the electric power industry, the IEC/CIM represents the most complete and widely accepted ontology. We attempt to show through three concrete examples how the CIM can reap advantages from a formal representation of knowledge in order to support complex processes. We present a semantic approach for finding ringlets in the distribution network, for checking specific data inconsistencies and finally for identifying CIM topological nodes. We conclude by stating that the combination of CIM and RDF has the main advantage of offering valuable flexibility in processing complex tasks.

While conjunctive query (CQ) answering over DL-Lite has been studied extensively, there have been few attempts to analyse CQs with negated atoms. This paper deepens the study of the problem. Answering CQs with safe negation and CQs with a single inequality over DL-Lite with role inclusions is shown to be undecidable, even for a fixed TBox and query.Without role inclusions, answering CQs with one inequality is P-hard and with two inequalities coNP-hard in data complexity.

We address the issue of Ontology-Based Data Access, with ontologies represented in the framework of existential rules, also known as Datalog+/-. A well-known approach involves rewriting the query using ontological knowledge. We focus here on the basic rewriting technique which consists of rewriting a conjunctive query (CQ) into a union of CQs. We assume that the set of rules is a finite unification set, i.e., for any CQ, there exists a finite sound and complete rewriting of this CQ with the rules. First, we study a generic breadth-first rewriting algorithm, which takes as input any rewriting operator. We define properties of the rewriting operator that ensure the correctness and the termination of this algorithm. Second, we study some operators with respect to the exhibited properties. All these operators have in common to be based on so-called piece-unifiers but they lead to different explorations of the rewriting space. Finally, an experimental comparison of these operators within an implementation of the generic breadth-first rewriting algorithm is presented.

We extend RDF with the ability to represent property values that exist, but are unknown or partially known, using constraints. Following ideas from the incomplete information literature, we develop a semantics for this extension of RDF, called RDF ⁱ , and study SPARQL query evaluation in this framework.

Efficient ontology debugging is a cornerstone for many activities in the context of the Semantic Web, especially when automatic tools produce (parts of) ontologies such as in the field of ontology matching. The best currently known interactive debugging systems rely upon some meta information in terms of fault probabilities, which can speed up the debugging procedure in the good case, but can also have negative impact on the performance in the bad case. The problem is that assessment of the meta information is only possible a-posteriori. Consequently, as long as the actual fault is unknown, there is always some risk of suboptimal interactive diagnoses discrimination. As an alternative, one might prefer to rely on a tool which pursues a no-risk strategy. In this case, however, possibly well-chosen meta information cannot be exploited, resulting again in inefficient debugging actions. In this work we present a reinforcement learning strategy that continuously adapts its behavior depending on the performance achieved and minimizes the risk of using low-quality meta information. Therefore, this method is suitable for application scenarios where reliable a-priori fault estimates are difficult to obtain. Using a corpus of incoherent real-world ontologies from the field of ontology matching, we show that the proposed risk-aware query strategy outperforms both meta information based approaches and no-risk strategies on average in terms of required amount of user interaction.

Nonmonotonic description logic programs (dl-programs) are a well-known formalism for combining rules and ontologies, where rules interact with an underlying ontology via dl-atoms that allow queries to the ontology under a possible update of its assertional part. It is known that dl-atoms may be nonmonotonic and dl-programs without nonmonotonic dl-atoms have many desirable properties. In this paper, we show that it is possible to remove nonmonotonic dl-atoms from a dl-program while preserving its strong/weak answer set semantics. Though the translation is faithful, it relies on the knowledge about monotonicity of dl-atoms. We then thoroughly investigate the complexity of deciding whether a dl-atom is monotonic under the description logics DL-Lite\(_{\mathcal R}\), \({\mathcal{EL}}^{++}\), \({\mathcal{SHIF}}\) and \({\mathcal{SHOIN}}\), which is of independent interest for computing strong answer sets. We show that the problem is intractable in general, but tractable for dl-atoms with bounded queries in DL-Lite\(_{\mathcal R}\).

Representing uncertain information is very important for modeling real world domains. Recently, the DISPONTE semantics has been proposed for probabilistic description logics. In DISPONTE, the axioms of a knowledge base can be annotated with a set of variables and a real number between 0 and 1. This real number represents the probability of each version of the axiom in which the specified variables are instantiated. In this paper we present the algorithm BUNDLE for computing the probability of queries from DISPONTE knowledge bases that follow the \(\mathcal{ALC}\) semantics. BUNDLE exploits an underlying DL reasoner, such as Pellet, that is able to return explanations for queries. The explanations are encoded in a Binary Decision Diagram from which the probability of the query is computed. The experiments performed by applying BUNDLE to probabilistic knowledge bases show that it can handle ontologies of realistic size and is competitive with the system PRONTO for the probabilistic description logic P-\(\mathcal{SHIQ}\)(D).

In this paper, we focus on the impact of ontology changes on production rules, in the context of rule programs written over the entities of OWL ontologies. Then, ontology evolutions may make rules inconsistent with respect to the knowledge modeled by the ontology. To address this problem, we propose to combine two approaches: the syntactic approach of the \(\mathcal{M}{\rm odel}\)-\(\mathcal{D}{\rm etect}\)-\(\mathcal{R}{\rm epair}\) (\({\mathcal{MDR}}\)) method, and a semantic approach based on a formal description of production rules and rule program inconsistencies. The present paper shows on simple use cases the expected benefits of such a combination, which relies on existing implementations.

In this paper we present the current state of affairs about our funded research projects concerning the investigation of Ontology-Based Data Access in the context of intermodal logistics. This application domain is particularly challenging for two main motivation. On the one hand, it is characterized by very large amounts of data; on the other hand, the design of a conceptual layer must strike a balance between efficient but potentially simplistic models, and sophisticated, but potentially highly inefficient ones.

SKOS (Simple Knowledge Organisation System) is a W3C Recommendation for sharing and linking structured vocabularies - taxonomies, thesauri, classification schemes, etc. - via theWeb [1]. Since the SKOS specification leaves the semantics of SKOS rather open, large modeling projects may specialise SKOS with informal modeling guidelines that narrow down the class of acceptable models (cf. [5]). Unfortunately, verifying that a (large) model complies with informal guidelines is a time consuming, error prone manual process.

Ontologies provide a conceptualization of a domain of interest which can be used for different objectives, such as for providing a formal description of the domain of interest for documentation purposes, or for providing a mechanism for reasoning upon the domain. For instance, they are the core element of the Ontology-Based Data Access (OBDA) [3,8] paradigm, in which the ontology is utilized as a conceptual view, allowing user access to the underlying data sources. With the aim to use an ontology as a formal description of the domain of interest, the use of expressive languages proves to be useful. If instead the goal is to use the ontology for reasoning tasks which require low computational complexity, the high expressivity of the language used to model the ontology may be a hindrance. In this scenario, the approximation of ontologies expressed in very expressive languages through ontologies expressed in languages which keep the computational complexity of the reasoning tasks low is pivotal.

A key challenge for personalized mobile search is to tailor the answers to the specific user by considering her contextual situation. To adapt the retrieved items to user’s context, this paper presents a preference-enabled querying mechanism for personalized mobile search. By exploiting the user’s dialogue history, we infer the weighted user preferences and interests. To further compute personalized answers, we aim to continuously collect the ratings given by the user’s friends regarding relevant topics from stream-based data sources such as Twitter. An experiment shows that our approach allows to compute the most relevant answers, providing an increased quality of search experience for the user.

Kiabora is a software tool dedicated to the analysis of a base of existential rules (also called Datalog± rules). It is able to check if a set of rules belongs to a known class for which entailment is decidable, either directly, by checking some syntactic properties, or by means of its Graph of Rule Dependencies, which allows to combine decidable cases. Kiabora is available online via a simple web form. It is written in Java and is easily extensible to take new decidability results into account. It comes with a textual format, called DLGP (for Datalog Plus), which can be seen as an extension to usual plain Datalog format. In this paper, we briefly introduce the existential rule framework as well as decidability results and presents the analysis performed by Kiabora. More details are available on Kiabora website.

Stream reasoning is an emerging research field focused on dynamic processing and continuous reasoning over huge volumes of streaming data. Finding the right trade-off between scalability and expressivity is a key challenge in this area. In this paper, we want to provide a baseline for exploring the applicability of complex reasoning to the Web of Data based on a solution that combines results and approaches from database research, stream processing, and nonmonotonic logic programming.

Ontology-based reasoning is considered a crucial task in the area of knowledge management. In this context, the interest in approaches that resort to Datalog (and its extensions) for implementing various reasoning tasks over ontologies is growing. Nonetheless, looking from the developer point of view, one can notice that the editing environments for ontologies on the one hand and Datalog-like logic programs on the other hand are often developed independently and miss a common perspective. In this paper we face with this issue proposing the integration of two major development environments for Datalog programs and Ontologies, respectively: ASPIDE and protégé. We extended both systems with specific plugins that enable a synergic interaction between the two development environments. The developer can then handle both ontologies and logic-based reasoning over them by exploiting specific tools integrated to work together.

We introduce a Horn description logic called Horn-DL, which is strictly and essentially richer than Horn-\(\mathcal{SROIQ}\), while still has PTime data complexity. In comparison with Horn-\(\mathcal{SROIQ}\), HornDL additionally allows the universal role and assertions of the form irreflexive (s), \(\lnot s(a,b)\), \(a \not\doteq b\). More importantly, in contrast to all the well-known Horn fragments \(\mathcal{EL}\), DL-Lite, DLP, Horn-\(\mathcal{SHIQ}\), Horn-\(\mathcal{SROIQ}\) of description logics, HornDL allows a form of the concept constructor “universal restriction” to appear at the left hand side of terminological inclusion axioms. Namely, a universal restriction can be used in such places in conjunction with the corresponding existential restriction. In the long version of this paper, we present the first algorithm with PTime data complexity for checking satisfiability of HornDL knowledge bases.

Recently, the problem of representing uncertainty in Description Logics (DLs) has received an increasing attention. In probabilistic DLs, axioms contain numeric parameters that are often difficult to specify or to tune for a human. In this paper we present an approach for learning and tuning the parameters of probabilistic ontologies from data. The resulting algorithm, called EDGE, is targeted to DLs following the DISPONTE approach, that applies the distribution semantics to DLs.