Characterizing tractability of simple well-designed pattern trees with projection

DOI10.1007/S00224-020-10002-ZMaRDI QIDQ2035467zbMATH OpenOpenAlexWikidataFDO

Authors Stefan Mengel, Sebastian Skritek

Publication date 24 June 2021

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

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/s00224-020-10002-z

zbMATH Keywords

characterizing tractable classesFPTquery evaluationSPARQLwell-designed pattern trees

Mathematics Subject Classification ID

Model theory (03Cxx) Theory of data (68Pxx) Theory of computing (68Qxx)

Recommendations

• On the complexity of enumerating the answers to well-designed pattern trees
• Complexity and expressive power of weakly well-designed SPARQL
• Beyond well-designed SPARQL
• When is the evaluation of conjunctive queries tractable?
• Conjunctive queries over trees

Cites work

• Beyond well-designed SPARQL
• Block-Sorted Quantified Conjunctive Queries
• CONSTRUCT queries in SPARQL
• Decomposing quantified conjunctive (or disjunctive) formulas
• scientific article; zbMATH DE number 7561480 (Why is no real title available?)
• On the complexity of database queries
• On the complexity of enumerating the answers to well-designed pattern trees
• Parametrized complexity theory.
• Static analysis and optimization of semantic web queries
• Structural tractability of counting of solutions to conjunctive queries
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The tractability frontier of graph-like first-order query sets
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• When is the evaluation of conjunctive queries tractable?

Cited in

(4)

• Patterns with Bounded Treewidth
• The Complexity of Learning Tree Patterns from Example Graphs
• scientific article; zbMATH DE number 7561480 (Why is no real title available?)
• On the complexity of enumerating the answers to well-designed pattern trees

Describes a project that uses

Uses Software

• SPARQL

This page was built for publication: Characterizing tractability of simple well-designed pattern trees with projection

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