Processing SPARQL queries with regular expressions in RDF databases

BMC Bioinformatics

Proceedings

Minh-Duc Pham¹  Jinsoo Lee¹  Wook-Shin Han¹  Jihwan Lee¹  Hwanjo Yu²  Jeong-Hoon Lee³  Hune Cho⁴ 

[1] Department of Computer Engineering, Kyungpook National University, Daegu, Korea;Department of Computer Science and Engineering, POSTECH, Pohang, Korea;Department of Computer Science, KAIST, Daejeon, Korea;Department of Medical Informatics, Kyungpook National University, Daegu, Korea;

关键词: Query Processing;    Resource Description Framework;    Regular Expression;    Parse Tree;    Execution Plan;   

DOI  :  10.1186/1471-2105-12-S2-S6

来源: Springer

【 摘 要 】

BackgroundAs the Resource Description Framework (RDF) data model is widely used for modeling and sharing a lot of online bioinformatics resources such as Uniprot (dev.isb-sib.ch/projects/uniprot-rdf) or Bio2RDF (bio2rdf.org), SPARQL - a W3C recommendation query for RDF databases - has become an important query language for querying the bioinformatics knowledge bases. Moreover, due to the diversity of users’ requests for extracting information from the RDF data as well as the lack of users’ knowledge about the exact value of each fact in the RDF databases, it is desirable to use the SPARQL query with regular expression patterns for querying the RDF data. To the best of our knowledge, there is currently no work that efficiently supports regular expression processing in SPARQL over RDF databases. Most of the existing techniques for processing regular expressions are designed for querying a text corpus, or only for supporting the matching over the paths in an RDF graph.ResultsIn this paper, we propose a novel framework for supporting regular expression processing in SPARQL query. Our contributions can be summarized as follows. 1) We propose an efficient framework for processing SPARQL queries with regular expression patterns in RDF databases. 2) We propose a cost model in order to adapt the proposed framework in the existing query optimizers. 3) We build a prototype for the proposed framework in C++ and conduct extensive experiments demonstrating the efficiency and effectiveness of our technique.ConclusionsExperiments with a full-blown RDF engine show that our framework outperforms the existing ones by up to two orders of magnitude in processing SPARQL queries with regular expression patterns.

【 授权许可】

Unknown   
© Lee et al; licensee BioMed Central Ltd. 2011. This article is published under license to BioMed Central Ltd. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.