semantic_treewidth (754B)
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 Relevant papers: 8 9 - [figueira2023approximation], [journal_version] [figueira2024semantic]: 10 - deciding whether a [UC2RPQ] is [query_equivalent] to a [query] of [treewidth] at most k is in [2EXPSPACE] 11 - also studies how to do [query_approximation] of [UC2RPQs] with [queries] of small [treewidth] 12 - better algorithm for evaluation ([fixed_parameter_tractable], singly exponential): [feier2024evaluating] 13 - cites [figueira2023approximation] 14 15 See also: [semantic_acyclicity] 16 17 Up: [database_theory]