Implementing flexible operators for regular path queries

Article English OPEN
Selmer, Petra ; Poulovassilis, Alexandra ; Wood, Peter T. (2015)
  • Publisher: CEUR Workshop Proceedings
  • Subject: csis

Given the heterogeneity of complex graph data on the web, such as RDF linked data,a user wishing to query such data may lack full knowledge of its structure and irregularities.\ud Hence, providing users with flexible querying capabilities can be beneficial. The query language we adopt comprises\ud conjunctions of regular path queries, thus including extensions proposed for SPARQL 1.1 to allow for querying paths using regular expressions. To this language we add two operators: APPROX, supporting standard notions of\ud approximation based on edit distance, and RELAX, which performs query relaxation based on RDFS inference rules.\ud We describe our techniques for implementing the extended language and present a performance study undertaken on two real-world data sets. Our baseline implementation performs competitively with other automaton-based approaches, and we demonstrate empirically how various optimisations can decrease execution times of queries containing APPROX and RELAX, sometimes by orders of magnitude.
  • References (23)
    23 references, page 1 of 3

    [1] Bio4j.

    [2] C. Bizer, A. Jentzsch, and R. Cyganiak.

    [3] D. Calvanese, G. D. Giacomo, M. Lenzerini, and M. Y. Vardi. Containment of conjunctive regular path queries with inverse. In KR, pages 176{185, 2000.

    [4] J. P. Ceden~o and K. S. Candan. R2DF framework for ranked path queries over weighted RDF graphs. In Proc. WIMS, pages 40:1{40:12, 2011.

    [5] M. Droste, W. Kuich, and H. Vogler. Handbook of Weighted Automata. Springer, 2009.

    [6] O. Hartig and R. Heese. The SPARQL query graph model for query optimization. In Proc. ESWC, pages 564{578, 2007.

    [7] T. Heath, M. Hausenblas, C. Bizer, and R. Cyganiak. How to publish linked data on the web (tutorial). In Proc. ISWC, 2008.

    [8] J. Huang, D. J. Abadi, and K. Ren. Scalable SPARQL querying of large RDF graphs. PVLDB, 4(11):1123{1134, 2011.

    [9] C. A. Hurtado, A. Poulovassilis, and P. T. Wood. Ranking approximate answers to semantic web queries. In Proc. ESWC, pages 263{277, 2009.

    [10] G. Kasneci, M. Ramanath, F. Suchanek, and G. Weikum. The YAGO-NAGA approach to knowledge discovery. SIGMOD Rec., 37(4):41{47, Mar. 2009.

  • Metrics
    views in OpenAIRE
    views in local repository
    downloads in local repository

    The information is available from the following content providers:

    From Number Of Views Number Of Downloads
    Birkbeck Institutional Research Online - IRUS-UK 0 43
Share - Bookmark