Complexity of redundancy detection on RDF graphs in the presence of rules, constraints, and queries

Issue title: Selected papers presented at the Fourth International Conference on Web Reasoning and Rule Systems (RR 2010)

Article type: Research Article

Authors: Pichler, Reinhard | Polleres, Axel^; | Skritek, Sebastian^; | Woltran, Stefan^;

Affiliations: Faculty of Informatics, Vienna University of Technology, Favoritenstraße 9, A-1040 Wien, Austria. E-mail: {lastname}@dbai.tuwien.ac.at | Siemens AG Österreich, Siemensstrasse 90, A-1210 Wien, Austria. E-mail: [email protected] | Digital Enterprise Research Institute, National University of Ireland, Galwway, IDA Business Park, Lower Dangan, Ireland

Note: [] Corresponding author. E-mail: [email protected].

Note: [] A preliminary version of this paper appeared at RR2010 [26].

Abstract: Based on practical observations on rule-based inference on RDF data, we study the problem of redundancy detection on RDF graphs in the presence of rules (in the form of Datalog rules) and constraints, (in the form of so-called tuple-generating dependencies), and with respect to queries (ranging from conjunctive queries up to more complex ones, particularly covering features of SPARQL, such as union, negation, or filters). To this end, we investigate the influence of several problem parameters (like restrictions on the size of the rules, the constraints, and/or the queries) on the complexity of detecting redundancy. The main result of this paper is a fine-grained complexity analysis of both graph and rule minimisation in various settings.

Keywords: RDF, optimisation, rules, constraints, computational complexity

DOI: 10.3233/SW-2012-0076

Journal: Semantic Web, vol. 4, no. 4, pp. 351-393, 2013