commit 665a287bc34a84a61bea18b19f87429ccf88cff6
parent eade7c24f28a2143201855e30b4e0b0b1638ae20
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Sat, 21 Jun 2025 22:05:27 +0200
commit with codex
Diffstat:
7 files changed, 46 insertions(+), 1 deletion(-)
diff --git a/conjunctive_query_boolean b/conjunctive_query_boolean
@@ -4,4 +4,4 @@
Up: [conjunctive_query], [query_boolean]
-Aliases: Boolean CQ, Boolean CQs, Boolean conjunctive query, BCQ, BCQs
+Aliases: Boolean CQ, Boolean CQs, Boolean conjunctive query, BCQ, BCQs, Boolean conjunctive queries
diff --git a/homomorphism b/homomorphism
@@ -10,6 +10,8 @@ Variants:
- [endomorphism]
- [morphism]
- [embedding]
+- [onto_homomorphism]
+ - [strong_onto_homomorphism]
Up: [mathematics]
diff --git a/homomorphism_minimal b/homomorphism_minimal
@@ -0,0 +1,7 @@
+# Homomorphism minimal
+
+A [query] Q (in a [query_language]) is *homomorphism minimal* if there is no [query] Q' (in the same [query_language]) such that Q' has a [homomorphism] to Q but Q has no [homomorphism] to Q'
+
+Defined in [morvan2025homomorphism]
+
+Up: [ucrpq_strongly_minimal]
diff --git a/onto_homomorphism b/onto_homomorphism
@@ -0,0 +1,7 @@
+# Onto homomorphism
+
+A [homomorphism] which is [surjective]
+
+Stronger notion: [strong_onto_homomorphism]
+
+Up: [homomorphism]
diff --git a/query_containment b/query_containment
@@ -0,0 +1,22 @@
+# Query containment
+
+For [Boolean_conjunctive_queries], it amounts to [query_evaluation] by [chandra1977optimal]
+- via [canonical_query] of a [relational_instance] and [canonical_instance] of a [query]
+- this is because [the_following_are_equivalent]:
+ - A [structure] A has a [homomorphism] to a structure B
+ - B satisfies the [canonical_query] of A
+ - the [canonical_query] of B is included in the [canonical_query] of A
+
+For other [query_languages]:
+- [CQs_with_inequalities], cf [jayram2006containment]
+- [Datalog_nonrecursive], cf [query_containment_datalog_nonrecursive]
+
+For other [semirings]:
+- [containment_bag_semantics]
+- [containment_other_semirings]
+
+[Computational_problem]: [query_containment_problem]
+
+Up: [database_theory]
+
+See also: [CSP], [morvan2025homomorphism]
diff --git a/query_containment_problem b/query_containment_problem
@@ -2,6 +2,8 @@
[Computational_problem] of deciding [query_containment]
+The query containment problem and [query_equivalence_problem] are [NP_complete] for [CQs] and [UCQs]
+
Up: [query_containment]
Aliases: QCP
diff --git a/strong_onto_homomorphism b/strong_onto_homomorphism
@@ -0,0 +1,5 @@
+# Strong onto homomorphism
+
+A [homomorphism] which is [surjective] on the [domain_elements] and on the [facts]
+
+Up: [onto_homomorphism]
