Efficient Processing of RDF Queries with Nested Optional Graph Patterns in an RDBMS

Artem Chebotko, Shiyong Lu, Mustafa Atay and Farshad Fotouhi
Additional contact information
Artem Chebotko: University of Texas - Pan American, USA
Shiyong Lu: Wayne State University, USA
Mustafa Atay: Winston-Salem State University, USA
Farshad Fotouhi: Wayne State University, USA

International Journal on Semantic Web and Information Systems (IJSWIS), 2008, vol. 4, issue 4, 1-30

Abstract: Relational technology has shown to be very useful for scalable Semantic Web data management. Numerous researchers have proposed to use RDBMSs to store and query voluminous RDF data using SQL and RDF query languages. In this article, we study how RDF queries with the socalled well-designed graph patterns and nested optional patterns can be efficiently evaluated in an RDBMS. We propose to extend relational databases with a novel relational operator, nested optional join (NOJ), that is more efficient than left outer join in processing nested optional patterns of well-designed graph patterns. We design three efficient algorithms to implement the new operator in relational databases: (1) nested-loops NOJ algorithm (NL-NOJ); (2) sortmerge NOJ algorithm (SM-NOJ); and (3) simple hash NOJ algorithm (SH-NOJ). Based on a real-life RDF dataset, we demonstrate the efficiency of our algorithms by comparing them with the corresponding left outer join implementations and explore the effect of join selectivity on the performance of our algorithms.

Date: 2008
References: Add references at CitEc
Citations:

Downloads: (external link)
https://services.igi-global.com/resolvedoi/resolve ... 018/jswis.2008100101 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:igg:jswis0:v:4:y:2008:i:4:p:1-30

Access Statistics for this article

International Journal on Semantic Web and Information Systems (IJSWIS) is currently edited by Brij Gupta

More articles in International Journal on Semantic Web and Information Systems (IJSWIS) from IGI Global
Bibliographic data for series maintained by Journal Editor ().