$\blacktriangleright$ (Membership for CQA($\pi$-wdQ$,\preceq,\forall$)) As
always, we consider the co-problem, i.e., whether $\mu$ is no answer of
$\pi_{X}Q$ over some $\preceq$-repaired graph $G_{R}$. Let us consider the
following procedure:

  1. 1.

Guess a repair $R$.

  2. 2.

Check that $R$ is $\preceq$-minimal.

  3. 3.

Check that $\mu$ is no answer of $Q$ over $G_{R}$.

The checks clearly only require access to a
$\mathsf{\Sigma}_{2}\mathsf{P}$-oracle (in fact, only the second check), and,
thus, CQA($\pi$-wdQ$,\preceq,\forall$) is in $\mathsf{\Pi}_{3}\mathsf{P}$ for
${\preceq}\in\\{=,\leq,\subseteq\\}$. ∎

##  Appendix D Full Proofs for IAR Semantics

######  Theorem 3.

The following statements are true for data complexity:

  * •

CQA($\mathcal{L},=,\cap$) is $\mathsf{coNP}$-c for
$\mathcal{L}\in\\{\textsc{Bgp}$, $\textsc{$\pi$-Bgp}\\}$.

  * •

CQA($\mathcal{L},\leq,\cap$) is $\mathsf{\Theta}_{2}\mathsf{P}$-c for
$\mathcal{L}\in\\{\textsc{Bgp}$, $\pi$-Bgp, wdQ, $\textsc{$\pi$-wdQ}\\}$.

  * •

CQA($\mathcal{L},\subseteq,\cap$) is $\mathsf{\Pi}_{2}\mathsf{P}$-c for
$\mathcal{L}\in\\{\textsc{Bgp}$, $\textsc{$\pi$-Bgp}\\}$.

The following statements are true for combined complexity:

  * •

CQA(Bgp$,=,\cap$) is $\mathsf{coNP}$-c.

  * •

CQA($\pi$-Bgp$,=,\cap$) is $\mathsf{\Theta}_{2}\mathsf{P}$-c.

  * •

CQA($\mathcal{L},\leq,\cap$) is $\mathsf{\Theta}_{2}\mathsf{P}$-c for
$\mathcal{L}\in\\{\textsc{Bgp}$, $\pi$-Bgp, $\textsc{wdQ}\\}$.

  * •

CQA($\mathcal{L},\subseteq,\cap$) is $\mathsf{\Pi}_{2}\mathsf{P}$-c for
$\mathcal{L}\in\\{\textsc{Bgp}$, $\textsc{$\pi$-Bgp}\\}$.

###### Proof.

$\blacktriangleright$ (Hardness for CQA(Bgp$,\preceq,\cap$) data complexity)
Notice that an atom $\mu(B(X))$ appears in every $\preceq$-repaired graph if
and only if it appears in the intersection of all $\preceq$-repaired graphs.
Thus, the hardness immediately carries over from the case for
$\forall$-semantics.

$\blacktriangleright$ (Hardness for CQA($\pi$-Bgp$,=,\cap$) combined
complexity) To show $\mathsf{\Theta}_{2}\mathsf{P}$-hardness, we reduce from
the problem CardMin-Precoloring on graphs with degree bounded by 5 (for
hardness of the reference problem see Lemma 1 in Section F) that asks whether
for a graph $G^{\prime}$ and pre-coloring $c:V(G^{\prime})\rightarrow
2^{\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}}$, a given vertex
$\texttt{{v}}_{1}$ is colored g in some 3-coloring of $G^{\prime}$ that
minimizes the use of the color g. W.l.o.g., we assume $(G^{\prime},c)$ to be
3-colorable.

To encode this problem, we construct the following data graph $G$. The nodes
of $G$ consist of

  * •

the vertices $V(G^{\prime})=\\{\texttt{{v}}_{1},\dots,\texttt{{v}}_{n}\\}$
added to the class $Vtx$,

  * •

the colors $\texttt{{r}},\texttt{{b}},\texttt{{g}}$,

  * •

and elements $I=\\{\texttt{{i}}_{1},\dots,\texttt{{i}}_{n}\\}$ to count added
to the class $Cnt$.

  * •

two auxiliary fresh nodes $\texttt{{s}},\texttt{{e}}$ also added to the class
$Cnt$,

Furthermore, we add the following atoms:

  * •

For vertices $\texttt{{v}}\in V(G^{\prime})$ we
$col(\texttt{{v}},\texttt{{c}})$ for $\texttt{{c}}\in c(\texttt{{v}})$ as
possible color.

  * •

We connect $\texttt{{v}}\in V(G^{\prime})$ to its $i\leq 5$ neighbors by
adding $e(\texttt{{u}},\texttt{{v}})$ for $(\texttt{{u}},\texttt{{v}})\in
G^{\prime}$ and $D_{i}(\texttt{{v}})$.

  * •

For each subset
$C\subseteq\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\},C\neq\emptyset$ we add
classes $Pre_{C}$ with $Pre_{C}(\texttt{{c}})$ for every $\texttt{{c}}\in C$.

  * •

We add $neqCol(\texttt{{c}},\texttt{{c}}^{\prime})$ for
$\texttt{{c}},\texttt{{c}}^{\prime}\in\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\},\texttt{{c}}\neq\texttt{{c}}^{\prime}$
to distinguish colors.

  * •

We add $neqCnt(\texttt{{i}}_{i},\texttt{{i}}_{j})$,
$neqCnt(\texttt{{s}},\texttt{{i}}_{i})$,
$neqCnt(\texttt{{i}}_{i},\texttt{{e}})$ for $i,j=1,\dots,n$ and $i\neq j$ to
distinguish counters.

  * •

We connect each counter $\texttt{{i}}\in I$ to each color, i.e., via
$allowed(\texttt{{i}},\texttt{{c}})$ for
$\texttt{{c}}\in\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}$.

  * •

We connect each counter $\texttt{{i}}\in I$ to each vertex $\texttt{{v}}\in
V(G^{\prime})$ via $match(\texttt{{i}},\texttt{{v}})$.

  * •

We connect $\texttt{{s}},\texttt{{e}}$ to themselves, i.e., we add
$match(\texttt{{s}},\texttt{{s}})$ and $match(\texttt{{e}},\texttt{{e}})$.

  * •

We add a specific order on the counters by adding
$nextCnt(\texttt{{i}}_{i},\texttt{{i}}_{i+1})$ for $i=1,\dots,n-1$ and
$nextCnt(\texttt{{s}},\texttt{{i}}_{1})$ as well as
$nextCnt(\texttt{{i}}_{n},\texttt{{e}})$.

  * •

We fully connect the vertices by adding
$nextVtx(\texttt{{v}}_{i},\texttt{{v}}_{j}),$
$nextVtx(\texttt{{s}},\texttt{{v}}_{i}),$ and
$nextVtx(\texttt{{v}}_{i},\texttt{{e}})$ for
$\texttt{{v}}_{i},\texttt{{v}}_{j}\in V(G^{\prime}),i\neq j$.

  * •

Lastly, as always, we again encode an arbitrary linear order $\preceq_{next}$
on all the nodes of $G$ that starts in s and ends in e. To that end, $next$ is
added to $G^{\prime}$ which indicates immediate predecessors and successors.

Next, we construct a shapes graph $(\mathcal{C,T})$. $\mathcal{C}$ is as
follows:

$\displaystyle\begin{split}\mathsf{col}\leftrightarrow{}&{}{=_{1}}col\land{}\bigg{(}\bigvee_{i=1}^{5}\Big{(}D_{i}\land\big{(}\\\
&(\exists col.\texttt{{r}}\land{=_{i}}e.(\lnot\exists col.\texttt{{r}}))\\\
&{}\lor{}(\exists col.\texttt{{g}}\land{=_{i}}e.(\lnot\exists
col.\texttt{{g}}))\\\ &{}\lor{}(\exists
col.\texttt{{b}}\land{=_{i}}e.(\lnot\exists
col.\texttt{{b}}))\big{)}\Big{)}\bigg{)}\end{split}$ (5)
$\displaystyle\begin{split}\mathsf{lin}\leftrightarrow{}&{}{=_{1}}nextVtx\land{}{=_{1}}nextVtx^{-}\end{split}$
(6)
$\displaystyle\begin{split}\mathsf{vtx}\leftrightarrow{}&Vtx\land\mathsf{col}\land\mathsf{lin}\end{split}$
(7)
$\displaystyle\begin{split}\mathsf{nxt}\leftrightarrow{}&{=_{1}}nextCnt\land{}{=_{1}}nextCnt^{-}\\\
&\land\big{(}(nextCnt^{*}\cdot nextCnt)\\\ &\quad\cup(nextCnt^{-*}\cdot
nextCnt^{-})\big{)}=neqCnt\end{split}$ (8)
$\displaystyle\begin{split}\mathsf{mat}\leftrightarrow{}&{}{=_{1}}match\land{}{=_{1}}(match\cdot
match^{-})\end{split}$ (9)
$\displaystyle\begin{split}\mathsf{con}\leftrightarrow{}&match\cdot
nextVtx\cdot match^{-}=nextCnt\end{split}$ (10)
$\displaystyle\begin{split}\mathsf{all}\leftrightarrow{}&\big{(}({=_{3}}allowed.(\texttt{{r}}\lor\texttt{{g}}\lor\texttt{{b}})\\\
&\quad{}\land\exists(match\cdot nxtVtx^{*}\cdot col).\texttt{{g}})\\\
&{}\lor({=_{2}}allowed.(\texttt{{r}}\lor\texttt{{b}})\\\
&\quad{}\land\lnot\exists(match\cdot nextVtx^{*}\cdot
col).\texttt{{g}})\big{)}\end{split}$ (11)
$\displaystyle\begin{split}\mathsf{cnt}\leftrightarrow{}&Cnt\land\mathsf{nxt}\land\mathsf{mat}\land\mathsf{con}\end{split}$
(12)
$\displaystyle\begin{split}\mathsf{s}\leftrightarrow{}&\texttt{{s}}\land\mathsf{mat}\land\mathsf{con}\end{split}$
(13)
$\displaystyle\begin{split}\mathsf{e}\leftrightarrow{}&\texttt{{e}}\land\mathsf{mat}\end{split}$
(14) $\displaystyle\begin{split}\mathsf{r}\leftrightarrow{}&\texttt{{r}}\land
Pre_{\\{\texttt{{r}}\\}}\land Pre_{\\{\texttt{{r}},\texttt{{g}}\\}}\land
Pre_{\\{\texttt{{r}},\texttt{{b}}\\}}\\\ &\land
Pre_{\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}}\land{=_{2}}neqCol\end{split}$
(15) $\displaystyle\begin{split}\mathsf{g}\leftrightarrow{}&\texttt{{g}}\land
Pre_{\\{\texttt{{g}}\\}}\land Pre_{\\{\texttt{{r}},\texttt{{g}}\\}}\land
Pre_{\\{\texttt{{g}},\texttt{{b}}\\}}\\\ &\land
Pre_{\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}}\land{=_{2}}neqCol\end{split}$
(16) $\displaystyle\begin{split}\mathsf{b}\leftrightarrow{}&\texttt{{b}}\land
Pre_{\\{\texttt{{b}}\\}}\land Pre_{\\{\texttt{{r}},\texttt{{b}}\\}}\land
Pre_{\\{\texttt{{g}},\texttt{{b}}\\}}\\\ &\land
Pre_{\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}}\land{=_{2}}neqCol\end{split}$
(17) $\displaystyle\begin{split}\mathsf{val}\leftrightarrow{}&\forall
next^{*}.(\mathsf{se}\lor\mathsf{vtx}\lor\mathsf{cnt}\lor\mathsf{r}\lor\mathsf{g}\lor\mathsf{b})\\\
&\land\exists next^{*}.\texttt{{e}}\end{split}$ (18)

The target is $\mathcal{T}=\\{\mathsf{val}(\texttt{{s}})\\}$, $\mu=\\{\\}$,
and the query is $\pi_{\emptyset}Q$ with

$\displaystyle Q={}$
$\displaystyle\bigwedge_{(\texttt{{v}}_{i},\texttt{{v}}_{j})\in
G^{\prime}}neqCol(y_{i},y_{j})$ $\displaystyle{}\land
Pre_{\\{\texttt{{g}}\\}}(y_{1})\land\bigwedge_{\texttt{{v}}_{i}\in
V(G^{\prime})}Pre_{c(\texttt{{v}}_{i})}(y_{i})$
$\displaystyle{}\land\bigwedge_{\texttt{{v}}_{i}\in
V(G^{\prime})}allowed(x_{i},y_{i})\land\bigwedge_{i\neq
j}neqCnt(x_{i},x_{j}).$

As before, the target $\mathsf{val}(\texttt{{s}})$ together with the
Constraint 18 ensures that every repaired graph $G_{R}$ is such that all nodes
satisfy specific constraints. Concretely, vertices $\texttt{{v}}\in
V(G^{\prime})$ have to satisfy Constraint 7 and thus also 5 and 6; counters
$\texttt{{i}}\in I$ have to satisfy Constraint 12 and thus also Constraints 8
through 11; the auxiliary nodes s has to satisfy the Constraint 13 and thus
also 9 and 10; the auxiliary nodes e has to satisfy the Constraint 14 and thus
also 9; and the colors $\texttt{{r}},\texttt{{g}},\texttt{{b}}$ respectively
satisfy the Constraints
$\ref{cnst:prec:r},\ref{cnst:prec:g},\ref{cnst:prec:b}$.

First, let us consider vertices. Constraint 5 ensures that every repair
“selects” a color for each vertex and that the resulting coloring is a valid
3-coloring adhering to $c$. Furthermore, Constraint 6 ensures that every
vertex appears exactly twice in the property $nextVtx$, once in the first
position and once in the second position.

Next, let us consider counters and the auxiliary nodes
$\texttt{{s}},\texttt{{e}}$. Firstly, Constraint 8 ensures that the properties
$nextCnt$ and $neqCnt$ are left unchanged. Then, Constraint 9 ensures that
counters $\texttt{{i}}_{i}\in I$ are matched 1-1 to vertices
$\texttt{{v}}(\texttt{{i}}_{i})\in V(G^{\prime})$. Furthermore, this
constraint also has to be satisfied by $\texttt{{s}},\texttt{{e}}$, ensuring
that they are match to themselves. Due to Constraint 10, this matching has to
consistent with the property $nextVtx$. This means that
$nextVtx(\texttt{{v}}(\texttt{{i}}_{i}),\texttt{{v}}(\texttt{{i}}_{i+1}))\in
G_{R}$ for $i=1,\dots,n-1$ as well as
$nextVtx(\texttt{{s}},\texttt{{v}}(\texttt{{i}}_{1}))\in G_{R}$ and
$nextVtx(\texttt{{v}}(\texttt{{i}}_{n}),\texttt{{e}})\in G_{R}$. Thus,
crucially, the property $nextVtx$ represents the immediate predecessors and
successors relation of a linear order $\preceq_{nextVtx}$ on all the vertices
$V(G^{\prime})$ that additionally starts in s and ends in e. Furthermore, by
correctly “selecting” $nextVtx$ and $match$, any such linear order can be
encoded in $G_{R}$.

Now, consider Constraint 11 which all counters also have to satisfy. This
constraint fixes the property $allowed$, which, thus, deterministically
depends on the linear order $\preceq_{nextVtx}$ represented by the $G_{R}$.
Concretely,
$allowed(\texttt{{i}}_{i},\texttt{{r}}),allowed(\texttt{{i}}_{i},\texttt{{b}})$
are always in $G_{R}$ but $allowed(\texttt{{i}}_{i},\texttt{{g}})$ is in
$G_{R}$ if and only if there is a $j\geq i$ such that
$\texttt{{v}}(\texttt{{i}}_{j})$ is colored g, i.e.,
$col(\texttt{{v}}(\texttt{{i}}_{j}),\texttt{{g}})\in G_{R}$.

Lastly, the constraints for the colors simply ensure that the property
$neqCol$ and the classes $Pre_{C}$ are left unchanged.

Thus, summarizing, the idea is the following: each repaired graph $G_{R}$
represents a valid 3-coloring of the graph adhering to the precoloring
together with a specific linear order $\preceq_{nextVtx}$ on the vertices.
Then, there is a bijection between counters $\texttt{{i}}_{i}$ and vertices
$\texttt{{v}}(\texttt{{i}}_{i})$ with the property:
$\texttt{{v}}(\texttt{{i}}_{i})\preceq_{makeLin}\texttt{{v}}(\texttt{{i}}_{j})$
if and only if $i\leq j$. Furthermore, the repaired graph allows the color g
to the counter $\texttt{{i}}_{i}$ if and only if there is a vertex
$\texttt{{v}}(\texttt{{i}}_{j})$ colored g that comes after the vertex
$\texttt{{v}}(\texttt{{i}}_{i})$, i.e., $j\geq i$. Thus, the $allowed$
relation “(over-) counts” the uses of g.

However, if the linear order is such the vertices colored g come first, the
repaired graph correctly counts the uses of g. Furthermore, for any two
repaired graphs $G_{R}$ and $G_{R^{\prime}}$, we have $\llbracket
allowed\rrbracket^{G_{R}}\subseteq\llbracket
allowed\rrbracket^{G_{R^{\prime}}}$ or the other way around. Thus, there is a
unique minimum $allowed$ relation which also appears in the intersection of
all repaired graphs $G_{\cap}$. Concretely, if $c$ is the minimum number of
uses of g required, $allowed(\texttt{{i}}_{i},\texttt{{g}})\in G_{\cap}$ if
and only if $i\leq c$, i.e., $G_{\cap}$ correctly counts the minimal uses of
$\texttt{{g}}.$ Furthermore, as no repaired graph alters the classes $Pre_{C}$
and the properties $neqCol$, $allowed$, and $neqCnt$, they are the same in
$G_{\cap}$ as they were in the construction.

Now, consider the query. The query asks whether there is a 3-coloring of the
graph that adheres to the precoloring, colors $\texttt{{v}}_{1}$ the color g,
and only uses g as little as possible. This is done by “guessing” a counter
$\texttt{{i}}_{j}$ (variable $(x_{i})$) and a color c (variable $(y_{i})$) for
each vertex $\texttt{{v}}_{i}$. A vertex can be colored g if and only if its
counter $\texttt{{i}}_{j}$ is less than or equal to $c$, i.e., $j\leq c$
(facilitated by $allowed(x_{i},y_{i})$), assuring that g is used at most $c$
times. Thus, values for the bound variables $x_{i}$ and $y_{i}$ exist exactly
when there is a coloring that colors $\texttt{{v}}_{1}$ the color g while
still minimizing the use of g, completing the proof of correctness.

$\blacktriangleright$ (Membership for CQA($\pi$-Bgp$,=,\cap$) data complexity)
The co-problem is to show that $\mu$ is no answer to $\pi_{X}Q(X,Y)$ over the
intersection $G_{\cap}$ of all repaired graphs. This is the case if for all
$\mu_{Y}\colon Y\rightarrow V(G)$, at least one atom $\alpha$ of $Q$ is not
sent to $G_{\cap}$ by $\mu\cup\mu_{Y}$. Thus, there must also be a repair
$R(\mu_{Y})$ such that $\alpha$ is not sent to $G_{R(\mu_{Y})}$ by
$\mu\cup\mu_{Y}$. Hence, $R(\mu_{Y})$ can be seen as a witness that
$\mu\cup\mu_{Y}$ is no answer to $Q$ over $G_{\cap}$. Since there are only a
polynomial number of $\mu_{Y}$, a NTM can guess a $R(\mu_{Y})$ together with a
supporting model for each $\mu_{Y}$. Thus, the co-problem is in $\mathsf{NP}$
and CQA($\pi$-Bgp$,=,\cap$) in $\mathsf{coNP}$.

$\blacktriangleright$ (Membership for CQA(Bgp$,=,\cap$) combined complexity)
Looking at the previous argumentation, notice that the size of $Q$ being fixed
was not used, but the fact that the number of $Y$ variables was fixed. Of
course, the same holds for Bgp in combined complexity and thus, also
CQA(Bgp$,=,\cap$) is in $\mathsf{coNP}$.

$\blacktriangleright$ (Membership for CQA($\pi$-Bgp$,=,\cap$) combined
complexity) CQA($\pi$-Bgp$,=,\cap$) is in $\mathsf{\Theta}_{2}\mathsf{P}$ as
we can compute the size $K$ of the intersection of the repaired graphs with
logarithmically many calls to an $\mathsf{NP}$-oracle. We can do this by
making oracle calls of the form: “is the size of intersection of all repaired
graphs less than $c$?” This question can be answered by an NTM following the
subsequent procedure:

  1. 1.

Let $S:=|G|+|H|$.

  2. 2.

Guess repairs $R_{1},\dots,R_{S-c+1}$.

  3. 3.

Check that $|\bigcap_{i}G_{R_{i}}|<c$.

Intuitively, $S$ is the number of potential atoms in the intersection, and
each $R_{i}$ witnesses that at least 1 potential atom does not appear in the
intersection. Of course, if the size of the intersection is less than $c$, at
least $S-c+1$ such repairs must exist (some may appear duplicately).

Then, given $K$, we can answer the query with a single $\mathsf{NP}$ call. For
this, we proceed as follows (the query is $\pi_{X}Q(X,Y)$):

  1. 1.

Let $S:=|G|+|H|$.

  2. 2.

Guess repairs $R_{1},\dots,R_{S-K+1}$, and a $\mu_{Y}\colon Y\rightarrow
V(G)$.

  3. 3.

Check that $|\bigcap_{i}G_{R_{i}}|=K$.

  4. 4.

Check that $\mu\cup\mu_{Y}$ is an answer to $Q$ over $\bigcap_{i}G_{R_{i}}$.

$\blacktriangleright$ (Membership for CQA($\pi$-wdQ$,\leq,\cap$) data
complexity) We start by showing that we can compute the size of the
intersection of the $\leq$-repaired graphs in $\mathsf{\Theta}_{2}\mathsf{P}$.
To do this, we first have to compute the minimal size $k$ of a repair with
logarithmically many $\mathsf{NP}$-oracle calls (as we have already done many
times). Then, using $k$, we make oracle calls of the form: “is the size of
intersection of all $\leq$-repaired graphs less than $c$?” Given $k$, this
question can be answered by an NTM similar to the previous case but where we
additionally have to check that $|R_{i}|=k$. Consequently, we can again use
binary search to compute the exact size $K$ of the intersection with only
logarithmically many $\mathsf{NP}$-oracle calls. Finally, given $k$ and $K$,
the question of whether $\mu$ is an answer to $Q$ becomes an
$\mathsf{NP}$-problem, and, thus, only requires a single additional
$\mathsf{NP}$-oracle call.

The reason for that is that given $k$ and $K$, a NTM can guess repairs
$R_{1},\dots,R_{S-K+1}$ and be sure that $G_{\cap}=\bigcap_{i}G_{R_{i}}$ if
$|\bigcap_{i}G_{R_{i}}|=K$. The remainder is then only a matter of going
through all possible (polynomially many) extensions of $\mu$ to the variables
projected away and, then, variables in the OPT-part. This proves the
$\mathsf{\Theta}_{2}\mathsf{P}$-membership.

$\blacktriangleright$ (Membership for CQA($\pi$-Bgp$,\leq,\cap$) and
CQA(wdQ$,\leq,\cap$) combined complexity) Using the same method as before, we
can determine $k$ and $K$. Then, given $k$ and $K$, answering a $\pi$-Bgp only
requires $\mathsf{NP}$-power, also in combined complexity. To accomplish this,
we simply have to guess the values of the variables projected away at the same
time we guess the repairs $R_{1},\dots,R_{S-K+1}$.

For a wdQ
$Q=((\dots((P\mathbin{\text{OPT}}P_{1})\mathbin{\text{OPT}}P_{2})\dots)\mathbin{\text{OPT}}P_{k})$,
the argument is slightly different as, given $k,$ $K$, answering the query
requires $\mathsf{coNP}$-power in combined complexity. I.e., given $k$ and
$K$, to identify no-instances we can guess a $P_{i}$ and a
$\mu_{P_{i}}\colon\mathsf{vars}(P_{i})\setminus\mathsf{vars}(P)\rightarrow
V(G)$ together with $\leq$-repairs $R_{1},\dots,R_{S-K+1}$ such that
$|\bigcap_{i}G_{R_{i}}|=K$. Then, if
$(\mu\cup\mu_{P_{i}})_{\mathsf{vars}(P_{i})}$ is an answer to $P_{i}$ over
$\bigcap_{i}G_{R_{i}}$ or $\mu$ is no answer to $P$ over
$\bigcap_{i}G_{R_{i}}$, we can assert that $\mu$ is also no answer to $Q$ over
the intersection of all repairs.

$\blacktriangleright$ (Membership for CQA($\pi$-Bgp$,\subseteq,\cap$) combined
complexity) We consider the co-problem, i.e., whether $\mu$ is no answer of
$Q$ over the intersection of all $\subseteq$-repaired graphs. For this, we
proceed as follows:

  1. 1.

Guess (a superset of the intersection of all $\subseteq$-repaired graphs)
$G_{\cap}=A_{\cap}\cup(G\setminus D_{\cap})$ together with repairs
$(A_{a},D_{a})$ for each $a\in H\setminus A_{\cap}$ and $(A_{d},D_{d})$ for
each $d\in D_{\cap}$.

  2. 2.

Check that $\mu$ is no solution of $Q$ over $G_{\cap}$.

  3. 3.

Check that $a\not\in A_{a}$ and that $(A_{a},D_{a})$ is a $\subseteq$-repair.

  4. 4.

Check that $d\in D_{d}$ and that $(A_{d},D_{d})$ is a $\subseteq$-repair.

All of these checks only require access to an $\mathsf{NP}$-oracle.
Furthermore, if all of these checks are positive, $G_{\cap}$ is indeed a
superset of the intersection of all $\subseteq$-repairs, and, since $\pi$-BGP
are monotone, $\mu$ is no answer of $Q$ over the intersection. Hence, we can
correctly assert that we are dealing with a no-instance. On the other hand, if
for all guesses at least one check is negative, there also has to be a check
that is negative when $G_{\cap}$ is the intersection of all
$\subseteq$-repairs and $(A_{a},D_{a}),(A_{d},D_{d})$ are $\subseteq$-repairs
with $a\not\in A_{a}$ and $d\in D_{d}$, respectively (The existence of
$(A_{a},D_{a}),(A_{d},D_{d})$ is guaranteed by $G_{\cap}$ being the
intersection). Thus, the first check has to be negative. We can, therefore,
correctly conclude that we are dealing with a yes-instance. Thus, in total,
the co-problem is in $\mathsf{\Sigma}_{2}\mathsf{P}$ and
CQA($\pi$-Bgp$,\subseteq,\cap$) is in $\mathsf{\Pi}_{2}\mathsf{P}$. ∎

######  Theorem 4.

The following statements are true for data complexity:

  * •

CQA(wdQ$,=,\cap$) is $\mathsf{DP}$-c.

  * •

CQA(wdQ$,\subseteq,\cap$) is $\mathsf{DP}_{2}$-c.

The following statements are true for combined complexity:

  * •

CQA(wdQ$,=,\cap$) is $\mathsf{\Theta}_{2}\mathsf{P}$-c.

  * •

CQA(wdQ$,\subseteq,\cap$) is $\mathsf{DP}_{2}$-c.

###### Proof.

We show the following for data and combined complexity, and
${\preceq}\in\\{=,\subseteq\\}$ (it also holds for $\leq$): If
CQA(Bgp$,\preceq,\cap$) is $\mathsf{C}$-complete and
CQA($\pi$-Bgp$,\preceq,\cap$) is $\mathsf{D}$-complete, then
CQA(wdQ$,\preceq,\cap$) is complete for $\mathsf{C}\land\mathsf{coD}=\\{C\cap
D\mid C\in\mathsf{C}\text{ and }D\in\mathsf{co}\mathsf{D}\\}$. Note that this
implies the statements in the theorem as
$\mathsf{DP}=\mathsf{coNP}\land\mathsf{NP}$,
$\mathsf{DP}_{2}=\mathsf{\Pi}_{2}\mathsf{P}\land\mathsf{\Sigma}_{2}\mathsf{P}$,
and
$\mathsf{\Theta}_{2}\mathsf{P}=\mathsf{coNP}\land\mathsf{\Theta}_{2}\mathsf{P}$.

$\blacktriangleright$ (Membership) we may assume that a wdQ $Q$ is of the form
$((\dots((P\mathbin{\text{OPT}}P_{1})\mathbin{\text{OPT}}P_{2})\dots)\mathbin{\text{OPT}}P_{k})$
with $\mathsf{vars}(P)=\mathsf{dom}(\mu)$. Then $\mu$ is an answer to $Q$ if
and only if $\mu$ is an answer to $P$ but, for all $i$, $\mu$ cannot be
extended to an answer of $P_{i}$. Checking if $\mu$ is an answer to $P$
corresponds to identifying yes-instances of CQA(Bgp$,=,\cap$); checking that
$\mu$ cannot be extended to an answer of any $P_{i}$ corresponds to
identifying no-instances of CQA($\textsc{$\pi$-Bgp},=,\cap$) (note that the
variables in $\mathsf{vars}(P_{i})\setminus\mathsf{vars}(P)$ behave like bound
variables in this case, since we are not interested in a particular extension
of $\mu$ to these variables but to any extension). The problem
CQA(wdQ$,\preceq,\cap$) can, therefore, be seen as the intersection of
CQA(Bgp$,\preceq,\cap$) and (multiple) CQA($\pi$-Bgp$,\preceq,\cap$). Notice
that identifying multiple no-instances of CQA($\textsc{$\pi$-Bgp},=,\cap$)
does not increase the complexity.

$\blacktriangleright$ (Hardness) For the hardness part, we reduce from the
complete problem ( CQA(Bgp$,\preceq,\cap$), co-CQA($\pi$-Bgp$,\preceq,\cap$)
), whose instances are pairs $(\mathcal{I},\mathcal{J})$, where $\mathcal{I}$
and $\mathcal{J}$ are instances of CQA(Bgp$,\preceq,\cap$) and
CQA($\pi$-Bgp$,\preceq,\cap$), respectively. That is, they have the form
$\mathcal{I}=(G_{\mathcal{I}},\mathcal{C}_{\mathcal{I}},\mathcal{T}_{\mathcal{I}},H_{\mathcal{I}},Q_{\mathcal{I}},\mu_{\mathcal{I}})$
and
$\mathcal{J}=(G_{\mathcal{J}},\mathcal{C}_{\mathcal{J}},\mathcal{T}_{\mathcal{J}},H_{\mathcal{J}},Q_{\mathcal{J}},\mu_{\mathcal{J}})$,
respectively, with $Q_{\mathcal{I}}(X)=P_{1}(X)$ and
$Q_{\mathcal{J}}(Y)=\pi_{Y}P_{2}(Y,Z)$.

A pair $(\mathcal{I},\mathcal{J})$ is a yes-instance instance if and only if
both $\mathcal{I}$ and $\mathcal{J}$ are yes-instances, that is, if
$\mu_{\mathcal{I}}$ is an answer to $Q_{\mathcal{I}}$ over the intersection of
all $\preceq$-repaired graphs of $G_{\mathcal{I}}$ w.r.t.
$((\mathcal{C}_{\mathcal{I}},\mathcal{T}_{\mathcal{I}}),H_{\mathcal{I}})$ and
$\mu_{\mathcal{J}}$ is not an answer to $Q_{\mathcal{J}}$ over the
intersection of all $\preceq$-repaired graphs of $G_{\mathcal{J}}$ w.r.t.
$((\mathcal{C}_{\mathcal{J}},\mathcal{T}_{\mathcal{J}}),H_{\mathcal{J}})$.

We may assume that the instances $\mathcal{I}$ and $\mathcal{J}$ share no
symbols; in other words, they use distinct variables, constants, classes,
properties, …. Then, to construct an instance of CQA(wdQ$,\preceq,\cap$), we
can combine the shapes graphs, the data graphs, the hypotheses, and the
variable assignments $\mu=\mu_{\mathcal{I}}\cup\mu_{\mathcal{J}}$.
Additionally, we add a new class $V_{\mathcal{J}}$ that consists of all nodes
$V(G_{\mathcal{J}})\cup V(H_{\mathcal{J}})$. Furthermore, we add auxiliary
nodes $\texttt{{s}},\texttt{{e}}$ and an arbitrary linear order on
$V(G_{\mathcal{J}})\cup V(H_{\mathcal{J}})$, where $next_{\mathcal{J}}$
indicates immediate predecessors and successors, and which starts in s and
ends in e. Let $G^{*}$ be these new atoms. Then, we also add the constraint

$\displaystyle\mathsf{val}\leftrightarrow\forall
next_{\mathcal{J}}^{*}.(\texttt{{s}}\lor\texttt{{e}}\lor
V_{\mathcal{J}})\land\exists next_{\mathcal{J}}^{*}.\texttt{{e}}$

together with the target $\mathsf{val}(\texttt{{s}})$.

Moreover, we define the query of the combined instance as
$Q(X,Y,Z)=P_{1}(X)\land\bigwedge_{y\in
Y}V_{\mathcal{J}}(y)\mathbin{\text{OPT}}P_{2}(Y,Z)$.

Let $(A_{i},D_{i})_{i},(A_{j},D_{j})_{j}$ be the $\preceq$-repairs of
$\mathcal{I}$ and $\mathcal{J}$, respectively. Then the $\preceq$-repairs of
the constructed instance are exactly $(A_{i}\cup A_{j},D_{i}\cup D_{j})_{i,j}$
due to the instances sharing no symbols. Furthermore, due to disjointedness,
we have the intersection of the $\preceq$-repaired graphs

$\displaystyle G_{\cap}$ $\displaystyle=\bigcap_{i,j}(A_{i}\cup
A_{j})\cup\bigcap_{i,j}((G_{\mathcal{I}}\cup
G_{\mathcal{J}})\setminus(D_{i}\cup D_{j}))\cup G^{*}$
$\displaystyle=\bigcap_{i}A_{i}\cup\bigcap_{i}(G_{\mathcal{I}}\setminus
D_{i})\cup\bigcap_{j}A_{j}\cup\bigcap_{j}(G_{\mathcal{J}}\setminus D_{j})\cup
G^{*}$ $\displaystyle=G_{\mathcal{I},\cap}\cup G_{\mathcal{J},\cap}\cup
G^{*},$

where $G_{\mathcal{I},\cap},G_{\mathcal{J},\cap}$ are the intersections of the
$\preceq$-repaired graphs of $\mathcal{I}$ and $\mathcal{J}$, respectively.
Thus, $\mu$ is an answer to $Q$ over the intersection $G_{\cap}$ if and only
if $\mu_{\mathcal{I}}$ is an answer to $Q_{\mathcal{I}}$ over
$G_{\mathcal{I},\cap}$ and $\mu_{\mathcal{J}}$ is not an answer to
$Q_{\mathcal{J}}$ over $G_{\mathcal{J},\cap}$. ∎

######  Theorem 5.

The following statements are true for data complexity:

  * •

CQA($\pi$-wdQ$,=,\cap$) is $\mathsf{\Theta}_{2}\mathsf{P}$-c.

  * •

CQA($\pi$-wdQ$,\subseteq,\cap$) is $\mathsf{\Theta}_{3}\mathsf{P}$-c.

The following statements are true for combined complexity:

  * •

CQA($\pi$-wdQ$,=,\cap$) and CQA($\pi$-wdQ$,\leq,\cap$) are
$\mathsf{\Sigma}_{2}\mathsf{P}$-c.

  * •

CQA($\pi$-wdQ$,\subseteq,\cap$) is $\mathsf{\Theta}_{3}\mathsf{P}$-c.

###### Proof.

$\blacktriangleright$ (Hardness for CQA($\pi$-wdQ$,=,\cap$) data complexity)
We reduce from the $\mathsf{\Theta}_{2}\mathsf{P}$-complete problem List-Pair-
SAT (for hardness see Lemma 2 in Section F). The instances consist of a list
$(\varphi_{1},\psi_{1}),\dots,(\varphi_{n},\psi_{n})$ of pairs of
propositional formula in 3-CNF, i.e.,
$\varphi_{i}=\bigwedge^{m(\varphi_{i})}_{j=1}(\texttt{{l}}_{1j}(\varphi_{i})\lor\texttt{{l}}_{2j}(\varphi_{i})\lor\texttt{{l}}_{3j}(\varphi_{i}))$
and
$\psi_{i}=\bigwedge^{m(\psi_{i})}_{j=1}(\texttt{{l}}_{1j}(\psi_{i})\lor\texttt{{l}}_{2j}(\psi_{i})\lor\texttt{{l}}_{3j}(\psi_{i}))$.
$(\varphi_{1},\psi_{1}),\dots,(\varphi_{n},\psi_{n})$ is a yes instance if
some pair $(\varphi_{i},\psi_{i})$ is such that $\varphi_{i}$ is unsatisfiable
while $\psi_{i}$ is satisfiable. W.l.o.g, we assume the variables of all
formulas to be pairwise disjoint.

The encoding is similar to the one used in Theorem 1. The nodes of the data
graph $G$ consist of:

  * •

All literals l.

  * •

Clauses
$\texttt{{C}}_{j}(\varphi_{i})=(\texttt{{l}}_{1j}(\varphi_{i})\lor\texttt{{l}}_{2j}(\varphi_{i})\lor\texttt{{l}}_{3j}(\varphi_{i}))$
and
$\texttt{{C}}_{j}(\psi_{i})=(\texttt{{l}}_{1j}(\psi_{i})\lor\texttt{{l}}_{2j}(\psi_{i})\lor\texttt{{l}}_{3j}(\psi_{i}))$.

  * •

Formulas $\varphi_{i},\psi_{i}$.

  * •

Counters $\texttt{{i}}_{i}$ for $i=1,\dots,n$.

  * •

Auxiliary elements $\texttt{{s}},\texttt{{e}}$ to $G$.

Literals l are added to the class $Lit$, clauses C to $Cl$, formulas
$\varphi_{i},\psi_{i}$ to $Phi$, and counters i to $Cnt$.

We now connect the nodes as they are connected logically.

  * •

Dual literals l and $\texttt{{l}}_{d}$ are connected via
$dual(\texttt{{l}},\texttt{{l}}_{d})$.

  * •

Literals $\texttt{{l}}_{kj}(\varphi_{i})$ (resp.
$\texttt{{l}}_{kj}(\psi_{i})$) are connected to clauses
$\texttt{{C}}_{j}(\varphi_{i})$ (resp. $\texttt{{C}}_{j}(\psi_{i})$) via
$or(\texttt{{l}}_{kj}(\varphi_{i}),\texttt{{C}}_{j}(\varphi_{i}))$ (resp.
$or(\texttt{{l}}_{kj}(\varphi_{i}),\texttt{{C}}_{j}(\psi_{i}))$).

  * •

Each clause $\texttt{{C}}_{j}(\varphi_{i})$ (resp.
$\texttt{{C}}_{j}(\psi_{i})$) is connected $\varphi_{i}$ (resp. $\psi_{i}$)
via $and(\texttt{{C}}_{j}(\varphi_{i}),\varphi_{i})$ (resp.
$and(\texttt{{C}}_{j}(\psi_{i}),\psi_{i})$).

  * •

Counters $\texttt{{i}}_{i}$ are connected to the formulas $\varphi_{i}$ and
$\psi_{i}$ via $is_{\varphi}(\texttt{{i}}_{i},\varphi_{i})$ and
$is_{\psi}(\texttt{{i}}_{i},\psi_{i})$, respectively.

Each literal l, clause $\texttt{{C}}_{ik}$, and formula $\varphi_{i},\psi_{i}$
is added to both the class $T$ and $F$, indicating that they can be either
true or false. All nodes of $G$ are put into a single arbitrary linear order
$\preceq_{next}$, encoded by the property $next$, indicating immediate
predecessors and successors, and which starts in s and ends in e.

We use the following constraints $\mathcal{C}$:

$\displaystyle\mathsf{lit}\leftrightarrow{}$ $\displaystyle
Lit\land((T\land\lnot F\land\exists dual.F)$
$\displaystyle\quad{}\lor(F\land\lnot T\land\exists dual.T))$
$\displaystyle\mathsf{cl}\leftrightarrow{}$ $\displaystyle
Cl\land{=_{3}}or^{-}\land{=_{1}}and\land($ $\displaystyle(F\land\lnot
T\land\forall or^{-}.F)$ $\displaystyle\lor(T\land\lnot F\land\exists
or^{-}.T)$ $\displaystyle\mathsf{phi}\leftrightarrow{}$ $\displaystyle
Phi\land((F\land\lnot T\land\exists and^{-}.F)$
$\displaystyle\quad{}\lor(T\land\lnot F\land\forall and^{-}.T)$
$\displaystyle\mathsf{cnt}\leftrightarrow{}$ $\displaystyle
Cnt\land{=_{1}}is_{\varphi}\land{=_{1}}is_{\psi}$
$\displaystyle\mathsf{val}\leftrightarrow{}$ $\displaystyle\forall
next^{*}.(\texttt{{s}}\lor\texttt{{e}}\lor\mathsf{lit}\lor\mathsf{cl}\lor\mathsf{phi}\lor\mathsf{cnt})$
$\displaystyle{}\land\exists next^{*}.\texttt{{e}}$

The target is $\\{\mathsf{val}(\texttt{{s}})\\}=\mathcal{T}$. $\mu$ is
$\\{\\}$ and the query is $\pi_{z}$ with

$\displaystyle Q=is_{\varphi}(x,y)\land
F(y)\mathbin{\text{OPT}}is_{\psi}(x,z)\land F(z).$

For each formula $\varphi_{i}$ and $\psi_{i}$, the repairs have the
(independent) choice of what truth values to assign to each literal x by
retaining either $T(\texttt{{x}})$ and not $F(\texttt{{x}})$ or the other way
around. The truth values of the dual literals, the clauses, and the formula
itself are then all functionally determined by this choice. Thus,
$F(\varphi_{i})$ (resp. $F(\psi_{i})$) is in the repaired graph if and only if
$\varphi_{i}$ (resp. $\psi_{i}$) evaluates to false under the given choice of
the truth values for the variables that appear in $\varphi_{i}$ (resp.
$\psi_{i}$). Since each truth value assignment constitutes a repair,
$F(\varphi_{i})$ (resp. $F(\psi_{i})$) appears in the intersection of all
repaired graphs if and only if $\varphi_{i}$ (resp. $\psi_{i}$) is
unsatisfiable. Hence, $\mu=\\{\\}$ is an answer to $Q$ if and only if there is
an $\texttt{{i}}_{i}$ (variable $x$) such that $\varphi_{i}$ (variable $y$) is
unsatisfiable but $\psi_{i}$ (variable $z$) is not unsatisfiable, i.e.,
$\psi_{i}$ is satisfiable. This completes the reduction.

$\blacktriangleright$ (Hardness for CQA($\pi$-wdQ$,\subseteq,\cap$) data
complexity) To show $\mathsf{\Theta}_{3}\mathsf{P}$-hardness we have to extend
the reduction used in the CQA($\pi$-wdQ$,=,\cap$) case, proceeding further up
the polynomial hierarchy. We reduce from the following
$\mathsf{\Theta}_{3}\mathsf{P}$-complete problem List-Pair-$2$-QBF (for
hardness see Lemma 2 in Section F). The instances consist of a list
$(\varphi_{1}(X(\varphi_{1}),Y(\varphi_{1}))$,
$\psi_{1}(X(\psi_{1}),Y(\psi_{1})))$, $\dots$,
$(\varphi_{n}(X(\varphi_{n}),Y(\varphi_{n}))$,
$\psi_{n}(X(\psi_{n}),Y(\psi_{n})))$ of pairs of propositional formula in
3-CNF, i.e.,
$\varphi_{i}=\bigwedge^{m(\varphi_{i})}_{j=1}(\texttt{{l}}_{1j}(\varphi_{i})\lor\texttt{{l}}_{2j}(\varphi_{i})\lor\texttt{{l}}_{3j}(\varphi_{i}))$
and
$\psi_{i}=\bigwedge^{m(\psi_{i})}_{j=1}(\texttt{{l}}_{1j}(\psi_{i})\lor\texttt{{l}}_{2j}(\psi_{i})\lor\texttt{{l}}_{3j}(\psi_{i}))$.
An instance is a yes instance if some pair
$(\varphi_{i}(X(\varphi_{i}),Y(\varphi_{i})),\psi_{i}(X(\psi_{i}),Y(\psi_{i})))$
is such that every truth assignment of the $X(\varphi_{i})$ can be extended to
a model of $\varphi_{i}$ while this is not the case for the $X(\psi_{i})$ and
$\psi_{i}$. W.l.o.g, we assume the variables of all formulas to be pairwise
disjoint.

For the encoding, we take the data graph $G$ from before, excluding the class
$Lit$, and extend it further:

  * •

for each literals l of a $X$ (resp. $Y$) variable we add
$Lit_{X}(\texttt{{l}})$ (resp. $Lit_{Y}(\texttt{{l}})$).

  * •

Each literals l of $Y(\varphi_{i})$ (resp. $Y(\psi_{i})$) and clause
$\texttt{{C}}_{j}(\varphi_{i})$ (resp. $\texttt{{C}}_{j}(\psi_{i})$) is
connected to $\varphi_{i}$ (resp. $\psi_{i}$) via
$isIn(\texttt{{l}},\varphi_{i})$ and
$isIn(\texttt{{C}}_{j}(\varphi_{i}),\varphi_{i})$ (resp.
$isIn(\texttt{{l}},\psi_{i})$ and
$isIn(\texttt{{C}}_{j}(\psi_{i}),\psi_{i})$).

  * •

For each $\varphi_{i},\psi_{i}$ we add $Ext(\varphi_{i}),Ext(\psi_{i})$ to $G$
which shall indicate whether the corresponding $Y$ variables are instantiated.

We use the following constraints $\mathcal{C}$:

$\displaystyle\mathsf{lit}_{X}\leftrightarrow{}$ $\displaystyle
Lit_{X}\land((T\land\lnot F\land\exists dual.F)$
$\displaystyle\quad{}\lor(F\land\lnot T\land\exists dual.T))$
$\displaystyle\mathsf{lit}_{Y}\leftrightarrow{}$ $\displaystyle
Lit_{Y}\land\exists isIn\land($ $\displaystyle(\exists isIn.Ext\land($
$\displaystyle\quad(T\land\lnot F\land\exists dual.F)$
$\displaystyle\quad{}\lor(F\land\lnot T\land\exists dual.T))$
$\displaystyle\lor(\lnot\exists isIn.Ext\land\lnot F\land\lnot T))$
$\displaystyle\mathsf{cl}\leftrightarrow{}$ $\displaystyle
Cl\land{=_{3}}or^{-}\land{=_{1}}and\land\exists isIn\land($
$\displaystyle(\exists isIn.Ext\land($ $\displaystyle\quad(F\land\lnot
T\land\forall or^{-}.F)$ $\displaystyle\quad{}\lor(T\land\lnot F\land\exists
or^{-}.T))$ $\displaystyle\lor(\lnot\exists isIn.Ext\land\lnot F\land\lnot
T))$ $\displaystyle\mathsf{phi}\leftrightarrow{}$ $\displaystyle
Phi\land((Ext\land T\land\lnot F\land\forall and^{-}.T)$
$\displaystyle\quad{}\lor(\lnot Ext\land\lnot F\land\lnot T))$
$\displaystyle\mathsf{cnt}\leftrightarrow{}$ $\displaystyle
Cnt\land{=_{1}}is_{\varphi}\land{=_{1}}is_{\psi}$
$\displaystyle\mathsf{val}\leftrightarrow{}$ $\displaystyle\forall
next^{*}.(\texttt{{s}}\lor\texttt{{e}}\lor\mathsf{lit}_{X}\lor\mathsf{lit}_{Y}\lor\mathsf{cl}\lor\mathsf{phi}\lor\mathsf{cnt})$
$\displaystyle{}\land\exists next^{*}.\texttt{{e}}$

We leave the target and $\mu$ unchanged, while the query now is $\pi_{z}Q$
with

$\displaystyle Q(z)=is_{\varphi}(x,y)\land
Ext(y)\mathbin{\text{OPT}}is_{\psi}(x,z)\land Ext(z).$

The idea is as follows. For each formula, the repairs have the choice of
whether to instantiate only the $X$ variables or both the $X$ and the $Y$
variables. In the first case, the formula has to be removed from the class
$Ext$ and the $X$ variables instantiated, but, at the same time, all literals
of the $Y$ as well as the clauses and the formula itself have to be removed
from both $T$ and $F$. In the second case, the formula remains in the class
$Ext$, but both the $X$ and the $Y$ variables have to be instantiated, and the
truth values of the dual literals, the clauses, and the formula itself are
then all functionally determined by this choice. Furthermore, the formula
itself has to evaluate to true.

Thus, intuitively, when concentrating on a single formula, repairs correspond
1-1 to instantiations of only the $X$ variables or a combination the $X$ and
the $Y$ that satisfy the formula. When the instantiation is the same on the
$X$ variables, a repair of the second kind is a subset of the repair of the
first kind. Thus, a formula $\varphi_{i}$ (resp. $\psi_{i}$) is not in the
class $Ext$ in some $\subseteq$-repaired graph $G_{R}$ if and only if the
instantiation of the $X$ variables represented by $G_{R}$ cannot be extended
to the $Y$ variables while satisfying the $\varphi_{i}$ (resp. $\psi_{i}$).

Concluding, $\mu=\\{\\}$ is an answer to $Q$ if and only if there is an
$\texttt{{i}}_{i}$ (variable $x$) such that for $\varphi_{i}$ (variable $y$),
every instantiation of the variables $X(\varphi_{i})$ can be extended to a
model of $\varphi_{i}$, while this is not true for $\psi_{i}$ (variable $z$)
and the variables $X(\psi_{i})$.

$\blacktriangleright$ (Hardness for CQA($\pi$-wdQ$,=,\cap$) and
CQA($\pi$-wdQ$,\leq,\cap$) combined complexity) Recall that answering
$\pi$-wdQ queries over fixed data graphs $G$ is already
$\mathsf{\Sigma}_{2}\mathsf{P}$-complete combined complexity (?). Thus, we can
explicitly name every atom from $G$ in the shapes graph such that the only
repaired graph is $G$ itself.

$\blacktriangleright$ (Membership for CQA($\pi$-wdQ$,=,\cap$) and
CQA($\pi$-wdQ$,\leq,\cap$) combined complexity) To check whether $\mu\colon
X\rightarrow V(G)$ is an answer to $\pi_{X}Q$ with
$Q=((\dots((P\mathbin{\text{OPT}}P_{1})\mathbin{\text{OPT}}P_{2})\dots)\mathbin{\text{OPT}}P_{k})$,
we can do the following:

  1. 1.

Let $S:=|G|+|H|$.

  2. 2.

Compute the size $K$ of the intersection of all repaired graphs.

  3. 3.

Guess repairs $R_{1},\dots,R_{S-K+1}$ and a
$\mu_{P}\colon\mathsf{vars}(P)\setminus X\rightarrow V(G)$.

  4. 4.

Check that $R_{i}$ is valid (and no smaller repair exists).

  5. 5.

Check that $|\bigcap_{i}G_{R_{i}}|=K$.

  6. 6.

Check that $\mu\cup\mu_{P}$ is an answer to $Q$ over $\bigcap_{i}G_{R_{i}}$.

Clearly, all checks only require access to an $\mathsf{NP}$-oracle and we have
already seen how to compute $K$ deterministically with access to an
$\mathsf{NP}$-oracle.

$\blacktriangleright$ (Membership for CQA($\pi$-wdQ$,=,\cap$) data complexity)
We can proceed similarly to the case CQA($\pi$-wdQ$,\leq,\cap$), but we skip
the computation of $k$. That is, we simply determine the size $K$ of the
intersection of all repaired graphs. Then, we ask the question of whether
$\mu$ is an answer to the query $\pi_{X}Q$. Given $K$, this only requires
$\mathsf{NP}$-power as a NTM can guess the intersection of all repaired graphs
$G_{\cap}$ (size $K$), and a witnessing repair (of size $k$) together with a
model supporting it for each atom not in the intersection. Then, the NTW can
go through all (polynomially many) instantiations of the bound variables and,
if needed, also through all (polynomially many) extensions to the remaining
variables in the OPT-part, always checking whether this variables assignment
satisfies the corresponding query over $G_{\cap}$. Thus, the NTW can return
yes if $\mu$ is an answer.

$\blacktriangleright$ (Membership for CQA($\pi$-wdQ$,\subseteq,\cap$) combined
complexity) The argument for $\mathsf{\Theta}_{3}\mathsf{P}$-membership
combined complexity of CQA($\pi$-wdQ$,\subseteq,\cap$) works similar to the
case of CQA($\pi$-wdQ$,=,\cap$) data complexity. However, we have to check
that the repairs are minimal and checking that $\mu$ is, in fact, an answer to
the query $\pi_{X}Q$ requires more power.

Concretely, we start by determining the size of the intersection of all
$\subseteq$-repaired graphs with logarithmically many
$\mathsf{\Sigma}_{2}\mathsf{P}$-oracle calls. The calls are of the form: “Is
size of the intersection of all $\subseteq$-repaired graphs less than $c$?”
This is a $\mathsf{\Sigma}_{2}\mathsf{P}$-question as we can guess the atoms
not in the intersection and a repair per atom as a witness. With access to an
$\mathsf{NP}$-oracle, we then have to check that there are no smaller repairs.

Given the size $K$ of the intersection, the question of whether $\mu$ is an
answer to $\pi_{X}Q$ over the intersection only requires a single further
$\mathsf{\Sigma}_{2}\mathsf{P}$-oracle call. A NTM with access to an
$\mathsf{NP}$-oracle simply has to guess the values $\mu_{X}$ for the
variables $X$, and the intersection $G_{\cap}$ together with a witnessing
repair per atom not in $G_{\cap}$, Then, it can check that each repair is
minimal and whether $\mu\cup\mu_{X}$ is an answer to the query over the
intersection. For the last check, a single $\mathsf{NP}$-oracle call suffices.
∎

##  Appendix E Full Proofs for CQA for Maximal Repairs

First, we recall the Boolean hierarchy $\mathsf{BH}$, which is less common
than the other complexity classes encountered so far: on the bottom levels, we
have $\mathsf{BH}_{1}$ = $\mathsf{NP}$ and $\mathsf{BH}_{2}$ = the class of
languages obtained as the intersection of a language in $\mathsf{BH}_{1}$ and
a language in $\mathsf{coNP}$. In other words, we have
$\mathsf{BH}_{2}=\mathsf{NP}\land\mathsf{coNP}=\mathsf{DP}$. For the general
case, we have $\mathsf{BH}_{2k}=\bigvee_{i=0}^{k}\mathsf{DP}$, i.e., the class
of languages that are the union of $k$ $\mathsf{DP}$ languages, and
$\mathsf{BH}_{2k+1}=\mathsf{NP}\lor\bigvee_{i=0}^{k}\mathsf{DP}$, i.e., the
class of languages that are the union of $k$ $\mathsf{DP}$ languages and an
$\mathsf{NP}$ language. In order to establish membership of a problem in
$\mathsf{BH}$, it suffices to show that the problem can be solved in
deterministic polynomial time with constantly many calls to an
$\mathsf{NP}$-oracle. Likewise, to show that a problem is hard for every level
of $\mathsf{BH}$, it suffices to exhibit a reduction from the combinations of
$k$ pairs of instances of an $\mathsf{NP}$-hard problem for arbitrary $k>0$
asking if there is a pair $(\mathcal{I}_{i},\mathcal{J}_{i})$ such that
$\mathcal{I}_{i}$ is a yes-instance and $\mathcal{J}_{i}$ is a no-instance.

######  Theorem 6.

mCQA($\textsc{Bgp},=,\mathcal{S}$) is $\mathsf{BH}_{k}$-hard data complexity
for every $k>0$ and $\mathcal{S}\in\\{\exists,\forall,\cap\\}$. Furthermore,
mCQA($\pi$-wdQ$,=,\exists$), mCQA($\pi$-wdQ$,=,\forall$), and
mCQA(wdQ$,=,\cap$) are in $\mathsf{BH}$ data complexity.

###### Proof.

$\blacktriangleright$ (Hardness of mCQA($\textsc{Bgp},=,\mathcal{S}$)) We
reduce from the $\mathsf{BH}_{2k}$-complete problem $k$-Pair-SAT. An instance
$\mathcal{I}$ consist of $k$ pairs
$\texttt{{p}}_{1},\dots,\texttt{{p}}_{k}=(\varphi_{1},\psi_{1}),\dots,(\varphi_{k},\psi_{k})$
of propositional formula in 3-CNF, i.e.,
$\varphi_{i}=\bigwedge^{m(\varphi_{i})}_{j=1}(\texttt{{l}}_{1j}(\varphi_{i})\lor\texttt{{l}}_{2j}(\varphi_{i})\lor\texttt{{l}}_{3j}(\varphi_{i}))$
and
$\psi_{i}=\bigwedge^{m(\psi_{i})}_{j=1}(\texttt{{l}}_{1j}(\psi_{i})\lor\texttt{{l}}_{2j}(\psi_{i})\lor\texttt{{l}}_{3j}(\psi_{i}))$.
$\mathcal{I}$ is a yes-instance if some pair $(\varphi_{i},\psi_{i})$ is such
that $\varphi_{i}$ is unsatisfiable while $\psi_{i}$ is satisfiable. W.l.o.g,
we assume the variables of all formulas to be pairwise disjoint.

We extend our standard encoding for propositional formulas. Concretely, the
nodes of the data graph $G$ consist of:

  * •

All literals l.

  * •

Clauses
$\texttt{{C}}_{j}(\varphi_{i})=(\texttt{{l}}_{1j}(\varphi_{i})\lor\texttt{{l}}_{2j}(\varphi_{i})\lor\texttt{{l}}_{3j}(\varphi_{i}))$
and
$\texttt{{C}}_{j}(\psi_{i})=(\texttt{{l}}_{1j}(\psi_{i})\lor\texttt{{l}}_{2j}(\psi_{i})\lor\texttt{{l}}_{3j}(\psi_{i}))$.

  * •

Formulas $\varphi_{i},\psi_{i}$.

  * •

The pairs $\texttt{{p}}_{1},\dots,\texttt{{p}}_{k}$.

  * •

The instance $\mathcal{I}$ itself.

  * •

Auxiliary elements
$\texttt{{s}},\texttt{{s}}_{\varphi_{1}},\texttt{{s}}_{\psi_{1}},\dots,\texttt{{s}}_{\varphi_{k}},\texttt{{s}}_{\psi_{k}},\texttt{{e}}$.

Intuitively, we need the additional
$\texttt{{s}}_{\varphi_{i}},\texttt{{s}}_{\psi_{i}}$ to increase the “weight”
of some targets such that they then always have to be satisfied. Literals l
are added to the class $Lit$, clauses C to $Cl$, formulas
$\varphi_{i},\psi_{i}$ to $Phi$, pairs p to $Pair$, the auxiliary elements
$\texttt{{s}},\texttt{{s}}_{\varphi_{i}},\texttt{{s}}_{\psi_{i}}$ to $Start$,
and the instance $\mathcal{I}$ to $Inst$.

As many times before, we connect the nodes as they are connected logically:

  * •

Dual literals l and $\texttt{{l}}_{d}$ are connected via
$dual(\texttt{{l}},\texttt{{l}}_{d})$.

  * •

Literals $\texttt{{l}}_{kj}(\varphi_{i})$ (resp.
$\texttt{{l}}_{kj}(\psi_{i})$) are connected to clauses
$\texttt{{C}}_{j}(\varphi_{i})$ (resp. $\texttt{{C}}_{j}(\psi_{i})$) via
$or(\texttt{{l}}_{kj}(\varphi_{i}),\texttt{{C}}_{j}(\varphi_{i}))$ (resp.
$or(\texttt{{l}}_{kj}(\varphi_{i}),\texttt{{C}}_{j}(\psi_{i}))$).

  * •

Each clause $\texttt{{C}}_{j}(\varphi_{i})$ (resp.
$\texttt{{C}}_{j}(\psi_{i})$) is connected $\varphi_{i}$ (resp. $\psi_{i}$)
via $and(\texttt{{C}}_{j}(\varphi_{i}),\varphi_{i})$ (resp.
$and(\texttt{{C}}_{j}(\psi_{i}),\psi_{i})$).

  * •

Each pair $\texttt{{p}}_{i}$ is connected to its components $\varphi_{i}$ and
$\psi_{i}$ via $and_{\varphi}(\varphi_{i},\texttt{{p}}_{i})$ and
$and_{\psi}(\psi_{i},\texttt{{p}}_{i})$, respectively.

  * •

Furthermore, each pair $\texttt{{p}}_{i}$ is connected to $\mathcal{I}$ via
$or(\texttt{{p}}_{i},\mathcal{I})$.

Each literal l, clause C, formula $\varphi_{i},\psi_{i}$, pair p, and the
instance $\mathcal{I}$ is added to both the class $T$ and $F$, indicating that
they can be either true or false. All nodes of $G$ except the $2k$ nodes
$\texttt{{s}}_{\varphi_{i}},\texttt{{s}}_{\psi_{i}}$ are put into a single
arbitrary linear order, where $next$ indicates immediate predecessors and
successors, and which starts in s and ends in e. The auxiliary nodes
$\texttt{{s}}_{\varphi_{i}},\texttt{{s}}_{\psi_{i}}$ are added as predecessors
of s, i.e.,
$next(\texttt{{s}}_{\varphi_{i}},\texttt{{s}}),next(\texttt{{s}}_{\psi_{i}},\texttt{{s}})$.

The set of constraints $\mathcal{C}$ then consists of:

$\displaystyle\mathsf{lit}\leftrightarrow{}$ $\displaystyle
Lit\land((T\land\lnot F\land\exists dual.F)$
$\displaystyle\quad{}\lor(F\land\lnot T\land\exists dual.T))$
$\displaystyle\mathsf{cl}\leftrightarrow{}$ $\displaystyle
Cl\land{=_{3}}or^{-}\land{=_{1}}and\land($ $\displaystyle(F\land\lnot
T\land\forall or^{-}.F)$ $\displaystyle\lor(T\land\lnot F\land\exists
or^{-}.T)$ $\displaystyle\mathsf{phi}\leftrightarrow{}$ $\displaystyle
Phi\land((F\land\lnot T\land\exists and^{-}.F)$
$\displaystyle\quad{}\lor(T\land\lnot F\land\forall and^{-}.T))$
$\displaystyle\mathsf{pair}\leftrightarrow{}$ $\displaystyle
Pair\land{=_{1}}and^{-}_{\varphi}\land{=_{1}}and^{-}_{\psi}\land{=_{1}}or\land($
$\displaystyle((F\land\lnot
T\land({=_{1}}and^{-}_{\varphi}.T\lor{=_{1}}and^{-}_{\psi}.F))$
$\displaystyle\lor(T\land\lnot
F\land{=_{1}}and^{-}_{\varphi}.F\land{=_{1}}and^{-}_{\psi}.T))$
$\displaystyle\mathsf{inst}\leftrightarrow{}$ $\displaystyle
Inst\land((F\land\lnot T\land\forall or^{-}.F)$
$\displaystyle\quad{}\lor(T\land\lnot F\land\exists or^{-}.T))$
$\displaystyle\mathsf{phiT}\leftrightarrow{}$ $\displaystyle Phi\land T$
$\displaystyle\mathsf{val}\leftrightarrow{}$ $\displaystyle\forall
next^{*}.(\texttt{{e}}\lor
Start\lor\mathsf{lit}\lor\mathsf{cl}\lor\mathsf{phi}\lor\mathsf{pair}\lor\mathsf{list})$
$\displaystyle{}\land\exists next^{*}.\texttt{{e}}$

The targets are $\mathcal{T}=\mathcal{T}_{1}\cup\mathcal{T}_{2}$ with

$\displaystyle\mathcal{T}_{1}$
$\displaystyle=\\{\mathsf{val}(\texttt{{s}})\\}\cup\\{\mathsf{val}(\texttt{{s}}_{\varphi_{i}}),\mathsf{val}(\texttt{{s}}_{\psi_{i}})\mid
i=1,\dots,k\\},$ $\displaystyle\mathcal{T}_{2}$
$\displaystyle=\\{\mathsf{phiT}(\varphi_{i}),\mathsf{phiT}(\psi_{i})\mid
i=1,\dots,k\\}.$

Furthermore, $H=\emptyset,\mu=\\{x\rightarrow\mathcal{I}\\}$, and the query is
$Q(x)=T(x)$.

Notice that there are $2k+1$ targets in $\mathcal{T}_{1}$ while there are only
$2k$ targets in $\mathcal{T}_{2}$. Intuitively, the first $2k+1$ only asks the
repair to remain true to the semantics of propositional logic, and thus, there
are repairs that validate those targets. Moreover, if one target of
$\mathcal{T}_{1}$ is validated by a repair, it may as well validate all
targets of $\mathcal{T}_{1}$. Therefore, max-repairs must validate all of
$\mathcal{T}_{1}$ and remain true to the semantics of proportional logic.

Furthermore, repairs validating the targets $\mathcal{T}_{1}$, i.e., max-
repairs, can choose the truth assignments for every variable freely, but the
remaining truth values (of the literals, clauses, $\dots$) deterministically
depend on this choice. A max-repair then validates $\mathsf{phiT}$ at
$\varphi_{i}$ (resp. $\psi_{i}$) if the choice of the truth assignment leads
to the $\varphi_{i}$ (resp. $\psi_{i}$) being evaluated to true under this
assignment, i.e., the corresponding formula is satisfiable. Consequently, a
repair maximizing the number of targets validated now must not only remain
true to the semantics of propositional logic but must pick truth assignments
that maximizes the number of formulas that evaluate to true. As the variables
of all formulas are pairwise disjoint, every maximal repair sets all
satisfiable formulas to true and all unsatisfiable formulas to false. Thus, in
these repairs, $\mathcal{I}$ is set to true iff there exists a pair
$(\varphi_{i},\psi_{i})$ such that $\varphi_{i}$ is unsatisfiable and
$\psi_{i}$ is satisfiable. Therefore, the reduction is correct no matter the
semantics used for CQA.

$\blacktriangleright$ (Membership for mCQA($\pi$-wdQ$,=,\exists$),
mCQA($\pi$-wdQ$,=,\forall$)) For data complexity, the targets $\mathcal{T}$
are considered fixed. Hence, there are only constantly many subsets
$\mathcal{T}^{\prime}$ of $\mathcal{T}$ and with constantly many
$\mathsf{NP}$-oracle calls we can determine the maximal cardinality of a
$\mathcal{T}^{\prime}$ such that there is a repair that validates all targets
in $\mathcal{T}^{\prime}$. Then, given $\mathcal{K}=|\mathcal{T}^{\prime}|$,
answering the question whether $\mu$ is an answer of $Q$ of a / all repaired
graphs validating $|\mathcal{T}^{\prime}|$ targets only requires a single call
to an $\mathsf{NP}$-oracle. To see this, we can simply revisit the
$\mathsf{NP}$ and $\mathsf{coNP}$ membership Full Proofs for
CQA($\pi$-wdQ$,=,\exists$) and CQA($\pi$-wdQ,$=,\forall$). The only change
required is that instead of guessing repairs $R$ together with supported
models $I$ such that $\mathcal{T}\subseteq I$, we guess $R,I$ such that
$\mathcal{T}^{\prime}\subseteq I$ for some
$\mathcal{T}^{\prime}\subseteq\mathcal{T},|\mathcal{T}^{\prime}|=\mathcal{K},$.

$\blacktriangleright$ (Membership for mCQA(wdQ$,=,\cap$)) Let us first
consider the easier case mCQA($\pi$-Bgp$,=,\cap$). For this, we can proceed as
before and first compute $\mathcal{K}=|\mathcal{T}^{\prime}|$. Then, we can
follow the membership proof of CQA($\pi$-Bgp$,=,\cap$) and insist that repairs
need only validate $\mathcal{K}$ target. Thus, mCQA($\pi$-Bgp$,=,\cap$) is in
$\mathsf{BH}$.

For the case of mCQA(wdQ$,=,\cap$), recall the membership proof of
CQA(wdQ$,=,\cap$). We can copy this proof for the present case, and as
mCQA($\pi$-Bgp$,=,\cap$) is in $\mathsf{BH}$ and
$\mathsf{BH}=\mathsf{BH}\land\mathsf{co}$-$\mathsf{BH}$, mCQA(wdQ$,=,\cap$) is
also in $\mathsf{BH}$. ∎

######  Theorem 7.

mCQA($\textsc{Bgp},=,\mathcal{S}$) is $\mathsf{\Theta}_{2}\mathsf{P}$-hard
combined complexity for $\mathcal{S}\in\\{\exists,\forall,\cap\\}$.
Furthermore, mCQA($\pi$-$\textsc{Bgp},=,\exists$), mCQA(wdQ$,=,\forall$), and
mCQA(Bgp$,=,\cap$) are in $\mathsf{\Theta}_{2}\mathsf{P}$ combined complexity.

###### Proof.

$\blacktriangleright$ (Hardness of mCQA($\textsc{Bgp},=,\mathcal{S}$)) We
reduce from the $\mathsf{\Theta}_{2}\mathsf{P}$-complete problem CardMinSat
(?). Recall, a propositional formula
$\varphi(\texttt{{x}}_{1},\dots,\texttt{{x}}_{n})$ in 3-CNF is a yes-instance
if the variable $\texttt{{x}}_{1}$ is true in some model minimizing the number
of variables set to true.

For the encoding, the nodes of the data graph $G$ consist of:

  * •

All literals l.

  * •

An additional copy $\texttt{{x}}^{\prime}_{i}$ for each variable
$\texttt{{x}}_{i}$.

  * •

The clauses C of $\varphi$.

  * •

The formula $\varphi$ itself.

  * •

$2n+1$ copies $\varphi_{1},\dots,\varphi_{2n+1}$ of $\varphi$.

  * •

Auxiliary nodes
$\texttt{{s}},\texttt{{s}}_{1},\dots\texttt{{s}}_{4n+3},\texttt{{e}}$.

Literals l are added to the class $Lit$, clauses C to $Cl$, the formula
$\varphi$ to $Phi$, copies $\texttt{{x}}^{\prime}_{i}$ of variables to $CVar$,
copies $\varphi_{i}$ of $\varphi$ to $CPhi$, and the auxiliary elements
$\texttt{{s}},\texttt{{s}}_{i}$ to $Start$.

We connect the nodes as they are connected logically.

  * •

Literals l and there dual $\texttt{{l}}^{d}$ are connected via
$dual(\texttt{{l}},\texttt{{l}}^{d})$

  * •

Literals are connected to clauses C they appear in via
$or(\texttt{{l}},\texttt{{C}}$.

  * •

Each clause C is connected to $\varphi$ via $and(\texttt{{C}},\varphi$.

  * •

Copies $\texttt{{x}}^{\prime}_{i}$ of variables and copies $\varphi_{i}$ of
$\varphi$ are connected to their mirrors via
$copy(\texttt{{x}}^{\prime}_{i},\texttt{{x}}_{i})$ and
$copy(\varphi_{i},\varphi)$.

Each literal l, clause C, formula $\varphi$, and copies
$\texttt{{x}}^{\prime}_{i},\varphi_{i}$ are added to both the class $T$ and
$F$, indicating that they can be either true or false. All nodes of $G$ except
the $4n+3$ nodes $\texttt{{s}}_{i}$ are put into a single arbitrary linear
order, where $next$ indicates immediate predecessors and successors, and which
starts in s and ends in e. The auxiliary nodes $\texttt{{s}}_{i}$ are added as
predecessors of s, i.e., $next(\texttt{{s}}_{i},\texttt{{s}})$.

The set of constraints $\mathcal{C}$ then consists of:

$\displaystyle\mathsf{lit}\leftrightarrow{}$ $\displaystyle
Lit\land((T\land\lnot F\land\exists dual.F)$
$\displaystyle\quad{}\lor(F\land\lnot T\land\exists dual.T))$
$\displaystyle\mathsf{cVar}\leftrightarrow{}$ $\displaystyle
CVar\land((T\land\lnot F\land\exists copy.T)$
$\displaystyle\quad{}\lor(F\land\lnot T\land\exists copy.F))$
$\displaystyle\mathsf{cl}\leftrightarrow{}$ $\displaystyle
Cl\land{=_{3}}or^{-}\land{=_{1}}and\land($ $\displaystyle(F\land\lnot
T\land\forall or^{-}.F)$ $\displaystyle\lor(T\land\lnot F\land\exists
or^{-}.T))$ $\displaystyle\mathsf{phi}\leftrightarrow{}$ $\displaystyle
Phi\land((\forall and^{-}.T\land T\land\lnot F)$
$\displaystyle\quad{}\lor(\exists and^{-}.F\land F\land\lnot T))$
$\displaystyle\mathsf{cPhi}\leftrightarrow{}$ $\displaystyle
CPhi\land((T\land\lnot F\land\exists copy.T)$
$\displaystyle\quad{}\lor(F\land\lnot T\land\exists copy.F))$
$\displaystyle\mathsf{phiT}\leftrightarrow{}$ $\displaystyle(Phi\lor
CPhi)\land T$ $\displaystyle\mathsf{litT}\leftrightarrow{}$
$\displaystyle(Lit\lor CVar)\land T$
$\displaystyle\mathsf{litF}\leftrightarrow{}$ $\displaystyle(Lit\lor
CVar)\land F$ $\displaystyle\mathsf{val}\leftrightarrow{}$
$\displaystyle\forall next^{*}.(\texttt{{e}}\lor
Start\lor\mathsf{phi}\lor\mathsf{cPhi}$
$\displaystyle\quad\quad\quad{}\lor\mathsf{lit}\lor\mathsf{cVar}\lor\mathsf{cl})$
$\displaystyle\land\exists next^{*}.\texttt{{e}}$

The targets are
$\mathcal{T}=\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\mathcal{T}_{3}\cup\mathcal{T}_{4}$
with

$\displaystyle\mathcal{T}_{1}$
$\displaystyle=\\{\mathsf{val}(\texttt{{s}})\\}\cup\\{\mathsf{val}(\texttt{{s}}_{i})\mid
i=1,\dots,4n+3\\}$ $\displaystyle\mathcal{T}_{2}$
$\displaystyle=\\{\mathsf{phiT}(\varphi)\\}\cup\\{\mathsf{phiT}(\varphi_{i})\mid
i=1,\dots,2n+1\\}$ $\displaystyle\mathcal{T}_{3}$
$\displaystyle=\\{\mathsf{litF}(\texttt{{x}}_{i}),\mathsf{litF}(\texttt{{x}}^{\prime}_{i})\mid
i=1,\dots,n\\}$ $\displaystyle\mathcal{T}_{4}$
$\displaystyle=\\{\mathsf{litT}(\texttt{{x}}_{1})\\}$

Furthermore,
$H=\emptyset,\mu=\\{x\rightarrow\varphi,y\rightarrow\texttt{{x}}_{1}\\}$, and
the query is $Q(x,y)=T(x)\land T(y)$.

Notice that there are $4n+4$ targets in $\mathcal{T}_{1}$ and only $4n+3$
other targets. Again, these targets ask the repair to remain true to the
semantics of propositional logic, and thus, there are repairs that validate
those targets. Moreover, if one target of $\mathcal{T}_{1}$ is validated by a
repair, it may as well validate all targets of $\mathcal{T}_{1}$. Therefore,
max-repairs must validate all of $\mathcal{T}_{1}$ and remain true to the
semantics of proportional logic. This means that repairs validating the
targets $\mathcal{T}_{1}$ can choose the truth assignments for every variable
freely, but the remaining truth values (of the literals, copies, $\dots$)
deterministically depend on this choice.

Next, let us consider $\mathcal{T}_{2}$. Notice that there are $2n+2$ targets
in $\mathcal{T}_{3}$ and only $2n+1$ other targets (in
$\mathcal{T}_{3},\mathcal{T}_{4}$). These ask for $\varphi$ to evaluate to
true. Thus, by arguing similar as for the targets $\mathcal{T}_{1}$, if
$\varphi$ is satisfiable, all max-repairs must validate $\mathcal{T}_{2}$ and,
consequently, represent models of $\varphi$.

We proceed with $\mathcal{T}_{3}$. Targets
$\mathsf{litF}(\texttt{{x}}_{i}),\mathsf{litF}(\texttt{{x}}^{\prime}_{i})$ ask
for $\texttt{{x}}_{i}$ to be set to false. Thus, if $\varphi$ is satisfiable,
max-repairs for the targets
$\mathcal{T}_{1}\cup\mathcal{T}_{2}\cup\mathcal{T}_{3}$ represent the minimal
models of $\varphi$.

Lastly, consider the remaining target
$\mathcal{T}_{4}=\\{\mathsf{litT}(\texttt{{x}}_{1})\\}$. This target asks for
$\texttt{{x}}_{1}$ to be set to true. However, this is a single target and
thus, models of $\varphi$ that set $\texttt{{x}}_{1}$ to true are only
slightly prioritized over models that set $\texttt{{x}}_{1}$ to false.

The targets for the shape name $\mathsf{phiT}$ are then validated if the
choice of the truth assignment leads to the formula $\varphi$ being evaluated
to true under this assignment, $\mathsf{litF}$ if the corresponding variable
is set to false, and $\mathsf{litT}$ is $\texttt{{x}}_{1}$ is set to true.
Thus, in total, if $\varphi$ is satisfiable, max-repairs are minimal models of
$\varphi$, and, if there is a minimal model with $\texttt{{x}}_{1}$ being set
to true, max-repairs are exactly those minimal models where $\texttt{{x}}_{1}$
is set to true. Consequently, this proves the correctness of reduction no
matter the semantics used for CQA.

$\blacktriangleright$ (Membership for mCQA($\pi$-$\textsc{Bgp},=,\exists$),
mCQA(wdQ$,=,\forall$), and mCQA(Bgp$,=,\cap$)) We only need to slightly modify
the decision procedure and its complexity analysis from the proof of the
previous theorem. First, in combined complexity, the set $\mathcal{T}$ is no
longer considered as fixed. Hence, we now determine the maximum cardinality
$\mathcal{K}$ of subsets $\mathcal{T}^{\prime}$ of $\mathcal{T}$ such that
there exists a repair of $G$ w.r.t., $((\mathcal{C},\mathcal{T}^{\prime}),H)$.
That is, by asking logarithmically many $\mathsf{NP}$-questions of the form
“does there exists a subset $\mathcal{T}^{\prime}\subseteq\mathcal{T}$ with
$|\mathcal{T}^{\prime}|\geq c$ such that there exists a repair of $G$ w.r.t.
$((\mathcal{C},\mathcal{T}^{\prime}),H)$?”

After that, we only need one more oracle call to decide if $\mu$ is an answer
to query $Q$ over some / all / the intersection of all repaired graphs of $G$
w.r.t. $((\mathcal{C},\mathcal{T}^{\prime}),H)$, where
$\mathcal{T}^{\prime}\subseteq\mathcal{T},|\mathcal{T}^{\prime}|=\mathcal{K}$.
For mCQA($\pi$-$\textsc{Bgp},=,\exists$), a NTW answering that oracle call has
to guess such a repaired graph together with an instantiation of the
quantified variables for the yes-instances. For mCQA(wdQ$,=,\forall$), the NTW
has to guess a repaired graph together with an instantiation of the variables
in the OPT-part for the no-instances. For mCQA(Bgp$,=,\cap$), the NTW has to
simply guess a repaired graph for the no-instances. ∎

##  Appendix F Reference Problems

Problem: |  CardMin-Precoloring
---|---
Input: |  A graph $G=(V,E)$ with $v_{1}\in V$, a precoloring $c\colon V\rightarrow 2^{\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}}$.
Question: |  Does there exist a 3-coloring of $G$ adhering to $c$ that colors $v_{1}$ the color g while at the same time minimizes the use of g?

######  Lemma 1.

CardMin-Precoloring is $\mathsf{\Theta}_{2}\mathsf{P}$-hard for 3-colorable
graphs with degree bounded by 5.

###### Proof sketch.

We reduce from the $\mathsf{\Theta}_{2}\mathsf{P}$-complete problem CardMinSat
(?). An instance is a propositional formula
$\varphi(x_{1},\dots,x_{n})=\bigwedge_{i}C_{i}=\bigwedge_{i}(l_{1i}\lor
l_{2i}\lor l_{3i})$ in 3-CNF including the variable $x_{1}$. $\varphi$ is a
yes-instance if $x_{1}$ is true in some model minimizing the variables set to
true. Now let us define $\psi=\varphi\lor(\lnot x_{1}\land
x_{2}\land\cdots\land x_{n+1})$. Then, $\psi$ has a minimal model setting
$x_{1}$ to true if and only if $\varphi$ has a minimal model setting $x_{1}$
to true.

Now, applying the classical reduction from propositional formulas to
3-Colorability to the formula $\psi(x_{1},\dots,x_{n+1})$, we can get a graph
$G$ such that $x_{1},\dots,x_{n+1},\varphi\in V(G)$. Furthermore, interpreting
g as true and r as false, we can ask for a graph $G$ such that a
$col\colon\\{x_{1},\dots,x_{n+1},\psi\\}\rightarrow\\{\texttt{{r}},\texttt{{g}}\\}$
is extendable to a coloring of the whole graph if and only if
$col(\psi)=\psi(col(x_{1},\dots,x_{n+1}))$. Thus, let us consider the
precoloring $c\colon
x_{i}\mapsto\\{\texttt{{r}},\texttt{{g}}\\},\varphi\mapsto\\{\texttt{{g}}\\}$,
and $v\mapsto\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}$ for all other $v\in
V(G)$. Then, each coloring $col$ adhering to $c$ corresponds to exactly one
model of $\psi$, and every model of $\psi$ corresponds to at least one
coloring adhering to $c$. Notice that $(G,c)$ is 3-colorable.

Two steps are left. First, we need to correspond minimal models of $\psi$ to
colorings of $(G,c)$ minimizing the use of g. I.e., the colors of all but the
variables $x_{i}$ have to be irrelevant. To achieve this, let us introduce a
triangle $v,v^{\prime},v^{\prime\prime}$ ($v^{\prime},v^{\prime\prime}$ are
new vertices) for each $v\in V(G),v\neq x_{i}$ and define
$c(v^{\prime})=c(v^{\prime\prime})=\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}$.
Thus, now, each coloring $col$ adhering to $c$ that minimizes the use of g
corresponds to exactly one minimal model of $\varphi$ and every minimal model
of $\varphi$ corresponds to at least one coloring adhering to $c$ that
minimizes the use of g.

Second, we need to ensure that the degree of every vertex is at most 5. To
achieve this, iteratively pick a vertex $v\in V(G)$ with neighbors
$v_{1},\dots,v_{k},k\geq 6$. Then, introduce two new triangles
$v,v^{\prime},v^{\prime\prime}$ and
$v^{\prime},v^{\prime\prime},v^{\prime\prime\prime}$, and connect
$v_{1},\dots,v_{3}$ to $v$ and $v_{4},\dots,v_{k}$ to
$v^{\prime\prime\prime}$. Furthermore, define
$c(v^{\prime})=c(v^{\prime\prime})=\\{\texttt{{r}},\texttt{{g}},\texttt{{b}}\\}$
and $c(v^{\prime\prime\prime})=c(v)$. Thus, the relative “sizes” of the
colorings remain the same as every coloring $col$ has to color exactly one of
the new vertices $v^{\prime},v^{\prime\prime},v^{\prime\prime\prime}$ the
color g. Furthermore, this does not change the colorability and
$col(v)=col(v^{\prime\prime\prime})$. This completes the sketch of the
reduction. ∎

Problem: |  List-Pair-$k$-QBF
---|---
Input: |  A list $(\varphi_{1}(X_{1}(\varphi_{1})\cdots X_{k}(\varphi_{1}))$, $\psi_{1}(X_{1}(\psi_{1})\cdots X_{k}(\psi_{1})))$, $\dots$, $(\varphi_{n}(X_{1}(\varphi_{n})\cdots X_{k}(\varphi_{n}))$, $\psi_{n}(X_{1}(\psi_{n})\cdots X_{k}(\psi_{n})))$ of pairs of propositional formulas in 3-CNF.
Question: |  Does there exist a $i$ such that $QX_{1}(\varphi_{i})\cdots\forall X_{k-1}(\varphi_{i})\exists X_{k}(\varphi_{i})\varphi_{i}$ and $\lnot QX_{1}(\psi_{i})\cdots\forall X_{k-1}(\psi_{i})\exists X_{k}(\psi_{i})\psi_{i}$ are both valid, where $Q=\forall$ if $k$ is even and $Q=\exists$ otherwise?

We refer to List-Pair-$1$-QBF also by List-Pair-SAT (in the proof of Theorem 5
we swap the roles of $\varphi$ and $\psi$ for the problem List-Pair-SAT as the
reduction is then more natural).

######  Lemma 2.

List-Pair-$k$-QBF is $\mathsf{\Theta}_{k+1}\mathsf{P}$-c.

###### Proof sketch.

We reduce from the canonical $\mathsf{\Theta}_{k+1}\mathsf{P}$-complete
problem LogLexMax-$k$-QBF. An instance is a quantified propositional formula
$\Phi=\exists X_{1}\forall X_{2}\dots QX_{k}\varphi(Y,X_{1}\cdots X_{k})$ with
free variables $Y=y_{1},\dots,y_{m}$ with $m\leq\log|\Phi|$. This is a yes-
instance if $y_{m}$ is true in the lexicographically (the order is given by
the bit vectors $(\alpha(y_{1}),\dots,\alpha(y_{m}))$) maximal model of
$\Phi(Y)$. Let us first consider the case where $k$ is odd.

Let us define for each bitvector $B=(b_{1},\dots,b_{m-1})$)

$\displaystyle\Phi_{B}=$ $\displaystyle\exists Y,X_{1}\forall
X_{2}\dots\exists X_{k}\bigvee_{B^{\prime}\geq(B,1)}Y=B\land\varphi,$
$\displaystyle\Psi_{B}=$ $\displaystyle\exists Y,X_{1}\forall
X_{2}\dots\exists X_{k}\bigvee_{B^{\prime}>(B,1)}Y=B\land\varphi.$

Preserving validity, these can clearly be transformed into formulas $\exists
X_{1}(\varphi_{B})\cdots\forall X_{k-1}(\varphi_{B})\exists
X_{k}(\varphi_{B})\varphi_{B}$ and $\exists X_{1}(\psi_{B})\cdots\forall
X_{k-1}(\psi_{B})\exists X_{k}(\psi_{B})\psi_{B},$ respectively, where
$\varphi_{B}$ and $\psi_{B}$ are in 3-CNF. (In fact,
$X_{i}=X_{i}(\psi_{B})=X_{i}(\varphi_{B})$ for $i\neq 1,k$.) Thus, we reduce
$\Phi$ to the list $(\varphi_{B}(X_{1}(\varphi_{B})\cdots
X_{k}(\varphi_{B})),\psi_{B}(X_{1}(\psi_{B})\cdots X_{k}(\psi_{B})))_{B}$ of
length $2^{m-1}\leq|\Phi|$. Note that $y_{m}$ is true in the lexicographically
maximal model of $\Phi$ if and only if there exists a $B$ such that both
$\Phi_{B}$ and $\lnot\Psi_{B}$ are valid, thus, entailing the correctness of
the reduction.

In the case where $k$ is odd, we proceed as follows. For each bitvector
$B=(b_{1},\dots,b_{m-1})$), we again define

$\displaystyle\Phi_{B}=$ $\displaystyle\exists Y,X_{1}\forall
X_{2}\dots\forall X_{k}\bigvee_{B^{\prime}\geq(B,1)}Y=B\land\varphi,$
$\displaystyle\Psi_{B}=$ $\displaystyle\exists Y,X_{1}\forall
X_{2}\dots\forall X_{k}\bigvee_{B^{\prime}>(B,1)}Y=B\land\varphi.$

Preserving validity, these can clearly be transformed into formulas
$\lnot\forall X_{1}(\varphi_{B})\cdots\forall X_{k-1}(\varphi_{B})\exists
X_{k}(\varphi_{B})\varphi_{B}$ and $\lnot\forall X_{1}(\psi_{B})\cdots\forall
X_{k-1}(\psi_{B})\exists X_{k}(\psi_{B})\psi_{B},$ respectively, where
$\varphi_{B}$ and $\psi_{B}$ are in 3-CNF. Thus, we reduce $\Phi$ to the list
$(\psi_{B}(X_{1}(\psi_{B})\cdots
X_{k}(\psi_{B})),\varphi_{B}(X_{1}(\varphi_{B})\cdots
X_{k}(\varphi_{B})))_{B}$ of length $2^{m-1}\leq|\Phi|$ (the positions of
$\varphi_{B}$ and $\psi_{B}$ have changed). Note that $y_{m}$ is true in the
lexicographically maximal model of $\Phi$ if and only if there exists a $B$
such that both $\lnot\Psi_{B}$ and $\Phi_{B}$ are valid, thus, entailing the
correctness of the reduction. ∎


11institutetext: Kansas State University, Manhattan, KS, USA 22institutetext:
Wright State University, Dayton, OH, USA

# Commonsense Ontology Micropatterns

Andrew Eells  Brandon Dave 11 Pascal Hitzler 22 Cogan Shimizu 1122

###### Abstract

The previously introduced Modular Ontology Modeling methodology (MOMo)
attempts to mimic the human analogical process by using modular patterns to
assemble more complex concepts. To support this, MOMo organizes organizes
ontology design patterns into design libraries, which are programmatically
queryable, to support accelerated ontology development, for both human and
automated processes. However, a major bottleneck to large-scale deployment of
MOMo is the (to-date) limited availability of ready-to-use ontology design
patterns. At the same time, Large Language Models have quickly become a source
of common knowledge and, in some cases, replacing search engines for
questions. In this paper, we thus present a collection of 104 ontology design
patterns representing often occurring nouns, curated from the common-sense
knowledge available in LLMs, organized into a fully-annotated modular ontology
design library ready for use with MOMo.

##  1 Introduction

Humans perform transfer learning through analogous connections in
understanding the unknowns of the world with previously acquired knowledge [6,
7]. In the scope of problem-solving, humans find similarities in their current
problem to draw logical connections that may aid in finding a working
solution, which, regardless of success, becomes part of the learning process
for the next iteration of problem-solving. The task of drawing similarities
requires humans to utilize their logical skills for generalizing a problem or
concept to allow for adaptations from their acquired knowledge.

Neurosymbolic Artificial Intelligence (AI) systems, in their pursuit of
General AI, also seek this ability to conduct transfer and analogy learning.
We posit that the use of modular ontology is one way that this can be
accomplished [11]. In particular, the notion of starting with a simple and
(perhaps) well-understood pattern of knowledge and adapting it to new
scenarios and use-cases; the mechanism by which we accomplish this we call
_modularization_. This overarching methodology is known as Modular Ontology
Modeling (MOMo), and it is by now an established paradigm for constructing
knowledge graphs (KG) and their schemas (i.e., an ontology) [14].

Ontology design patterns, which are tiny ontologies that are intended to solve
domain-invariant modeling problems [5], are the usual starting point for the
MOMo methodology. They may be sourced from many places, including the Ontology
Design Pattern Portal111https://ontologydesignpatterns.org/ or Modular
Ontology Design Libraries (MODLs) [15]. MODLs are annotated, curated
collections of ODPs, combined with an index ontology that can be queried for
patterns of different types and relationships between patterns.

In this paper, we provide such a design library, which we call CS-MODL,
composed of _commonsense micropatterns_. For the purposes of this work, we
define our title.

  * •

commonsense we loosely mean “what first comes to mind.” In this case, we ask
an LLM about common properties of common nouns (as discussed below) and
receive some simple and naïve responses, which are then encoded into:

  * •

micropatterns we contrast micropatterns versus ODPs. In this case,
micropatterns do not have a sophisticated or rich semantics. Indeed, they are
defined using rdfs:domain and rdfs:range, without more complicated OWL axioms.

Concretely, we describe the methodology we used to construct the 104
commonsense micropatterns contained in CS-MODL, discuss an example, and
provide the library as an online resource.

The rest of the paper is organized as follows: Section 2 introduces our
methodologies for obtaining the appropriate information from our chosen LLM
and constructing the commonsense micropatterns. Section 3 provides an example
of a generated commonsense micropattern. Section 4 summarizes the
contributions of our commonsense library of patterns. Section 5 wraps up the
paper with notes on future areas we observe as next steps to this research.

##  2 Methodology

The construction of these commonsense patterns was completed in two steps.
First, we prompt an LLM in several ways (Section 2.3) to produce an ontology
design pattern for each noun in question (Section 2.2). Then, the responses
are consolidated into patterns via a set of heuristics (Section 2.4), and the
patterns are packaged into a MODL (Section 4).

###  2.1 Large Language Models as Commonsense

LLMs, like GPT-4, ingest and learn from more information than any human
possibly could. While it is certainly arguable that any LLM demonstrates
human-level intelligence, it is also inarguable that it can present a
commonsense view of the world – in particular through the a declarative
memory, having learned, perhaps as an accident of learning from “mostly
correct” language, facts about the world [2].

They are able to represent this information and “knowledge” in human-readable
ways with surprising fluency, and as we demonstrate below: frequently in valid
RDF [3]. The following sections describe how we decided on which facts to
extract (i.e., which commonsense notions to prompt), how we prompted for them,
and the resultant collection of patterns.

###  2.2 Noun Selection

The nouns selected are the 101 most common nouns in American English, as
listed in the Corpus of Contemporary American English (COCA) [1]. We
additionally include the nouns “chair”, “sofa”, and “loveseat” from our
preliminary explorations for viability of our idea. All 104 nouns in our
investigation are listed in Figure 1.

  1. 1.

Air

  2. 2.

Area

  3. 3.

Art

  4. 4.

Back

  5. 5.

Body

  6. 6.

Book

  7. 7.

Business

  8. 8.

Car

  9. 9.

Case

  10. 10.

Chair

  11. 11.

Change

  12. 12.

Child

  13. 13.

City

  14. 14.

Community

  15. 15.

Company

  16. 16.

Couch

  17. 17.

Country

  18. 18.

Day

  19. 19.

Door

  20. 20.

Education

  21. 21.

End

  22. 22.

Eye

  23. 23.

Face

  24. 24.

Fact

  25. 25.

Family

  26. 26.

Father

  27. 27.

Force

  28. 28.

Friend

  29. 29.

Game

  30. 30.

Girl

  31. 31.

Government

  32. 32.

Group

  33. 33.

Guy

  34. 34.

Hand

  35. 35.

Head

  36. 36.

Health

  37. 37.

History

  38. 38.

Home

  39. 39.

Hour

  40. 40.

House

  41. 41.

Idea

  42. 42.

Information

  43. 43.

Issue

  44. 44.

Job

  45. 45.

Kid

  46. 46.

Kind

  47. 47.

Law

  48. 48.

Level

  49. 49.

Life

  50. 50.

Line

  51. 51.

Lot

  52. 52.

Loveseat

  53. 53.

Man

  54. 54.

Member

  55. 55.

Minute

  56. 56.

Moment

  57. 57.

Money

  58. 58.

Month

  59. 59.

Morning

  60. 60.

Mother

  61. 61.

Name

  62. 62.

Night

  63. 63.

Number

  64. 64.

Office

  65. 65.

Others

  66. 66.

Parent

  67. 67.

Part

  68. 68.

Party

  69. 69.

People

  70. 70.

Person

  71. 71.

Place

  72. 72.

Point

  73. 73.

Power

  74. 74.

President

  75. 75.

Problem

  76. 76.

Program

  77. 77.

Question

  78. 78.

Reason

  79. 79.

Research

  80. 80.

Result

  81. 81.

Right

  82. 82.

Room

  83. 83.

School

  84. 84.

Service

  85. 85.

Side

  86. 86.

Sofa

  87. 87.

State

  88. 88.

Story

  89. 89.

Student

  90. 90.

Study

  91. 91.

System

  92. 92.

Teacher

  93. 93.

Team

  94. 94.

Thing

  95. 95.

Time

  96. 96.

War

  97. 97.

Water

  98. 98.

Way

  99. 99.

Week

  100. 100.

Woman

  101. 101.

Word

  102. 102.

Work

  103. 103.

World

  104. 104.

Year

Figure 1: The 104 nouns conceptualized into our commonsense micropatterns.

###  2.3 Prompt Engineering

We prompted the LLM222For this work, we used GPT-4-0613. in several different
ways, as we wished to test how it would respond to multiple variants of the
same prompts. The initial prompts were a command (1) and a request (2), and
then variations were added to include the noun as “the following” (3 and 4),
as seen below.

  1. 1.

Generate an ontology that covers [noun].

  2. 2.

Could you develop a basic design pattern for representing [noun] in an
ontology?

  3. 3.

Generate an ontology that covers the following: [noun].

  4. 4.

Could you develop a basic design pattern for representing the following in an
ontology: [noun].

Finally, the LLM was prompted to generate 9 additional variations of each
prompt. See below for Prompt 1’s variations. In each case, the prompt was
tried with and without the additional instruction of “Provide it in valid
Turtle/RDF format, excluding any extra text.” for a total of 20 prompts per
noun.

  1. 1.

Generate an ontology that covers [noun].

  2. 2.

Develop an ontology dedicated to [noun].

  3. 3.

Construct an ontology focused on [noun].

  4. 4.

Build an ontology surrounding the concept of a [noun].

  5. 5.

Formulate an ontology related to [noun].

  6. 6.

Establish an ontology based on [noun].

  7. 7.

Design an ontology to encompass [noun].

  8. 8.

Produce an ontology specifically for [noun].

  9. 9.

Compose an ontology to represent [noun].

  10. 10.

Make an ontology that pertains to [noun].

###  2.4 Response Consolidation

As noted, the LLM generated 80 responses for each of the 104 nouns in our
collection. These responses were stored in a tab-delimited (TSV) file.
However, not every response contained valid RDF and some contained no RDF at
all. The number of responses was too large for manual processing, so we
developed a script that would apply heuristics to each response file in order
to integrate the responses into a single micropattern. The script consists of
three parts, applied to each noun:

  1. 1.

extraction – for each specific prompt response (i.e., a row in the TSV), the
script attempts to identify and extract the portion of the response in RDF.
Unfortunately, not every response output an ODP or easily recognizable RDF.
Generally speaking, cleaning required the removal of extra text (even when
prompted _not_ to provide extra text) and surrounding Markdown formatting
(e.g., code fencing).

  2. 2.

cleaning – a set of heuristics was applied to each extract RDF (generally in
turtle format) to allow for ingestion of the RDF into an
rdflib333https://rdflib.readthedocs.io/en/stable/ graph structure. The most
common type of cleaning necessary was the usage of newline characters. The LLM
understood how to comment (i.e., separating class declarations from properties
from assertions) but did not understand new lines. This frequently resulted in
malformed Turtle, since the first part of the triple would be commented out.

  3. 3.

integration – once each valid (or cleanable) TTL file was extracted from the
response, we combine the properties (removing all triples pertaining to
individuals), and annotate the result, giving us a commonsense micropattern
for the noun. The annotations are further discussed in Section 4.

While we note that we combine all (valid and cleanable) responses into a
single micropattern, the script is set up in a much more flexible way.

First, it is necessary to recall that the process by which ODPs are utilized
in the MOMo process is based on customization to the use-case at hand; that is
properties are frequently removed, added, or renamed for best fit. This
process is known as _template-based instantiation_ [8], and it is a core
aspect of the methodology. Specifically, each property with (explicit or
inferred) domain and range, is assessed for fit. If it is not applicable
(i.e., out of scope or too specific or general), the property and associated
sub-graphs are removed. Conversely, if there are parts of the use-case that
are not covered by the ODP, these must be added. In automated processes, it is
generally easier to pare down an overly superfluous pattern. That is, if there
are no matches or fillers for the slots that a pattern provides, they should
be dropped. We follow this strategy for our micropatterns, meaning that we
include each property from every response, which includes variants of the same
property. For example, in Figure 2, which shows a schema diagram of a
commonsense micropattern for Air, hasHumidity has a range of both Humidity and
xsd:float. It is conceivable that one or the other is unnecessary, or that
they may be used in tandem (i.e., where a connection from Humidity is made to
the xsd:string), e.g., as a type of shortcut or view [13, 17].

Yet, this strategy may not be applicable for all systems. As such, the script
allows for a voting mechanism to take place. This might be useful if
additional prompt variants are used or if multiple LLMs are prompted for ODPs,
thus allowing for properties (with domains and ranges) that appear in multiple
patterns from multiple sources are those that appear in the final
micropattern. The voting mechanism is as follows.

For the usable response, we extracted 3-tuples expressing Properties
associated with a noun, and the Property’s respective described scoped domain
and range. This process also included the notion of a voting process, which
would decide the final noun pattern’s implemented properties based on
occurrence per generated noun ontology. Our noun ontologies ended up with
limited duplicate occurrences of the same triplets (s, p, o) (ranging from 1
to 4 total occurrences), and so, we chose not to implement the voting process
and a threshold to implement properties to the final noun pattern. This allows
us to maximally express the noun’s ontology as stripping the ontology down
would be an easier task than building around a concept.

Finally, when generating the micropattern, we minimally describe the
properties and classes. That is, we use only rdfs:Class, rdfs:subClassOf,
rdfs:range, and rdfs:domain. The script, however, is designed in such a way to
be easily modifiable to improve the semantic expressivity of the patterns. For
example, we could use a simple heuristics, plus a set of axiom patterns (i.e.,
taken from [4]), to assert the most common types of constraints for a
particular property.

##  3 Example Pattern

Figure 2: A graphical schema diagram of the Air ontology

We have selected a pattern, Air, which exemplifies many interesting properties
of our commonsense micropatterns. The schema diagram for this micropattern is
shown in Figure 2. The gold boxes reflect classes. The yellow ellipses
indicate datatypes. Black filled arrows are binary relations. When labels
overlap multiple arrows, we use this to show that there are multiple ranges
for the property.

As noted in Section 2.4, there are some reuse of property names (e.g.,
hasHumidity) that would technically be not allowed in OWL. However, we suggest
that _pruning_ is easier than growing, so a system that utilizes CS-MODL can
simply remove the unused property, as necessary.

The turtle file for this example can be found in the repository.

###  3.1 License & Availability

Our artifacts are made available online through a GitHub
repository.444https://github.com/kastle-lab/commonsense-micropatterns/ All
data (which includes documentation, prompts, responses, extracted and cleaned
TTL files, integrated patterns, and CS-MODL itself) and the supporting scripts
that generated the data are provided under an open and permissive license (GNU
Lesser General Public License v2.1), and it is also included explicitly in the
repository.

##  4 A Commonsense Modular Ontology Design Library

The purpose of a MODL is to collect together (curate) a set of ontology design
patterns. In the first version [15], these were generally well-documented and
useful patterns. A forthcoming second version has many more, spanning a wider
set of application scenarios.555https://github.com/kastle-lab/modular-
ontology-design-library This particular MODL, CS-MODL, is similar insofar that
it also satisfies broad use-cases. The purpose of which is to collect together
patterns of similar quality, abstraction, and expressivity for the purpose of
modeling commonly occurring entities (e.g., in informal language or the real
world).

The CS-MODL, like other MODLs, is programmatically queryable through OPaL
annotations [10, 9] indicating that CS-MODL contains sufficient metadata
scaffolding such that top-level conceptual components (i.e., the key notion)
of patterns can be easily matched to external entities detected by a
framework.666We note that we are trying to have a better acronym – OPaL –
instead of the previously published acronym! For example, if a vision
interpreter finds something with four legs, it could match to the Chair
pattern. Inversely, if a chair is detected, _most_ chairs have four legs, and
this can be inferred from the matched pattern. This matching process can also
be used for inferring _behaviors_ or _functionalities_ of said items, which is
even more applicable to this use case.

##  5 Conclusion

Large language models have quickly become a source of commonsense information,
in some cases supplanting search engine use. This easily available source of
knowledge can enhance transfer and analogy learning, especially in combination
with knowledge engineering methodologies (such as modular ontology modeling).

In this paper, we have described our methodology for obtaining 104 commonsense
micropatterns from an LLM. This process is generalizable from our chosen list,
and the code to produce additional patterns is available online and
permissibly licensed. These patterns are organized into a modular ontology
design library (MODL), which we call CS-MODL, also available in the same
repository. CS-MODL can facilitate the construction of internal knowledge
frameworks of automated systems through specializing or generalizing from the
commonsenese micropatterns.

### Future Work

We have identified some areas for future enhancement.

  1. 1.

The list of nouns that we utilized to seed our prompts for patterns is naïve.
That is, no effort was put into organizing them into a subsumption hierarchy
or otherwise identifying unifying concepts. Creating both this hierarchy, as
well as examining similar hierarchies for relations between these concepts, is
an immediate next step. Additionally, these relations can be encoded in the
CS-MODL index allowing for substantially more sophisticated pattern
identification.

  2. 2.

We will evaluate the use of CS-MODL in a more principled way (i.e., through
use in a case study) pertaining to ontology learning from text, and in a
multi-agent teaming, visual sensor fusion exercise.

  3. 3.

Describe the patterns more expressively (i.e., fully describe the patterns in
OWL instead of only using RDFS).

  4. 4.

Improved documentation: schema diagrams, summaries, and explanation of the
formalization (i.e., in the style of [16] and [12]) will be explored.

_Acknowledgement._ The authors acknowledge partial funding by the National
Science Foundation under grant 2333532 ”Proto-OKN Theme 3: An Education
Gateway for the Proto-OKN.”

## References

  * [1] English-Corpora: COCA, https://www.english-corpora.org/coca/
  * [2] Cohen, R., Geva, M., Berant, J., Globerson, A.: Crawling the internal knowledge-base of language models (2023)
  * [3] Cyganiak, R., Wood, D., Lanthaler, M. (eds.): RDF 1.1 Concepts and Abstract Syntax. W3C Recommendation 25 February 2014 (2014), available from http://www.w3.org/TR/rdf11-concepts/
  * [4] Eberhart, A., Shimizu, C., Chowdhury, S., Sarker, M.K., Hitzler, P.: Expressibility of OWL axioms with patterns. In: Verborgh, R., Hose, K., Paulheim, H., Champin, P., Maleshkova, M., Corcho, Ó., Ristoski, P., Alam, M. (eds.) The Semantic Web - 18th International Conference, ESWC 2021, Virtual Event, June 6-10, 2021, Proceedings. Lecture Notes in Computer Science, vol. 12731, pp. 230–245. Springer (2021). https://doi.org/10.1007/978-3-030-77385-4_14, https://doi.org/10.1007/978-3-030-77385-4_14
  * [5] Gangemi, A., Presutti, V.: Ontology design patterns. In: Staab, S., Studer, R. (eds.) Handbook on Ontologies, pp. 221–243. International Handbooks on Information Systems, Springer (2009). https://doi.org/10.1007/978-3-540-92673-3_10, https://doi.org/10.1007/978-3-540-92673-3_10
  * [6] Gentner, D., Smith, L.: Analogical reasoning. In: Ramachandran, V. (ed.) Encyclopedia of Human Behavior (Second Edition), pp. 130–136. Academic Press, San Diego, second edition edn. (2012). https://doi.org/https://doi.org/10.1016/B978-0-12-375000-6.00022-7, https://www.sciencedirect.com/science/article/pii/B9780123750006000227
  * [7] Gentner, D., Smith, L.A.: Analogical learning and reasoning., pp. 668–681. Oxford library of psychology., Oxford University Press, New York, NY, US (2013). https://doi.org/10.1093/oxfordhb/9780195376746.001.0001, https://doi.org/10.1093/oxfordhb/9780195376746.001.0001
  * [8] Hammar, K., Presutti, V.: Template-based content ODP instantiation. In: Hammar, K., Hitzler, P., Krisnadhi, A., Lawrynowicz, A., Nuzzolese, A.G., Solanki, M. (eds.) Advances in Ontology Design and Patterns [revised and extended versions of the papers presented at the 7th edition of the Workshop on Ontology and Semantic Web Patterns, WOP@ISWC 2016, Kobe, Japan, 18th October 2016]. Studies on the Semantic Web, vol. 32, pp. 1–13. IOS Press (2016). https://doi.org/10.3233/978-1-61499-826-6-1, https://doi.org/10.3233/978-1-61499-826-6-1
  * [9] Hirt, Q., Shimizu, C., Hitzler, P.: Extensions to the ontology design pattern representation language. In: Janowicz, K., Krisnadhi, A.A., Poveda-Villalón, M., Hammar, K., Shimizu, C. (eds.) Proceedings of the 10th Workshop on Ontology Design and Patterns (WOP 2019) co-located with 18th International Semantic Web Conference (ISWC 2019), Auckland, New Zealand, October 27, 2019. CEUR Workshop Proceedings, vol. 2459, pp. 76–75. CEUR-WS.org (2019), http://ceur-ws.org/Vol-2459/short2.pdf
  * [10] Hitzler, P., Gangemi, A., Janowicz, K., Krisnadhi, A.A., Presutti, V.: Towards a simple but useful ontology design pattern representation language. In: Blomqvist, E., Corcho, Ó., Horridge, M., Carral, D., Hoekstra, R. (eds.) Proceedings of the 8th Workshop on Ontology Design and Patterns (WOP 2017) co-located with the 16th International Semantic Web Conference (ISWC 2017), Vienna, Austria, October 21, 2017. CEUR Workshop Proceedings, vol. 2043. CEUR-WS.org (2017), http://ceur-ws.org/Vol-2043/paper-09.pdf
  * [11] Hitzler, P., Shimizu, C.: Modular ontologies as a bridge between human conceptualization and data. In: Chapman, P., Endres, D., Pernelle, N. (eds.) Graph-Based Representation and Reasoning - 23rd International Conference on Conceptual Structures, ICCS 2018, Edinburgh, UK, June 20-22, 2018, Proceedings. Lecture Notes in Computer Science, vol. 10872, pp. 3–6. Springer (2018). https://doi.org/10.1007/978-3-319-91379-7_1, https://doi.org/10.1007/978-3-319-91379-7_1
  * [12] Karima, N., Hammar, K., Hitzler, P.: How to document ontology design patterns. In: Hammar, K., Hitzler, P., Lawrynowicz, A., Krisnadhi, A., Nuzzolese, A., Solanki, M. (eds.) Advances in Ontology Design and Patterns, Studies on the Semantic Web, vol. 32, pp. 15–28. IOS Press, Amsterdam (2017)
  * [13] Krisnadhi, A.A., Hitzler, P., Janowicz, K.: On the capabilities and limitations of OWL regarding typecasting and ontology design pattern views. In: Tamma, V.A.M., Dragoni, M., Gonçalves, R.S., Lawrynowicz, A. (eds.) Ontology Engineering - 12th International Experiences and Directions Workshop on OWL, OWLED 2015, co-located with ISWC 2015, Bethlehem, PA, USA, October 9-10, 2015, Revised Selected Papers. Lecture Notes in Computer Science, vol. 9557, pp. 105–116. Springer (2015). https://doi.org/10.1007/978-3-319-33245-1_11, https://doi.org/10.1007/978-3-319-33245-1_11
  * [14] Shimizu, C., Hammar, K., Hitzler, P.: Modular ontology modeling. Semantic Web 14(3), 459–489 (2023). https://doi.org/10.3233/SW-222886, https://doi.org/10.3233/SW-222886
  * [15] Shimizu, C., Hirt, Q., Hitzler, P.: MODL: A modular ontology design library. In: Janowicz, K., Krisnadhi, A.A., Poveda-Villalón, M., Hammar, K., Shimizu, C. (eds.) Proceedings of the 10th Workshop on Ontology Design and Patterns (WOP 2019) co-located with 18th International Semantic Web Conference (ISWC 2019), Auckland, New Zealand, October 27, 2019. CEUR Workshop Proceedings, vol. 2459, pp. 47–58. CEUR-WS.org (2019), http://ceur-ws.org/Vol-2459/paper4.pdf
  * [16] Shimizu, C., Hitzler, P., Hirt, Q., Rehberger, D., Estrecha, S.G., Foley, C., Sheill, A.M., Hawthorne, W., Mixter, J., Watrall, E., Carty, R., Tarr, D.: The enslaved ontology: Peoples of the historic slave trade. J. Web Semant. 63, 100567 (2020). https://doi.org/10.1016/J.WEBSEM.2020.100567, https://doi.org/10.1016/j.websem.2020.100567
  * [17] Shimizu, C., Stephen, S., Christou, A., Currier, K., Mahdavinejad, M.S., Norouzi, S.S., Dalal, A., Barua, A., Fisher, C.K., D’Onofrio, A., Thelen, T., Janowicz, K., Rehberger, D., Schildhauer, M., Hitzler, P.: Knowwheregraph-lite: A perspective of the knowwheregraph. In: Ortiz-Rodríguez, F., Villazón-Terrazas, B., Tiwari, S., Bobed, C. (eds.) Knowledge Graphs and Semantic Web - 5th Iberoamerican Conference and 4th Indo-American Conference, KGSWC 2023, Zaragoza, Spain, November 13-15, 2023, Proceedings. Lecture Notes in Computer Science, vol. 14382, pp. 199–212. Springer (2023). https://doi.org/10.1007/978-3-031-47745-4_15, https://doi.org/10.1007/978-3-031-47745-4_15