commit d7878eb709d0c8b0bcd603370b287f73b80164ac
parent f6979328a13bb596f06f177882c8c91343c8502d
Author: Antoine Amarilli <a3nm@a3nm.net>
Date: Thu, 25 Sep 2025 11:06:10 +0200
commit with codex
Diffstat:
5 files changed, 32 insertions(+), 7 deletions(-)
diff --git a/chase_termination b/chase_termination
@@ -1,10 +1,14 @@
# Chase termination
depends on the kind of [chase]:
-- [chase_oblivious]
-- [chase_restricted]
+- [chase_oblivious]: [oblivious_chase_termination]
+- [chase_restricted]: [restricted_chase_termination]
-recent work: [hanisch2024chase]
+depends on whether you want all instances or an input instance
+
+[academic_papers]:
+- [gogacz2014all]
+- recent work: [hanisch2024chase]
- idea: beyond [ptime] [data_complexity]
Up: [chase], [termination]
diff --git a/omqa b/omqa
@@ -8,6 +8,18 @@ subtlety: [omqa_finite] vs [omqa_unrestricted]
OMQA and [counting]: [bienvenu2022complexity]
+Approaches:
+- [chase]: materializing the entailed facts
+ - the result of the chase may be finite ([chase_termination]) or infinite
+ - it may have [bounded_treewidth]
+- [query_rewriting]
+ - can be to different [query_languages]:
+ - to [UCQs]
+ - when you have [bounded_derivation_depth]
+ - to [Datalog]
+
+OMQA with [transitive_relations]: [OMQA_transitive]
+
Up: [database_theory]
-See also: [description_logics]
+See also: [description_logics], [BDD_FC_conjecture]
diff --git a/query_rewriting b/query_rewriting
@@ -8,11 +8,16 @@ from a [query], produce a [query] which is [query_equivalent] and has some bette
- [first_order_rewriting]
- [fok_rewriting]
- [datalog_rewriting]
+- [UCQ_rewriting]
## Distiction
-Distinguish [rewriting] (an [algorithm] that can rewrite a [query_language] into another in a [computable] way) and [expressibility] ([queries] in a given [query_language] can always be expressed as a [query_equivalent] [query] in another [query_language])
+Distinguish
+- rewritability
+ - an [algorithm] that can rewrite a [query_language] into another in a [computable] way
+- [expressibility]
+ - [queries] in a given [query_language] can always be expressed as a [query_equivalent] [query] in another [query_language]
Up: [database_theory]
-See also: [query_evaluation]
+See also: [query_evaluation], [OMQA]
diff --git a/transitivity_tgds b/transitivity_tgds
@@ -7,3 +7,5 @@ Results on transitivity:
- [baget2015combining], problem with a condition for transitivity plus [linear_rules] ([existential_rule])
Up: [transitivity] for [open_world_query_answering]
+
+See also: [transitive_relations]
diff --git a/tuple_generating_dependency_multi_head b/tuple_generating_dependency_multi_head
@@ -4,10 +4,12 @@ A [tuple_generating_dependency] with multiple [atoms] in the [head] of the [TGDs
Studied in [gottlob2020multi]
+Some open questions about [chase_termination], cf [gogacz2014all]
+
Classes:
- [tuple_generating_dependency_linear_multi_head]
Up: [tuple_generating_dependency]
-Aliases: TGD multi head, TGDs multi head, multi head TGD, multi head TGDs
+Aliases: TGD multi head, TGDs multi head, multi head TGD, multi head TGDs, multiheaded rules, multi head rules, multihead rules
