commit 3e656e99f837f95fc9174676972c9fd6411aebc4
parent 642798d43fdeee53aa938da66dab3a86928ece7e
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 24 Jun 2025 22:50:33 +0200
commit with codex
Diffstat:
14 files changed, 90 insertions(+), 15 deletions(-)
diff --git a/conjunctive_query_acyclic b/conjunctive_query_acyclic
@@ -6,7 +6,7 @@ Can be evaluated by [yannakakis_algorithm] following a [join_tree]
the evaluation problem is in the complexity class [logcfl], and the the complexity is in O(database×query + output)
-We can test in linear time if a [hypergraph] is acyclic and if so build the join tree: [gyo] algorithm
+We can test in linear time if a [hypergraph] is acyclic and if so build the [join_tree]: [GYO_algorithm]
- not so obvious to understand where the [linear_time] claim comes from...
For Boolean queries, even with [self_joins], if the query is not acyclic then we can reduce from a hard problem ([triangle_detection] ou [hyperclique_detection])
diff --git a/homomorphism b/homomorphism
@@ -5,13 +5,7 @@
- [graph_homomorphism]
- [homomorphism_count]
-Variants:
-- [automorphism]
-- [endomorphism]
-- [morphism]
-- [embedding]
-- [onto_homomorphism]
- - [strong_onto_homomorphism]
+Variants: [homomorphism_variants]
Up: [mathematics]
diff --git a/homomorphism_variants b/homomorphism_variants
@@ -0,0 +1,11 @@
+# Homomorphism variants
+
+- [automorphism]
+- [endomorphism]
+- [morphism]
+- [embedding]
+- [onto_homomorphism]
+ - [strong_onto_homomorphism]
+- [retraction]
+
+Up: [homomorphism]
diff --git a/maximal_under_approximation b/maximal_under_approximation
@@ -0,0 +1,9 @@
+# Maximal under approximation
+
+A *maximal under approximation* with property P is an [under_approximation] Q' of Q having property P such that any query [query_contained] in Q having property P is also [query_contained] in Q'
+
+For [CQs], for P being "having treewidth at most k", maximal under approximations exist, cf [barcelo2014efficient]. Connection to [semantic_treewidth]: a [CQ] has semantic treewidth at most k iff it is [query_equivalent] to its maximal under approximation for [treewidth] k
+
+Up: [under_approximation]
+
+See also: [minimal_over_approximation]
diff --git a/minimal_over_approximation b/minimal_over_approximation
@@ -0,0 +1,9 @@
+# Minimal over approximation
+
+A *minimal over approximation* with property P is an [over_approximation] Q' of Q having property P such that any query having property P in which Q is [query_contained] in Q is such that Q' is also [query_contained] in it
+
+For [CQs], minimal over approximations do not always exist, and the decidability of their existence is open except in special cases, cf [morvan2025homomorphism] p133 and [barcelo2020more]
+
+Up: [over_approximation]
+
+See also: [maximal_under_approximation]
diff --git a/np_definition_reductions b/np_definition_reductions
@@ -0,0 +1,10 @@
+# Np definition reductions
+
+- usual notion is [many_one_reduction]
+ - with [turing_reduction], the difference between [np] and [coNP] disappears
+ - https://cstheory.stackexchange.com/questions/138/many-one-reductions-vs-turing-reductions-to-define-npc
+
+- it is open whether [np_complete] problems under [logspace_reductions] and [ptime_reduction] are different
+ - cf https://en.wikipedia.org/wiki/Log-space_reduction
+
+Up: [np_complete]
diff --git a/over_approximation b/over_approximation
@@ -0,0 +1,9 @@
+# Over approximation
+
+An [over_approximation] of a [query] Q in a given [query_class] is a [query] from the same class in which Q is [query_contained]
+
+- [minimal_over_approximation]
+
+Up: [query_approximation]
+
+See also: [under_approximation]
diff --git a/query_approximation b/query_approximation
@@ -0,0 +1,10 @@
+# Query approximation
+
+- [under_approximation]
+ - [maximal_under_approximation]
+- [over_approximation]
+ - [minimal_under_approximation]
+
+Up: [query_evaluation]
+
+See also: [Approximate_query_evaluation]
diff --git a/query_containment b/query_containment
@@ -20,3 +20,5 @@ For other [semirings]:
Up: [database_theory]
See also: [CSP], [morvan2025homomorphism]
+
+Aliases: query contained
diff --git a/query_evaluation b/query_evaluation
@@ -17,6 +17,7 @@
- [query_evaluation_incremental]
- [approximate_query_evaluation]
+- [query_approximation]
Up: [database_theory]
diff --git a/retraction b/retraction
@@ -0,0 +1,9 @@
+# Retraction
+
+A *retraction* is a [homomorphism] from a [structure] A to a [substructure] A' which is the [identity_function] on A'
+
+The [core] of a [structure] is a retraction on a [substructure] whose [domain] has minimum [cardinality]
+
+Discussed in [morvan2025homomorphism] p40-41
+
+Up: [homomorphism_variants]
diff --git a/semantic_acyclicity b/semantic_acyclicity
@@ -1,9 +1,9 @@
# Semantic acyclicity
-- decide if [conjunctive_query] is [query_equivalent] to [conjunctive_query_acyclic]
+The [computational_problem] of deciding if [query] is [query_equivalent] to [query_acyclic], within a specific [query_class]
+- for [UC2RPQ], cf [morvan2025homomorphism] Chapter V
+- for [CQs], it is [NP_complete], cf [barcelo2016semantic]
-- e.g., for [uc2rpq]
-
-Up: [database_theory]
+Up: [computational_problem], [database_theory]
See also: [semantic_treewidth], [formula_width]
diff --git a/semantic_treewidth b/semantic_treewidth
@@ -4,13 +4,17 @@ The semantic treewidth of a [query] Q in a certain [query_class] C is the smalle
Can be studied for [query_classes] such as [CQs] or for [UC2RPQs]
-Relevant [academic_papers]:
+[morvan2025homomorphism] p132: for [CQs], the semantic treewidth can be computed on the [core] of the [query], so it is [coNP_complete]
+
+Relevant [academic_paper]:
- [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]
+
+Can be used for [semantic_treewidth_evaluation]
+
+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]
See also: [semantic_acyclicity]
diff --git a/under_approximation b/under_approximation
@@ -0,0 +1,7 @@
+# Under approximation
+
+An [under_approximation] of a [query] Q in a given [query_class] is a [query] from the same class which is [query_contained] in Q, and an [over-approximation] is a query in which Q is [query_contained]
+
+- [maximal_under_approximation]
+
+Up: [query_approximation]
