nach oben

2016 | Buch

Kapitel lesen Erstes Kapitel lesen

Web Reasoning and Rule Systems

10th International Conference, RR 2016, Aberdeen, UK, September 9-11, 2016, Proceedings

herausgegeben von: Magdalena Ortiz, Stefan Schlobach

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 10th International Conference on Web Reasoning and Rule Systems, RR 2016, held in Aberdeen, Scotland, UK, in September 2016.The 10 full papers and 3 technical communications presented were carefully reviewed and selected from 17 submissions. Extensions and adaptations of classical rule-based languages have found their application in a range of areas, such as ontologies for the semantic web; querying web data; semantic data management; common-sense reasoning on the web

Inhaltsverzeichnis

Frontmatter

On the Complexity of Evaluating Regular Path Queries over Linear Existential Rules

Abstract

In the setting of ontology-mediated query answering, a query is evaluated over a knowledge base consisting of a database instance and an ontology. While most work in the area focuses on conjunctive queries, navigational queries are gaining increasing attention. In this paper, we investigate the complexity of evaluating the standard form of navigational queries, namely two-way regular path queries, over knowledge bases whose ontology is expressed by means of linear existential rules. More specifically, we show how to extend an approach developed for DL-Lite\(_\mathcal {R}\) to obtain an exponential-time decision procedure for linear rules. We prove that this algorithm achieves optimal worst-case complexity by establishing a matching ExpTime lower bound.

Meghyn Bienvenu, Michaël Thomazo

Towards Practical OBDA with Temporal Ontologies

(Position Paper)

Abstract

The temporal dimension of data, which contains such important information as duration or sequence of events and is present in many applications of ontology-based data access (OBDA) concerned with logs or streams, is getting growing attention in the community. To give a proper treatment to the events occurring in the data from the ontological perspective, we assume in our approach that every concept is temporalized, i.e., has temporal validity time, and the ontology language expresses the constraints between validity times of concepts. In this paper we outline the state of art and the future challenges of our research. On the theoretical side, we are interested in enriching the ontology languages with the operators for constructing the temporal concepts that are expressive enough to capture the patterns required by industrial use-cases. On the practical side, we are interested in implementing the ontology-mediated query answering with temporalized concepts in the OBDA system Ontop and performing extensive evaluations using large amounts of real-world data.

Diego Calvanese, Elem Güzel Kalaycı, Vladislav Ryzhikov, Guohui Xiao

Semantic Analysis of R2RML Mappings for Ontology-Based Data Access

Abstract

Ontology-based data access (OBDA) deals with the problem of accessing autonomous data sources through a shared, virtual ontology, and declarative mappings connecting the data sources to the ontology. The W3C standard R2RML allows for mapping relational data sources to RDFS/OWL ontologies. In this paper, we present algorithms for the semantic analysis of R2RML mappings in the OBDA setting, when the ontology is expressed in OWL 2 QL. The focus of such algorithms is to identify the main semantical anomalies (inconsistency and redundancy) of a mapping specification with respect to the ontology and/or the data sources. Such algorithms have been implemented in the mapping analysis tool developed within the Optique European project. We also report on the experiments conducted within the Optique project use cases.

Cristina Civili, Jose Mora, Riccardo Rosati, Marco Ruzzi, Valerio Santarelli

Validating Ontologies Against OWL 2 Profiles with the SPARQL Template Transformation Language

Abstract

In this paper we address the general research question of How can we express constraints on RDF data and how can we check that an RDF graph satisfies some given constraints? and we focus on expressing constraints defining OWL 2 profiles and checking these constraints for OWL validation. We propose an approach based on the SPARQL Template Transformation language (STTL). An STTL template is a transformation rule that applies to a given RDF graph and the recursive call of a set of STTL templates on an RDF graph outputs some textual data resulting from the transformation of this graph. We show that STTL can be used as a constraint language for RDF and we use it to implement the semantics of OWL 2 profiles: each profile is represented by a set of STTL templates that a valid ontology must satisfy.

Olivier Corby, Catherine Faron-Zucker, Raphaël Gazzotti

Revisiting Grounded Circumscription in Description Logics

Abstract

Circumscription is a paradigm of non-monotonic logic meant to formalize the common-sense understanding that, among competing theories that represent phenomena equally well, the one with the fewest “abnormal” assumptions should be selected. Several papers have considered ways of adding circumscription to Description Logics. One of the proposals with good computational properties is Grounded Circumscription, introduced by Sengupta, Krishnadi and Hitzler in 2011. Our paper builds on their general idea, but identifies some problems with the original semantics definition, which gives rise to counter-intuitive consequences and renders the proposed tableau algorithm incorrect. We give an example that makes the problem explicit and propose a modification of the semantics that remedies this issue. On the algorithmic side, we show that a big part of the reasoning can actually be transferred to standard Description Logics, for which tools and results already exist.

Stathis Delivorias, Sebastian Rudolph

Query Rewriting under Linear Knowledge Bases

Abstract

With the adoption of the recent SPARQL 1.1 standard, RDF databases are capable of directly answering more expressive queries than simple conjunctive queries. In this paper we exploit such capabilities to answer conjunctive queries (CQs) under ontologies expressed in the description logic called linear \(\mathcal {EL}^ {\ell }in \), a restricted form of \(\mathcal {EL}\). In particular, we show a query answering algorithm that rewrites a given CQ into a conjunctive regular path query (CRPQ) which, evaluated on the given instance, returns the correct answer. Our technique is based on the representation of infinite unions of CQs by non-deterministic finite-state automata. Our results achieve optimal data complexity, as well as producing rewritings straightforwardly implementable in SPARQL 1.1.

Mirko M. Dimartino, Andrea Calì, Alexandra Poulovassilis, Peter T. Wood

Scalable Reasoning by Abstraction Beyond DL-Lite

Abstract

Recently, it has been shown that ontologies with large datasets can be efficiently materialized by a so-called abstraction refinement technique. The technique consists of the abstraction phase, which partitions individuals into equivalence classes, and the refinement phase, which re-partitions individuals based on entailments for the representative individual of each equivalence class. In this paper, we present an abstraction-based approach for materialization in \(\mathrm {DL\text{- }Lite}\), i.e. we show that materialization for \(\mathrm {DL\text{- }Lite}\) does not require the refinement phase. We further show that the approach is sound and complete even when adding disjunctions and nominals to the language. The proposed technique allows not only for faster materialization and classification of the ontologies, but also for efficient consistency checking; a step that is often omitted by practical approaches based on query rewriting. A preliminary empirical evaluation on both real-life and benchmark ontologies demonstrates that the approach can handle ontologies with large datasets efficiently.

Birte Glimm, Yevgeny Kazakov, Trung-Kien Tran

The Impact of Active Domain Predicates on Guarded Existential Rules

Abstract

We claim it is realistic to assume that a database management system provides access to the active domain via built-in relations. Therefore, product databases, i.e., databases that include designated predicates that hold the active domain, form a natural notion that deserves our attention. An important issue then is to look at the consequences of product databases for the expressiveness and complexity of central existential rule languages. We focus on guarded existential rules, and we investigate the impact of product databases on their expressive power and complexity. We show that the queries expressed via (frontier-)guarded rules gain in expressiveness, and in fact, they have the same expressive power as Datalog. On the other hand, there is no impact on the expressiveness of the queries specified via weakly-(frontier-)guarded rules since they are powerful enough to explicitly compute the predicates needed to access the active domain. We also observe that there is no impact on the complexity of the languages in question.

Georg Gottlob, Andreas Pieris, Mantas Šimkus

Negative Knowledge for Certain Query Answers

Abstract

Querying incomplete data usually amounts to finding answers we are certain about. Standard approaches concentrate on positive information about query answers, and miss negative knowledge, which can be useful for two reasons. First, sometimes it is the only type of knowledge one can infer with certainty, and second, it may help one find good and efficient approximations of positive certain answers. Our goal is to consider a framework for defining both positive and negative certain knowledge about query answers and to show two applications of it. First, we demonstrate that it naturally leads to a way of representing certain information that has hitherto not been used in querying incomplete databases. Second, we show that approximations of such certain information can be computed efficiently for all first-order queries over relational databases.

Leonid Libkin

Extending Weakly-Sticky Datalog: Query-Answering Tractability and Optimizations

Abstract

Weakly-sticky (WS) Datalog\(^\pm \) is an expressive member of the family of Datalog\(^\pm \) programs that is based on the syntactic notions of stickiness and weak-acyclicity. Query answering over the WS programs has been investigated, but there is still much work to do on the design and implementation of practical query answering (QA) algorithms and their optimizations. Here, we study sticky and WS programs from the point of view of the behavior of the chase procedure, extending the stickiness property of the chase to that of generalized stickiness of the chase (gsch-property). With this property we specify the semantic class of GSCh programs, which includes sticky and WS programs, and other syntactic subclasses that we identify. In particular, we introduce joint-weakly-sticky (JWS) programs, that include WS programs. We also propose a bottom-up QA algorithm for a range of subclasses of GSCh. The algorithm runs in polynomial time (in data) for JWS programs. Unlike the WS class, JWS is closed under a general magic-sets rewriting procedure for the optimization of programs with existential rules. We apply the magic-sets rewriting in combination with the proposed QA algorithm for the optimization of QA over JWS programs.

Mostafa Milani, Leopoldo Bertossi

A Hybrid Approach to Query Answering Under Expressive Datalog

Abstract

Datalog\(^\pm \) is a family of ontology languages that combine good computational properties with high expressive power. Datalog\(^\pm \) languages are provably able to capture many relevant Semantic Web languages. In this paper we consider the class of weakly-sticky (WS) Datalog\(^\pm \) programs, which allow for certain useful forms of joins in rule bodies as well as extending the well-known class of weakly-acyclic TGDs. So far, only nondeterministic algorithms were known for answering queries on WS Datalog\(^\pm \) programs. We present novel deterministic query answering algorithms under WS Datalog\(^\pm \). In particular, we propose: (1) a bottom-up grounding algorithm based on a query-driven chase, and (2) a hybrid approach based on transforming a WS program into a so-called sticky one, for which query rewriting techniques are known. We discuss how our algorithms can be optimized and effectively applied for query answering in real-world scenarios.

Mostafa Milani, Andrea Calì, Leopoldo Bertossi

Functional Inferences over Heterogeneous Data

Abstract

The increasing availability of knowledge bases (KBs) on the web has opened up the possibility of improved inference in automated query answering (QyA) systems. We have developed a rich inference framework (RIF) that responds to queries where no suitable answer is readily contained in any available data source, by applying functional inferences over heterogeneous data from the web. Our technique combines heuristics, logic and statistical methods to infer novel answers to queries. It also determines what facts are needed for inference, searches for them, and then integrates these diverse facts and their formalisms into a local query-specific inference tree. We explain the internal representation of RIF, the grammar and inference methods for expressing queries and the algorithm for inference. We also show how RIF estimates confidence in its answers, given the various forms of uncertainty faced by the framework.

Kwabena Nuamah, Alan Bundy, Christopher Lucas

A Combined Approach to Incremental Reasoning for EL Ontologies

Abstract

Due to the dynamic nature of knowledge and data in semantic applications, ontology incremental reasoning technologies are essential for ontology management systems. Nowadays, many proposed incremental reasoning solutions and implemented systems apply forward chaining completion algorithms to handle the removal and addition of axioms. In this paper, we propose a novel approach to ontology incremental reasoning that combines forward and backward chaining completion for \(\mathcal {EL}\). Compared to existing work, this approach can be applied with or without bookkeeping, does not affect parallelisation or tractability, and reduces the effort for re-deriving the over-deleted results both theoretically and empirically.

Yuan Ren, Jeff Z. Pan, Isa Guclu, Martin Kollingbaum

Backmatter

Titel: Web Reasoning and Rule Systems
herausgegeben von: Magdalena Ortiz
Stefan Schlobach
Verlag: Springer International Publishing
Electronic ISBN: 978-3-319-45276-0
Print ISBN: 978-3-319-45275-3
DOI: https://doi.org/10.1007/978-3-319-45276-0