The complexity of regular expressions and property paths in SPARQL

DOI10.1145/2494529zbMATH Open1321.68130OpenAlexW2045978585WikidataQ130907221 ScholiaQ130907221MaRDI QIDQ2943554FDOQ2943554

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

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

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)

Cited In (7)

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

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)