commit 33821430c4dd2ca148491c1a121b6c9f14f16b7c
parent b18949321d32a1a8738a70ef0896a5e63edd8188
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Wed, 25 Jun 2025 14:47:59 +0200
commit with codex
Diffstat:
19 files changed, 120 insertions(+), 51 deletions(-)
diff --git a/boolean_formula b/boolean_formula
@@ -2,7 +2,7 @@
An [expression] which represents a [boolean_function], built from [literals] using the [Boolean_operators]
-- [read_once]
+- [boolean_formula_read_once]
- [conjunctive_normal_form]
- [disjunctive_normal_form]
- [clause]
diff --git a/database_modification b/database_modification
@@ -0,0 +1,8 @@
+# Database modification
+
+- [tuple_deletion]
+- [tuple_insertion]
+
+See also: [graph_modification]
+
+Up: [RDM]
diff --git a/deletion_propagation b/deletion_propagation
@@ -0,0 +1,16 @@
+# Deletion propagation
+
+Find the minimal set of [facts] to delete from a [database] so that the query result in changed in a certain way
+
+- [generalized_deletion_propagation], cf [deletion_propagation]
+ - [deletion_propagation_with_source_side_effects]
+ - special case (for [Boolean_queries]): [query_resilience]
+ - [deletion_propagation_with_view_side_effects]
+ - [aggregated_deletion_propagation]
+ - [smallest_witness_problem]
+
+A special case of [RDM] where the only [database_modifications] permitted are [tuple_deletions]
+
+Up: [database_theory]
+
+See also: [Query_resilience]
diff --git a/deletion_propagation_with_source_side_effects b/deletion_propagation_with_source_side_effects
@@ -0,0 +1,9 @@
+# Deletion propagation with source side effects
+
+The case of [deletion_propagation] where we want to find the smallest number of input tuples to [tuple_delete] in order to remove a given [query_answer]
+
+Special case (for [Boolean_queries]): [query_resilience]
+
+Up: [deletion_propagation]
+
+See also: [deletion_propagation_with_view_side_effects]
diff --git a/edge_deletion b/edge_deletion
@@ -4,6 +4,6 @@
Up: [graph_modification]
-See also: [vertex_deletion]
+See also: [vertex_deletion], [edge_insertion]
Aliases: edge removal
diff --git a/graph_modification b/graph_modification
@@ -11,6 +11,6 @@ An [update] on [graphs]
Up: [graph]
-See also: [graph_removal_lemma], [database_repairs]
+See also: [graph_removal_lemma], [database_repairs], [database_modification], [update_word]
Aliases: graph modifications
diff --git a/integer_linear_program b/integer_linear_program
@@ -0,0 +1,7 @@
+# Integer linear program
+
+Like a [linear_program] but the [variables] must be [integers]
+
+Up: [integer_linear_programming]
+
+See also: [mixed_integer_linear_program]
diff --git a/integer_linear_programming b/integer_linear_programming
@@ -1,18 +0,0 @@
-# Integer linear programming
-
-[NP_hard] [computational_problem]
-
-Notion of [linear_relaxation] to transform into a [linear_programming] [computational_problem]
-- but the solution of the linear program is usually not optimal for the original problem
- - cf [integrality_gap]
- - cf [relaxation]
-
-- [matrix_ilp]
-
-- [two_variable_per_equality] (TVPE) / [two_variable_per_inequality] (TVPI)
-
-Up: [computational_problem], [optimization]
-
-See also: [linear_relaxation]
-
-Aliases: ILP
diff --git a/linear_programming b/linear_programming
@@ -1,17 +0,0 @@
-# Linear programming
-
-minimize c^t x st A^t x = b and x >= 0 pointwise
-- [dual] problem: [variables] y dans R^d, cost b, we want to minimize b^t y
- - and A y \geq c, defines a [polytope]
- - so we want to find the point inside the polytope which minimizes the cost
-
-[algorithms]
-- [simplex_algorithm], fast in practice but slow in memory
-- [ellipsoid], moderate in both
-- [interior_point] methods, it's the best in practice
-- can be approximated ("first order methods")
-- recent improvements
-
-Up: [optimization]
-
-See also: [integer_linear_programming], [linear_equation], [linear_relaxation], [farkas_lemma], [linear_algebra_program], [linear_system]
diff --git a/matrix_ilp b/matrix_ilp
@@ -1,12 +0,0 @@
-# Matrix ILP
-
-An [integer_linear_programming] [computational_problem] associated to a [matrix]
-- i.e., optimize cx subject to Ax \geq b, for A a matrix
-
-Cf [strongly_unimodular] and [totally_unimodular]
-
-Discussed in [crama1986strong], see also [hypergraph_signed]
-
-Up: [integer_linear_programming]
-
-See also: [hypergraph_unimodular]
diff --git a/minimum_equivalent_dnf b/minimum_equivalent_dnf
@@ -0,0 +1,9 @@
+# Minimum equivalent DNF
+
+Given a [DNF] φ and integer k, does there exist a [DNF] which is [equivalent] to φ and has at most k [literal] occurrences?
+
+Studied in [umans2001minimum], showed to be [Sigma_P_2_complete]
+
+See also: [umans2001minimum], [Minimum_formula_size_problem], [DNF_minimization], [goldsmith2008complexity]
+
+Up: [computational_problem]
diff --git a/mixed_integer_linear_program b/mixed_integer_linear_program
@@ -0,0 +1,7 @@
+# Mixed integer linear program
+
+Like a [linear_program] but some [variables] are specified to be [integers]
+
+Special case (when all [variables] are [integers]): [integer_linear_program]
+
+Up: [linear_programming]
diff --git a/query_resilience b/query_resilience
@@ -9,6 +9,12 @@ Can be posed in [set_semantics] or [bag_semantics]
- cf [makhija2022unified] Table 1
- even for [SJFCQs]
+By [query_class]:
+- [query_resilience_sjfcq]
+- [query_resilience_cq]
+- [query_resilience_ucq]
+- [query_resilience_rpq]
+
[Academic_papers]:
- ideas of [network_flow] in [meliou2010complexity]
- introduced in [freire2015complexity]
@@ -43,6 +49,10 @@ Research directions:
- [reliability_rpq]
- [reliability_rpq_vertices]
+Generalization:
+
+- [deletion_propagation_with_source_side_effects]
+
Up: [database_theory]
See also: [pqe], [minimal_witness]
diff --git a/query_resilience_sjfcq b/query_resilience_sjfcq
@@ -0,0 +1,11 @@
+# Query resilience for sjfcq
+
+- [dichotomy] in [freire2015complexity] in [set_semantics]
+- [dichotomy] in [makhija2023unified] in [bag_semantics]
+
+encoding to [ILP] in [makhija2023unified]
+- between [bag_semantics] and [set_semantics], the constraints are the same, only the [objective_function] changes
+
+Up: [query_resilience] for [SJFCQs]
+
+See also: [triads]
diff --git a/reverse_data_management b/reverse_data_management
@@ -0,0 +1,16 @@
+# Reverse data management
+
+https://en.wikipedia.org/wiki/Reverse_data_management
+
+do changes on the inputs (optimal changes) to achieve a desired outcome on the output
+
+- [deletion_propagation]: delete tuples from database to delete a tuple result
+ - source side effects
+ - aggregation
+- which problems could arise and cause a certain result in the query result?
+ - e.g., deletions
+- [minimum_witness_problem]
+
+See also: [graph_modification_problem]
+
+Aliases: RDM
diff --git a/smallest_witness b/smallest_witness
@@ -13,4 +13,4 @@ Up: [database_theory]
See also: [query_resilience], [smallest_synthetic_witness], [synthetic_witness]
-Aliases: minimum witness, minimal witness
+Aliases: minimum witness, minimal witness, smallest witness problem, minimum witness problem, minimal witness problem
diff --git a/tuple_deletion b/tuple_deletion
@@ -0,0 +1,9 @@
+# Tuple deletion
+
+The [deletion] of a [tuple] from a [database_instance]
+
+Up: [database_modification]
+
+Aliases: tuple delete
+
+See also: [tuple_insertion], [edge_deletion]
diff --git a/tuple_insertion b/tuple_insertion
@@ -0,0 +1,7 @@
+# Tuple insertion
+
+The [insertion] of a [tuple] in a [database_instance]
+
+Up: [database_modification]
+
+See also: [tuple_deletion], [edge_insertion]
diff --git a/umans2001minimum b/umans2001minimum
@@ -0,0 +1,7 @@
+# umans2001minimum
+
+studies the [minimum_equivalent_DNF] problem and shows that it is [Sigma_p_2_complete]
+
+See also: [minimum_formula_size_problem], [goldsmith2008complexity]
+
+Up: [Academic_paper]
