Edinburgh Research Explorer

TriAL: A navigational algebra for RDF triplestores

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

https://dl.acm.org/citation.cfm?doid=3194314.3154385
Original languageEnglish
Article number5
Number of pages45
JournalACM Transactions on Database Systems
Volume43
Issue number1
Early online date23 Mar 2018
DOIs
Publication statusPublished - 11 Apr 2018

Abstract

Navigational queries over RDF data are viewed as one of the main applications of graph query languages, and yet the standard model of graph databases – essentially labeled graphs – is different from the triples-based model of RDF. While encodings of RDF databases into graph data exist, we show that even the most natural ones are bound to lose some functionality when used in conjunction with graph query languages. The solution is to work directly with triples, but then many properties taken 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 and are closed, i.e., they produce sets of triples, rather than graphs. Our basic language is called TriAL, or Triple Algebra: it guarantees closure properties by replacing the product with a family of join operations. We extend TriAL with recursion, and explain why such an extension is more intricate for triples than for graphs. We present a declarative language, namely a fragment of datalog, capturing the recursive algebra. For both languages, the combined complexity of query evaluation is given by low-degree polynomials.We compare our language with previously studied graph query languages such as adaptations of XPath, regular path queries, and nested regular expressions; many of these languages are subsumed by the recursive triple algebra. We also provide an implementation of recursive TriAL 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.

    Research areas

  • RDF, Triple algebra, Query evaluation

Download statistics

No data available

ID: 44424181