commit 3bfbfb2371eaf04b8efecf08d8864266e4bbb215
parent 0b878009fbff364f648a65e87e70004a22f283f3
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 5 Jun 2025 14:28:50 +0200
commit with codex
Diffstat:
10 files changed, 89 insertions(+), 4 deletions(-)
diff --git a/atom_dominated b/atom_dominated
@@ -0,0 +1,5 @@
+# Atom dominated
+
+A [atom] A *dominates* an [atom] B in a [CQ] if the [variables] of A are a [subset] of that of B
+
+Up: [conjunctive_query]
diff --git a/conjunctive_query_inequality b/conjunctive_query_inequality
@@ -4,8 +4,8 @@ A [CQ] with [inequality_mathematics]
- [union_of_conjunctive_query_inequality]
-Up: [conjunctive_query], [inequality_mathematics]
+Up: [conjunctive_query], [query_inequality]
See also: [query_with_negation]
-Aliases: CQ inequalities
+Aliases: CQ inequalities, conjunctive query inequalities
diff --git a/group b/group
@@ -18,7 +18,7 @@ Tools:
- [cayley_graph]
- [cayley_table]
-Up: [algebraic_structure], [mathematics]
+Up: [algebraic_structure], [group_theory]
See also: [monoid], [group_language]
diff --git a/linear_queries b/linear_queries
@@ -0,0 +1,9 @@
+# Linear queries
+
+Notion of [makhija2024unified] for [query_resilience]
+
+A [CQ] is a *linear query* if it does not contain a [triad]
+
+Up: [CQ]
+
+Aliases: linear query
diff --git a/permutation b/permutation
@@ -24,6 +24,7 @@
## Derived notions
- [permutation_pattern]
+- [symmetric_group]
Up: [mathematics]
diff --git a/query_inequality b/query_inequality
@@ -0,0 +1,10 @@
+# Query inequality
+
+A [inequality_mathematics] in a [query], to say that two [variables] cannot be mapped to the same [domain_element]
+
+- [conjunctive_query_inequality]
+- [union_of_conjunctive_queries_inequality]
+
+Up: [query_language]
+
+Aliases: query inequalities
diff --git a/query_language b/query_language
@@ -22,6 +22,7 @@
- with [negation]
- with [aggregation]
- [aggregation]
+- [query_inequality]
## Subclasses
diff --git a/query_resilience b/query_resilience
@@ -0,0 +1,50 @@
+# Resilience
+
+The *resilience* of a [query] Q on a [database] D is the minimal number of [tuples] to be deleted from D so that Q is not satisfied:
+- can be 0 if Q is false on D
+- can be infinity if Q is true on every [subdatabase] of D
+
+Can be posed in [set_semantics] or [bag_semantics]
+- There is a difference between the two
+ - cf [makhija2022unified] Table 1
+ - even for [SJFCQs]
+
+[Academic_papers]:
+- ideas of [network_flow] in [meliou2010complexity]
+- introduced in [freire2015complexity]
+ - gives a [dichotomy] for [SJFCQs]
+ - their notion of [triads] is called [active_triads] in [makhija2022unified]
+- [freire2019new] for [CQs] with [self_joins]
+- [qin2022resilience]: for [SJFCQs] with [query_inequalities]
+- [makhija2022unified] with [neha]
+ - also talks about [causal_responsibility]
+ - results on [SJFCQs] in [bag_semantics]:
+ - resilience is [PTIME] for [linear_queries]
+ - resilience is [NP_complete] for all other [SJFCQs], i.e., queries with [triads]
+ - for [SJFCQs] in [set_semantics]
+ - resilience is [NP_complete] for [SJFCQs] with an [active_triad]
+ - resilience is [PTIME] otherwise
+- [bodirsky2023complexity]: connections to [CSPs] ([resilience_csp])
+ - only in [bag_semantics]
+ - gives a [dichotomy] for [2RPQs]
+- [amarilli2025resilience], for [RPQs]
+
+Notions:
+- [triad], [active_triad]
+- [join_path]
+- linearizable query
+
+Tools:
+- [integer_linear_programming]
+- [vertex_cover]
+
+Research directions:
+- [query_resilience_provenance]
+- [reliability_rpq]
+ - [reliability_rpq_vertices]
+
+Up: [database_theory]
+
+See also: [pqe], [minimal_witness]
+
+Aliases: database resilience, resilience databases, resilience database
diff --git a/sjfcq b/sjfcq
@@ -6,4 +6,4 @@
Up: [conjunctive_query], [self_join]
-Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free, self-join-free CQ, self-join-free CQs, conjunctive query self join free
+Aliases: self join free CQ, self join free CQs, selfjoin free CQ, selfjoin free CQs, cq self join free, cqs self join free, self-join-free CQ, self-join-free CQs, conjunctive query self join free, SJFCQs
diff --git a/symmetric_group b/symmetric_group
@@ -0,0 +1,9 @@
+# Symmetric group
+
+The [group] of [permutations] over a [set]
+
+- [function_composition] as [composition_law]
+- [function_inverse] as [inverse]
+- [identity_function] as [neutral_element]
+
+Up: [group]
