Diamond is a Rete match based system that evaluates SPARQL queries on Linked Data. The evaluation of SPARQL query predicates is a useful intermediate milestone for a system ultimately intended to support full rule-based inference on Linked Data. A byproduct is the integrated graphical rule debugging environment is a rst of its kind debug environment for SPARQL queries.
The Linked Data model is an emerging component of the Semantic Web. The
base layer of the Semantic Web is a representation of a directed labeled graph,
expressed using resource description framework (RDF). Each edge of such a
graph is commonly known as a triple. A triple is composed of a subject, a
predicate and an object. The predicate is the edge label. The subject and object are
vertex labels. Each constituent may be a URI. The intention is that labels form
global unique ids and overlay DNS services to identify a particular server that
may provide additional details (semantics) for the URI in the form of additional
triples. The object of a triple may contain a literal. Thus, an RDF graph can
represent complex data, spanning an arbitrary set of Internet servers [
Formal semantics for the Linked Data model are still emerging [
One can expect that Linked Data crawlers will be intelligent. To date, all Linked Data speci cations and most related work is limited to RDF. There is no explicit connection to the schema, ontology and rule layers, (RDFS, OWL, RIF), of the Semantic Web technology stack. Thus, in Linked Data, any semantic entailment will necessarily be implemented by inference processes associated with the processes that initiate and control the Linked Data crawlers. For example, SPARQL 1.1 allows triples to be updated. SPARQL 1.1 also inlucdes entailment rules that de ne closure over subclass hierarchies. Unless a system admits to limiting query and inferance to a potentialy inconsistent cache, it is necessarily the case that inferance entail freshly collected data.
Architecturally, the intrinsic, incremental behavior of the Rete Match aligns well with the web crawling aspects of the Linked Data model. This is true if one is evaluating rule predicates, or just a single predicate. When a Linked Data URI is dereferenced it returns a set of triples. The values of the triples may include additional URIs that have not yet been dereferenced. This operational behavior is identical to the algorithmic behavior of the Rete match per its original context, the incremental evaluation of changes to working memory in forward-chaining rule systems. Since an RDF graph is arbitrarily large and dynamic, even if an implementation references a local cache of prefetched triples, one can anticipate that any formal semantics will have to be consistent with an evaluation method that, operationally, crawls the web of Linked Data and reports results prior to reaching all reachable vertices. I.e. crawling can paused at any time, and the system evaluated.
Motivated, in part, by the anticipation intelligent Linked Data agents, we
have rst built a SPARQL query engine based on the Rete match and
architected the integration of a Rete-based system with link-crawling and caching
components [
Serendipitously our implementation of a graphical rule debugger is also a SPARQL query debugger. Those already familiar with graphical debugging environments for Rete-based inference engines will already be familiar with the operation and concomitant rendering of the Rete network and its content. This is not the case for most developers in the SPARQL community.
We anticipate the development of a SPARQL query debugger will, further,
be welcomed by that community as SPARQL queries can be expansive, even
larger than comparable SQL queries. To support this claim, a query from the
Berlin SPARQL Benchmark Suite is reproduced in Figure 1. This benchmark
is distinguished as it provides semantically equivalent queries in SQL, as shown
in Figure 2. The de nition of a set of Rete operators for SPARQL follows from
long standing connections made between relational algebra and rule predicates,
and results that prove an expressive equivalence between SPARQL, DatalogNeg
without recursion and relational algebra. [
The Diamond architecture is illustrated in Figure 3. The Rete network is created,
dynamically, from a runtime library of Rete netword object de nitions [
For demo purposes we use the benchmark query illustrated in Figure 1. For pedagogical purposes the screen shots are created by choosing an illustrative subset of 5 triple patterns. Video can be found at http://ribs.csres.utexas.edu/diamond/. Figure 4 is a screen shot of the debugger when there are triples that satisfy 4 of the 5 triple patterns. No triples that satisfy the third triple pattern.
Given the potential for a large number of both triples (data) and triple patterns (SPARQL clauses) the Rete network is rendered seperately from the data and the contents of the memory nodes. The contents of a memory node is viewed by clicking on the node in the Rete network, which opens a new window. Users may open, resize and move such windows anywhere on the screen. To save space, the gure shows three memory node windows overlayed on the window of the Rete network. We show, contents of one alpha-memory, that there is a repre2 http://www.openrdfo_ rg/ sentation of a successful join in the rst beta-memory. The remainder of the network is empty.
Upon a the arrival of a triple that satis es the third triple pattern the query becomes satis ed. Figure 5 shows the subsequent state of the Rete network. Each of the beta memories now has content. 4
Although Diamond currently treats a SPARQL query as the predicate of a single
rule, the system is easily extended to process a set of forward-chaining rules.
The overlap of operator level equivalence between SPARQL query predicate
evaluation and rule system evaluation is well established in the literature [
Acknowledgments. This research is supported by an NSF grant IIS-1018554. Juan F. Sequeda was supported by an NSF Graduate Research Fellowship.