Welcome to the InfoSci Platform
Reference Hub1
The Graph Signature: A Scalable Query Optimization Index for RDF Graph Databases Using Bisimulation and Trace Equivalence Summarization

The Graph Signature: A Scalable Query Optimization Index for RDF Graph Databases Using Bisimulation and Trace Equivalence Summarization

Mustafa Jarrar, Anton Deik
Copyright: © 2015 |Volume: 11 |Issue: 2 |Pages: 30
ISSN: 1552-6283|EISSN: 1552-6291|EISBN13: 9781466676206|DOI: 10.4018/IJSWIS.2015040102
Cite Article Cite Article

MLA

Jarrar, Mustafa, and Anton Deik. "The Graph Signature: A Scalable Query Optimization Index for RDF Graph Databases Using Bisimulation and Trace Equivalence Summarization." IJSWIS vol.11, no.2 2015: pp.36-65. http://doi.org/10.4018/IJSWIS.2015040102

APA

Jarrar, M. & Deik, A. (2015). The Graph Signature: A Scalable Query Optimization Index for RDF Graph Databases Using Bisimulation and Trace Equivalence Summarization. International Journal on Semantic Web and Information Systems (IJSWIS), 11(2), 36-65. http://doi.org/10.4018/IJSWIS.2015040102

Chicago

Jarrar, Mustafa, and Anton Deik. "The Graph Signature: A Scalable Query Optimization Index for RDF Graph Databases Using Bisimulation and Trace Equivalence Summarization," International Journal on Semantic Web and Information Systems (IJSWIS) 11, no.2: 36-65. http://doi.org/10.4018/IJSWIS.2015040102

Export Reference

Mendeley
Favorite Full-Issue Download

Abstract

Querying large data graphs has brought the attention of the research community. Many solutions were proposed, such as Oracle Semantic Technologies, Virtuoso, RDF3X, and C-Store, among others. Although such approaches have shown good performance in queries with medium complexity, they perform poorly when the complexity of the queries increases. In this paper, the authors propose the Graph Signature Index, a novel and scalable approach to index and query large data graphs. The idea is that they summarize a graph and instead of executing the query on the original graph, they execute it on the summaries. The authors' experiments with Yago (16M triples) have shown that e.g., a query with 4 levels costs 62 sec using Oracle but it only costs about 0.6 sec with their index. Their index can be implemented on top of any Graph database, but they chose to implement it as an extension to Oracle on top of the SEM_MATCH table function. The paper also introduces disk-based versions of the Trace Equivalence and Bisimilarity algorithms to summarize data graphs, and discusses their complexity and usability for RDF graphs.

Request Access

You do not own this content. Please login to recommend this title to your institution's librarian or purchase it from the IGI Global bookstore.