Zeitschriftenartikel:
R. Pichler, A. Polleres, S. Skritek, S. Woltran:
"Complexity of redundancy detection on RDF graphs in the presence of rules, constraints, and queries";
Semantic Web (eingeladen),
4
(2013),
4;
S. 351
- 393.
Kurzfassung englisch:
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.
Schlagworte:
RDF, optimisation, rules, constraints, computational complexity
"Offizielle" elektronische Version der Publikation (entsprechend ihrem Digital Object Identifier - DOI)
http://dx.doi.org/10.3233/SW-2012-0076
Elektronische Version der Publikation:
http://iospress.metapress.com/content/m34210jv627727qv/fulltext.pdf
Zugeordnete Projekte:
Projektleitung Reinhard Pichler:
Service-orientierte Datenintegration
Projektleitung Reinhard Pichler:
Theoretisch Effiziente Lösbarkeit vs. Praktische Berechnung
Erstellt aus der Publikationsdatenbank der Technischen Universität Wien.