Abstract
Based on practical observations on rule-based inference on RDF data, we study the problem of redundancy elimination 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), as well as 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.
Preliminary results have been presented at the Alberto Mendelzon Workshop 2010. R. Pichler, S. Skritek and S. Woltran were supported by the Vienna Science and Technology Fund (WWTF), project ICT08-032. A. Polleres was supported by Science Foundation Ireland under Grant No. SFI/08/CE/I1380 (Lion-2).
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.
References
Hogan, A., Decker, S.: On the ostensibly silent ‘W’ in OWL 2 RL. In: Polleres, A. (ed.) RR 2009. LNCS, vol. 5837, pp. 118–134. Springer, Heidelberg (2009)
Ianni, G., Krennwallner, T., Martello, A., Polleres, A.: Dynamic querying of mass-storage RDF data with rule-based entailment regimes. In: Bernstein, A., Karger, D.R., Heath, T., Feigenbaum, L., Maynard, D., Motta, E., Thirunarayan, K. (eds.) ISWC 2009. LNCS, vol. 5823, pp. 310–327. Springer, Heidelberg (2009)
Muñoz, S., Pérez, J., Gutiérrez, C.: Minimal deductive systems for RDF. In: Franconi, E., Kifer, M., May, W. (eds.) ESWC 2007. LNCS, vol. 4519, pp. 53–67. Springer, Heidelberg (2007)
Grosof, B.N., Horrocks, I., Volz, R., Decker, S.: Description Logic Programs: Combining Logic Programs with Description Logics. In: Proc. WWW’03, pp. 48–57 (2003)
de Bruijn, J., Polleres, A., Lara, R., Fensel, D.: OWL−. WSML D20.1v0.2 (2005)
ter Horst, H.J.: Completeness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary. J. Web Sem. 3(2-3), 79–115 (2005)
Hogan, A., Harth, A., Polleres, A.: Scalable authoritative OWL reasoning for the web. International Journal on Semantic Web and Information Systems 5(2) (2009)
Motik, B., Grau, B.C., Horrocks, I., Wu, Z., Fokoue, A., Lutz, C.: OWL 2 Web ontology language profiles. W3C Recommendation (October 2009)
Hayes, P.: RDF semantics. Technical report, W3C. W3C Recommendation (February 2004)
Lausen, G., Meier, M., Schmidt, M.: SPARQLing constraints for RDF. In: Proc. EDBT’08. ACM Press, New York (2008)
Meier, M.: Towards Rule-Based Minimization of RDF Graphs under Constraints. In: Calvanese, D., Lausen, G. (eds.) RR 2008. LNCS, vol. 5341, pp. 89–103. Springer, Heidelberg (2008)
Pichler, R., Polleres, A., Skritek, S., Woltran, S.: Minimizing RDF graphs under rules and constraints revisited. Technical report, DERI (April 2010), http://www.deri.ie/fileadmin/documents/DERI-TR-2010-04-23.pdf
Beckett, D., Berners-Lee, T.: Turtle - Terse RDF Triple Language, W3C Team Submission (January 2008), http://www.w3.org/TeamSubmission/turtle/
Ullman, J.D.: Principles of Database and Knowledge Base Systems. Computer Science Press, New York (1989)
Gutierrez, C., Hurtado, C., Mendelzon, A.: Foundations of semantic web databases. In: Proc. PODS’04, pp. 95–106. ACM, New York (2004)
Eiter, T., Faber, W., Fink, M., Woltran, S.: Complexity results for answer set programming with bounded predicate arities and implications. Ann. Math. Artif. Intell. 51(2-4), 123–165 (2007)
Eiter, T., Fink, M., Tompits, H., Traxler, P., Woltran, S.: Replacements in non-ground answer-set programming. In: Proc. KR’06, pp. 340–351. AAAI Press, Menlo Park (2006)
Pettorossi, A., Proietti, M.: Transformation of logic programs. In: Gabbay, D.M., Hogger, C.J., Robinson, J.A. (eds.) Handbook of Logic in Artificial Intelligence and Logic Programming, vol. 5, pp. 697–787. Oxford University Press, Oxford (1998)
Angles, R., Gutierrez, C.: The expressive power of SPARQL. In: Sheth, A.P., Staab, S., Dean, M., Paolucci, M., Maynard, D., Finin, T., Thirunarayan, K. (eds.) ISWC 2008. LNCS, vol. 5318, pp. 114–129. Springer, Heidelberg (2008)
Pérez, J., Arenas, M., Gutierrez, C.: Semantics and complexity of SPARQL. ACM Trans. Database Syst. 34(3) (2009)
Vardi, M.: On the complexity of bounded-variable queries. In: Proc. PODS’95, pp. 266–276. ACM Press, New York (1995)
de Bruijn, J.: RIF RDF and OWL Compatibility. W3C Proposed Recommendation (May 2010), http://www.w3.org/TR/2010/PR-rif-rdf-owl-20100511/
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2010 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Pichler, R., Polleres, A., Skritek, S., Woltran, S. (2010). Redundancy Elimination on RDF Graphs in the Presence of Rules, Constraints, and Queries . In: Hitzler, P., Lukasiewicz, T. (eds) Web Reasoning and Rule Systems. RR 2010. Lecture Notes in Computer Science, vol 6333. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-15918-3_11
Download citation
DOI: https://doi.org/10.1007/978-3-642-15918-3_11
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-15917-6
Online ISBN: 978-3-642-15918-3
eBook Packages: Computer ScienceComputer Science (R0)