Regular queries on graph databases

DOI10.1007/s00224-016-9676-2zbMath1375.68047OpenAlexW2339264483MaRDI QIDQ2402613

Miguel Romero, Moshe Y. Vardi, Juan L. Reutter

Publication date: 20 September 2017

Published in: Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2015/4984/

zbMATH Keywords

graph databasescontainmentregular queriesconjunctive regular path queries

Mathematics Subject Classification ID

Database theory (68P15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Certified Graph View Maintenance with Regular Datalog, Querying the Unary Negation Fragment with Regular Path Expressions., Fine-Grained Complexity of Regular Path Queries, Foundations of graph path query languages. Course notes for the reasoning web summer school 2021, Path querying with conjunctive grammars by matrix multiplication, Unnamed Item, Unnamed Item, Path querying on acyclic graphs using Boolean grammars

Uses Software

• nSPARQL
• XPath
• GraphLog

Cites Work

• Unnamed Item
• Unnamed Item
• Relative expressive power of navigational querying on graphs
• Decidable containment of recursive queries
• Rewriting of regular expressions and regular path queries
• Recursive queries and context-free graph grammars
• Conjunctive query containment revisited
• Containment of queries for graphs with data
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Regular Path Queries in Lightweight Description Logics: Complexity and Algorithms
• Semantic Acyclicity on Graph Databases
• Incomplete Information in Relational Databases
• Equivalences Among Relational Expressions with the Union and Difference Operators
• Conjunctive query containment and answering under description logic constraints
• Data Integration in the Life Sciences
• Regular Queries on Graph Databases.