The complexity of regular expressions and property paths in SPARQL

DOI10.1145/2494529MaRDI QIDQ2943554zbMATH OpenOpenAlexWikidataFDO

Authors Katja Losemann, Wim Martens

Publication date 3 September 2015

Published in ACM Transactions on Database Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/2494529

zbMATH Keywords

graph databasesquery evaluationregular expressions

Mathematics Subject Classification ID

Theory of programming languages (68N15) Information storage and retrieval of data (68P20) Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Knowledge representation (68T30) Mathematical aspects of software engineering (specification, verification, metrics, requirements, etc.) (68N30) Database theory (68P15)

Recommendations

• A trichotomy for regular simple path queries on graphs
• Evaluation and enumeration problems for regular path queries
• Querying regular graph patterns
• Finding Regular Simple Paths in Graph Databases
• On decidability of boundedness property for regular path queries

Cited in

(10)

• Formal languages in information extraction and graph databases
• Fine-Grained Complexity of Regular Path Queries
• Evaluation and enumeration problems for regular path queries
• A trichotomy for regular simple path queries on graphs
• A Trichotomy for Regular Trail Queries
• Fine-grained complexity of regular path queries
• Modern techniques for querying graph-structured databases
• Complexity and Expressiveness of ShEx for RDF
• Regular expressions with backreferences: polynomial-time matching techniques
• Evaluating regular path queries on compressed adjacency matrices

This page was built for publication: The complexity of regular expressions and property paths in SPARQL

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