Characterizing tractability of simple well-designed pattern trees with projection

DOI10.1007/s00224-020-10002-zOpenAlexW3084963100WikidataQ112681728 ScholiaQ112681728MaRDI QIDQ2035467

Sebastian Skritek, Stefan Mengel

Publication date: 24 June 2021

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

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

zbMATH Keywords

query evaluationSPARQLFPTcharacterizing tractable classeswell-designed pattern trees

Mathematics Subject Classification ID

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

Uses Software

• SPARQL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Structural tractability of counting of solutions to conjunctive queries
• On the complexity of database queries
• Parametrized complexity theory.
• Tractable hypergraph properties for constraint satisfaction and conjunctive queries
• Static analysis and optimization of semantic web queries
• Decomposing Quantified Conjunctive (or Disjunctive) Formulas
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The tractability frontier of graph-like first-order query sets
• When is the evaluation of conjunctive queries tractable?
• On the Complexity of Enumerating the Answers to Well-designed Pattern Trees
• Block-Sorted Quantified Conjunctive Queries

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