TL;DR
This paper introduces "Hexastore," a novel RDF data management system that uses six distinct indexing schemes to efficiently query Semantic Web data. By treating subjects, predicates, and objects equally and creating indices for all possible orderings, Hexastore achieves significant performance improvements (up to five orders of magnitude) over existing methods, particularly for complex, non-property-bound queries.
What Problem Does This Paper Address?
The Semantic Web vision relies on the Resource Description Framework (RDF) for interlinked, machine-processable data. However, managing the ever-growing volume of RDF data efficiently has been a major challenge. Existing RDF storage systems often struggle with scalability and performance, especially for queries that don't explicitly specify the RDF property. Many systems either map RDF to traditional relational databases, losing semantic richness, or use specialized indexing schemes that are optimized for specific query types but falter on more general ones. The paper argues that previous approaches, like vertical partitioning (creating separate tables for each property), are too property-centric and fail to address the full spectrum of query needs.
Methods
The core innovation of Hexastore is its "sextuple indexing" scheme. Instead of focusing solely on properties, Hexastore creates six distinct indices, each representing a different ordering of the three RDF elements (subject, predicate, object). For each element (e.g., subject), it maintains two vectors: one prioritizing predicates and the other objects. These vectors are augmented with lists of the third RDF element. This creates a comprehensive indexing structure that materializes all 3! = 6 possible orderings of RDF elements.
Key aspects of the method include:
- Sextuple Indexing: Six indices (spo, sop, pso, pos, osp, ops) are created, covering all permutations of subject, predicate, and object.
- Vector and List Structure: Each index uses vectors for two elements and lists for the third, allowing for efficient retrieval of related data.
- Dictionary Encoding: Similar to other systems, Hexastore uses integer keys to represent URIs and strings, reducing storage and improving lookup speed.
- Shared Lists: To mitigate space overhead, terminal lists (e.g., object lists) are shared between complementary indices (e.g., spo and pso).
Datasets
The paper evaluates Hexastore using two datasets:
- Barton Data Set: A real-world dataset derived from the MIT Barton Libraries catalog, containing approximately 61 million triples and 285 unique properties. This dataset is noted for its irregular structure, reflecting the semi-structured nature of Semantic Web data.
- LUBM Data Set: A synthetic dataset based on the Lehigh University benchmark (LUBM), modeling academic information. The authors generated a dataset with about 6.8 million triples and 18 predicates.
The paper also references benchmark queries from previous work, particularly from [5], to ensure a fair comparison.
Key Insights and Ideas
- RDF's Triple Nature as an Asset: The paper reframes the inherent triple structure of RDF, often seen as a limitation, into a strength by leveraging all possible orderings for indexing.
- Beyond Property-Centricity: The most significant insight is that efficient RDF management requires treating subjects, predicates, and objects with equal importance, rather than prioritizing properties as many previous systems did.
- Universal Merge-Joins: A crucial consequence of the sextuple indexing is that all pairwise joins required during query processing can be performed as efficient, linear-time merge-joins, drastically reducing computational cost compared to traditional join algorithms.
- Avoiding NULLs and Sparsity: The indexing scheme naturally avoids NULL values by only storing relevant relationships, making it more concise and efficient than relational mappings that often suffer from sparsity.
- Predictable Space Overhead: While Hexastore increases storage space (up to a worst-case five-fold increase), this overhead is predictable and deterministic, unlike some other approaches that might have variable or ad-hoc space requirements.
Key Results
The experimental evaluation demonstrates substantial performance gains for Hexastore:
- Query Speedup: Hexastore consistently outperforms previous methods, achieving speedups of one to three orders of magnitude (100x to 1000x) compared to a single-index property-based approach (COVP1) and one to two orders of magnitude (10x to 100x) better than a two-index property-based approach (COVP2). In some cases, the speedup reaches five orders of magnitude.
- Scalability: Hexastore exhibits excellent scalability, with query response times remaining relatively constant even as the dataset size increases, particularly for queries that benefit from the pos index.
- Handling Complex Queries: The system excels at queries that do not bind property values, a weakness of many prior systems.
- Memory Usage: Hexastore incurs a roughly four-fold increase in memory usage compared to COVP1, which the authors deem an acceptable trade-off for the performance benefits.
Limitations and Future Work
- Storage Space: The primary limitation acknowledged is the increased storage space requirement, which can be up to five times that of a simple triples table.
- Update Performance: Handling updates and insertions can be slow as they affect all six indices. However, the authors note that current RDF applications typically don't involve massive updates.
- Index Selection: Future work could explore methods for selecting the most suitable indices for a given workload to optimize storage and performance.
- Cracking Techniques: Applying database cracking techniques for index maintenance is suggested as a promising avenue.
- Disk-Based Implementation: The authors plan to implement a disk-based Hexastore and compare it to other systems and relational databases.
Summary updated