RDF reasoning typically does not occur in browser-based applications despite being critical to the next generation of Web technologies. The primary constraint is that client-side reasoners do not meet the performance requirements of modern applications and the technicalities of using reasoners make them inaccessible to front-end developers.
CEUR ceur-ws.org
RDF reasoning has been integral to the Semantic Web since its inception in 2001 [
N3.js [
We implement Horn Logic [
First, we describe the existing N3.js store index. For each triple in the store, the subject, predicate and object are converted to a canonical string. An internal record maintains a mapping https://www.cs.ox.ac.uk/people/jesse.wright/ (W. Jesse)
© 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). between these canonical strings and a numerical ID. Triples are stored by adding these numerical IDs as keys in nested indexes (dictionaries). The N3.js store uses three, three-layered indexes to store data. The depth of these indexes reflects the fact that a triple has three elements: subject (s), predicate (p) and object (o). The three indexes are ordered as osp, spo and pos.
We assume that most applications have a limited number of rules, i.e. less than 100 as with RDFS and OWL2RL inference. Consequently our reasoner implementation1 optimises to reduce the time complexity of reasoning with respect to dataset size. The first step of reasoning in N3.js is re-writing rules to: (1) convert each non-variable term in the premise and conclusion into the internal ID used by the N3.js store index; (2) convert each variable into a pointer to a shared memory location into which concrete values for the variable will be substituted (c.f. Figure 2a); (3) identify matching patterns between a rule’s conclusion and the premise(s) of the same or other rules (c.f. Figure 3a) to establish which rules need to be evaluated next when new implicit data is discovered; and (4) precompute which of the 3 N3.js store indexes should be used for looking up triples matching a rule premise. Figure 1b shows how the rule {?s a ?o . ?o rdfs:subClassOf ?o2} → {?s a ?o2} (R1) is stored in memory with respect to the index mapping in Table 1a. Figure 3a displays the dependencies between {?o1 rdfs:subClassOf ?o2 . ?o2 rdfs:subClassOf ?o3 } → {?o1 rdfs:subClassOf ?o3} (R2) and R1.
Rules are then evaluated as follows: (1) perform a nested loop join on the premises, the outermost loop iterates through triples matching the first premise - substituting bindings into the variable memory locations (c.f. Figure 2a), subsequent nested loops iterate over the remaining premises and iterate through all triples matching the partially-bound pattern (c.f. Figure 2b); (2) new conclusion triples found added to the three-layered indexes; (3) for each new conclusion, identify matching premises from the same, or other, rules (c.f. Figure 3a); and (4) perform the subsequent reasoning run using rules with these premises pre-filled (c.f. Figure 3b) to avoid re-evaluating the same patterns across reasoning runs. 1https://github.com/rdfjs/N3.js/pull/296 (3a) The dependency between R2 and R1 is stored (3b) Matches to the first premise of R1 can then and can be used to pre-fill variables in R1 after R2 be iterated through to produce new derivations on has been evaluated. subsequent reasoning runs.
We evaluate this N3.js reasoner against the only other known browser-available reasoning
engines: EYE JS [
Table 1 presents the time taken to perform RDFS materialisation on Tim Berners-Lee’s profile
card and the FOAF ontology [
Table 2 presents the time taken to materialise all inferences for the the Data Deep Taxonomy Benchmark (DTB) using the N3.js Reasoner, EYE JS, and HyLAR. This modification of the deep taxonomy benchmark encodes subclasses as facts (:N0 rdfs:subClassOf :N1) rather than rules (?X rdf:type :N0 → ?X rdf:type :N1), as the N3.js reasoner is optimised to handle a large number of facts. The depth variable indicates the number of nested subclasses in the dataset. The extended (ext) taxonomy benchmark scales the number of instances of the class :N0 with the depth; consequently the number of implicit facts scales quadratically with depth.
The N3.js Reasoner primarily outperforms HyLAR because (1) HyLAR does not index triples or rules; consequently, HyLAR iterates through all facts when matching each premise taking () time (2) HyLAR does not create internal representations for terms and triples - resulting in (2a) costly string and object comparison operations for rule matching where N3.js is comparing integers and (2b) costly object creation where N3.js is adding integers to an existing index.
These results show that N3.js can eficiently reason over moderately-sized datasets in the browser, proving that we can now perform RDF inference in the client.
The reasoner is now distributed with N3.js; making it easily accessible to JavaScript developers via NPM. Documentation can be found in the README.
Jesse Wright is funded by the Department of Computer Science, University of Oxford.