Expressive path queries on graph with data

DOI10.2168/LMCS-11(4:1)2015zbMATH Open1448.68228arXiv1507.07911MaRDI QIDQ3196358FDOQ3196358

Authors: Pablo Barceló, Gaëlle Fontaine, Anthony Widjaja Lin 

Publication date: 29 October 2015

Published in: Logical Methods in Computer Science (Search for Journal in Brave)

Abstract: Graph data models have recently become popular owing to their applications, e.g., in social networks and the semantic web. Typical navigational 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 first 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 expressible 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 to WL in terms of expressive power.

Full work available at URL: https://arxiv.org/abs/1507.07911

Recommendations

• Expressive path queries on graphs with data
• Querying Graphs with Data
• Regular expressions with binding over data words for querying graph databases
• Regular expressions for querying data graphs
• Regular queries on graph databases

zbMATH Keywords

graph databasesregister automatagraph logicsnon elementaryRPQs

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Database theory (68P15)

Cited In (13)

• Expressive path queries on graphs with data
• Path logics for querying graphs: combining expressiveness and efficiency
• Querying best paths in graph databases
• Straight-path queries in trajectory data
• Path querying on acyclic graphs using Boolean grammars
• Investigations on Path Indexing for Graph Databases
• Title not available (Why is that?)
• Graph logics with rational relations: the role of word combinatorics
• Graph logics with rational relations: the role of word combinatorics
• Containment of queries for graphs with data
• Regular expressions with binding over data words for querying graph databases
• Querying Graphs with Data
• Relative expressive power of navigational querying on graphs

Uses Software

• XPath

This page was built for publication: Expressive path queries on graph with data

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3196358)