Projects per year
Abstract
Querying RDF data is 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 languages with relational languages, such as finitevariable logics, and 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 examples of the usefulness of TriAL in querying graph and RDF data.
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 languages with relational languages, such as finitevariable logics, and 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 examples of the usefulness of TriAL in querying graph and RDF data.
Original language  English 

Title of host publication  Proceedings of the 32nd ACM SIGMODSIGACTSIGART Symposium on Principles of Database Systems, PODS 2013 
Publisher  ACM 
Pages  201212 
Number of pages  12 
ISBN (Print)  9781450320665 
DOIs  
Publication status  Published  2013 
Fingerprint
Dive into the research topics of 'Trial for RDF: adapting graph query languages for RDF data'. Together they form a unique fingerprint.Projects
 2 Finished


XML with Incomplete Information: Representation, Querying and Applications
1/09/09 → 30/11/13
Project: Research