Projects per year
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 triplesbased 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 lowdegree 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.
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 lowdegree 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.
Original language  English 

Article number  5 
Number of pages  46 
Journal  ACM Transactions on Database Systems 
Volume  43 
Issue number  1 
Early online date  23 Mar 2018 
DOIs  
Publication status  Published  1 Apr 2018 
Keywords
 RDF
 Triple algebra
 Query evaluation
Fingerprint
Dive into the research topics of 'TriAL: A navigational algebra for RDF triplestores'. Together they form a unique fingerprint.

VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research
Profiles

Leonid Libkin
 School of Informatics  Chair of Foundations of Data Management
 Laboratory for Foundations of Computer Science
 Foundations of Computation
Person: Academic: Research Active