TriAL: A Navigational Algebra for RDF Triplestores

Abstract

Navigational queries over RDF data are viewed as one of the main applications of graphquery languages, and yet the standard model of graph databases –essentially labeled graphs — is different from the triples-basedmodel of RDF. While encodings of RDF databases into graph data exist,we show that even the most natural ones are bound to lose somefunctionality when used in conjunction with graph query languages. Thesolution is to work directly with triples, but then many propertiestaken for granted in the graph database context (e.g., reachability)lose their natural meaning.Our goal is to introduce languages that work directly over triples andare closed, i.e., they produce sets of triples, rather thangraphs. Our basic language is called $TA$, or Triple Algebra: itguarantees closure properties by replacing the product with a familyof join operations. We extend $TA$ with recursion, and explainwhy such an extension is more intricate for triples than forgraphs. We present a declarative language, namely a fragment ofdatalog, capturing the recursive algebra. For both languages, thecombined complexity of query evaluation is given by low-degreepolynomials. We compare our language with previously studied graph querylanguages such as adaptations of XPath, regular path queries, andnested regular expressions; many of these languages are subsumed bythe recursive triple algebra.We also provide an implementation of recursive $TA$ on top of a relational query engine, and show its usefulness by running a wide array of navigational queries over real world RDF data,while at the same time testing how our implementation compares to existing RDF systems.