Evaluating graph queries using semantic treewidth

DOI10.4230/LIPICS.ICDT.2024.22MaRDI QIDQ6902065zbMATH OpenFDO

Authors Cristina Feier, Tomasz Gogacz, Filip Murlak

Publication date 11 November 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ICDT.2024.22

zbMATH Keywords

conjunctive two-way regular path queriesDatalog encodingfixed-parameter tractable evaluationoptimizationsemantic treewidth

Mathematics Subject Classification ID

Database theory (68P15)

Cites work

• Approximation and semantic tree-width of conjunctive regular path queries
• Conjunctive query containment revisited
• Constraint solving via fractional edge covers
• Finding Regular Simple Paths in Graph Databases
• scientific article; zbMATH DE number 839556 (Why is no real title available?)
• scientific article; zbMATH DE number 7297854 (Why is no real title available?)
• Hypertree decompositions and tractable queries
• Semantic acyclicity on graph databases
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Which problems have strongly exponential complexity?

Cited in

(2)

• Semantic tree-width and path-width of conjunctive regular path queries
• Fine-grained complexity of ontology mediated queries (invited paper)

This page was built for publication: Evaluating graph queries using semantic treewidth

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