commit 2d2ad7228a6d9691982621ee08a72e0367a69a34
parent b508197fc3be90990b0da7ea8122c3ee05801581
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 21 Jun 2025 20:14:58 +0200
commit with codex
Diffstat:
21 files changed, 150 insertions(+), 10 deletions(-)
diff --git a/core b/core
@@ -18,6 +18,6 @@ The [core] of an [instance] A is a [subinstance] B of A such that there is no [h
Up: [homomorphism]
-See also: [chase_core]
+See also: [chase_core], [CQ_minimization]
Aliases: cores
diff --git a/cq_minimization b/cq_minimization
@@ -0,0 +1,11 @@
+# CQ minimization
+
+The *CQ minimization* problem is the [query_minimization] problem on [CQs]
+
+Can be done by a [greedy_algorithm], as explained in [morvan2025homomorphism] p17 among other places: iteratively remove [variables] while the resulting [query] (on an [induced_substructure]) is still [query_equivalent]
+
+The result is unique up to [isomorphism]: it is called the [core] of Q. It also minimizes the number of [atoms], the [pathwidth], and the [treewidth]
+
+Up: [query_minimization]
+
+Aliases: minimization_conjunctive_query
diff --git a/crpq b/crpq
@@ -1,13 +1,20 @@
# CRPQ
-- [c2rpq]
-- [ucrpq]
-- [rpq]
-- [conjunctive_query]
+[Special_cases]:
+- [RPQ]
+- [CQ]
-[Generalization]: [conjunctive_context_free_path_query]
+[Generalizations]:
+- [C2RPQ]
+- [UCRPQ]
+- [conjunctive_context_free_path_query]
-- [crpq_containment]
+[Computational_problems]:
+- [CRPQ_containment]
+- [CRPQ_minimization]
+
+Concepts:
+- [CRPQ_expansion]
Up: [graph_query_languages]
diff --git a/crpq_containment b/crpq_containment
@@ -5,3 +5,5 @@
[beaudou2023complexity]
Up: [crpq], [query_containment]
+
+See also: [UCRPQ_containment]
diff --git a/crpq_expansion b/crpq_expansion
@@ -0,0 +1,11 @@
+# CRPQ expansion
+
+An *expansion* of a [CRPQ] Q is a [CQ] obtained from Q by replacing each [atom] A by a [path] for some [word] of the [formal_language] that labels A
+
+An *expansion* of a [UCRPQ] Q is an expansion of some disjunct of Q
+
+Up: [crpq]
+
+See also: [Crpq_minimization]
+
+Aliases: UCRPQ expansion
diff --git a/crpq_fully_contracted b/crpq_fully_contracted
@@ -0,0 +1,6 @@
+# CRPQ fully contracted
+
+A [CRPQ] is *fully contracted* if every [CRPQ_segment] consists of precisely one [atom]
+- defined in [morvan2025homomorphism] p94
+
+Up: [crpq_minimization]
diff --git a/crpq_internal_variable b/crpq_internal_variable
@@ -0,0 +1,5 @@
+# CRPQ internal variable
+
+A [variable] in a [CRPQ] which has [in_degree] 1 and [out_degree] 1 and is not an [output_variable]
+
+Up: [crpq_segment]
diff --git a/crpq_minimal b/crpq_minimal
@@ -0,0 +1,10 @@
+# CRPQ minimal
+
+A [CRPQ] Q is *minimal* if there is no [query_equivalent] [CRPQ] having less [atoms] than Q
+- defined in [morvan2025homomorphism] p93
+
+Corollary IV.2.9 of [morvan2025homomorphism]: every [strongly_minimal_CRPQ] is minimal
+
+Up: [crpq_minimization]
+
+Aliases: minimal CRPQ, minimal CRPQs
diff --git a/crpq_minimization b/crpq_minimization
@@ -0,0 +1,14 @@
+# Crpq minimization
+
+The [computational_problem] of computing from a [CRPQ] Q a [CRPQ_minimal] which is [query_equivalent] to Q
+
+Covered in [morvan2025homomorphism]
+
+Formal [decision_problem] for [UCRPQs]: [UCRPQ_minimization_problem]
+
+Notions:
+- [CRPQ_fully_contracted]
+- [CRPQ_non_redundant]
+- [CRPQ_strongly_minimal]
+
+Up: [crpq], [query_minimization]
diff --git a/crpq_redundant_atom b/crpq_redundant_atom
@@ -0,0 +1,6 @@
+# Crpq redundant atom
+
+An [atom] in a [CRPQ] is *redundant* if removing it results in a [query_equivalent] [CRPQ]
+- defined in [morvan2025homomorphism] p94
+
+Up: [crpq_minimization]
diff --git a/crpq_segment b/crpq_segment
@@ -0,0 +1,8 @@
+# CRPQ segment
+
+A [crpq_segment] is a maximal path of [atoms] of a [CRPQ] where every intermediate [variable] is a [CRPQ_internal_variable]
+- defined in [morvan2025homomorphism] p93
+
+Up: [crpq_fully_contracted]
+
+Aliases: CRPQ segments
diff --git a/embedding b/embedding
@@ -0,0 +1,5 @@
+# Embedding
+
+An [injective] [homomorphism]
+
+Up: [homomorphism], [injective]
diff --git a/graph_embedding b/graph_embedding
@@ -9,4 +9,4 @@ Up: [graph]
Aliases: graph embeddings
-See also: [structure_embedding]
+See also: [structure_embedding], [embedding]
diff --git a/homomorphism b/homomorphism
@@ -9,6 +9,7 @@ Variants:
- [automorphism]
- [endomorphism]
- [morphism]
+- [embedding]
Up: [mathematics]
diff --git a/minimization b/minimization
@@ -1,6 +1,6 @@
# Minimization
-- [minimization_conjunctive_query], cf [homomorphism] / [core]
+- [query_minimization]
- [minimization_automaton]
- [automaton_minimal]
diff --git a/query_minimization b/query_minimization
@@ -1,7 +1,16 @@
# Query minimization
+The [function_problem], given a [query] Q in a [query_language], of computing a [query] Q' (usually in the same language) which is [query_equivalent] to Q but is "smaller"
+- usually smaller number of [atoms]
+- but can be another measure, e.g., the [treewidth]
+
+This problem can be turned into a [decision_problem] by asking, given a [query] Q and integer k, whether there exists a query which is [query_equivalent] to Q but has at most k atoms
+
+For various [query_languages]:
- [CQ_minimization]
+ - cf [homomorphism] / [core]
- [CRPQ_minimization]
+- [UCRPQ_minimization]
Up: [query_problems]
diff --git a/semantic_treewidth b/semantic_treewidth
@@ -4,7 +4,7 @@ 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 papers:
+Relevant [academic_papers]:
- [figueira2023approximation], [journal_version] [figueira2024semantic]:
- deciding whether a [UC2RPQ] is [query_equivalent] to a [query] of [treewidth] at most k is in [2EXPSPACE]
diff --git a/ucrpq b/ucrpq
@@ -0,0 +1,10 @@
+# UCRPQ
+
+A [disjunction] of [CRPQs]
+
+- [UCRPQ_minimization]
+- [UCRPQ_containment]
+
+Up: [CRPQ]
+
+Aliases: UCRPQs
diff --git a/ucrpq_containment b/ucrpq_containment
@@ -0,0 +1,9 @@
+# UCRPQ containment
+
+The [query_containment] [computational_problem] for [UCRPQs]
+
+[Academic_papers]:
+- Studied in [figeira2025semantic], e.g., Proposition 3.11
+- Reviewed in [morvan2025homomorphism]
+
+Up: [query_containment], [UCRPQ]
diff --git a/ucrpq_minimization_problem b/ucrpq_minimization_problem
@@ -0,0 +1,15 @@
+# UCRPQ minimization problem
+
+[Decision_problem] defined in [morvan2025homomorphism], p91:
+- Input: a [UCRPQ] Q and integer k
+- Output: is there a [query_equivalent] [UCRPQ] with at most k [atoms] which is equivalent to Q
+
+For [CRPQs], the problem is [EXPSPACE_hard] ([morvan2025homomorphism], Theorem IV.5.2) and in [2EXPSPACE] ([CRPQ_minimization_upper_bound], [morvan2025homomorphism], Theorem IV.3.1)
+
+For [UCRPQs], the problem is [EXPSPACE_complete] ([morvan2025homomorphism], Corollary IV.4.7)
+
+Different from [CRPQ_minimization] in the sense that there are [minimal_CRPQs] that admit a [query_equivalent] [UCRPQ] whose constituent [CRPQs] have fewer [atoms], cf [morvan2025homomorphism] Proposition IV.4.1
+
+Up: [crpq_minimization], [decision_problem]
+
+Aliases: CRPQ minimization problem
diff --git a/ucrpq_strongly_minimal b/ucrpq_strongly_minimal
@@ -0,0 +1,11 @@
+# CRPQ strongly minimal
+
+A [UCRPQ] Q is *strongly minimal* if it has a [homomorphism_minimal] [UCRPQ_expansion] whose [core] has a number of [CRPQ_segments] equal to the number of [atoms] of Q
+
+By Corollary IV.2.9 of [morvan2025homomorphism]: every strongly minimal CRPQ is a [minimal_CRPQ]. But by Proposition IV.2.15 there are [minimal_CRPQs] that are not strongly minimal, for instance x -a^+-> x
+
+By Corollary IV.2.16 of [morvan2025homomorphism], it is [EXPSPACE_hard] to test whether a [UCRPQ] is strongly minimal
+
+Up: [crpq_minimization]
+
+Aliases: strongly minimal CRPQ, strongly minimal UCRPQ
