View publication
| Title | Expressive Languages for Path Queries over Graphs with Data |
| Authors | Pablo Barceló, Gaelle Fontaine, Anthony Widjaja Lin |
| Publication date | 2013 |
| Abstract | Graph data models have recently become popular owing to their applications, e.g., in social networks, semantic web. Typical navi- gational query languages over graph databases | such as Conjunctive Regular Path Queries (CRPQs) | cannot express relevant properties of the interaction between the underlying data and the topology. Two languages have been recently proposed to overcome this problem: walk logic (WL) and regular expressions with memory (REM). In this paper, we begin by investigating fundamental properties of WL and REM, i.e., complexity of evaluation problems and expressive power. We rst show that the data complexity of WL is nonelementary, which rules out its practicality. On the other hand, while REM has low data complexity, we point out that many natural data/topology properties of graphs ex- pressible in WL cannot be expressed in REM. To this end, we propose register logic, an extension of REM, which we show to be able to express many natural graph properties expressible in WL, while at the same time preserving the elementariness of data complexity of REMs. It is also incomparable in expressive power against WL. |
| Downloaded | 7 times |
| Pages | 71-85 |
| Conference name | Logic for Programming, Artificial Intelligence, and Reasoning |
| Publisher | Springer (New York, NY, USA) |
|
|
| Reference URL |
|