wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

semantic_treewidth (1039B)

      1 # Semantic treewidth
      2 
      3 The semantic treewidth of a [query] Q in a certain [query_class] C is the smallest value k such that Q is [query_equivalent] to a [query] in C having [treewidth] k
      4 
      5 Can be studied for [query_classes] such as [CQs] or for [UC2RPQs]
      6 
      7 [morvan2025homomorphism] p132: for [CQs], the semantic treewidth can be computed on the [core] of the [query], so it is [coNP_complete]
      8 
      9 Relevant [academic_paper]:
     10 
     11 - [figueira2023approximation], [journal_version] [figueira2024semantic]:
     12   - deciding whether a [UC2RPQ] is [query_equivalent] to a [query] of [treewidth] at most k is in [2EXPSPACE]
     13   - also studies how to do [query_approximation] of [UC2RPQs] with [queries] of small [treewidth]
     14 
     15 Can be used for [semantic_treewidth_evaluation]
     16 
     17 For [CQs], semantic treewidth is the limit of [FPT] evaluation, by [grohe2007complexity], assuming a fixed arity [relational_schema]. For unrestricted schemas something similar is known for [submodular_width], cf [marx2013tractable]
     18 
     19 See also: [semantic_acyclicity]
     20 
     21 Up: [database_theory]