ARCHITECTURE
Figure 1 shows Kowari's high-level architecture. The topmost layer provides access APIs, below which is a query engine, backed by a storage layer.
The upper API layer supports many of the common Semantic Web and industry standard access APIs. The Query Engine is separated from the access API layer by a transport layer, allowing the APIs to be used across a network connection. The Session and Resolver APIs are responsible for taking access requests and directing them to the storage layer.
Data represented in the query engine exists in its original state and is said to be in a globalized form. Data represented in some portions of the storage layer is represented numerically and is said to be in a localized form, that is the numerical values are local to the Kowari instance and cannot be used externally. Globalization is the process of turning these local numeric representations of data into global representations suitable for returning to a user.
Access APIs
As shown in Figure 1, Kowari provides a number of developer level access APIs. These include Simple Ontology Framework API (SOFA)SOFA, Java RDF (JRDF)JRDF, JenaJena, interactive Tucana Query Language (iTQL)iTQL, an older version of the RDF Data Query Language (RDQL)RDQL and Simple Object Access Protocol (SOAP)SOAP. Other APIs including a JavaServer Pages tag library and an RDFS JavaBean are also provided but not shown in the diagram. The JRDF, SOFA, Jena and iTQL APIs can all be used on the client side or in-JVM local to the server.
Query Engine
The Kowari query engine uses an abstract object model that is bound to a concrete query syntax and other higher level APIs by the Session API. This abstraction allows for easy API integration and the adoption of different query languages. By default, Kowari's query engine parses and executes commands in iTQL.
After a query has been issued, it is parsed into a set of constraints and models. Models can be combined into an object called a model expression using the set operations union, intersection and partition. Individual models are described by URLs, of which the host portion is used to describe the server where the model appears.
Constraints define a subset of a model, and the results may be combined using inner joins and append operations. The full combination of constraints from a query forms an object called a constraint expression. The constraints in the constraint expression will normally be evaluated against the full model expression, however individual constraints may override this and can define a single model to be resolved against. If this override operation is employed then it is stored within the constraint that it applies to.
The full combination of the model expression and the constraint expression forms the basis of a query object, and this is then sent to the first server found in the model expression.
Once a query is received, the first task of the query engine is to estimate the size of the data that each constraint will resolve to, which is determined by resolving each constraint and requesting an upper bound to the size of the result. As results may be very large, using estimates to the upper bound can avoid unnecessary traversal of the data to obtain an exact figure.
Normal constraints are resolved by applying them to each model in the model expression, with the results being combined according to the operations from the model expression. For those constraints that override the model expression, the resolution is performed against a single model.
The constraint results are then used along with the operations defined in the constraint expression to construct an execution plan that will optimize the order in which the individual constraints should be joined together. This initial optimization attempts to minimize both time and space usage, with inner joins on smaller data sets being preferred in order to reduce the size of the working data set.
Once the initial plan is established, the query engine starts to combine the results using the join operations from the query. During this process the sizes of intermediate results may indicate a more efficient execution plan. When this happens the query engine will further optimize the plan, modifying the order of subsequent joins as it proceeds. Once the final join operation has completed the results are returned to the client.
Resolver API
At the interface between the upper parts of the query engine and the storage layer sits an abstraction layer called the Resolver API. This API gets its name from the resolution of constraints on RDF statements by the storage layer when called by the query engine. An incoming query is broken down to the point where individual constraints are to be resolved against individual RDF models. The Resolver API has been developed to allow these simple operations to be applied against almost any kind of data source. The intention is to allow pluggable graphs implementations other than the native Kowari data store. These alternative graph implementations are called Resolvers. There are two types of Resolver: external and internal. Internal resolvers are those whose data source is controlled solely by Kowari (e.g. the XA Statement Store), while external resolvers are those whose data source is not controlled by Kowari (e.g. a relational database).
Generally, RDF models are listed in a special model known as the system model. Models that can be resolved with Internal Resolvers are listed in the system model and are local to a Kowari server. For example, the native XA Statement Store is implemented as an internal Resolver, and all models stored in the XA Statement Store are listed in the system model. Arbitrary model URLs that are external to Kowari are not referred to in the system model and these are handled by the External Resolvers.
An internal Resolver operates on a data store internal to a Kowari server and therefore has its own model listed within the Kowari system model. Usually, internal Resolvers are used alongside data stores with RDF-ready information, which require very little or no conversion. Internally resolved models are the most stable as they are controlled solely by Kowari.
An external Resolver has its model outside of the scope of the system model and outside the control of Kowari. External Resolvers are useful for data stores that are not in an RDF-ready format and require some processing before results can be returned. This is most often used for resolving data in serialized file formats, but can also be useful for connecting to remote systems via wire protocols. A relational database or electronic mail service, for example, may be connected to Kowari via external Resolvers.
There is a danger to using external Resolvers because the data being queried is not controlled by Kowari and there is no guarantee of the model being present. External factors, such as other users, servers, or security protocols may alter or remove files or stores being resolved, thus contaminating or causing errors in the results.
The full API is comprised of three interfaces, known as Resolver, ResolverFactory and Resolution. The ResolverFactory interface has only 3 methods. These handle initialization, cleaning up, and creating instances of the Resolver interface. The Resolver interface has five methods, three of which are used for data modification and transactions, and can be ignored for read-only data stores, such as an RDF/XML file. The Resolution interface is for non-volatile data objects used to return results from the Resolver interface. The simplicity of these interfaces means that the Resolver API is quite easy to implement, regardless of the type of data being accessed.
When Kowari starts, a configuration file is read that contains a list of Resolvers to use. As each Resolver implementation is loaded, it registers its ability to handle a type of model. For external Resolvers, the type is based on the protocol part of the model's URL. When a constraint is to be resolved against a model on the current server, the query engine looks up the type in the system model, and maps the request to the appropriate Resolver.
Data Store
Kowari's native data store (the XA Statement Store) is a native Java version 1.4 transactional data store that stores RDF statements persistently on disk without the use of an external database.
The Statement Store stores statements as quad-tuples consisting of subject, predicate, object and meta nodes. The first three items form a standard RDF statement and the meta node describes which model the statement appears in. Each quad is unique, so a statement that appears in two models will be listed twice, with differing meta node values.
To increase speed and reduce redundancy, the nodes that make up a statement are stored as 64 bit integers, allocated by the Node Pool. These integers are known as node numbers, and correspond to URIs and Literals which are stored in the String Pool. The Statement Store is essentially composed of these two stores that together provide the full requirements of RDF storage.
Kowari stores RDF statements in six different orders. This corresponds to the minimum number of ways the four node types can be arranged such that any collection of one to four nodes can be used to find any statement or group of statements that match. Each of these orderings therefore acts as a compound index, and independently contains all of the statements for the RDF store.
The String Pool is built using an Adelson-Velskii and Landis (AVL) tree to store and order its elements, while the indexes in the Statement Store are based on a hybrid of AVL trees and B-Trees. AVL trees are balanced binary trees, offering fast, simple searching and modification, while B-trees are balanced multi-branch trees which can take more space overhead, with each node taking longer to traverse, but the trees are shallower to search.
The String Pool uses an AVL tree to store indexes into a set of flat files which hold any kind of RDF data. In this context, RDF data includes URI References, String Literals, and recently, all XML Schema data types. The data is ordered in the tree according to the semantics of each type. The pool also holds a reverse index to locate any entry according to its node number.
The Statement Store indexes use an AVL tree to locate a block of statements found in a separate file. Within each block is up to 256 ordered statements. Like a B*-tree, these blocks make the tree much shallower to search, and get split into two blocks when more than the maximum number of statements are inserted. However, it is indexed with an AVL tree, with the speed and simplicity that this structure offers. Thus, the hybrid picks up some of the speed advantages of both approaches.
The statement-based approach of the storage layer treats predicates (properties) as just another data element. This contrasts with existing database formalisms (e.g. SWRDB), which treat relations as completely different from elements. The statements are indexed using six parallel AVL trees - an index for each required ordering of subject, predicate, object and meta node. AVL trees are balanced binary search trees where the height of the two subtrees of any node differs by at most one, the children of any node are themselves AVL trees. This structure has the useful property that searching, insertion, and deletion times are O(log n), where n is the number of nodes in the tree. O(log n) times are guaranteed by the fact that the trees are balancedAVL.
Each index in Kowari is an AVL tree that provides addressing information into a large random-accessed file. Using this structure allows the AVL trees to remain relatively small and can often fit into physical memory. In practice, the speed of searching, insertion and deletion operations are linear when the depth of the AVL trees is relatively small. As trees may become unbalanced during write operations, they must be rebalanced, often by rotation of a node's children. This is a simple operation on the addressing information tree that does not affect the underlying data. In the general case, rebalancing times are also O(log n). Nodes are split into two when full.
AVL trees are particularly useful for RDF stores whose query approach systematically constrains one or more elements of a triple (or quad if model information is added to the "triple"). Triples may be indexed in order and rotated to create parallel indexes. Any given constraint on one or more triple elements may thus be satisfied as a simple range in one of the indexes. For example, a query asking for RDF statements whose subject is a given string may be satisfied by performing a search for triples in a subject-first index where the subject returned is the number corresponding to that string literal that can be used as a key in a hash table lookup.
If the meta nodes are ignored for simplicity, the number of required indexes is reduced to 3. The AVL trees for these indexes each have a different key ordering, defined as follows:
(subject, predicate, object), (predicate, object, subject) and (object, subject, predicate).Each node in the AVL tree holds the following information:
- A set of triples sorted in the key order for this tree;
- The number of triples in the set for this node;
- A copy of the first triple in the sorted set;
- A copy of the last triple in the sorted set;
- The ID of the left subtree node;
- The ID of the right subtree node; and
- The height of the subtree rooted at this node.
All triples in the left subtree compare less than the first triple in the sorted set and all triples in the right subtree compare greater than the last triple in the sorted set. Space for a fixed maximum number of triples is reserved for each node. A triple is added to a tree by inserting it into the sorted set of an existing node. If the only appropriate node is full then a new node will be allocated and added to the tree. A triple is removed from the tree by identifying the node that contains it and removing it from the sorted set. If the sorted set becomes empty then the node is removed from the tree.
A design goal was to keep index addressing information in memory for as long as possible. AVL tree nodes are split between two files such that the sorted set of triples for a node are stored as a block in one file while the remaining fields are stored as a record in the other file. This ensures that the traversal of an AVL tree does not result in sorted sets of triples being unnecessarily read into memory. This also allows for different file I/O mechanisms to be used for the two files. This is similar to approaches using B-trees in many relational databases.
B-trees generally do not fill their nodes completely, with each node having some number of entries between N/2 and N, where N is the order of the tree. This results in an index being (on average) about 25% larger than it needs to be. This pushes B-tree indexes out of a range that can be memory-mapped or cached, much sooner. This is a major concern when indexes can reach several gigabytes in size. AVL trees also tend to be faster to traverse than B-trees when the entire tree fits in memory.
Figure 2 illustrates the internal workings of the directed graph implementation in Kowari, showing a portion of an index implemented in an AVL tree (for simplicity the meta node information is not shown). The data (stored as a series of triples) is sorted by the first component of the triple. The first component of each triple in the figure represents the address of a subject. The data is stored only in the indices and is not stored separately elsewhere. Storing the data multiple times increases the storage requirements for the data set but allows for very rapid responses to queries since each query component can use the most appropriate index.
