nach oben

2014 | Buch

Kapitel lesen Erstes Kapitel lesen

Web Reasoning and Rule Systems

8th International Conference, RR 2014, Athens, Greece, September 15-17, 2014. Proceedings

herausgegeben von: Roman Kontchakov, Marie-Laure Mugnier

Verlag: Springer International Publishing

Buchreihe : Lecture Notes in Computer Science

Enthalten in: Springer Professional "Wirtschaft+Technik" , Springer Professional "Technik" , Springer Professional "Wirtschaft"

Einloggen, um Zugang zu erhalten

Über dieses Buch

This book constitutes the refereed proceedings of the 8th International Conference on Web Reasoning and Rule Systems, RR 2014, held in Athens, Greece in September 2014. The 9 full papers, 9 technical communications and 5 poster presentations presented together with 3 invited talks, 3 doctoral consortial papers were carefully reviewed and selected from 33 submissions. The conference covers a wide range of the following: semantic Web, rule and ontology languages, and related logics, reasoning, querying, searching and optimization, incompleteness, inconsistency and uncertainty, non-monotonic, common sense, and closed-world reasoning for the web, dynamic information, stream reasoning and complex event processing, decision making, planning, and intelligent agents, machine learning, knowledge extraction and information retrieval, data management, data integration and reasoning on the web of data, ontology-based data access, system descriptions, applications and experiences.

Inhaltsverzeichnis

Frontmatter

Invited Talks

P ≠ P

Why Some Reasoning Problems Are More Tractable Than Others

Abstract

Knowledge representation and reasoning leads to a wide range of computational problems, and it is of great interest to understand the difficulty of these problems. Today this question is mainly studied using computational complexity theory and algorithmic complexity analysis. For example, entailment in propositional Horn logic is P-complete and a specific algorithm is known that runs in linear time. Unfortunately, tight algorithmic complexity bounds are rare and often based on impractical algorithms (e.g., O(n ^2.373) for transitive closure by matrix multiplication), whereas computational complexity results abound but are very coarse-grained (e.g., many P-complete problems cannot be solved in linear time).

In this invited paper, we therefore advocate another approach to gauging the difficulty of a computation: we reformulate computational problems as query answering problems, and then ask how powerful a query language is needed to solve these problems. This reduces reasoning problems to a computational model – query answering – that is supported by many efficient implementations. It is of immediate practical interest to know if a problem can be reduced to query answering in an existing database system. On the theoretical side, it allows us to distinguish problems in a more-fine grained manner than computational complexity without being specific to a particular algorithm. We provide several examples of this approach and discuss its merits and limitations.

Markus Krötzsch

Web Reasoning for Cultural Heritage

Abstract

Cultural Heritage is the focus of a great and continually increasing number of R&D initiatives, aiming at efficiently managing and disseminating cultural resources on the Web. As more institutions make their collections available online and proceed to aggregate them in domain repositories, knowledge-based management and retrieval becomes a necessary evolution from simple syntactic data exchange. In the process of aggregating heterogeneous resources and publishing them for retrieval and creative reuse, networks such as Europeana and DPLA invest in technologies that achieve semantic data integration. The resulting repositories join the Linked Open Data cloud, allowing to link cultural heritage domain knowledge to existing datasets. Integration of diverse information is achieved through the use of formal ontologies, enabling reasoning services to offer powerful semantic search and navigation mechanisms.

Alexandros Chortaras, Nasos Drosopoulos, Ilianna Kollia, Nikolaos Simou

Full Papers

Planning with Transaction Logic

Abstract

Automated planning has been the subject of intensive research and is at the core of several areas of AI, including intelligent agents and robotics. In this paper, we argue that Transaction Logic is a natural specification language for planning algorithms, which enables one to see further afield and thus discover better and more general solutions than using one-of-a-kind formalisms. Specifically, we take the well-known \({\textit{STRIPS}}\) planning strategy and show that Transaction Logic lets one specify the \({\textit{STRIPS}}\) planning algorithm easily and concisely, and to prove its completeness. Moreover, extensions to allow indirect effects and to support action ramifications come almost for free. Finally, the compact and clear logical formulation of the algorithm made possible by this logic is conducive to fruitful experimentation. To illustrate this, we show that a rather simple modification of the \({\textit{STRIPS}}\) planning strategy is also complete and yields speedups of orders of magnitude.

Reza Basseda, Michael Kifer, Anthony J. Bonner

A Generalization of Approximation Fixpoint Theory and Application

Abstract

The approximation fixpoint theory (AFT) provides an algebraic framework for the study of fixpoints of operators on bilattices, and has been useful in dealing with semantics issues for various types of logic programs. The theory in the current form, however, only deals with consistent pairs on a bilattice, and it thus does not apply to situations where inconsistency may be part of a fixpoint construction. This is the case for FOL-programs, where a rule set and a first-order theory are tightly integrated. In this paper, we develop an extended theory of AFT that treats consistent as well as inconsistent pairs on a bilattice. We then apply the extended theory to FOL-programs and explore various possibilities on semantics. This leads to novel formulations of approximating operators, and new well-founded semantics and characterizations of answer sets for FOL-programs. The work reported here shows how consistent approximations may be extended to capture wider classes of logic programs whose semantics can be treated uniformly.

Yi Bi, Jia-Huai You, Zhiyong Feng

Query Answering over Contextualized RDF/OWL Knowledge with Forall-Existential Bridge Rules: Attaining Decidability Using Acyclicity

Abstract

The recent outburst of context-dependent knowledge on the Semantic Web (SW) has led to the realization of the importance of the quads in the SW community. Quads, which extend a standard RDF triple, by adding a new parameter of the ‘context’ of an RDF triple, thus informs a reasoner to distinguish between the knowledge in various contexts. Although this distinction separates the triples in an RDF graph into various contexts, and allows the reasoning to be decoupled across various contexts, bridge rules need to be provided for inter-operating the knowledge across these contexts. We call a set of quads together with the bridge rules, a quad-system. In this paper, we discuss the problem of query answering over quad-systems with expressive forall-existential bridge rules. It turns out the query answering over quad-systems is undecidable, in general. We derive a decidable class of quad-systems, namely context-acyclic quad-systems, for which query answering can be done using forward chaining. Tight bounds for data and combined complexity of query entailment has been established for the derived class.

Mathew Joseph, Gabriel Kuper, Luciano Serafini

Computing Datalog Rewritings for Disjunctive Datalog Programs and Description Logic Ontologies

Abstract

We study the closely related problems of rewriting disjunctive datalog programs and non-Horn DL ontologies into plain datalog programs that entail the same facts for every dataset. We first propose the class of markable disjunctive datalog programs, which is efficiently recognisable and admits polynomial rewritings into datalog. Markability naturally extends to \(\mathcal{SHI}\) ontologies, and markable ontologies admit (possibly exponential) datalog rewritings. We then turn our attention to resolution-based rewriting techniques. We devise an enhanced rewriting procedure for disjunctive datalog, and propose a second class of \(\mathcal{SHI}\) ontologies that admits exponential datalog rewritings via resolution. Finally, we focus on conjunctive query answering over disjunctive datalog programs. We identify classes of queries and programs that admit datalog rewritings and study the complexity of query answering in this setting. We evaluate the feasibility of our techniques over a large corpus of ontologies, with encouraging results.

Mark Kaminski, Yavor Nenov, Bernardo Cuenca Grau

Querying Temporal Databases via OWL 2 QL

Abstract

SQL:2011, the most recently adopted version of the SQL query language, has unprecedentedly standardized the representation of temporal data in relational databases. Following the successful paradigm of ontology-based data access, we develop a practical approach to querying the SQL:2011-based temporal data model via the semantic layer of OWL 2 QL. The interval-based temporal query language (TQL), which we propose for this task, is based on naturally characterizable combinations of temporal logic with conjunctive queries. As the central contribution, we present rules for sound and complete rewriting of TQL queries into two-sorted first-order logic, and consequently, into corresponding SQL queries, which can be evaluated in any existing relational database management system compliant with the SQL:2011 temporal data model. Importantly, the proposed rewriting is based on the direct reuse of the standard rewriting techniques for conjunctive queries under OWL 2 QL. This renders our approach modular and easily implementable. As a notable corollary, we show that the data complexity of TQL query answering remains in AC⁰, i.e., as in the usual, non-temporal case.

Szymon Klarman, Thomas Meyer

Towards Mapping Analysis in Ontology-Based Data Access

Abstract

In this paper we study mapping analysis in ontology-based data access (OBDA), providing an initial set of foundational results for this problem. We start by defining general, language-independent notions of mapping inconsistency, mapping subsumption, and mapping redundancy in OBDA. Then, we focus on specific mapping languages for OBDA and illustrate techniques for verifying the above properties of mappings.

Domenico Lembo, Jose Mora, Riccardo Rosati, Domenico Fabio Savo, Evgenij Thorstensen

Conjunctive Query Answering in Finitely-Valued Fuzzy Description Logics

Abstract

Fuzzy Description Logics (DLs) generalize crisp ones by providing membership degree semantics for concepts and roles. A popular technique for reasoning in fuzzy DL ontologies is by providing a reduction to crisp DLs and then employ reasoning in the crisp DL. In this paper we adopt this approach to solve conjunctive query (CQ) answering problems for fuzzy DLs. We give reductions for Gödel, and Łukasiewicz variants of fuzzy

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-11113-1_9/978-3-319-11113-1_9_IEq1_HTML.gif

and two kinds of fuzzy CQs. The correctness of the proposed reduction is proved and its complexity is studied for different fuzzy variants of

https://static-content.springer.com/image/chp%3A10.1007%2F978-3-319-11113-1_9/978-3-319-11113-1_9_IEq2_HTML.gif

Theofilos Mailis, Rafael Peñaloza, Anni-Yasmin Turhan

Exchange-Repairs: Managing Inconsistency in Data Exchange

Abstract

In a data exchange setting with target constraints, it is often the case that a given source instance has no solutions. Intuitively, this happens when data sources contain inconsistent or conflicting information that is exposed by the target constraints at hand. In such cases, the semantics of target queries trivialize, because the certain answers of every target query over the given source instance evaluate to “true”. The aim of this paper is to introduce and explore a new framework that gives meaningful semantics in such cases by using the notion of exchange-repairs. Informally, an exchange-repair of a source instance is another source instance that differs minimally from the first, but has a solution. In turn, exchange-repairs give rise to a natural notion of exchange-repair certain answers (in short, XR-certain answers) for target queries in the context of data exchange with target constraints.

After exploring the structural properties of exchange-repairs, we focus on the problem of computing the XR-certain answers of conjunctive queries. We show that for schema mappings specified by source-to-target GAV dependencies and target equality-generating dependencies (egds), the XR-certain answers of a target conjunctive query can be rewritten as the consistent answers (in the sense of standard database repairs) of a union of source conjunctive queries over the source schema with respect to a set of egds over the source schema, thus making it possible to use a consistent query-answering system to compute XR-certain answers in data exchange. In contrast, we show that this type of rewriting is not possible for schema mappings specified by source-to-target LAV dependencies and target egds. We then examine the general case of schema mappings specified by source-to-target GLAV constraints, a weakly acyclic set of target tgds and a set of target egds. The main result asserts that, for such settings, the XR-certain answers of conjunctive queries can be rewritten as the certain answers of a union of conjunctive queries with respect to the stable models of a disjunctive logic program over a suitable expansion of the source schema.

Balder ten Cate, Richard L. Halpert, Phokion G. Kolaitis

Rules and Ontology Based Data Access

Abstract

In OBDA an ontology defines a high level global vocabulary for user queries, and such vocabulary is mapped to (typically relational) databases. Extending this paradigm with rules, e.g., expressed in SWRL or RIF, boosts the expressivity of the model and the reasoning ability to take into account features such as recursion and n-ary predicates. We consider evaluation of SPARQL queries under rules with linear recursion, which in principle is carried out by a 2-phase translation to SQL: (1) The SPARQL query, together with the RIF/SWRL rules, and the mappings is translated to a Datalog program, possibly with linear recursion; (2) The Datalog program is converted to SQL by using recursive common table expressions. Since a naive implementation of this translation generates inefficient SQL code, we propose several optimisations to make the approach scalable. We implement and evaluate the techniques presented here in the Ontop system. To the best of our knowledge, this results in the first system supporting all of the following W3C standards: the OWL 2 QL ontology language, R2RML mappings, SWRL rules with linear recursion, and SPARQL queries. The preliminary but encouraging experimental results on the NPD benchmark show that our approach is scalable, provided optimisations are applied.

Guohui Xiao, Martin Rezk, Mariano Rodríguez-Muro, Diego Calvanese

Technical Communications

Semantic Search for Earth Observartion Products using Ontology Services

Abstract

Access to Earth Observation products remains difficult for end users in most domains. Although various search engines have been developed, they neither satisfy the needs of scientific communities for advanced search of EO products, nor do they use standardized vocabularies reusable from other organizations. To address this, we present the Prod-Trees platform, a semantically-enabled search engine for EO products enhanced with EO-netCDF, a new standard for accessing Earth Observation products.

Maria Karpathiotaki, Kallirroi Dogani, Manolis Koubarakis, Bernard Valentin, Paolo Mazzetti, Mattia Santoro, Sabina Di Franco

Airport Context Analytics

Abstract

Airports today can constitute a perfect environment for developing novel digital marketplaces offering location-specific and semantically rich context-aware services, such as personalized marketing campaigns, last minute, discounted airline tickets while helping users access the airport and speed through the airport process.

Underpinning the above vision is the ability to target service content to users’ current context, e.g., their location, intent, environment, in real time. The contribution of this work is that it uses a pervasive computing system with three key ingredients: (a) a data model, comprising user and service content entities, (b) a user context model and (c) rules for simple pattern matching on service content and user context event streams. This modus operandi is encapsulated inside a SOA architecture, the Common Airport Portal - CAP and it is illustrated through the description of a real application, Offers and Coupons Services that was deployed recently at Athens International Airport (AIA) (http://airpoint.gr).

Eli Katsiri, George Papastefanatos, Manolis Terrovitis, Timos Sellis

Navigating among Educational Resources in the Web of Linked Data

Abstract

Linked Data seem to play a seminal role in the establishment of the Semantic Web as the next-generation Web. This is even more important for digital object collections and educational institutions that aim not only to promote and disseminate their content but also to aid its discoverability and contextualization. Having already ‘semantified’ a popular digital repository system, DSpace, in this paper we show how repository metadata can be exposed as Linked Data, thus enhancing their machine understandability and contributing to the LOD cloud. Our effort comes complete with an updated UI that allows for reasoning-based search and navigation between linked resources within and outside the scope of the digital repository.

Dimitrios A. Koutsomitropoulos, Georgia D. Solomou, Aikaterini K. Kalou

Investigating Information Diffusion in a Multi-Social-Network Scenario via Answer Set Programming

Abstract

Information Diffusion is a classical problem in Social Network Analysis, where it has been deeply investigated for single social networks. In this paper, we begin to study it in a multi-social-network scenario, where many social networks coexist and are strictly connected to each other, thanks to those users who join more social networks. In this activity, Answer Set Programming provided us with a powerful and flexible tool for an easy set-up and implementation of our investigations.

Giuseppe Marra, Antonino Nocera, Francesco Ricca, Giorgio Terracina, Domenico Ursino

Web Stream Reasoning Using Probabilistic Answer Set Programming

Abstract

We propose a framework for reasoning about dynamic Web data, based on probabilistic Answer Set Programming (ASP). Our approach, which is prototypically implemented, allows for the annotation of first-order formulas as well as ASP rules and facts with probabilities, and for learning of such weights from examples (parameter estimation). Knowledge as well as examples can be provided incrementally in the form of RDF data streams. Optionally, stream data can be configured to decay over time. With its hybrid combination of various contemporary AI techniques, our framework aims at prevalent challenges in relation to data streams and Linked Data, such as inconsistencies, noisy data, and probabilistic processing rules.

Matthias Nickles, Alessandra Mileo

Efficient Federated Debugging of Lightweight Ontologies

Abstract

In the last years ontologies have been applied increasingly as a conceptual view facilitating the federation of numerous data sources using different access methods and data schemes. Approaches such as ontology-based data integration (OBDI) are aimed at this purpose. According to these approaches, queries formulated in an ontology describing the knowledge domain as a whole are translated into queries formulated in vocabularies of integrated data sources. In such integrative environments the increasing number of heterogeneous data sources increases the risk of inconsistencies. These inconsistencies become a serious obstacle for leveraging the full potential of approaches like OBDI since inconsistencies can be hardly identified by existing reasoning algorithms, which mostly have been developed for processing of locally available knowledge bases. In this paper we present an alternative approach for efficient federated debugging. Our solution relies on the generation of so called clash queries that are evaluated over all integrated data sources. We further explain how these queries can be used for pinpointing those assertions that cause inconsistencies and discuss finally some experimental evaluation results of our implementation.

Andreas Nolle, Christian Meilicke, Heiner Stuckenschmidt, German Nemirovski

Revisiting the Hardness of Query Answering in Expressive Description Logics

Abstract

Answering conjunctive queries over Description Logic (DL) knowledge bases is known to be 2ExpTime-hard for the DLs \(\mathcal{ALCI}\), \(\mathcal{SH}\), and their extensions. In this technical note, we revisit these results to identify other equally hard settings. In particular, we show that a simple adaptation of the proof for \(\mathcal{SH}\) proves that query answering is 2ExpTime-hard already for \(\mathcal{ALC}\) if we consider more expressive query languages such as positive existential queries and (restricted classes of) conjunctive regular path queries.

Magdalena Ortiz, Mantas Šimkus

An Ontology for Container Terminal Operations

Abstract

In this paper we describe the desctop ontology for container terminal operations. It is a semantic-based representation of the main functions of a container terminal, in order to formally represent the operational flows which the terminal operators should be supported in.

Luca Pulina

Hydrowl: A Hybrid Query Answering System for OWL 2 DL Ontologies

Abstract

This system description paper introduces the OWL 2 query answering system Hydrowl. Hydrowl is based on novel hybrid techniques which in order to compute the query answers combine at run-time a reasoner ans ₁ supporting a (tractable) fragment of OWL 2 (e.g., OWL 2 QL and OWL 2 RL) with a fully-fledged OWL 2 DL reasoner ans ₂. The motivation is that if most of the (query answering) work is delegated to the (usually) very scalable system ans ₁ while the interaction with ans ₂ is kept to a bare minimum, then we can possibly provide with scalable query answering even over expressive fragments of OWL 2 DL. We discuss the system’s architecture and we present an overview of the techniques used. Finally, we present some first encouraging experimental results.

Giorgos Stoilos

Backmatter

Titel: Web Reasoning and Rule Systems
herausgegeben von: Roman Kontchakov
Marie-Laure Mugnier
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-11113-1
Print ISBN: 978-3-319-11112-4
DOI: https://doi.org/10.1007/978-3-319-11113-1

Springer Professional

Über dieses Buch

Inhaltsverzeichnis

Frontmatter

Invited Talks

P ≠ P

Web Reasoning for Cultural Heritage

Full Papers

Planning with Transaction Logic

A Generalization of Approximation Fixpoint Theory and Application

Query Answering over Contextualized RDF/OWL Knowledge with Forall-Existential Bridge Rules: Attaining Decidability Using Acyclicity

Computing Datalog Rewritings for Disjunctive Datalog Programs and Description Logic Ontologies

Querying Temporal Databases via OWL 2 QL

Towards Mapping Analysis in Ontology-Based Data Access

Conjunctive Query Answering in Finitely-Valued Fuzzy Description Logics

Exchange-Repairs: Managing Inconsistency in Data Exchange

Rules and Ontology Based Data Access

Technical Communications

Semantic Search for Earth Observartion Products using Ontology Services

Airport Context Analytics

Navigating among Educational Resources in the Web of Linked Data

Investigating Information Diffusion in a Multi-Social-Network Scenario via Answer Set Programming

Web Stream Reasoning Using Probabilistic Answer Set Programming

Efficient Federated Debugging of Lightweight Ontologies

Revisiting the Hardness of Query Answering in Expressive Description Logics

An Ontology for Container Terminal Operations

Hydrowl: A Hybrid Query Answering System for OWL 2 DL Ontologies

Backmatter

Premium Partner