commit 73b42532a9d15d4b0b84d9aef5bcbc673225a63e
parent 63afabfe4e565589d63fe4daeb9c08d911b68ae2
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Tue, 22 Sep 2026 16:23:25 +0200
commit with codex
Diffstat:
19 files changed, 82 insertions(+), 11 deletions(-)
diff --git a/approximation b/approximation
@@ -33,4 +33,4 @@ Other notions:
Up: [research_directions]
-Aliases: approximate counting, approximated
+Aliases: approximate counting, approximated, approximations
diff --git a/asymmetric_graph b/asymmetric_graph
@@ -0,0 +1,9 @@
+# Asymmetric graph
+
+A [graph] where the only [automorphism] is the [identity_function]
+
+See also: [graph_rigid]
+
+Up: [graph]
+
+Aliases: asymmetric graphs, graph assymetric, graphs assymetric, asymmetric digraphs, digraph assymetric, digraphs assymetric, assymetric digraph
diff --git a/conjunctive_query b/conjunctive_query
@@ -9,6 +9,7 @@ Subclasses:
- [conjunctive_query_hierarchical]
- [conjunctive_query_acyclic]
- [conjunctive_query_self_join_free]
+- [connected_CQ]
Generalization:
- [conjunctive_query_signed]
diff --git a/connected_component b/connected_component
@@ -8,7 +8,7 @@ Variants:
- [strongly_connected_component]
- [biconnected_component]
-See also: [graph_connected]
+See also: [graph_connected], [connected_query]
Up: [graph_basic_notions]
diff --git a/connected_cq b/connected_cq
@@ -0,0 +1,7 @@
+# Connected CQ
+
+A [CQ] whose [Gaifman_graph] is [connected]
+
+Up: [conjunctive_query], [query_connected]
+
+See also: [connected_UCQ], [connected_homomorphism_closed_query]
diff --git a/disjoint_path_2 b/disjoint_path_2
@@ -12,4 +12,4 @@ Up: [disjoint_paths]
See also: [edge_connectedness], [simple_path_RPQ], [even_path_problem]
-Aliases: two disjoint path problem, two disjoint paths, Disjoint path 2, twodisjoint path problem, two disjoint simple path, two disjoint simple paths, two disjoint simple path problem, two disjoint simple paths problem, 2 disjoint path problem, 2 disjoint paths problem
+Aliases: two disjoint path problem, two disjoint paths, two disjoint paths problem, Disjoint path 2, twodisjoint path problem, two disjoint simple path, two disjoint simple paths, two disjoint simple path problem, two disjoint simple paths problem, 2 disjoint path problem, 2 disjoint paths problem, 2 disjoint simple path, 2 disjoint simple paths, 2 disjoint simple path problem, 2 disjoint simple paths problem
diff --git a/first_order_rewriting b/first_order_rewriting
@@ -1,7 +1,7 @@
# First order rewriting
-- [fok_rewriting]
+- [FOk_rewriting]
Up: [query_rewriting], [first_order_logic]
-Aliases: first_order_rewritability, first_order_rewritable
+Aliases: first_order_rewritability, first_order_rewritable, FO rewritable, FO-rewritable
diff --git a/graph_operations b/graph_operations
@@ -5,6 +5,7 @@
- [edge_contraction]
- [underlying_undirected_graph]
- [subdivision]
+- [replacement_operation]
Up: [graph]
diff --git a/graph_rigid b/graph_rigid
@@ -0,0 +1,11 @@
+# Rigid graph
+
+A [graph] which is [rigid]
+
+[graph_rigid_vs_asymmetric]
+
+Up: [graph], [rigid]
+
+Aliases: rigid graph, rigid graphs, rigid digraph, rigid digraphs
+
+See also: [asymmetric_graph]
diff --git a/graph_rigid_vs_asymmetric b/graph_rigid_vs_asymmetric
@@ -0,0 +1,5 @@
+# Graph rigid vs asymmetric
+
+In [hell2004graphs] Section 4.2: "a [digraph] is [rigid_digraph] if and only if it is [asymmetric_digraph] and a [core]"
+
+Up: [graph_rigid]
diff --git a/homomorphism b/homomorphism
@@ -11,6 +11,7 @@ Notions:
- [homomorphism_closed]
- [homomorphism_equivalence]
- [homomorphism_count]
+- [homomorphic_image]
[Computational_problem]: [homomorphism_problem]
@@ -18,6 +19,6 @@ Variants: [homomorphism_variants]
Up: [mathematics]
-See also: [core], [retraction_minimum_violation]
+See also: [core], [retraction_minimum_violation], [homomorphism_closed_query]
Aliases: homomorphisms, hom
diff --git a/homomorphism_closed b/homomorphism_closed
@@ -5,8 +5,12 @@ A [query] Q is *closed under [homomorphism]* if the following holds:
[cate2023when]: characterization of which classes are closed under [homomorphism_count]
+Special case:
+
+- [connected_homomorphism_closed_query]
+
Up: [closure] under [homomorphism]
-Aliases: closed under homomomorphism, homomorphism closed query, homomorphism closed queries
+Aliases: closed under homomomorphism, homomorphism closed query, homomorphism closed queries, homomorphism-closed query, homomorphism-closed queries
See also: [infinite_UCQ]
diff --git a/infinite_ucq b/infinite_ucq
@@ -0,0 +1,11 @@
+# Infinite UCQ
+
+An *infinite UCQ* is a [query] which is a generally infinite [disjunction] of [CQs]
+
+There are precisely the [homomorphism_closed] queries
+
+[UCQs] are precisely those infinite UCQs where the disjunction can be finite
+
+Up: [homomorphism_closed], [UCQ]
+
+Aliases: infinite UCQs
diff --git a/lutz2022complete b/lutz2022complete
@@ -2,7 +2,7 @@
[academic_paper] by [carsten] and [leif]
-Complexity [trichotomy] for [ontology_mediated_query] about [el] class:
+Complexity [trichotomy] for [OMQs] about [EL] class:
We know that every [OMQ] from (EL,AQ) (or (EL,CQ)) falls into one of the following classes:
diff --git a/query b/query
@@ -8,7 +8,7 @@
- [query_with_negation]
- [database_returning_queries]
- [query_constants] / [constant_free_query]
-- [match]
+- [query_match]
- [minimal_match]
## Problems
diff --git a/query_boolean b/query_boolean
@@ -13,6 +13,12 @@ In [logic], this is called a [sentence]
[computational_problem]: [query_evaluation_Boolean]
+Notions:
+
+- [query_match]
+- [minimal_match]
+- [minimum_match]
+
Up: [query]
Aliases: boolean query
diff --git a/query_match b/query_match
@@ -0,0 +1,11 @@
+# Query match
+
+A *query match* is a [homomorphic_image] of a *query* in a [database_instance]
+
+- easy to define for [CQs] and [UCQs]
+- also for [RPQs], [CRPQs], etc.
+- can be defined for [Datalog] by looking at the [leaves] of [derivation_trees]
+
+Up: [query]
+
+Aliases: match, matches, query matches
diff --git a/query_relevance b/query_relevance
@@ -5,3 +5,5 @@ Given a [database] D, a [Boolean_query] Q, and a [fact] f of D, we say that f is
See [bienvenu2026how]
Up: [provenance]
+
+Aliases: relevance
diff --git a/rigid b/rigid
@@ -1,9 +1,11 @@
# Rigid
-A [structure] is *rigid* if its only [automorphism] is the identity
+A [structure] is *rigid* if its only [endomorphism] is the identity
+
+- [rigid_graph]
Up: [structure]
-See also: [core]
+See also: [core], [assymmetric_structure]
Aliases: rigid structure
