At the meeting on 11th Nov, we saw that some queries admit "rewritings", i.e. a sequence of transformations that produces some extra full guarded rules together with a simplified query.
My approach was the following: Regard the input BCQ $Q = \exists \vec{x}. \bigwedge_i R_i(\vec{y_i})$ as an undirected multi-hypergraph $H_Q$ (i.e. an undirected hypergraph with overlapping edges) with
$\operatorname{elems}(\vec{x})$ as the set of vertices
for each $i$, a hyperedge named $R_i$ that spans $\operatorname{elems}(\vec{y_i})$
We shall denote by $\operatorname{Vertxs}(R)$ the set of vertices spanned by $R$. For a hyperedge $R$, define the set of $R$-exported variables $\mathrm{Exp}_R$ to be $\set{ v \in \operatorname{Vertxs}(R) \mid \exists \text{ a hyperedge } R'. R' \not\subseteq R \text { and } v \in \operatorname{Vertxs}(R') }$. Now we can collapse a hyperedge $R$ by
removing all hyperedges ${ S_i }$ that were contained in $R$ (including $R$ itself)
removing all vertices in $\operatorname{Vertxs}(R)$ that were not $R$-exported
adding a new hyperedge (hence a fresh predicate symbol) labelled $\mathrm{SubGoal}_R$ that spans $\mathrm{Exp}_R$
adding a full data integrity rule: $\forall R. \bigwedge_i S_i \rightarrow \mathrm{SubGoal}_R(\mathrm{Exp}_R)$
The process of applying the transformation above until we have reached the fixpoint may be able to simplify the input query. We discussed that this is an instance of (or, is?) the GYO (Graham-Yu-Ozsoyoglu) algorithm.
I should read up what this algorithm is precisely, add reference and then write my understanding (and the way this can be applied to our problem) in a note.
At the meeting on 11th Nov, we saw that some queries admit "rewritings", i.e. a sequence of transformations that produces some extra full guarded rules together with a simplified query.
My approach was the following: Regard the input BCQ $Q = \exists \vec{x}. \bigwedge_i R_i(\vec{y_i})$ as an undirected multi-hypergraph $H_Q$ (i.e. an undirected hypergraph with overlapping edges) with
We shall denote by $\operatorname{Vertxs}(R)$ the set of vertices spanned by $R$. For a hyperedge $R$, define the set of $R$-exported variables $\mathrm{Exp}_R$ to be $\set{ v \in \operatorname{Vertxs}(R) \mid \exists \text{ a hyperedge } R'. R' \not\subseteq R \text { and } v \in \operatorname{Vertxs}(R') }$. Now we can collapse a hyperedge $R$ by
The process of applying the transformation above until we have reached the fixpoint may be able to simplify the input query. We discussed that this is an instance of (or, is?) the GYO (Graham-Yu-Ozsoyoglu) algorithm.
I should read up what this algorithm is precisely, add reference and then write my understanding (and the way this can be applied to our problem) in a note.