Benchmarking Reachability Techniques for the Optimization of RDF Queries

Abstract

Today, a large amount of data is shared online, and much of it is connected like a network.

RDF (Resource Description Framework) graphs are used to describe this data using triples (subject, predicate, object), and they are important in the Semantic Web and Linked Open Data. However, as RDF graphs become very large, it becomes difficult to answer queries quickly, especially reachability queries which check if there is a path between two nodes.

This research studies how to improve the RDF QDAG (Query Directed Acyclic Graph), a structure that makes querying faster by removing cycles in the graph. While RDF QDAG is efficient, it has some limits with complex path queries. To solve this, we integrated several indexing techniques such as Tree-Cover Indexing, 2-Hop Labeling, Approximate Transitive Closure, TreeBased Indexing, Generalized Transitive Closure (GTC), and 2-Hop Labeling with Constraints.

We tested these techniques using real RDF data. The results show that our system can answer queries faster and use less memory. This work helps improve how large RDF graphs are managed and makes it easier to run advanced queries for semantic applications.