As the number and scale of Semantic Web applications in use increases, so does the need to e ciently store and retrieve RDF data. Current published schemes for RDF data management either fail to embrace the schema exibility inherent in RDF or make restrictive assumptions about application usage models. This paper describes a storage and indexing scheme based on linked lists and memory-mapped les, and presents theoretical and empirical analysis of its strengths and weaknesses versus other techniques. This scheme is currently used in Parliament (formerly DAML DB), a triple store with rule support that has recently been released as open source.
As the number and scale of Semantic Web applications in use increases, so does
the need to e ciently store and retrieve RDF [
Despite the fact that RDF's graph-based data model is inherently di erent than relational data models, many published schemes for RDF data storage involve reductions to a traditional RDBMS [3{7]. This results in the de ciencies of RDBMS's (in exible schemas, inability to e ciently query variable predicates) being propagated to RDF storage; arguably, avoiding these de ciencies is one of the major reasons for adopting an RDF data model. Other published approaches eschew the mapping to an RDBMS, but su er either inadequate load or query performance for many applications. In this paper, we argue that the storage approach in Parliament provides excellent load and query performance with low space consumption and avoids the pitfalls of many other specialized RDF storage systems.
Parliament [
Recently, BBN has decided to release Parliament as an open source project.
Parliament provides the underlying storage mechanism, while using Jena [
The remainder of this paper is structured as follows. Section 2 addresses
related work. Section 3 describes the index structure within Parliament.
Section 4 explains how the operations on the structure are performed. Section 5
provides both worst case and average case analysis of the indexing mechanism,
and Section 6 provides a small empirical comparison to supplement [
The related work on RDF data management systems falls into two major categories: solutions that involve a mapping to a relational database, and those that do not. 2.1
A large proportion of the previously published approaches involve a mapping of the RDF data model into some form of relational storage. These include triplestable approaches, property tables, and vertical partitioning. There is a strong temptation to use relational systems to store RDF data since such a great amount of research has been done on making relational systems e cient. Moreover, existing RDBMS systems are extremely scalable and robust. Unfortunately, each of the proposed ways of doing this mapping has de ciencies.
The triples-table approach has been employed in 3store [
Property tables were introduced later, and allowed multiple triple patterns
referencing the same subject to be retrieved without an expensive join. This
approach has been used in Jena 2 [
The vertical partitioning approach suggested in [
The other primary approaches to RDF data storage eliminate the need for a standard RDBMS and focus instead on indexing speci c to the RDF data model. This set of approaches tends to better address the query models of the semantic web, but each su ers its own set of weaknesses.
The RDF store YARS [
The commercial quad store Virtuoso [
Hexastore [
Other commercial triple stores such as OWLIM [
This section explains the three parts of the storage structure of Parliament: the resource table, the statement table, and the resource dictionary. This description is simpli ed for the sake of clarity; it does not discuss using quads instead of triples, optimizations for blank nodes, the rule engine, or some small implementation details. Parliament can be compiled in either 32 or 64 bit modes, and the width of the elds described varies accordingly. 3.1
The Resource Table is a single le of xed-length records, each of which represents a single resource or literal. The records are sequentially numbered, and this number serves as the ID of the corresponding resource. This allows direct access to a record given its ID via simple array indexing. Each record has eight components: { Three statement ID elds representing the rst statements that contain this resource as a subject, predicate, and object, respectively { Three count elds containing the number of statements using this resource as a subject, predicate, and object, respectively { An o set into the string representations le described below, used to retrieve the string representation of the resource { Bit- eld ags encoding various attributes of the resource
The rst subject, rst predicate, and rst object statement identi ers provide pointers into the statement table, which is described below. The subject, predicate, and object counts bene t the nd operations and query optimization, discussed in Section 4. For the remainder of the paper, these counts will be referred to as count(resource; pos) for the count of a resource in the given position. The usage of the o set into the string representations le will be explained below. 3.2
The Statement Table is the most important part of Parliament's storage approach. It is similar to the resource table in that it is a single le of xed-length records, each of which represents a single statement. The records are sequentially numbered, and this number serves as the ID of the corresponding statement. Each record has seven components: { Three resource ID elds representing the subject, predicate, and object of the statement, respectively { Three statement ID elds representing the next statements that use the same resource as a subject, predicate, and object, respectively { Bit- eld ags encoding various attributes of the statement
The three resource ID elds allow a statement ID to be translated into the triple of resources that represent that statement. The three next statement pointers allow fast traversal of the statements that share either a subject, predicate, or object, while still storing each statement only once.
Figure 1 shows an example knowledge base consisting of ve triples. Each triple row in the statement list table shows its resource identi er as a number and the pointers to the next statements as arrows. Omitted arrows indicate pointers to a special statement identi er, the null statement identi er, which indicates the end of the linked list. 3.3
Like many other triple stores [
The second half of the dictionary is the reverse lookup from a resource ID to a string representation. This is implemented in a memory-mapped le containing sequential, variable-length, and null-terminated string representations of resources. A resource ID is translated into the corresponding string representation by using the resource ID to index into the resource table, retrieving the string representation o set, and using this to index into the string representations le to retrieve the associated string. Thus, looking up a string representation from a resource identi er is a constant time operation.
The current approach stores each string representation twice. Future implementations may eliminate this redundancy. Three of the four les that comprise a Parliament triple store (the resource table, the statement table, and the string representations le) are stored and accessed via a common operating system facility called \memory mapping". This is independent of the index structure of the store, but is worth mentioning because it confers a signi cant performance advantage. Most modern operating systems use memory mapping to implement their own demand-paged virtual memory subsystem, and so this mechanism for accessing les tends to be highly optimized and keeps frequently accessed pages in memory. 4
The three fundamental operations that a triple store can perform are query, insertion (assertion), and deletion (retraction). These are discussed below. 4.1
Parliament performs a lookup of a single triple pattern according to the following algorithm: 1. If any of the triple pattern elements are bound, Parliament uses the B-tree to translate the string representations of these resources into resource ID's. 2. If any bound elements are not found in the B-tree, then the query result is the empty set, and the query algorithm terminates. 3. If none of the elements are bound, then the query result is the entire statement list. Parliament enumerates this by iterating across all of the records in the statement table and retrieving the string representations of the elements. 4. If exactly one element is bound, then Parliament looks in the resource table for the resource table the ID of the rst statement using that resource in the position the resource appears in the given triple pattern. 5. If two or three elements are bound, then Parliament looks in the resource table for those resource ID's to retrieve count(resource; pos) for each. Parliament selects the resource whose count is smallest, and retrieves from the resource table the ID of the rst statement using that resource in the position the resource appears in the given triple pattern. 6. Starting with that statement ID, Parliament traverses the linked list of statement records corresponding to the position of the minimal count resource. 7. If the triple pattern contains exactly one bound resource, then this list of statements is exactly the answer to the query, and again Parliament retrieves the string representations of the elements as it enumerates the list to form the query result. 8. If two or three elements are bound, then as Parliament enumerates the linked list of statements, it checks whether the resources in the positions of the non-minimal count resources are the same as the bindings in the given triple pattern. Whenever a match is found, Parliament retrieves the string representations of the elements and adds that triple to the query result.
Whenever Parliament is enumerating statements, it skips over statements whose \deleted" ag has been set. See Section 4.3 below for details.
Parliament is designed as an embedded triple store and does not include a
SPARQL or other query language processor. Such queries are supported by
accessing Parliament as a storage model from higher-level frameworks such as Jena
or Sesame. Single nd operations (as discussed above) are combined together by
the higher-level framework, with Parliament-speci c extensions for optimization.
In particular, when using Parliament with Jena's query processors [
To insert a triple (s; p; o), Parliament executes the following algorithm: 1. Parliament uses the B-tree to translate the string representations of the three resources into resource ID's. 2. If all three elements are found in the B-tree, then Parliament performs a query for the triple pattern (s; p; o). Note that this is necessarily a fully bound query pattern. If the triple is found, then no insertion is required, and the algorithm terminates. 3. If any elements are not found in the B-tree, then Parliament creates new resources for each of them as follows: (a) Parliament appends the string representation of the resource to the end of the string representations le. If the le is not large enough to contain the string, then the le is enlarged rst. The o set of the beginning of the string is noted for use in the next step. (b) Parliament appends a new record to the end of the resource table. If the le is not large enough to contain the new record, then the le is enlarged rst. The number of the record is saved as the new resource ID for use in the steps below, and the o set from the string representations le is written to the appropriate eld in this record. The record's counts are initialized to zero, and the rst statement ID's are set to null. (c) Parliament inserts a new entry into the B-tree. The entry contains the resource's string representation as its key and the new resource ID as its value. 4. Parliament now has three valid resource ID's representing the triple, and knows that the triple is not present in the statement table. 5. Parliament appends a new record to the end of the statement table. If the le is not large enough to contain the new record, then the le is enlarged rst. The number of the record is saved as the new statement ID for use in the steps below, and the three resource ID's obtained above are written to the appropriate elds in this record. The record's next statement ID's are all set to null. 6. For each of the three resources, Parliament inserts the new statement record at the head of that resource's linked list for the corresponding triple position as follows: (a) The resource record's rst statement ID for the resource's position is written into the corresponding next statement ID eld in the new statement record. Note that if this resource was newly inserted for this statement, then this step will write a null into the next statement ID eld. (b) The ID of the new statement is written into the resource record's rst statement ID for the resource's position. 4.3
The index structure of Parliament's statement table is not conducive to the e cient removal of a statement record from the three linked lists of which it is a member. These linked lists are singly linked, and so there is no way to remove a record except to traverse all three lists from the beginning.
Due to these di culties, Parliament \deletes" statements by marking them with a ag in the bit eld portion of the statement record. Thus, the algorithm consists of a nd (as in the case of an insertion, this is a fully bound query pattern) followed by setting the ag on the found record. In the future, we may utilize doubly linked lists so that the space occupied by deleted statements can be reclaimed e ciently. However, in our work to date deletion has been infrequent enough that this has been deemed a lower priority enhancement. 5
As is readily apparent, the presented approach su ers some unfortunate worst
case performance, but the average case performance is quite good. This is
consistent with empirical results presented in [
The worst-case performance for a single triple pattern lookup is dependent on how many of the elements in the pattern (s; p; o) are bound. If zero elements are bound, the triple pattern results in a total scan of the statement list, resulting in O(n). Since all triples are the expected result, this is the best possible worst case performance. If one element is bound, the chain for that particular element will be traversed with time O(count(bound; pos)). Again exactly the triples that answer the pattern are traversed.
Things change slightly for the cases where two or three of the (s; p; o) elements are bound. If two elements are bound, the shorter of the two lists will be traversed. This triple pattern can be returned in
O(min(count(bound1; pos1); count(bound2; pos2))) However, this could be O(n) if all triples use the two bound elements. If all three elements are bound, the shortest of the three lists will be traversed. This shortest list will be longest when the set of statements is exactly the three-way cross product of the set of resources. In this case, if the number of resources is m, then the number of statements is m3 and every list is of length m2. Thus the list length is n2=3, and a nd operation for three bound elements is O(n2=3).
Since an insertion rst requires a nd on the triple to be inserted, it incurs the worst-case cost of a nd with three bound elements, O(n2=3). It also incurs the cost of inserting any nodes in the triple that were not previously known into the dictionary, but this logarithmic time O(log m) is overshadowed by the worst case nd time. After that, adding the triple to the head of the lists is done in O(1) constant time. Thus the worst-case of the insertion operation is O(n2=3).
Here we note that this worst-case performance is indeed worse than other previously published approaches, which are logarithmic. However, the scenarios that produce these worst-case results are quite rare in practice, as will be shown in the following section. 5.2
While the worst-case performance is worse than other approaches, analyzing the relevant qualities of several example data sets leads us to believe that the average case performance is actually quite good.
The most relevant feature of a data set with respect to its performance within this indexing scheme is the length of the various statement lists for a particular subject, predicate, or object. For instance, the worst-case time of the insert operation and the nd operation with three bound elements is O(n2=3), but this is associated with the case that the set of triples is the cross-product of the subjects, predicates, and objects, which is a highly unlikely real world situation. Since these bounds are derived from the shortest statement list, analysis of the average list lengths in a data set is a key measure to how this scheme will perform in the real world. { Due to the previous, insert operations should generally be quite fast. { The predicate list is only likely to be used for nd operations when only the predicate is bound, and thus only when all statements with the given predicate must be touched to be returned anyway. { Find operations with two bound elements, which have the most troubling theoretical worst-case performance, necessarily include either a bound subject or bound object. As a result, these too should generally be quite fast.
These conclusions collectively suggest real world performance that is much more impressive than the worst-case analysis would imply, and this is shown empirically in the following section. 6
Since Hexastore [
Evaluation was performed on a MacBook Pro laptop with a 2.6 GHz dual
core CPU, 4 GB of RAM, and a 7200 RPM SATA HD, running Mac OS X
10.5.7. This platform was most convenient for execution of both systems. While
Hexastore's evaluation focused on only query performance, we feel it is important
to include insertion performance and memory utilization as well, as there are
many Semantic Web applications for which these factors are signi cant. We have
focused on the Lehigh University Benchmark [
The insertion performance graph is shown in Figure 2. The throughput of Parliament stays fairly stable at approximately 35k statements per second. This throughput is 3 to 7 times larger than that of Hexastore, which starts at approximately 9k statements per second, and declines to less than 5k statements per second as the total number of triples increases. Parliament's throughput results include both persisting the data to disk (the Python version of Hexastore is entirely memory-based) and forward chaining for its RDFS inference capabilities.
Figures 3, 4, 5, 6, and 7 show the relative query performance of Parliament and Hexastore on LUBM queries 1, 2, 3, 4, and 9 respectively.
Queries 1, 3, and 4 produce results where both systems appear to be following the same growth pattern, though Hexastore performs slightly better on queries 1 and 3 and Parliament performs better on query 4. Parliament also demonstrates more variability in the query execution times, which is likely a result of the dependency on the operating system's memory mapping functionality. 40 ) 35 d n o c e s r 30 0 3.5 )s 2.5 d n o c e s llii m ( e e s n o p s e R m i T1.5 3 2 1 0 0.0 0.5 1.0 1.5 2.0 2.5 3.0 3.5 4.0
4.5 Millions of Statements Loaded
Parliament HexaStore 1400 1200 Parliament HexaStore 20 18 16
Query 4 (modi ed) Response Time 0.0 0.5 1.0 1.5 2.0 2.5 3.0 Millions of Statements Loaded 3.5 4.0 4.5 Fig. 7. LUBM
Query 9 (modi ed) Response Time
Parliament HexaStore Parliament HexaStore
Queries 2 and 9 show Parliament and Hexastore following di erent growth curves, with Parliament performing better in query 9 and Hexastore performing better in query 2. This is more likely the result of di ering query plans within the two systems than a strength or de ciency of the storage structure, but without insight into the query planner of Hexastore we cannot verify this claim.
Finally, Table 2 shows an estimate of memory used by Hexastore and Parliament with all 4.3M statements loaded. These numbers are as reported by Mac OS X, but as is often the case with virtual memory management, the memory metrics are only useful as course estimates. However, they show what was expected; Parliament's storage scheme requires signi cantly less storage space.
Overall, we conclude that Parliament maintains very comparable query performance to Hexastore, while signi cantly outperforming Hexastore with respect to insertion throughput and required space. 7
In this paper, we have shown the storage and indexing scheme based on linked lists and memory mapping used in Parliament. This scheme is designed to balance insertion performance, query performance, and space usage. We found that while the worst-case performance does not compare favorably with other approaches, average case analysis indicates good performance. Experiments demonstrate that Parliament maintains excellent query performance while signi cantly increasing insertion throughput and decreasing space requirements compared to Hexastore. Future work will include experiments focusing on di erent query optimization strategies for Parliament, explanations and analysis of Parliament's internal rule engine, and further optimizations to the storage structure.