The complexity of regular expressions and property paths in SPARQL

DOI10.1145/2494529MaRDI QIDQ2943554zbMATHOpenAlexWikidataFDO

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

(8)

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

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)