commit 8dedaa6cf5fdec80b58f0ee7b50d9e76e5897783
parent 9a9a5b15a5dd738fbb7abe47f1b2d94bb05e2f27
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Fri, 10 Jan 2025 14:51:08 +0100
commit with codex
Diffstat:
6 files changed, 41 insertions(+), 6 deletions(-)
diff --git a/2rpq b/2rpq
@@ -0,0 +1,9 @@
+# 2RPQs
+
+A [generalization] of [RPQs] where we allow inverse predicates
+
+Generalization: [C2RPQs]
+
+Up: [graph_query_languages], [regular_path_query]
+
+Aliases: 2RPQs
diff --git a/approximation b/approximation
@@ -1,7 +1,7 @@
# Approximation
Two kinds of approximation:
-- [approximation_additive]: section 3.2.1 souihli2012querying [monte_carlo] [hoeffdings_inequality]
+- [approximation_additive]: section 3.2.1 [souihli2012querying] [monte_carlo] [hoeffdings_inequality]
- [approximation_multiplicative]: what follows is about those
Complexity classes [approximation_class]:
@@ -14,7 +14,7 @@ Problems: [approximation_problems]
Reasons not to get it:
- conditional inapproximability [fpras_vs_npc]: no FPRAS if the [decision_problem] "décision =0" is [np_hard], unless you have [nptime] = [bpp] or [nptime] = [rp]
- [sharp_is]: no FPRAS to count the [independent_set] of a [graph]
-- no [FPRAS] for [monotone2cnf] (calautti2022query), cf [sharp_satisfiability_fpras]
+- no [FPRAS] for [monotone2cnf] ([calautti2022query]), cf [sharp_satisfiability_fpras]
- [hardness_of_approximation]
Applications:
@@ -25,6 +25,8 @@ Applications:
Notion of [reduction]: [approximation_preserving_reduction]
+Other notion: [query_approximation]
+
Up: [research_directions]
Aliases: approximate counting
diff --git a/c2rpq b/c2rpq
@@ -1,7 +1,9 @@
# C2RPQ
-conjunction of [2rpq]
+[Query_conjunction] of [2RPQs]
Generalization: [uc2rpq]
Up: [graph_query_languages], [conjunctive_query], [2rpq], [crpq]
+
+Aliases: C2RPQs
diff --git a/query_language b/query_language
@@ -39,3 +39,5 @@
Up: [database_theory]
See also: [query_rewriting]
+
+Aliases: query class, query classes, query languages
diff --git a/semantic_treewidth b/semantic_treewidth
@@ -0,0 +1,17 @@
+# Semantic treewidth
+
+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
+
+Can be studied for [query_classes] such as [CQs] or for [UC2RPQs]
+
+Relevant papers:
+
+- [figueira2023approximation], [journal_version] [figueira2024semantic]:
+ - deciding whether a [UC2RPQ] is [query_equivalent] to a [query] of [treewidth] at most k is in [2EXPSPACE]
+ - also studies how to do [query_approximation] of [UC2RPQs] with [queries] of small [treewidth]
+- better algorithm for evaluation ([fixed_parameter_tractable], singly exponential): [feier2024evaluating]
+ - cites [figueira2023approximation]
+
+See also: [semantic_acyclicity]
+
+Up: [database_theory]
diff --git a/uc2rpq b/uc2rpq
@@ -1,9 +1,12 @@
# UC2RPQ
-union of [c2rpq]
-
-- [feier2024evaluating]: article on [treewidth]
+[query_union] of [C2RPQs]
+Studied for such [queries]:
- [semantic_acyclicity]
+ - [figueira2024semantic]
+ - [feier2024evaluating]: article on [treewidth] and
Up: [graph_query_languages], [c2rpq], [union_of_conjunctive_queries]
+
+Aliases: UC2RPQs
