main-content

Über dieses Buch

This book constitutes the refereed proceedings of the 9th International Conference on Web Reasoning and Rule Systems, RR 2015, held in Berlin, Germany, in August 2015. The 5 full papers, 4 technical communications presented together with 4 invited talks were carefully reviewed and selected from 16 submissions. The scale and the heterogenous nature of web data poses many challenges, and turns basic tasks such as query answering and data transformations into complex reasoning problems. Rule-based systems have found many applications in this area. The RR conference welcomes original research from all areas of Web Reasoning and Rule Systems. Topics of particular interest are: answer set programming, complex events, datalog, description logics, event-condition-action rules, information extraction, and logic programming.

Inhaltsverzeichnis

Frontmatter

Abstract
Prominent sources of Big Data include technological and social trends, such as mobile computing, blogging, and social networking. The means to analyse such data are becoming more accessible with the development of business models like cloud computing, open-source and crowd sourcing. But that data have characteristics that pose challenges to traditional database systems. Due to the uncontrolled nature by which data is produced, much of it is free text, often in informal natural language, leading to computing environments with high levels of uncertainty and error. In this talk I will offer a vision of a database system that aims to facilitate the development of modern data-centric applications, by naturally unifying key functionalities of databases, text analytics, machine learning and artificial intelligence. I will also describe my past research towards pursuing the vision by extensions of Datalog — a well studied rule-based programming paradigm that features an inherent integration with the database, and has a robust declarative semantics. These extensions allow for incorporating information extraction from text, and for specifying statistical models by probabilistic programming.
Benny Kimelfeld

An Ontology for Historical Research Documents

Abstract
In this paper we present the conceptual layer of stole, our ontology-based digital archive aiming at helping historical researchers to organize data, extract information and derive new knowledge from historical documents.
Giovanni Adorni, Marco Maratea, Laura Pandolfo, Luca Pulina

Semantic Views of Homogeneous Unstructured Data

Abstract
Homogeneous unstructured data (HUD) are collections of unstructured documents that share common properties, such as similar layout, common file format, or common domain of values. Building on such properties, it would be desirable to automatically process HUD to access the main information through a semantic layer – typically an ontology – called semantic view. Hence, we propose an ontology-based approach for extracting semantically rich information from HUD, by integrating and extending recent technologies and results from the fields of classical information extraction, table recognition, ontologies, text annotation, and logic programming. Moreover, we design and implement a system, named KnowRex, that has been successfully applied to curriculum vitae in the Europass style to offer a semantic view of them, and be able, for example, to select those which exhibit required skills.
Weronika T. Adrian, Nicola Leone, Marco Manna

Supportedly Stable Answer Sets for Logic Programs with Generalized Atoms

Abstract
Answer Set Programming (ASP) is logic programming under the stable model or answer set semantics. During the last decade, this paradigm has seen several extensions by generalizing the notion of atom used in these programs. Among these, there are dl-atoms, aggregate atoms, HEX atoms, generalized quantifiers, and abstract constraints. In this paper we refer to these constructs collectively as generalized atoms. The idea common to all of these constructs is that their satisfaction depends on the truth values of a set of (non-generalized) atoms, rather than the truth value of a single (non-generalized) atom. Motivated by several examples, we argue that for some of the more intricate generalized atoms, the previously suggested semantics provide unintuitive results and provide an alternative semantics, which we call supportedly stable or SFLP answer sets. We show that it is equivalent to the major previously proposed semantics for programs with convex generalized atoms, and that it in general admits more intended models than other semantics in the presence of non-convex generalized atoms. We show that the complexity of supportedly stable answer sets is on the second level of the polynomial hierarchy, similar to previous proposals and to answer sets of disjunctive logic programs.
Mario Alviano, Wolfgang Faber

Planning with Regression Analysis in Transaction Logic

Abstract
Heuristic search is arguably the most successful paradigm in Automated Planning, which greatly improves the performance of planning strategies. However, adding heuristics usually leads to very complicated planning algorithms. In order to study different properties (e.g. completeness) of those complicated planning algorithms, it is important to use an appropriate formal language and framework. In this paper, we argue that Transaction Logic is just such a specification language, which lets one formally specify both the heuristics, the planning algorithm, and also facilitates the discovery of more general and more efficient algorithms. To illustrate, we take the well-known regression analysis mechanism and show that Transaction Logic lets one specify the concept of regression analysis easily and thus express $$\textit{RSTRIPS}$$, a classical and very complicated planning algorithm based on regression analysis. Moreover, we show that extensions to that algorithm that allow indirect effects and action ramification are obtained almost for free. Finally, a compact and clear logical formulation of the algorithm lets us prove the completeness of $$\textit{RSTRIPS}$$—a result that, to the best of our knowledge, has not been known before.
Reza Basseda, Michael Kifer

Web Ontology Representation and Reasoning via Fragments of Set Theory

Abstract
In this paper we use results from Computable Set Theory as a means to represent and reason about description logics and rule languages for the semantic web.
Specifically, we introduce the description logic $$\mathcal {DL}\langle 4LQS^R\rangle (\mathbf {D})$$–allowing features such as min/max cardinality constructs on the left-hand/right-hand side of inclusion axioms, role chain axioms, and datatypes–which turn out to be quite expressive if compared with $$\mathcal {SROIQ}(\mathbf {D})$$, the description logic underpinning the Web Ontology Language OWL. Then we show that the consistency problem for $$\mathcal {DL}\langle 4LQS^R\rangle (\mathbf {D})$$-knowledge bases is decidable by reducing it, through a suitable translation process, to the satisfiability problem of the stratified fragment $$4LQS^R$$ of set theory, involving variables of four sorts and a restricted form of quantification. We prove also that, under suitable not very restrictive constraints, the consistency problem for $$\mathcal {DL}\langle 4LQS^R\rangle (\mathbf {D})$$-knowledge bases is NP-complete. Finally, we provide a $$4LQS^R$$-translation of rules belonging to the Semantic Web Rule Language (SWRL).
Domenico Cantone, Cristiano Longo, Marianna Nicolosi-Asmundo, Daniele Francesco Santamaria

Allotment Problem in Travel Industry: A Solution Based on ASP

Abstract
In the travel industry it is common for tour operators to pre-book from service suppliers blocks of package tours, which are called allotments in jargon. The selection of package tours is done according to several preference criteria aimed at maximizing the expected earnings given a budget. In this paper we formalize an allotment problem that abstracts the requirements of a real travel agent, and we solve it using Answer Set Programming. The obtained specification is executable, and it implements an advanced feature of the iTravel+ system.
Carmine Dodaro, Nicola Leone, Barbara Nardi, Francesco Ricca

A Rule-based Framework for Creating Instance Data from OpenStreetMap

Abstract
Reasoning engines for ontological and rule-based knowledge bases are becoming increasingly important in areas like the Semantic Web or information integration. It has been acknowledged however that judging the performance of such reasoners and their underlying algorithms is difficult due to the lack of publicly available datasets with large amounts of (real-life) instance data. In this paper we describe a framework and a toolbox for creating such datasets, which is based on extracting instances from the publicly available OpenStreetMap (OSM) geospatial database. To this end, we give a formalization of OSM and present a rule-based language to specify the rules to extract instance data from OSM data. The declarative nature of the approach in combination with external functions and parameters allows one to create several variants of the dataset via small modifications of the specification. We describe a highly flexible toolbox to extract instance data from a given OSM map and a given set of rules. We have employed our tools to create benchmarks that have already been fruitfully used in practice.
Thomas Eiter, Jeff Z. Pan, Patrik Schneider, Mantas Šimkus, Guohui Xiao

Web Stream Reasoning in Practice: On the Expressivity vs. Scalability Tradeoff

Abstract
Advances in the Internet of Things and the Web of Data created huge opportunities for developing applications that can generate actionable knowledge out of streaming data. The trade-off between scalability and expressivity is a key challenge in this setting, and more investigation is required to identify what are the relevant features in optimizing this trade-off, and what role do they have in the optimization. In this paper we motivate the need for heuristics to design adaptive solutions and, following an empirical approach, we highlight some key concepts and ideas that can guide the design of heuristics for adaptive optimization of Web Stream Reasoning.
Stefano Germano, Thu-Le Pham, Alessandra Mileo

A Procedure for an Event-Condition-Transaction Language

Abstract
Event-Condition-Action languages are the commonly accepted paradigm to express and model the behavior of reactive systems. While numerous Event-Condition-Action languages have been proposed in the literature, differing e.g. on the expressivity of the language and on its operational behavior, existing Event-Condition-Action languages do not generally support the action component to be formulated as a transaction. In this paper, sustaining that it is important to execute transactions in reactive languages, we propose an Event-Condition-Transaction language, based on an extension of Transaction Logic. This extension, called Transaction Logic with Events ($$\mathcal {TR}^{ev}$$), combines reasoning about the execution of transactions with the ability to detect complex events. An important characteristic of $$\mathcal {TR}^{ev}$$ is that it takes a choice function as a parameter of the theory, leaving open the behavioral decisions of the logic, and thereby allowing it to be suitable for a wide-spectrum of application scenarios like Semantic Web, multi-agent systems, databases, etc. We start by showing how $$\mathcal {TR}^{ev}$$ can be used as an Event-Condition-Action language where actions are considered as transactions, and how to differently instantiate this choice function to achieve different operational behaviors. Then, based on a particular operational instantiation of the logic, we present a procedure that is sound and complete w.r.t. the semantics and that is able to execute $$\mathcal {TR}^{ev}$$ programs.
Ana Sofia Gomes, José Júlio Alferes

Backmatter

Weitere Informationen