Web Reasoning and Rule Systems

Machine Learning Technology Artificial Intelligence Technology Natural Language Processing Technology Semantic Web Technology Ontology Technology Reasoning Technology Knowledge Information Technology Collecting AI Conference Papers Digital Transformation Technology Navigation of this Blog

Web Reasoning and Rule Systems

This book is the refereed proceedings of the 5th International Conference on Web Reasoning and Rule Systems, RR 2011, held in Galway, Ireland, in August 2011. This book is the refereed proceedings of the 5th International Conference on Web Reasoning and Rule Systems, RR 2011, held in Galway, Ireland, in August 2011, and contains 13 full papers, 12 short papers and 2 invited talks. The papers cover current topics in the Semantic Web, the interaction between well established web languages such as RDF and OWL and classical reasoning approaches, reasoning languages, querying and optimisation, rules and ontologies.

Exchanging More Than Complete Data

In traditional data exchange settings, source instances are restricted to be complete in the sense that all facts are either true or false in these instances. While natural in a typical database transformation scenario, this restriction is increasingly becoming an obstacle for the development of a wide range of applications that need to exchange objects that allow multiple interpretations. In particular, it is motivated by two specific applications that go beyond the usual data exchange scenarios: exchange of incomplete information and exchange of knowledge bases.

In this talk, we propose a general framework for data exchange that can address these two applications. Specifically, we address the problem of exchanging information given by a representation system, which is a finite description of a complete instance, and demonstrate the robustness of our proposal by applying it to the problem of exchanging incomplete information and knowledge bases.

Ontological Query Answering with Existential Rules

The need for an ontology layer on data, associated with advanced reasoning mechanisms that can utilise ontology-coded semantics, is recognised by both the database and knowledge representation communities. This paper focuses on the ontology query response problem, where data is queried while taking into account ontology knowledge. To tackle this problem, we consider a logical framework based on existential rules, also known as Tuple-Generating Dependencies or Datalog+/- rules. This framework can also be defined in graph terms. As the implications of queries by existential rules are undecidable, the key challenge is to define the class of decidable rules as large as possible. This paper is a survey of the class of decidable rules, including a review of the main complexity results. It relies largely on previous work presented at IJCAI‘2009 [BLMS09] and KR’2010 [BLM10] (and work developed in the journal paper [BLMS11]) and has been updated to include the latest results.

The ONTORULE Project : Where Ontology Meets Business Rules

The aim of ONTORULE is to enable users, from business executives to business analysts to IT developers, to interact in their own way with the parts of a business application that are relevant to them. This extended abstract describes the approach to business rule application development proposed by the ONTORULE project and presents the architecture and semantic technologies developed for this purpose and validated and demonstrated in two pilot applications.

Towards Farsighted Dependencies for Existential Rules

We consider existential rules (also called tuple-generating dependencies or Datalog+/- rules). These rules are particularly suited to the timely ontological query-response problem of querying data while considering term knowledge. As this problem is generally undecidable, various conditions guaranteeing decidability have been proposed in the literature. In this paper, we focus on conditions that restrict the way rules interact in order to guarantee that the forward chaining mechanism is finite. After a review of existing proposals, a generalisation of the notion of rule dependence called k-dependence is proposed. It can also be used for rule-based compilation, leading to improved query answering algorithms.

Context-Dependent OWL Reasoning in Sindice – Experiences and Lessons Learnt

Sindice’s Semantic Web Index can search over 260 million documents. Inferring web data can make explicit what was tacit knowledge, adding value to the information and ultimately enabling Sindice to be more competitive in accuracy and recall. However, due to the scale and heterogeneity of web data, the inference engine of the Sindice system needs to (1) scale out by parallelisation on clusters of machines and (2) cope with unexpected data usage. This paper reports on the experiences and lessons learnt in building a large-scale inference engine for Sindice. This inference approach has been introduced, used and refined for Sindice since 2008.

Little Knowledge Rules the Web: Domain-Centric Result Page Extraction

Web extraction is the process of turning unstructured HTML into structured data. Previous approaches have relied solely on detecting repeated structures in the result pages. Such approaches require intensive user interaction in exchange for accuracy.

This paper presents the Amber (‘Adaptable Model-based Extraction of Result Pages’) system, which replaces human interaction with a domain ontology applicable to all sites in the domain. It models domain knowledge about (1) domain records and attributes, (2) low-level (textual) representations of these concepts, and (3) constraints linking the representations to records and attributes. By parameterising these constraints, the domain-independent heuristic derives attributes and records using the iterative structure of the results page. Amber is implemented with logic rules that allow an explicit formulation of the heuristic and easy adaptation to different domains.

We applied Amber to the UK property domain and achieved near perfect accuracy on a representative sample of 50 agency websites.

Conjunctive Query Answering in Probabilistic Datalog+/– Ontologies

Datalog+/- is a recently developed ontology language that is particularly useful for representing and reasoning about lightweight ontologies and is considered to play a central role in the context of query response and information extraction for the Semantic Web. In addition to uncertainty as an intrinsic aspect of the web, uncertainty due to inconsistency and incompleteness, uncertainty due to automatic processing of web data and uncertainty due to the integration of multiple heterogeneous data sources must also be addressed. This paper presents two algorithms for answering connection queries for probabilistic extensions of guarded Datalog+/- using Markov logic networks as probabilistic semantics. The conjunctive query is ‘What is the probability that a given set of atoms is valid? These queries are particularly relevant for web information extraction. This is because extractors often deal with uncertain rules and facts, and have to make decisions based on the likelihood that certain facts can be inferred. The first algorithm for answering conjunctive queries is basic, using classical forward chaining (known as the chase procedure), while the second algorithm is a backward chaining algorithm, which operates on a specific subset of guarded Datalog+/-.

Paraconsistent Semantics for Hybrid MKNF Knowledge Bases

Hybrid MKNF knowledge bases were originally based on stable model semantics, a mature method that combines rules and descriptive logic (DL). Grounded semantics have been proposed for such knowledge bases to improve the efficiency of reasoning. However, the integration of rules and DLs can lead to inconsistencies, even if they are consistent with each other. Therefore, conventional reasoning systems based on the two semantics will break down. In this paper, we employ the four-valued logic proposed by Belnap and present a parallel consistent semantics that can detect and effectively handle inconsistencies for hybrid MKNF knowledge bases. We also show that our proposed semantics can be transformed into stable model semantics via linear transformation operators and that the data complexity in our paradigm is no higher than in classical reasoning. Furthermore, we provide a fixpoint algorithm for computing paraconsistent MKNF models.

Linked Rules: Principles for Rule Reuse on the Web

An ontology is an information model that provides vocabulary, terms and associated meanings to model a domain. An ontology is a shared conceptualisation. In recent years, this has never been truer, as ontologies have been developed through the efforts of a community that includes experts from academia as well as industry. These efforts have been complemented by the standardisation of formats and languages for representing and (re)using ontologies and data on the (semantic) web, such as RDF, OWL and SPARQL. Rules, on the other hand, are (rarely) used for knowledge representation (defining semantics and integrity constraints). Rules are also used for other intelligent reasoning tasks, such as business logic and policy definition. With the proliferation of shared information models, sharing and re-use of rules is possible and may be necessary. Furthermore, the emergence of the Rule Interchange Format (RIF) allows rules to be shared between many rule systems. We propose a set of basic principles and features for representing and sharing rules on the web so that rules can be effectively re-used, and show some ways of rule re-use. Finally, we describe how some of these features work in practice in the N3-based AIR web rules language.

Polynomial Conjunctive Query Rewriting under Unary Inclusion Dependencies

Ontology-based data access (OBDA) is widely accepted as a key element of the new generation of information systems: in the OBDA paradigm, potentially incomplete relational data is enriched by ontologies that represent extended knowledge of the application domain. We consider the problem of conjunctive query response in OBDA. Certain ontology languages have been identified as FO rewritable (e.g. DL-Lite and TGD sticky join sets). However, all known query rewriting techniques produce queries that increase the user query size exponentially, which can be a serious problem for standard relational database engines. In this paper, we present polynomial query rewriting for conjunctive queries under binary inclusion dependencies. On the other hand, we show that binary inclusion dependencies do not admit polynomial query rewriting algorithms.

Reasoning as Axioms Change

This paper introduces a new incremental algorithm for computing changes of materialised views in logical databases, such as those used in rule-based reasoners. Such reasoners have to deal with the problem of changing axioms in the presence of materialising derived atoms. Existing approaches have drawbacks: some need to generate and evaluate large transformed programmes that are Datalog¬ whereas the source programme is Datalog¬, and others recalculate the entire extension, even if only a small part of the predicate extension is affected by the change There are. The method presented in this paper overcomes both of these drawbacks.

Query Rewriting for Inconsistent DL-Lite Ontologies

In this paper, we study the problem of obtaining meaningful answers to queries for inconsistent DL – Lite ontologies. We consider various variants of inconsistency-tolerant semantics and show that for some of such variants, the answer to a conjunctive query (UCQ) is first-order (FOL) rewritable, i.e. it can be reduced to a standard evaluation of FOL/SQL queries against a database. The FOL rewritability of UCQs for consistent ontologies is one of the features of DL – Lite. Therefore, we show that in such a setting, inconsistency tolerant query responses have the same computational complexity as standard query responses and can rely on established relational database technology as well as under standard DL semantics.

Decidability of Unification in EL without Top Constructor

Descriptive logic has attracted much attention in recent years. Description logic is a knowledge representation formalism used in natural language processing, the organisation of technical systems, databases and biomedical ontologies. There, unification is used as a tool for recognising equivalent concepts. It has been proved that unification in is NP-complete. has been proved to be NP-complete. This result is based on the locality property of certain unifiers. Indeed, the SNOMED CT, a large medical ontology, is built on a subset of the ++ formalism, but without top concepts. It is interesting to investigate the decidability of unification in extensions that do not use top concepts. In this paper we investigate the decidability of unification in We show that the same locality holds for unification in However, as in the case of unification in , unification does not follow immediately from locality. However, by further restricting the locality, we prove that and construct a NExpTime decision procedure for this problem. Furthermore, this procedure allows us to compute a specific set of solutions to the unification problem.

On the Equivalence between the Action Language and Partial Actions in Transaction Logic

Transaction logic with partially defined actions (TR PAD) is an expressive formalism for inferring the effects of actions and declaratively specifying transactions that change state. Action languages are well-known formalisms for describing changing domains and inferring actions. The aim of this paper is to compare these two formalisms and identify their similarities and divergences to better understand their modelling and reasoning capabilities. The paper provides a sound asymptotic formula for a large fragment of TR PAD and shows that this asymptotic formula is complete with respect to the LP embedding of .PAD. It also explores how action planning is modelled in both languages and discusses its relationship to other languages that represent behaviour.

Reasoning with Actions in Transaction Logic

This paper introduces TR PAD (Transaction Logic with Partially Defined Actions) – an expressive formalism for reasoning about the effects of combined actions – TR PAD is based on a subset of Transaction Logic but extended with special premise formulae that generalise the data and transition formulae of the original Transaction Logic. We develop a sound and complete proof theory for TR PAD and illustrate its formalism with many non-trivial examples. Furthermore, we show that a large part of TR PAD is reducible to ordinary logic programming and that this reduction is sound and complete.

Interpolation and Extrapolation in Conceptual Spaces: A Case Study in the Music Domain

In most knowledge representations, atomic properties correspond to natural language labels. Although these labels are usually considered primitive, automating certain forms of commonsense reasoning requires background knowledge about the cognitive meaning of these labels. We consider two forms of such commonsense reasoning, which we call interpolative and extrapolative reasoning. In both cases, rule-based knowledge is augmented with knowledge about the geometric representation of labels in the concept space. Specifically, to support interpolative reasoning, it is necessary to know which labels are conceptually between other labels, given that intermediate conditions tend to lead to intermediate conclusions. Extrapolative reasoning is based on information about the direction of change required in replacing one label with another, from the perspective that parallel changes in the conditions of a rule tend to lead to parallel changes in its conclusions. This paper proposes a practical method for acquiring knowledge about the conceptual space representation of such labels. The paper illustrates this method in the domain of music genres from metadata obtained from the music recommendation website last.fm.

Improve Efficiency of Mapping Data between XML and RDF with XSPARQL

XSPARQL is a language for converting data between the tree-based XML format and the graph-based RDF format XML is a widely adopted data exchange format, accompanied by its own query language XQuery; RDF is a standard Semantic Web XSPARQL is a query language that integrates XQuery and SPARQL and provides a more intuitive and maintainable way to convert data between the two data formats. implementation can be inefficient when evaluating nested queries. However, such queries occur frequently in practice when dealing with XML data. Several approaches for optimising nested queries are presented and compared. Implementing these optimisations can improve efficiency by up to two orders of magnitude in practical evaluation.

A Smart Campus Prototype for Demonstrating the Semantic Integration of Heterogeneous Data

This paper describes the implementation of a prototype smart campus application that integrates heterogeneous data using semantic technologies. The prototype is based on a layered semantic architecture that facilitates semantic data access and integration using OWL, SWRL and SPARQL. The focus of this paper is on the implementation of the prototype and lessons learned from its development.

An Ontological Approach for Modeling Technical Standards for Compliance Checking

This paper outlines a formal semantic-based approach to modelling several regulations in the photovoltaic sector to support the implementation of technical assessments at the French Centre for Science of the Building Industry (CSTB). Starting from the text of the regulations, we first specify the SBVR rules and then formalise them into ontology-based rules in the SPARQL language. These are used for modelling the compliance checking process required to carry out the technical assessment.

Integrating Linked Data through RDFS and OWL: Some Lessons Learnt

In this paper, the PhD thesis ‘Exploiting RDFS and OWL for Integrating Heterogeneous, Large-Scale, Linked Data Corpora’ Summarises lessons learned from the In this paper, three use cases for reasoning on linked data were considered. It summarises how to overcome the scalability and robustness challenges faced when reasoning on linked data. We validate our method against an open domain corpus of 1.1 billion quadruple representations crawled from 4 million Linked Data documents and discuss the applicability and usefulness of our reasoning method in such a scenario.

Instant Feedback on Discovered Association Rules with PMML-Based Query-by-Example

A longstanding research challenge in the association rule mining task is to identify, from the large number of rules discovered, which rules are interesting for domain experts. We demonstrate a new feature of the SEWEBAR-CMS system, which uses an arbitrary rule as an example query to discover, with one click, whether this rule has an interesting relationship with a rule already stored in the knowledge base, using an XML-based declarative language such as PMML, XSLT transformations to add new relationships.

Local Closed World Semantics: Grounded Circumscription for Description Logics

We present an improved local closed bound extension for description logics. This extension is based on circumscription and deviates from previous circumscription description logics [1,3] in that the extension of minimisation predicates can only include extensions of named individuals in the knowledge base. This improved semantics is not only highly intuitively appealing, but can be applied to expressive description logics without losing reversibility.

RDF Semantics for Web Association Rules

We present a lexical extension to RDFS that allows assertions on the rules that hold for associations between sets of RDFS classes, interacting with class subassumptions and instance typing, and a language extension that appropriately captures the meaning typically given to association rules with context, support and confidence statements with real-world semantics. Furthermore, it presents a sound and complete procedure for the association rule inclusion problem.

Root Justifications for Ontology Repair

An ontology (also called a glossary or knowledge base) is an entity used to represent a domain (field of knowledge). Typically, ontology components include categories (concepts), relations (roles) and objects (individuals).

Description Logic (DL) is a class of knowledge representation languages suitable for formalising and reasoning about ontologies [1]. The reasoning process is performed by a selected DL reasoner. We do not provide a comprehensive introduction to DLs, but refer the reader to the book by Baader et al [1].

ELOG: A Probabilistic Reasoner for OWL EL

Log-linear descriptive logic is a probabilistic logic that combines several concepts and methods from the fields of knowledge representation and inference and statistical relational AI. We describe in detail the implementation of the log-linear reasoner ELOG. The reasoner employs database techniques to dynamically transform the inference problem into an integer linear programme (ILP); to reduce the size and complexity of the ILP, a form of truncated planar reasoning is employed during inference.

Combining Production Systems and Ontologies

Production systems are an established paradigm in knowledge representation and ontologies are widely used to model and reason about application domains. Description logics are the basis of, for example, the web ontology language OWL, which is a well-studied formalism for representing ontologies. In this study, production systems (ps) and description logics (dl) are combined to enable ontology languages to express both facts and rules.

We explore the space of design options for combining the traditional closed-world semantics of ps with the open-world semantics of dl, and propose a general semantics for such a combination. We show how our semantics can be encoded in a fixpoint extension of first-order logic. Show that in special cases (monotonic and light PS), checking system properties such as termination is decidable.

MapResolve

We propose a MapReduce-based approach to scalable reasoning for description logic ontologies. Our work is inspired by previous work that proposed MapReduce for more expressive logic, providing fast materialisation of RDFS ontologies. We describe the challenges imposed by higher expressiveness and how they can be solved.

Inline Evaluation of Hybrid Knowledge Bases

The deployment of knowledge representation formalisms on the web has created the need for hybrid formalisms that combine heterogeneous knowledge bases. The aim of this research is to improve the efficiency of reasoning on hybrid knowledge bases (KBs). The traditional reasoning method for hybrid knowledge bases is to use different reasoners to access different data sources, which causes overhead. To improve this, we propose a new strategy called inline evaluation. Thus, a single reasoner can be used to perform the inference task, improving the efficiency of hybrid inference.

Web Reasoning and Rule Systems

Web Reasoning and Rule Systems

contents

コメント