commit 9568f40f1b591fb0739defc5dfe10023229e1ed8
parent 33821430c4dd2ca148491c1a121b6c9f14f16b7c
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 25 Jun 2025 18:02:33 +0200
commit with codex
Diffstat:
11 files changed, 32 insertions(+), 4 deletions(-)
diff --git a/aggregated_deletion_propagation b/aggregated_deletion_propagation
@@ -0,0 +1,9 @@
+# Aggregated deletion propagation
+
+[Deletion_propagation] where you want to delete some number of [query_answers] (but it is not specified which ones)
+
+Studied in [hu2020aggregated]
+
+Up: [deletion_propagation]
+
+Aliases: ADP-SS, ADP SS
diff --git a/causal_responsibility b/causal_responsibility
@@ -0,0 +1,10 @@
+# Causal responsibility
+
+For a [Boolean_query] Q and [fact] F in an input [relational_database] D, we say that a tuple has "causal responsibility k" if D satisfies Q but there is a set Γ of at most k facts such that D\Γ satisfies Q but D\(Γ cup {F}) does not satisfy Q
+- i.e., removing Γ makes F "counterfactual", i.e., it becomes critical for the query to be true
+
+- [meliou2010complexity]: [dichotomy] on [SJFCQs] in [set_semantics]
+- [makhija2023unified]: [dichotomy] on [SJFCQs] in [bag_semantics]
+ - goes via [MILP]
+
+Up: [database_theory]
diff --git a/database_modification b/database_modification
@@ -6,3 +6,5 @@
See also: [graph_modification]
Up: [RDM]
+
+Aliases: database modifications
diff --git a/deletion_propagation b/deletion_propagation
@@ -7,7 +7,7 @@ Find the minimal set of [facts] to delete from a [database] so that the query re
- special case (for [Boolean_queries]): [query_resilience]
- [deletion_propagation_with_view_side_effects]
- [aggregated_deletion_propagation]
- - [smallest_witness_problem]
+ - [smallest_witness_problem]: do as many [tuple_deletions] as possible without changing the [query_answers]
A special case of [RDM] where the only [database_modifications] permitted are [tuple_deletions]
diff --git a/deletion_propagation_with_source_side_effects b/deletion_propagation_with_source_side_effects
@@ -7,3 +7,5 @@ Special case (for [Boolean_queries]): [query_resilience]
Up: [deletion_propagation]
See also: [deletion_propagation_with_view_side_effects]
+
+Aliases: DPSS, DP_SS
diff --git a/matrix_types b/matrix_types
@@ -19,5 +19,6 @@
- [strongly_unimodular] matrix
- [pet_matrix]
- [matrix_symmetric]
+- [matrix_balanced]
Up: [matrix]
diff --git a/np_complete b/np_complete
@@ -26,4 +26,4 @@ Up: [completeness] for [nptime]
See also: [intractability], [np_hard], [conp_complete]
-Aliases: NP-completeness, NP_completeness
+Aliases: NP-completeness, NP_completeness, NPc
diff --git a/probabilistic_databases b/probabilistic_databases
@@ -28,3 +28,5 @@
See also: [relational_algebra], [relational_calculus]
Up: [database_theory]
+
+Aliases: probabilistic database
diff --git a/set_cover b/set_cover
@@ -7,3 +7,5 @@ Given a universe [set], and a collection of [subsets] whose [union] is the unive
See also: [hitting_set], [vertex_cover], [edge_cover]
Up: [set]
+
+Aliases: vertex cover hypergraphs
diff --git a/tuple_deletion b/tuple_deletion
@@ -4,6 +4,6 @@ The [deletion] of a [tuple] from a [database_instance]
Up: [database_modification]
-Aliases: tuple delete
+Aliases: tuple delete, tuple deletions
See also: [tuple_insertion], [edge_deletion]
diff --git a/vertex_cover b/vertex_cover
@@ -1,6 +1,6 @@
# Vertex cover
-A vertex cover in a [graph] is a subset of vertices such that every edge is incident to at least one vertex of the subset.
+A vertex cover in a [graph] is a [subset] of [vertices] such that every [edge] is incident to at least one [vertex] of the [subset].
[linear_relaxation]: [fractional_vertex_cover]
- and [dual]: [fractional_edge_packing]
