From Figure 7 it appears that the error rate grows sub-linearly with regret.
Note that the relevant scale for the regret is the difference in expected
utility between the two decisions, hence we plot the normalised regret bound
where we divide $\delta$ by this expected utility difference. Note that even
for relatively large regret bounds, representing agents that generalise
weakly, we can still identify the causal structure with a high accuracy. For
example when the regret bound is 30% of the expected utility difference, we
can still identify the correct causal structure in $\sim 90\%$ of the randomly
generated CIDs. This describes an agent that is guaranteed to incur a regret
of at most $30\%$ of the expected utility difference between the decisions
before the domain shift. If the domain shift results in the expected utility
difference being less that $30\%$ of the unshifted expected utility
difference, the agent can return a sub-optimal decision.

Algorithm 2 Graph Learner for simple CID

1:function graph learner($\Pi^{\delta}_{\Sigma}$, $U$, $\delta$, $N$)

2: $d_{1},d_{2},x^{\prime},y^{\prime},q_{\text{crit}}\leftarrow\text{Algorithm
1}(U,\Pi^{\delta}_{\Sigma},N,\sigma_{1}=\textrm{do}(Y=0))$ $\triangleright$
Identify $q_{\text{crit}}$ for $\textrm{do}(Y=0)$

3: Exp. U difference
$=(U(d_{2},x^{\prime},y^{\prime})-U(d_{1},x^{\prime},y^{\prime}))*(1-1/q_{\text{crit}})$

4: $\Delta_{0}=U(0,0,d_{2})-U(0,0,d_{1})$

5: $\Delta_{1}=U(1,0,d_{2})-U(1,0,d_{1})$

6: $P(X_{Y=0}=0)=(\text{Exp. U
difference}-\Delta_{1})/(\Delta_{0}-\Delta_{1})$

7:

8: $d_{1},d_{2},x^{\prime},y^{\prime},q_{\text{crit}}\leftarrow\text{Algorithm
1}(U,\Pi^{\delta}_{\Sigma},N,\sigma_{1}=\textrm{do}(Y=1))$ $\triangleright$
Identify $q_{\text{crit}}$ for $\textrm{do}(Y=1)$

9: Exp. U difference
$=(U(d_{2},x^{\prime},y^{\prime})-U(d_{1},x^{\prime},y^{\prime}))*(1-1/q_{\text{crit}})$

10: $\Delta_{0}=U(0,1,d_{2})-U(0,1,d_{1})$

11: $\Delta_{1}=U(1,1,d_{2})-U(1,1,d_{1})$

12: $P(X_{Y=1}=0)=(\text{Exp. U
difference}-\Delta_{1})/(\Delta_{0}-\Delta_{1})$

13:

14:
$d_{1},d_{2},x^{\prime},y^{\prime},q_{\text{crit}}\leftarrow\text{Algorithm
1}(U,\Pi^{\delta}_{\Sigma},N,\sigma_{1}=\textrm{do}(X=0))$ $\triangleright$
Identify $q_{\text{crit}}$ for $\textrm{do}(X=0)$

15: Exp. U difference
$=(U(d_{2},x^{\prime},y^{\prime})-U(d_{1},x^{\prime},y^{\prime}))*(1-1/q_{\text{crit}})$

16: $\Delta_{0}=U(0,0,d_{2})-U(0,0,d_{1})$

17: $\Delta_{1}=U(0,1,d_{2})-U(0,1,d_{1})$

18: $P(Y_{X=0}=0)=(\text{Exp. U
difference}-\Delta_{1})/(\Delta_{0}-\Delta_{1})$

19:

20:
$d_{1},d_{2},x^{\prime},y^{\prime},q_{\text{crit}}\leftarrow\text{Algorithm
1}(U,\Pi^{\delta}_{\Sigma},N,\sigma_{1}=\textrm{do}(X=1))$ $\triangleright$
Identify $q_{\text{crit}}$ for $\textrm{do}(X=1)$

21: Exp. U difference
$=(U(d_{2},x^{\prime},y^{\prime})-U(d_{1},x^{\prime},y^{\prime}))*(1-1/q_{\text{crit}})$

22: $\Delta_{0}=U(1,0,d_{2})-U(1,0,d_{1})$

23: $\Delta_{1}=U(1,1,d_{2})-U(1,1,d_{1})$

24: $P(Y_{X=1}=0)=(\text{Exp. U
difference}-\Delta_{1})/(\Delta_{0}-\Delta_{1})$

25:

26: if $P(Y_{X=0}=0)=P(Y_{X=1}=0)$ then $\triangleright$ Identify $G$ and $P$
from interventionals

27: if $P(X_{Y=0}=0)=P(X_{Y=1}=0)$ then

28: $G\leftarrow()$

29: $P(x,y)=P(X_{Y=0}=x)P(Y_{X=0}=y)$

30: else

31: $G\leftarrow(Y\rightarrow X)$

32: $P(x,y)=P(Y_{X=0}=y)P(X_{Y=y}=x)$

33: end if

34: else

35: $G\leftarrow(X\rightarrow Y)$

36: $P(x,y)=P(X_{Y=0}=x)P(Y_{X=x}=y)$

37: end if

38: return $G,P(x,y)$

39:end function

##  Appendix G Appendix: transportability & Pearl’s causal hierarchy

#### Transportability.

The problem of evaluating policies under distributional shifts has been
studied extensively in transportability theory (Pearl & Bareinboim, 2011;
Bareinboim & Pearl, 2016; Bellot & Bareinboim, 2022). For decision tasks as
outlined in Section 2.2, transportability aims to provide necessary and
sufficient conditions for identifying the expected utility following a
distributional shift, $R=\mathbb{E}[u\mid d,\textbf{pa}_{D};\sigma]$, given
(partial) knowledge of i) the joint $P$, causal graph $G$ and interventional
distributions $I$ in the source domain, and ii) (partial) knowledge of the
joint $P^{*}$ and causal graph $G^{*}$ in the target domain (Pearl &
Bareinboim, 2011; Bareinboim & Pearl, 2012b). Hence, these results differ from
Theorems 1 and 2 in that they restrict to the case where all assumptions on
the data generating process (i.e. inductive biases) can be expressed as
(partial) knowledge of the underlying CBN. For example, Bareinboim & Pearl
(2016) claim the problem is essentially solved in the case where ‘assumptions
are expressible in DAG form’. This does not constrain possible approaches to
domain generalisation that make use of non-causal assumptions and
heuristics444Indeed, notable examples of causal assumptions that go beyond
those expressible in DAG form include restricting the classes of structural
equations Mooij et al. (2016) and assuming cause-effect asymmetry (Mitrovic et
al., 2018), and indeed deep learning algorithms exploit a much wider set of
inductive biases than causal assumptions alone (Neyshabur et al., 2014;
Battaglia et al., 2018; Rahaman et al., 2019; Goyal & Bengio, 2022; Cohen &
Welling, 2016). In many real-world tasks these may be sufficient to identify
‘good enough’ (i.e. regret-bounded) policies without requiring knowledge of
the causal structure of the data generating process. Our aim has been to
establish if learning causal models is necessary for domain generalisation in
general. Hence assuming that agents are restricted to using inductive biases
that amount to (partial) knowledge of the underlying CBN would be begging the
question.

#### Causal hierarchy’s theorem (CHT).

The celebrated causal hierarchy theorem (Bareinboim et al., 2022; Ibeling &
Icard, 2021) shows that for almost all environments there are causal relations
between environment variables that cannot be identified from observational
data without additional assumptions. Does this imply that a causal model is
necessary for identifying optimal policies?

First, note that the CHT is an insufficiency result, and only implies trivial
necessity results. For example, is a causal model necessary for identifying
all causal and associative relations between environment variables? Yes, but
only because this set of observational and interventional distributions is a
causal model. Formally, we can identify the underlying causal model (up to
latent confounders) by assuming causal faithfulness, which holds for almost
all causal models (Meek, 2013). The difference here is that the CHT is
concerned with the identifiability of all causal and associative relations
between environment variables. This sets a much higher bar than domain
generalisation, which focuses on identifying a strict subset of these (regret-
bounded policies) (Figure 3).

Secondly, the CHT is concerned with the collapse (or lack thereof) of the
causal hierarchy. For example, that observational data is insufficient for
identifying all causal queries. We do not restrict agents to having
observational training data—in fact, typically we assume that agents have
access to both observational and interventional data in the online learning
setting that we consider (e.g. agents can intervene to fix the decision node
$D$ by assumption).

Finally, we can imagine a refinement of the CHT which states that
observational data is insufficient for identifying regret-bounded policies
without additional assumptions, bringing it in line with Theorems 1 and 2. If
this was implied by the CHT, it would not imply our results unless we restrict
to the case where all assumptions as constraints on the causal structure
(similar to transportability). Likewise, it is simple to show that Theorem 1
does not imply the CHT. In deriving Theorem 1 we do not restrict to
observational distributions (or make any restrictions on the data available to
the agent when generating its policy).


# Reduced clique graphs: a correction to “Chordal graphs and their clique
graphs”

Dillon Mayhew  and  Andrew Probert

###### Abstract.

Galinier, Habib, and Paul introduced the reduced clique graph of a chordal
graph $G$. The nodes of the reduced clique graph are the maximal cliques of
$G$, and two nodes are joined by an edge if and only if they form a non-
disjoint separating pair of cliques in $G$. In this case the weight of the
edge is the size of the intersection of the two cliques. A clique tree of $G$
is a tree with the maximal cliques of $G$ as its nodes, where for any $v\in
V(G)$, the subgraph induced by the nodes containing $v$ is connected. Galinier
et al. prove that a spanning tree of the reduced clique graph is a clique tree
if and only if it has maximum weight, but their proof contains an error. We
explain and correct this error.

In addition, we initiate a study of the structure of reduced clique graphs by
proving that they cannot contain any induced cycle of length five (although
they may contain induced cycles of length three, four, or six). We show that
no cycle of length four or more is isomorphic to a reduced clique graph. We
prove that the class of clique graphs of chordal graphs is not comparable to
the class of reduced clique graphs of chordal graphs by providing examples
that are in each of these classes without being in the other.

##  1\. Introduction

We consider only simple graphs. A _chord_ of a cycle is an edge that joins two
vertices of the cycle without being in the cycle itself. A graph is _chordal_
if any cycle with at least four vertices has a chord. A _clique_ is a set of
pairwise adjacent vertices. If $S$ is a set of vertices and $P$ is a path,
then $P$ is _$S$ -avoiding_ if no internal vertex of $P$ is in $S$. Assuming
that $a$ and $b$ are distinct vertices, an _$ab$ -separator_ is a set $S$ of
vertices not containing either $a$ or $b$ such that there is no $S$-avoiding
path from $a$ to $b$. If, in addition, $S$ does not properly contain an
$ab$-separator then it is a _minimal $ab$-separator_.

If $G$ is a chordal graph, then $C(G)$ is the corresponding _clique graph_
(also known as the _clique intersection graph_). The vertices of $C(G)$ are
the maximal cliques of $G$, and two maximal cliques are adjacent in $C(G)$ if
and only if they have a non-empty intersection. The vertices of the _reduced
clique graph_ , $C_{R}(G)$, are again the maximal cliques of $G$, but $C$ and
$C^{\prime}$ are adjacent in $C_{R}(G)$ if and only if $C\cap
C^{\prime}\neq\emptyset$ and $C$ and $C^{\prime}$ form a _separating pair_ :
that is, there is no $(C\cap C^{\prime})$-avoiding path from a vertex in
$C-C^{\prime}$ to a vertex in $C^{\prime}-C$. Note that the vertices of
$C_{R}(G)$ are identical to the vertices of $C(G)$, and every edge of
$C_{R}(G)$ is an edge of $C(G)$.

Figure 1. A chordal graph, its clique graph, and its reduced clique graph.

The reduced clique graph was introduced in [GHP95] (where it is called a
clique graph) and studied further in [HS12, HL09, MUU10, McK11].

Let $G$ be a graph, and let $T$ be a tree whose vertices are the maximal
cliques of $G$. If, for every $v\in V(G)$, the maximal cliques of $G$ that
contain $v$ induce a subtree of $T$, then $T$ is a _clique tree_. Clique trees
were introduced by Gavril [Gavril], who proved that a graph has a clique tree
exactly when it is chordal.

We weight each edge of $C_{R}(G)$ as follows: the edge joining cliques $C$ and
$C^{\prime}$ is weighted with $|C\cap C^{\prime}|$. The following result is
[GHP95]*Theorem 6.

######  Theorem 1.1.

Let $G$ be a connected chordal graph. Let $T$ be a spanning tree of
$C_{R}(G)$. Then $T$ is a clique tree if and only if it is a maximum-weight
spanning tree.

Although the statement of Theorem 1.1 is correct, the proof in [GHP95]*Theorem
6 is not. The issue arises in the proof that a maximum-weight spanning tree
must be a clique tree. We illustrate the error by using the same argument to
prove a false statement.

######  Non-theorem 1.2.

Let $G$ be a chordal graph. Let $C_{0},C_{1},\ldots,C_{n}$ be the sequence of
maximal cliques in a path of $C_{R}(G)$ where $n>1$. Assume that there is a
vertex $v$ of $G$ such that $v$ is in $C_{0}\cap C_{n}$, but in none of the
cliques $C_{1},\ldots,C_{n-1}$. Then $C_{0}$ and $C_{n}$ are adjacent in
$C_{R}(G)$.

###### Non-proof.

Consider the subgraph $G^{\prime}$ of $G$ induced by $C_{0}\cup
C_{1}\cup\cdots\cup C_{n}$. Thus $G^{\prime}$ is chordal. From
[Rose]*Corollary 2 we see that either $v$ is a _simplicial vertex_ (meaning
that the neighbours of $v$ in $G^{\prime}$ form a clique), or there is a pair,
$a$, $b$, of vertices such that $v$ belongs to a minimal $ab$-separator of
$G^{\prime}$. In the former case $v$ is in a unique maximal clique of
$G^{\prime}$ ([BP93]*Theorem 3.1). But $C_{0}$ and $C_{n}$ are distinct
maximal cliques of $G^{\prime}$ that contain $v$. Therefore we can let $S$ be
a minimal $ab$-separator of $G^{\prime}$, where $v$ is in $S$. The proof of
[Buneman]*Lemma 2.3 shows that there are two distinct maximal cliques, $D_{a}$
and $D_{b}$, of $G^{\prime}$ such that $D_{a}$ and $D_{b}$ properly contain
$S$, and $D_{a}-S$ is in the same connected component of $G^{\prime}-S$ as
$a$, while $D_{b}-S$ is in the same component as $b$. Thus $D_{a}$ and $D_{b}$
are maximal cliques of $G^{\prime}$ that contain $v$. But the only maximal
cliques of $G^{\prime}$ that contain $v$ are $C_{0}$ and $C_{n}$. Therefore we
can assume without loss of generality that $D_{a}=C_{0}$ and $D_{b}=C_{n}$.
Any path from a vertex of $C_{0}-C_{n}$ to a vertex of $C_{n}-C_{0}$ must
contain a vertex in $S=C_{0}\cap C_{n}$. Therefore $C_{0}$ and $C_{n}$ form a
non-disjoint separating pair, so $C_{0}$ and $C_{n}$ are adjacent in
$C_{R}(G)$, as claimed. ∎

We can see that this non-theorem is, indeed, not a theorem by examining Figure
1. Set $C_{0}$, $C_{1}$, and $C_{2}$ to be the maximal cliques
$\\{2,3,4,6,8,9\\}$, $\\{1,2,3\\}$, and $\\{2,3,5,7,8,9\\}$, respectively.
Thus $C_{0},C_{1},C_{2}$ is the vertex sequence of a path in $C_{R}(G)$. The
vertex $8$ is in $C_{0}\cap C_{2}$, but not in $C_{1}$. However $C_{0}$ and
$C_{2}$ are not adjacent in $C_{R}(G)$. The error in the “proof” lies in the
claim that “the only maximal cliques of $G^{\prime}$ that contain $v$ are
$C_{0}$ and $C_{n}$”. This need not be true. Indeed, $\\{2,3,4,5,8,9\\}$ is a
maximal clique in the subgraph induced by $C_{0}\cup C_{1}\cup C_{2}$, and it
contains $8$, but it is not equal to either $C_{0}$ or $C_{2}$. Exactly the
same error appears in the proof of [GHP95]*Theorem 6. Nonetheless, Theorem 1.1
is true, and we prove it in the next section.

##  2\. Reduced clique graphs and clique trees

In [matroidpaper] we will apply our main theorem to some matroid problems. For
these purposes we would like to extend its scope somewhat. Instead of
weighting the edges of $C_{R}(G)$ with sizes of intersections, we consider
more general weightings.

######  Definition 2.1.

Let $G$ be a chordal graph. We consider a function $\sigma$ which takes

$\\{\emptyset\\}\cup\\{C\cap C^{\prime}\colon C,C\ \text{are distinct maximal
cliques of}\ G\\}$

to non-negative integers. We insist that $\sigma(\emptyset)=0$ and if $X$ and
$X^{\prime}$ are in the domain of $\sigma$ and $X\subset X^{\prime}$, then
$\sigma(X)<\sigma(X^{\prime})$. In such a case the function $\sigma$ is a
_legitimate weighting_ of $G$.

######  Theorem 2.2.

Let $G$ be a connected chordal graph and let $\sigma$ be a legitimate
weighting of $G$. Every clique tree is a spanning tree of $C_{R}(G)$ and every
edge of $C_{R}(G)$ is contained in a clique tree. Moreover, a spanning tree of
$C_{R}(G)$ is a clique tree if and only if it has maximum weight amongst all
spanning trees.

Note that the function that takes each intersection $C\cap C^{\prime}$ to
$|C\cap C^{\prime}|$ is a legitimate weighting, so Theorem 2.2 does indeed
imply Theorem 1.1. We now start proving the intermediate results required for
the proof of Theorem 2.2.

######  Proposition 2.3.

Let $G$ be a chordal graph, and let $C$ and $C^{\prime}$ be maximal cliques of
$G$. Let $S$ be a set of vertices that contains $C\cap C^{\prime}$. Let
$v_{0},v_{1},\ldots,v_{k}$ be the vertex sequence of $P$, a shortest-possible
$S$-avoiding path from a vertex in $C-C^{\prime}$ to a vertex in
$C^{\prime}-C$. Then $(C\cap C^{\prime})\cup\\{v_{i},v_{i+1}\\}$ is a clique
for each $i=0,1,\ldots,k-1$.

###### Proof.

If $C\cap C^{\prime}=\emptyset$ then the result holds trivially, so we assume
$C\cap C^{\prime}$ is non-empty. Note that every vertex in $C\cap C^{\prime}$
is adjacent to $v_{0}$, and also to $v_{k}$, since these vertices are in
$C-C^{\prime}$ and $C^{\prime}-C$. Now the result can only fail if there is a
vertex $x\in C\cap C^{\prime}$ that is not adjacent to $v_{i}$ for some
$i\in\\{1,\ldots,k-1\\}$. Let $p$ be the largest integer such that $p<i$ and
$x$ is adjacent to $v_{p}$. Similarly, let $q$ be the smallest integer such
that $q>i$ and $x$ is adjacent to $v_{q}$. Consider the cycle obtained by
adding the edges $v_{p}x$ and $v_{q}x$ to $v_{p},v_{p+1},\ldots,v_{q}$. This
cycle contains the distinct vertices $v_{p}$, $v_{i}$, $v_{q}$, and $x$, so it
must contain a chord. No chord can join two vertices in the path $P$, since
$P$ is as short as possible. Thus any chord is incident with $x$. But $x$ is
not adjacent to any of the vertices in $v_{p+1},\ldots,v_{q-1}$ by the choice
of $p$ and $q$, so we have a contradiction. ∎

######  Proposition 2.4.

Let $G$ be a chordal graph, and let $C$ and $C^{\prime}$ be maximal cliques of
$G$ where $C\cap C^{\prime}\neq\emptyset$. If $C$ and $C^{\prime}$ are not
adjacent in $C_{R}(G)$, then they are joined by a path of $C_{R}(G)$ with
vertex sequence $C_{0},C_{1},\ldots,C_{s}$, where each $C_{i}\cap C_{i+1}$
properly contains $C\cap C^{\prime}$.

###### Proof.

Assume this fails for $C$ and $C^{\prime}$, and they have been chosen so that
$C\cap C^{\prime}$ is as large as possible. Let $S$ be $C\cap C^{\prime}$.
Because $C$ and $C^{\prime}$ are not adjacent in $C_{R}(G)$, but
$S\neq\emptyset$, it follows that there is an $S$-avoiding path from a vertex
in $C-C^{\prime}$ to a vertex in $C^{\prime}-C$. Let
$v_{0},v_{1},\ldots,v_{k}$ be the vertex sequence of such a path, where $k$ is
as small as possible. We assume $v_{0}$ is in $C-C^{\prime}$ while $v_{k}$ is
in $C^{\prime}-C$. We apply Proposition 2.3 and for each $i=1,\ldots,k$, we
let $D_{i}$ be a maximal clique of $G$ that contains
$S\cup\\{v_{i-1},v_{i}\\}$. Set $D_{0}$ to be $C$ and set $D_{k+1}$ to be
$C^{\prime}$. Note that $D_{i}\neq D_{j}$ when $i<j$, because $v_{i-1}$ is not
adjacent to $v_{j}$. For each $i=0,1,\ldots,k$, the intersection of $D_{i}$
and $D_{i+1}$ contains $S$ as well as $v_{i}$. If $D_{i}$ and $D_{i+1}$ are
adjacent in $C_{R}(G)$ then we let $P_{i}$ be the path of $C_{R}(G)$
consisting of $D_{i}$, $D_{i+1}$, and the edge between them. Otherwise $D_{i}$
and $D_{i+1}$ are not adjacent in $C_{R}(G)$ and the assumption on the
cardinality of $S$ means that there is a path $P_{i}$ of $C_{R}(G)$ from
$D_{i}$ to $D_{i+1}$ such that every intersection of consecutive cliques in
$P_{i}$ properly contains $S\cup v_{i}$. We concatenate the paths
$P_{0},P_{1},\ldots,P_{k}$ and obtain a walk of $C_{R}(G)$ from $C$ to
$C^{\prime}$. The intersection of any two consecutive cliques in this walk
properly contains $S$. It follows that there is a path of $C_{R}(G)$ from $C$
to $C^{\prime}$ with exactly the same property, and now $C$ and $C^{\prime}$
fail to provide a counterexample after all. ∎

Figure 2 illustrates Proposition 2.4. The intersection of cliques
$C=\\{1,2,3\\}$ and $C^{\prime}=\\{3,5,7,8\\}$ is $\\{3\\}\neq\emptyset$, but
$C$ and $C^{\prime}$ are not adjacent in $C_{R}(G)$. However, there is a path
between $C$ and $C^{\prime}$ in $C_{R}(G)$, and the intersection of any
consecutive two cliques in the path properly contains $\\{3\\}$.

Figure 2.

######  Proposition 2.5.

Let $G$ be a connected chordal graph. Let $T$ be a clique tree of $G$. Assume
that $C$ and $C^{\prime}$ are maximal cliques of $G$ that are adjacent in $T$.
Then $C$ and $C^{\prime}$ are adjacent in $C_{R}(G)$.

###### Proof.

Assume $C$ and $C^{\prime}$ are adjacent in $T$, but not in $C_{R}(G)$. We
partition the maximal cliques of $G$ as follows. Let $\mathcal{U}$ be the set
of maximal cliques of $G$ such that $D$ is in $\mathcal{U}$ if and only if the
path of $T$ from $D$ to $C$ does not contain $C^{\prime}$. Similarly, define
$\mathcal{U}^{\prime}$ so that $D^{\prime}$ is in $\mathcal{U}^{\prime}$ if
and only if the path of $T$ from $D^{\prime}$ to $C^{\prime}$ does not contain
$C$. Note that every maximal clique of $G$ is in exactly one of $\mathcal{U}$
or $\mathcal{U}^{\prime}$, since $T$ is a tree. Furthermore $C$ is in
$\mathcal{U}$ and $C^{\prime}$ is in $\mathcal{U}^{\prime}$. Let $U$ be the
union of the cliques in $\mathcal{U}$, and let $U^{\prime}$ be the union of
the cliques in $\mathcal{U}^{\prime}$. Every vertex is in at least one maximal
clique so $U\cup U^{\prime}=V(G)$. Note that $C\subseteq U$ and
$C^{\prime}\subseteq U^{\prime}$, so neither $U$ nor $U^{\prime}$ is empty.

If $U\cap U^{\prime}=\emptyset$, then we choose $u\in U$ and $u^{\prime}\in
U^{\prime}$ so that $u$ and $u^{\prime}$ are adjacent in $G$. (We are able to
do so because $G$ is connected.) The edge between $u$ and $u^{\prime}$ is
contained in a maximal clique. If this maximal clique is in $\mathcal{U}$ then
$u^{\prime}$ is in $U\cap U^{\prime}$, and if it is in $\mathcal{U}^{\prime}$
then $u$ is in $U\cap U^{\prime}$. In either case we have a contradiction, so
$U\cap U^{\prime}\neq\emptyset$.

Choose an arbitrary vertex $v$ in $U\cap U^{\prime}$. Choose $D\in\mathcal{U}$
and $D^{\prime}\in\mathcal{U}^{\prime}$ such that $v$ is in $D\cap
D^{\prime}$. Because $T$ is a clique tree, it follows that $v$ is contained in
all the cliques belonging to the path of $T$ from $D$ to $D^{\prime}$. In
particular, $v$ is contained in $C$ and $C^{\prime}$. Thus $U\cap
U^{\prime}\subseteq C\cap C^{\prime}$ and $C\cap C^{\prime}$ is non-empty.

Let $S$ be $C\cap C^{\prime}$. Since $C$ and $C^{\prime}$ are not adjacent in
$C_{R}(G)$, we can apply Proposition 2.4 and find a path $P$ of $C_{R}(G)$
from $C$ to $C^{\prime}$, where the intersection of each pair of consecutive
cliques in this path properly contains $S$. Since $C$ is in $\mathcal{U}$ and
$C^{\prime}$ is in $\mathcal{U}^{\prime}$, there is an edge of $P$ that joins
a clique $D\in\mathcal{U}$ to a clique $D^{\prime}\in\mathcal{U}^{\prime}$.
Then $D\cap D^{\prime}$ properly contains $S$, so we choose $v$ in $(D\cap
D^{\prime})-S$. Again using the fact that $T$ is a clique tree, we see that
the path of $T$ from $D$ to $D^{\prime}$ consists of cliques that contain $v$.
In particular, $v$ is in $C\cap C^{\prime}=S$, and we have a contradiction
that completes the proof. ∎

It follows from Proposition 2.5 that every clique tree of $G$ is a spanning
tree of $C_{R}(G)$.

######  Proposition 2.6.

Let $G$ be a connected chordal graph and let $\sigma$ be a legitimate
weighting of $G$. Let $T$ be a clique tree of $G$. Let $C$ and $C^{\prime}$ be
maximal cliques of $G$ that are adjacent in $C(G)$ and let $P$ be the path of
$T$ between $C$ and $C^{\prime}$. The weight of any edge in $P$ is at least
$\sigma(C\cap C^{\prime})$. Moreover, if $C$ and $C^{\prime}$ are adjacent in
$C_{R}(G)$, then at least one edge in $P$ has weight equal to $\sigma(C\cap
C^{\prime})$.

###### Proof.

Let $S$ be $C\cap C^{\prime}$. Let $P$ be the path of $T$ from $C$ to
$C^{\prime}$, and let the cliques in this path be $C_{0},C_{1},\ldots,C_{n}$,
where $C_{0}=C$ and $C_{n}=C^{\prime}$. Note that $P$ is a path of $C_{R}(G)$
by Proposition 2.5. Thus any two consecutive cliques in the path have a non-
empty intersection. Assume $\sigma(C_{i}\cap C_{i+1})<\sigma(S)$ for some $i$.
If $S$ were a subset of $C_{i}\cap C_{i+1}$, then we would have
$\sigma(S)\leq\sigma(C_{i}\cap C_{i+1})$ by the definition of a legitimate
weighting, but this is not true. Therefore we can choose $v$ to be a vertex in
$S-(C_{i}\cap C_{i+1})$. Now $v$ is a vertex of both $C$ and $C^{\prime}$, but
the path of $T$ between $C$ and $C^{\prime}$ contains at least one maximal
clique (either $C_{i}$ or $C_{i+1}$) that does not contain $v$. This
contradicts the fact that $T$ is a clique tree. Therefore the weight of any
edge in $P$ is at least equal to $\sigma(S)$.

Now assume that $C$ and $C^{\prime}$ are adjacent in $C_{R}(G)$, so that they
form a separating pair. That is, there are distinct connected components of
$G-S$ that contain, respectively, $C-S$ and $C^{\prime}-S$. There must be
maximal cliques $D$ and $D^{\prime}$ that are adjacent in $P$, where $D-S$ is
in the same connected component of $G-S$ as $C-S$, and $D^{\prime}-S$ is not
in this connected component. This means that $D\cap D^{\prime}$ is contained
in $S$. Hence $\sigma(D\cap D^{\prime})\leq\sigma(S)$. The previous paragraph
shows that $\sigma(D\cap D^{\prime})\geq\sigma(S)$, so the result follows. ∎

The proof of the next result is a straightforward adaptation of a proof given
by Blair and Peyton [BP93]*Theorem 3.6.

######  Lemma 2.7.

Let $G$ be a connected chordal graph. Let $\sigma$ be a legitimate weighting
of $G$ and let $T$ be a spanning tree of $C(G)$. Then $T$ is a clique tree of
$G$ if and only if it is a maximum-weight spanning tree of $C(G)$.

###### Proof.

If $T$ is a clique tree, then for any pair of maximal cliques, $C$ and
$C^{\prime}$, such that $C$ and $C^{\prime}$ are adjacent in $C(G)$, the
weight of the edge between $C$ and $C^{\prime}$ is no greater than the weight
of any edge in the path of $T$ between $C$ and $C^{\prime}$ (Proposition 2.6).
It immediately follows that $T$ has maximum weight.

For the other direction, we assume that $T$ is a maximum-weight spanning tree.
Because every chordal graph has a clique tree, and any clique tree is a
spanning tree of $C_{R}(G)$ (and hence of $C(G)$), we can choose a clique tree
$T^{\prime}$ so that $T$ and $T^{\prime}$ have as many edges in common as
possible. We can choose an edge in $T$ that is not in $T^{\prime}$, because
otherwise there is nothing left for us to prove. So let $e$ be such an edge,
and assume that $e$ joins maximal cliques $C$ and $C^{\prime}$. There are two
connected components of $T\backslash e$, one containing $C$ and the other
containing $C^{\prime}$. Let $P$ be the path of $T^{\prime}$ from $C$ to
$C^{\prime}$. We let $f$ be an edge of $P$ which joins two cliques that are
not in the same component of $T\backslash e$. Note that $f$ is an edge of
$T^{\prime}$, and hence an edge of $C(G)$.

If $(T-e)\cup f$ is not a spanning tree of $C(G)$, then there is a path of $T$
between the end-vertices of $f$ that does not use $e$. But the end-vertices of
$f$ are in different connected components of $T\backslash e$, so $(T-e)\cup f$
is indeed a spanning tree. Similarly, if $(T^{\prime}-f)\cup e$ is not a
spanning tree, then there is a path of $T^{\prime}$ between $C$ and
$C^{\prime}$ that does not contain $f$. But $P$ is the unique path of
$T^{\prime}$ between $C$ and $C^{\prime}$, and $f$ is an edge of $P$. So
$(T-e)\cup f$ and $(T^{\prime}-f)\cup e$ are both spanning trees of $C(G)$.

Applying Proposition 2.6 to the clique tree $T^{\prime}$ shows that the weight
of $f$ is at least the weight of $e$. Since $T$ is a maximum-weight spanning
tree, and $(T-e)\cup f$ is a spanning tree it follows that the weights on $e$
and $f$ must be equal. Let $D$ and $D^{\prime}$ be the maximal cliques joined
by $f$. Any element that is in both $C$ and $C^{\prime}$ must be in all the
cliques in $P$, since $T^{\prime}$ is a clique tree. This shows that $C\cap
C^{\prime}\subseteq D\cap D^{\prime}$. If $C\cap C^{\prime}$ were a proper
subset of $D\cap D^{\prime}$, then the definition of a legitimate weighting
would mean that the weight of $e$ is strictly less than the weight of $f$,
which is not true. Therefore $C\cap C^{\prime}=D\cap D^{\prime}$.

We note that $(T^{\prime}-f)\cup e$ cannot be a clique tree, since it has one
more edge in common with $T$ than $T^{\prime}$ does. Therefore we choose a
vertex $v\in V(G)$ so that the maximal cliques containing $v$ do not induce a
subtree of $(T^{\prime}-f)\cup e$. Let $T^{\prime\prime}$ be the subtree of
$T^{\prime}$ induced by the maximal cliques containing $v$. Then $f$ is in
$T^{\prime\prime}$, or else $T^{\prime\prime}$ would be a subtree of
$(T^{\prime}-f)\cup e$. This means that $v$ is in $D\cap D^{\prime}=C\cap
C^{\prime}$. So both $C$ and $C^{\prime}$ are in $T^{\prime\prime}$, but they
are not in the same component of $T^{\prime\prime}\backslash f$, because in
that case $(T^{\prime}-f)\cup e$ would contain a cycle. So $e$ joins two
vertices of $T^{\prime\prime}$ that are in different components of
$T^{\prime\prime}\backslash f$. Thus $(T^{\prime\prime}-f)\cup e$ is a subtree
of $(T^{\prime}-f)\cup e$, and we have a contradiction that completes the
proof. ∎

###### Proof of Theorem 2.2.

We have already noted that every clique tree is a spanning tree of $C_{R}(G)$.
Let $T$ be a clique tree of $G$. Then $T$ is a maximum-weight spanning tree of
$C(G)$ by Lemma 2.7. But every edge of $T$ is an edge of $C_{R}(G)$, by
Proposition 2.5. Since $C_{R}(G)$ is a subgraph of $C(G)$ it follows that $T$
is a maximum-weight spanning tree of $C_{R}(G)$.

For the other direction, we let $T$ be a maximum-weight spanning tree of
$C_{R}(G)$. We claim that $T$ is also a maximum-weight spanning tree of
$C(G)$. To prove this claim, let $e$ be an arbitrary edge of $C(G)$ that is
not in $T$, let $C$ and $C^{\prime}$ be the maximal cliques of $G$ joined by
$e$, and let $P$ be the path of $T$ that joins $C$ and $C^{\prime}$. If $e$ is
an edge of $C_{R}(G)$, then the weight of $e$ is no greater than the weight of
any edge in $P$, since $T$ is a maximum-weight spanning tree of $C_{R}(G)$.
Therefore we assume that $e$ is not an edge of $C_{R}(G)$. Now it follows from
Proposition 2.4 and the definition of a legitimate weighting that the edges in
$P$ all have weight strictly greater than the weight of $e$. In either case,
the weight of $e$ does not exceed the weight of any edge in $P$. This implies
that $T$ is indeed a maximum-weight spanning tree of $C(G)$, and thus $T$ is a
clique tree of $G$ by Lemma 2.7.

To complete the proof, we let $e$ be an arbitrary edge of $C_{R}(G)$. We will
prove that $e$ is in a maximum-weight spanning tree of $C_{R}(G)$. We let $C$
and $C^{\prime}$ be the maximal cliques joined by $e$. Let $T$ be an arbitrary
maximum-weight spanning tree of $C_{R}(G)$, so that $T$ is a clique tree by
the previous paragraph. If $e$ is in $T$ then we have nothing left to prove,
so assume that $P$ is the path of $T$ joining $C$ to $C^{\prime}$, where $P$
contains more than one edge. Proposition 2.6 shows that $P$ contains an edge,
$f$, with weight equal to the weight of $e$. Now $(T-f)\cup e$ is a maximum-
weight spanning tree of $C_{R}(G)$ that contains $e$, and we are done. ∎

From the previous arguments we can deduce further additional facts, both noted
in [GHP95]: any edge that is in $C(G)$ but not $C_{R}(G)$ cannot be in any
maximum-weight spanning tree of $C(G)$. Secondly, $C_{R}(G)$ is in fact the
union of all clique trees of $G$.

Although the next fact is incidental to our main results here, we note it for
a future application in [matroidpaper].

######  Proposition 2.8.

Let $G$ be a connected chordal graph, and let $T$ be a clique tree of $G$. Let
$C$ and $C^{\prime}$ be adjacent in $T$ and let $S$ be $C\cap C^{\prime}$.
Assume that $D$ and $D^{\prime}$ are maximal cliques of $G$ and the path of
$T$ from $D$ to $D^{\prime}$ contains both $C$ and $C^{\prime}$. Then $D-S$
and $D^{\prime}-S$ are in different connected components of $G-S$.

###### Proof.

Let $\mathcal{U}$ be the family of maximal cliques of $G$ such that $D$ is in
$\mathcal{U}$ if and only if the path of $T$ from $D$ to $C$ does not contain
$C^{\prime}$. Similarly, we let $\mathcal{U}^{\prime}$ be the family of
maximal cliques where $D^{\prime}$ is in $\mathcal{U^{\prime}}$ if and only if
the path of $T$ from $D^{\prime}$ to $C^{\prime}$ does not contain $C$. Note
that every maximal clique of $G$ belongs to exactly one of $\mathcal{U}$ and
$\mathcal{U}^{\prime}$. We are asserting that if $D\in\mathcal{U}$ and
$D^{\prime}\in\mathcal{U}^{\prime}$, then $D-S$ and $D^{\prime}-S$ are in
different connected components of $G-S$. Assume that this fails for $D$ and
$D^{\prime}$, where $D\cap D^{\prime}$ is as large as possible. Let $H$ be the
connected component of $G-S$ that contains both $D-S$ and $D^{\prime}-S$.

Let $P$ be the path of $T$ from $D$ to $D^{\prime}$. Therefore $P$ contains
both $C$ and $C^{\prime}$. Let $v$ be an arbitrary vertex of $D\cap
D^{\prime}$. Then $v$ is in every maximal clique that appears in $P$, since
$T$ is a clique tree. In particular, $v$ is in $C$ and $C^{\prime}$. Thus $v$
is in $S$, and this shows that $D\cap D^{\prime}$ is contained in $S$.

Let $v_{0},v_{1},\ldots,v_{k}$ be the vertex sequence of a shortest-possible
path of $H$ from a vertex $v_{0}\in D-S$ to a vertex $v_{k}\in D^{\prime}-S$.
This is an $S$-avoiding path, where $S$ contains $D\cap D^{\prime}$. Thus we
can apply Proposition 2.3. For $i=1,2,\ldots,k$ we let $D_{i}$ be a maximal
clique of $G$ that contains $(D\cap D^{\prime})\cup\\{v_{i-1},v_{i}\\}$. Let
$D_{0}$ be $D$ and let $D_{k+1}$ be $D^{\prime}$. Note that each $D_{i}-S$ is
contained in $H$. This is true for $D_{0}$ and $D_{k+1}$ by definition, and
every other $D_{i}$ contains the edge $v_{i-1}v_{i}$, which is in the path of
$H$ from $v_{0}$ to $v_{k}$. Since $D_{0}$ is in $\mathcal{U}$ and $D_{k+1}$
is in $\mathcal{U}^{\prime}$, we can choose $i$ so that $D_{i}$ is in
$\mathcal{U}$ and $D_{i+1}$ is in $\mathcal{U}^{\prime}$. The intersection of
$D_{i}$ and $D_{i+1}$ is larger than $D\cap D^{\prime}$, since it contains
$(D\cap D^{\prime})\cup v_{i}$. As $D_{i}-S$ and $D_{i+1}-S$ are both
contained in $H$ we have a contradiction to the choice of $D$ and
$D^{\prime}$. ∎

##  3\. The structure of reduced clique graphs

Habib and Stacho comment on the possibility of investigating the structure of
graphs that are isomorphic to reduced clique graphs [HS12]*p. 714. In this
section we make a contribution to this investigation. We start by answering an
obvious question that requires a non-trivial proof.

######  Corollary 3.1.

Let $G$ be a chordal graph. Then $C_{R}(G)$ is connected if and only if $G$ is
connected.

###### Proof.

Assume that $H$ and $H^{\prime}$ are distinct connected components of $G$. No
maximal clique of $H$ can share a vertex with a maximal clique of
$H^{\prime}$. It follows that there be no path of $C_{R}(G)$ that joins two
such cliques. Thus $C_{R}(G)$ is not connected.

The other direction is stated without proof in [HS12]*p. 716. Assume that $G$
is connected. Since $G$ is chordal it has a clique tree [Gavril]*Theorem 2,
and Proposition 2.5 shows that every edge of the clique tree is an edge of
$C_{R}(G)$. Thus $C_{R}(G)$ has a spanning tree, so it is connected. ∎

Next we note a characterisation of clique graphs due to Szwarcfiter and
Bornstein.

######  Theorem 3.2 ([SB94]*Theorem 2.1).

The graph $H$ is isomorphic to $C(G)$ for some connected chordal graph $G$ if
and only if $H$ has a spanning tree $T$ such that whenever $u$ and $v$ are
adjacent in $H$, the path of $T$ from $u$ to $v$ induces a clique of $H$.

###  3.1. Induced cycles

Next we observe that clique graphs can have induced cycles of any length. We
will later show that this is not true for reduced clique graphs. For an
integer $n\geq 3$ the _wheel graph_ with $n$ spokes is obtained from a cycle
of $n$ vertices by adding a new vertex and making it adjacent to all vertices
of the cycle. Thus the wheel graph with $n$ spokes has an induced cycle of $n$
vertices.

######  Proposition 3.3.

For each integer $n\geq 3$ the wheel graph with $n$ spokes is isomorphic to
the clique graph of a chordal graph.

###### Proof.

This is easy to prove using Theorem 3.2, but we will give a direct
construction. Start with a clique on the $n+1$ vertices
$u_{0},u_{1},\ldots,u_{n-1},x$. For each $i\in\mathbb{Z}/n\mathbb{Z}$, add a
new vertex $v_{i}$ and make it adjacent to $u_{i}$ and $u_{i+1}$. Call the
resulting graph $G$. It is easy to verify that $G$ is chordal, and its maximal
cliques are $\\{u_{0},u_{1},\ldots,u_{n-1},x\\}$ along with
$\\{v_{i},u_{i},u_{i+1}\\}$ for each $i\in\mathbb{Z}/n\mathbb{Z}$. The result
follows. ∎

######  Definition 3.4.

Let $G$ be a chordal graph. Let $C_{0},C_{1},\ldots,C_{n-1}$ be a cyclic
ordering of the maximal cliques in an induced cycle of $C_{R}(G)$. We take the
indices to be from $\mathbb{Z}/n\mathbb{Z}$, so $C_{i}$ and $C_{j}$ are
adjacent in $C_{R}(G)$ if and only if $j\in\\{i-1,i+1\\}$. If $|C_{i}\cap
C_{i+1}|\leq|C_{j}\cap C_{j+1}|$ for every $j\in\mathbb{Z}/n\mathbb{Z}$, then
we say that the edge between $C_{i}$ and $C_{i+1}$ is a _minimal_ edge of the
cycle.

######  Lemma 3.5.

Let $G$ be a chordal graph. Let $C_{0},C_{1},\ldots,C_{n-1}$ be a cyclic
ordering of the maximal cliques in an induced cycle of $C_{R}(G)$, where
$n\geq 4$ and the indices are from $\mathbb{Z}/n\mathbb{Z}$. Assume that the
edge between $C_{0}$ and $C_{1}$ is a minimal edge of the induced cycle. Let
$S$ be $C_{0}\cap C_{1}$ and for $i=0,1$ let $H_{i}$ be the connected
component of $G-S$ that contains $C_{i}-S$. Then $H_{0}$ and $H_{1}$ are
distinct connected components and $C_{i}-S$ is contained in $H_{0}$ or $H_{1}$
for every $i\in\mathbb{Z}/n\mathbb{Z}$. Furthermore, either:

  1. (i)

$H_{0}$ contains all of $C_{0}-S,C_{2}-S,\ldots,C_{n-1}-S$,

  2. (ii)

$H_{1}$ contains all of $C_{1}-S,C_{2}-S,\ldots,C_{n-1}-S$, or

  3. (iii)

$n=4$, and $H_{0}$ contains $C_{0}-S$ and $C_{2}-S$ while $H_{1}$ contains
$C_{1}-S$ and $C_{3}-S$.

###### Proof.

Note that because $C_{0},C_{1},\ldots,C_{n-1}$ are distinct maximal cliques of
$G$, none of them is contained in $S$. Thus $C_{i}-S$ is non-empty for all
$i$. We consider the connected components of $G-S$. Any set $C_{i}-S$ is
contained in such a component. Because $C_{0}$ and $C_{1}$ form a separating
pair, $C_{0}-S$ and $C_{1}-S$ are contained in different connected components
of $G-S$, so $H_{0}$ and $H_{1}$ are distinct components.

######  Claim 3.5.1.

Assume that $i$ and $j$ are distinct indices in $\mathbb{Z}/n\mathbb{Z}$ such
that there are distinct connected components of $G-S$, call them $H_{i}$ and
$H_{j}$, that contain $C_{i}-S$ and $C_{j}-S$ respectively. Assume also that
$C_{i}$ is adjacent in $C_{R}(G)$ to $C_{p}$, where $C_{p}-S$ is not contained
in $H_{i}$ and that $C_{j}$ is adjacent to $C_{q}$, where $C_{q}-S$ is not
contained in $H_{j}$. Then $C_{i}$ and $C_{j}$ are adjacent in $C_{R}(G)$.

###### Proof.

Note that because the cycle of $C_{R}(G)$ is induced, $p$ is in
$\\{i-1,i+1\\}$ and $q$ is in $\\{j-1,j+1\\}$. Note also that $C_{i}\cap
C_{p}$ is contained in $S$. If this containment is proper then $|C_{i}\cap
C_{p}|<|S|=|C_{0}\cap C_{1}|$ and we have violated our assumption that the
edge between $C_{0}$ and $C_{1}$ is minimal. Therefore $C_{i}$ and $C_{p}$
both contain $S$. The same argument shows $S\subseteq C_{j}\cap C_{q}$. Now
$C_{i}\cap C_{j}$ is equal to $S$. Moreover $C_{i}-S$ and $C_{j}-S$ are in
different components of $G-S$, so $C_{i}$ and $C_{j}$ form a separating pair
of maximal cliques. Hence they are adjacent in $C_{R}(G)$. ∎

We colour the cliques of $C_{0},C_{1},\ldots,C_{n-1}$ in the following way.
For each $i\in\mathbb{Z}/n\mathbb{Z}$, if $C_{i}-S$ is contained in $H_{0}$ we
colour $C_{i}$ red, and if $C_{j}-S$ is in $H_{1}$ we colour $C_{i}$ blue.
Thus $C_{0}$ is red and $C_{1}$ is blue.

######  Claim 3.5.2.

Any maximal clique $C_{i}$ is either red or blue.

###### Proof.

If the claim fails then there is some $i\in\mathbb{Z}/n\mathbb{Z}-\\{0,1\\}$
such that $C_{i}-S$ is contained in neither $H_{0}$ nor $H_{1}$. Let $H_{i}$
be the connected component of $G-S$ that contains $C_{i}-S$. We colour any
clique $C_{j}$ in $C_{0},C_{1},\ldots,C_{n-1}$ green if $C_{j}-S$ is contained
in $H_{i}$. We know that the collections of red, blue, and green cliques are
all non-empty. So therefore we can find a red clique, $C_{\text{red}}$,
adjacent to a clique that is not red. We can similarly find $C_{\text{blue}}$,
a blue clique that is adjacent to a non-blue clique, and $C_{\text{green}}$, a
green clique that is adjacent to a clique that is not green. Now Claim 3.5.1
implies that $C_{\text{red}}$, $C_{\text{blue}}$, and $C_{\text{green}}$ are
adjacent to each other in $C_{R}(G)$. As they are three distinct vertices in
an induced cycle of $C_{R}(G)$ with at least four vertices, this is an
immediate contradiction. ∎

If $C_{1}$ is the only blue clique, then statement (i) holds and we have
nothing left to prove. Similarly, if $C_{0}$ is the only red clique, then (ii)
holds and we are done. So we assume there are at least two red cliques and at
least two blue cliques. We can choose $C_{\text{red}}$ and
$C_{\text{red}}^{\prime}$ to be distinct red cliques that are adjacent to blue
cliques, and we can choose $C_{\text{blue}}$ and $C_{\text{blue}}^{\prime}$ to
be two distinct blue cliques that are adjacent to red cliques. Now Claim 3.5.1
implies that $C_{\text{red}}$ and $C_{\text{red}}^{\prime}$ are adjacent to
both $C_{\text{blue}}$ and $C_{\text{blue}}^{\prime}$. Thus the four cliques
induce a cycle in $C_{R}(G)$. This is impossible if $n\geq 5$, so we conclude
that $n=4$. Now $C_{0}$ is a red clique and it is adjacent to two blue
cliques. Thus $C_{1}$ and $C_{3}$ are blue, $C_{2}$ is red, and we are
finished. ∎

The example in Figure 1 shows that a reduced clique graph may contain an
induced cycle with four vertices. We will next show that there is no example
with an induced cycle of five vertices.

######  Lemma 3.6.

There is no chordal graph $G$ such that $C_{R}(G)$ has an induced cycle with
exactly five vertices.

###### Proof.

Assume otherwise and let $G$ be a chordal graph such that $C_{R}(G)$ contains
an induced cycle with five vertices. Let $C_{0},C_{1},C_{2},C_{3},C_{4}$ be
the maximal cliques in this cycle, where the indices are from
$\mathbb{Z}/5\mathbb{Z}$ and $C_{i}$ is adjacent to $C_{j}$ if and only if
$j\in\\{i-1,i+1\\}$. By adding a constant to these indices as necessary, we
may assume that

$|C_{0}\cap C_{1}|\leq|C_{i}\cap C_{i+1}|$

for all $i\in\mathbb{Z}/5\mathbb{Z}$, so that the edge between $C_{0}$ and
$C_{1}$ is a minimal edge of the cycle. Let $S$ be $C_{0}\cap C_{1}$. Note
that $S$ is non-empty.

Now we apply Lemma 3.5. By applying the permutation $\rho\colon i\mapsto 1-i$
as necessary, we may assume that statement (ii) in Lemma 3.5 applies.
Therefore we let $H_{0}$ and $H_{1}$ be connected components of $G-S$ such
that $H_{0}$ contains $C_{0}-S$ and $H_{1}$ contains $C_{1}-S$, $C_{2}-S$,
$C_{3}-S$, and $C_{4}-S$.

######  Claim 3.6.1.

$C_{0}\cap C_{4}=S=C_{0}\cap C_{1}$.

###### Proof.

Because $C_{0}-S$ and $C_{4}-S$ are contained in different components of
$G-S$, it follows that $C_{0}\cap C_{4}\subseteq S$. All we have left to prove
is that this containment is not proper. If it were proper, then we would
contradict the assumption that the edge between $C_{0}$ and $C_{1}$ is
minimal. ∎

######  Claim 3.6.2.

Neither $C_{2}$ nor $C_{3}$ contains $S$.

###### Proof.

Note that $C_{0}\cap C_{2}\subseteq S$ because $C_{0}-S$ and $C_{2}-S$ are
contained in different components of $G-S$. Certainly any path from a vertex
of $C_{0}-C_{2}$ to a vertex of $C_{2}-C_{0}$ must use a vertex of $S$. If
$C_{0}\cap C_{2}=S$, then $C_{0}$ and $C_{2}$ form a separating pair, so
$C_{0}$ and $C_{2}$ are adjacent in $C_{R}(G)$. This contradicts the fact that
$C_{0}$ and $C_{2}$ are non-consecutive vertices in an induced cycle. The same
argument shows that $C_{3}$ does not contain $S$. ∎

######  Claim 3.6.3.

$C_{2}\cap C_{4}\subseteq C_{1}$ and $C_{3}\cap C_{1}\subseteq C_{4}$.

###### Proof.

Assume that $x$ is a vertex of $C_{2}\cap C_{4}$ that is not in $C_{1}$. By
Claim 3.6.2 we can let $y$ be a vertex in $S-C_{2}$. Thus $y$ is in
$C_{1}-C_{2}$. So $x$ is in $C_{2}-C_{1}$ and $y$ is in $C_{1}-C_{2}$. Claim
3.6.1 implies that $y$ is in $C_{4}$. As $x$ is also in $C_{4}$ we see that
$x$ and $y$ are adjacent. Because $C_{1}$ and $C_{2}$ are adjacent in
$C_{R}(G)$ they have a non-empty intersection, but now the edge $xy$ shows
that $C_{1}$ and $C_{2}$ do not form a separating pair and we have a
contradiction. A symmetric argument shows $C_{3}\cap C_{1}\subseteq C_{4}$. ∎

######  Claim 3.6.4.

$C_{2}$ contains a vertex of $C_{1}-C_{4}$ and $C_{3}$ contains a vertex of
$C_{4}-C_{1}$.

###### Proof.

By symmetry it suffices to prove the first statement. Assume that $C_{2}$
contains no vertex of $C_{1}-C_{4}$. Because $C_{1}$ and $C_{2}$ are adjacent
in $C_{R}(G)$, they have at least one vertex in common. By our assumption, no
vertex of $C_{1}\cap C_{2}$ is in $C_{1}-C_{4}$, so any such vertex must be in
$C_{1}\cap C_{4}$. Therefore $C_{2}$ and $C_{4}$ are not disjoint. Since
$C_{2}$ and $C_{4}$ are not adjacent in $C_{R}(G)$, we can let $P$ be a
$(C_{2}\cap C_{4})$-avoiding path from a vertex $x\in C_{2}-C_{4}$ to $y\in
C_{4}-C_{2}$.

Our assumption means that $x$ is not in $C_{1}-C_{4}$, so it is in
$C_{2}-C_{1}$. Our assumption and Claim 3.6.3 imply that $C_{2}\cap
C_{4}=C_{2}\cap C_{1}$. Therefore $P$ is a $(C_{2}\cap C_{1})$-avoiding path.
But Claim 3.6.2 shows that we can choose a vertex $z$ in $S-C_{2}$. Thus $z$
is in $C_{1}-C_{2}$ and Claim 3.6.1 shows that $z$ is in $C_{4}$. Assuming
that $z$ and $y$ are not equal, they are adjacent, as both are in $C_{4}$. By
appending (if necessary) the edge $yz$ to the end of $P$ we obtain a
$(C_{1}\cap C_{2})$-avoiding path from a vertex in $C_{2}-C_{1}$ to a vertex
in $C_{1}-C_{2}$. Hence $C_{1}$ and $C_{2}$ do not form a separating pair and
this contradicts the fact that they are adjacent in $C_{R}(G)$. ∎

######  Claim 3.6.5.

Either $C_{2}\cap(C_{1}\cap C_{4})\subseteq C_{3}$ or $C_{3}\cap(C_{1}\cap
C_{4})\subseteq C_{2}$.

###### Proof.

Note that $C_{2}\cap C_{3}$ is non-empty, since $C_{2}$ and $C_{3}$ are
adjacent in $C_{R}(G)$. If the claim fails, then we choose $x\in(C_{2}\cap
C_{1}\cap C_{4})-C_{3}$ and $y\in(C_{3}\cap C_{1}\cap C_{4})-C_{2}$. Now $x$
and $y$ are both in $C_{1}\cap C_{4}$, so they are adjacent. Moreover $x$ is
in $C_{2}-C_{3}$ and $y$ is in $C_{3}-C_{2}$. Thus $C_{2}$ and $C_{3}$ do not
form a separating pair and we have a contradiction. ∎

By using Claim 3.6.5, we will assume that $C_{2}\cap(C_{1}\cap C_{4})$ is a
subset of $C_{3}$. The other outcome from Claim 3.6.5 yields to a symmetric
argument. Using Claim 3.6.2 we choose a vertex $x\in S$ that is not in
$C_{3}$. Note that Claim 3.6.1 implies that $S$ is contained in $C_{1}\cap
C_{4}$. So $x$ is in $(C_{1}\cap C_{4})-C_{3}$. Our assumption therefore
implies that $x$ is not in $C_{2}$.

By Claim 3.6.4 we can also choose $y$ in $C_{2}\cap(C_{1}-C_{4})$ and $z$ in
$C_{3}\cap(C_{4}-C_{1})$. Claim 3.6.3 implies that $y$ is in $C_{2}-C_{3}$ and
$z$ is in $C_{3}-C_{2}$. Now $x$ and $y$ are adjacent as they are both in
$C_{1}$, and $x$ and $z$ are adjacent as they are both in $C_{4}$. Note that
$C_{2}\cap C_{3}$ is non-empty as $C_{2}$ and $C_{3}$ are adjacent in
$C_{R}(G)$. But the path with vertex sequence $y,x,z$ is $(C_{2}\cap
C_{3})$-avoiding, so $C_{2}$ and $C_{3}$ do not form a separating pair. This
final contradiction completes the proof. ∎

Lemma 3.6 shows that the class of reduced clique graphs is contained in the
class of graphs with no length-five induced cycle. We next show that this
containment is proper.

######  Proposition 3.7.

Let $n\geq 4$ be an integer. There is no chordal graph $G$ such that either
$C(G)$ or $C_{R}(G)$ is a cycle with $n$ vertices.

###### Proof.

Szwarcfiter and Bornstein characterise the clique graphs of chordal graphs
[SB94]. In particular $H$ is isomorphic to $C(G)$ for some chordal graph $G$
if and only if $H$ has a spanning tree $T$ such that whenever $u$ and $v$ are
adjacent in $H$, the path of $T$ from $u$ to $v$ induces a clique of $H$. Now
assume $H$ is a cycle with at least four vertices. Any spanning tree of $H$ is
a Hamiltonian path. The end vertices of this path are adjacent in $H$, but the
path of the spanning tree between these vertices does not induce a clique.
Therefore $H$ is not isomorphic to $C(G)$ for any chordal graph $G$.

We turn to reduced chordal graphs. Assume for a contradiction that $G$ is a
chordal graph with $C_{0},C_{1},\ldots,C_{n-1}$ as its list of maximal
cliques, where the indices are from $\mathbb{Z}/n\mathbb{Z}$, and $C_{i}$ is
adjacent to $C_{j}$ in $C_{R}(G)$ if and only if $j\in\\{i-1,i+1\\}$. We can
assume without loss of generality that the edge between $C_{0}$ and $C_{1}$ is
a minimal edge of $C_{R}(G)$. Let $S$ be $C_{0}\cap C_{1}$. Assume that
statement (iii) in Lemma 3.5 holds. Thus $n=4$ and there are distinct
connected components, $H_{0}$ and $H_{1}$, of $G-S$ such that $H_{0}$ contains
$C_{0}-S$ and $C_{2}-S$ while $H_{1}$ contains $C_{1}-S$ and $C_{3}-S$. Note
that $C_{0}\cap C_{3}\subseteq S$, and in fact $C_{0}\cap C_{3}$ is equal to
$S$, or else the minimality of the $C_{0}$-$C_{1}$ edge is contradicted.

Either $C_{0}\cap C_{2}$ is empty, or it is not. In the latter case, we can
apply Proposition 2.4 to $C_{0}$ and $C_{2}$. We see that either $C_{0}\cap
C_{1}$ or $C_{0}\cap C_{3}$ properly contains $C_{0}\cap C_{2}$. By symmetry,
we can assume $C_{0}\cap C_{2}$ is a proper subset of $C_{0}\cap C_{1}=S$.
Thus $C_{0}-S$ and $C_{2}-S$ are disjoint sets. They are contained in the same
connected component of $G-S$, so we can let $P$ be a shortest-possible path of
$H_{0}$ from a vertex of $C_{0}-S$ to a vertex of $C_{2}-S$. On the other
hand, if $C_{0}\cap C_{2}$ is empty, then $C_{0}-S$ and $C_{2}-S$ are again
disjoint subsets in $H_{0}$, so we again let $P$ be a shortest-possible path
of $H_{0}$ from $C_{0}-S$ to $C_{2}-S$. In either case, $P$ contains exactly
one vertex of $C_{0}$ and exactly one vertex of $C_{2}$. Then $P$ must contain
at least one edge, and this edge is in a maximal clique that is equal to
neither $C_{0}$ nor $C_{2}$. Nor can this maximal clique be $C_{1}$ or
$C_{3}$, because any edge of $P$ is contained in $H_{0}$. So we have a
contradiction in the case that (iii) in Lemma 3.5 holds.

Now we assume that either (i) or (ii) holds. By applying the permutation
$\rho\colon i\mapsto 1-i$ as necessary, we will assume that $H_{0}$ and
$H_{1}$ are distinct connected components of $G-S$, and that $H_{0}$ contains
$C_{0}-S$ while $H_{1}$ contains $C_{i}-S$ for $i=\\{1,2,\ldots,n-1\\}$. By
the same argument as earlier, we can see that $C_{n-1}$ contains $S$, or else
the choice of the $C_{0}-C_{1}$ edge is contradicted.

Now $C_{1}\cap C_{n-1}$ contains $S$, and $C_{1}$ and $C_{n-1}$ are non-
adjacent in $C_{R}(G)$. We apply Proposition 2.4 and see that there is a path
of $C_{R}(G)$ from $C_{1}$ to $C_{n-1}$ such that every intersection of
consecutive cliques in the path properly contains $C_{1}\cap C_{n-1}$. This
path is either $C_{1},C_{0},C_{n-1}$, or it is $C_{1},C_{2},\ldots,C_{n-1}$.
Assume the former. Then $C_{1}\cap C_{0}=S$ properly contains $C_{1}\cap
C_{n-1}\supseteq S$ and we have a contradiction. Hence any intersection of
consecutive cliques in $C_{1},C_{2},\ldots,C_{n-1}$ properly contains
$C_{1}\cap C_{n-1}$, and hence contains $S$. It follows that $C_{2}$ contains
$S$ and thus $C_{0}\cap C_{2}$ is non-empty.

Since $C_{0}-S$ and $C_{2}-S$ are contained in different components of $G-S$,
any path of a vertex from $C_{0}-C_{2}$ to a vertex of $C_{2}-C_{0}$ must
contain a vertex of $S=C_{0}\cap C_{2}$. Thus $C_{0}$ and $C_{2}$ form a
separating pair in $G$, and hence they are adjacent in $C_{R}(G)$, which is a
contradiction. ∎

###  3.2. Clique graphs vs. reduced clique graphs

Consider the classes $\\{C(G)\\}$ and $\\{C_{R}(G)\\}$, where $G$ ranges over
all chordal graphs. Proposition 3.3 and Lemma 3.6 show that the wheel with
five spokes is isomorphic to a graph in the former class but not the latter.
Is there a graph that is isomorphic to a graph in the latter class but not the
former? We will show that the answer is, once again, yes. Recall that if $G$
and $G^{\prime}$ are disjoint graphs, then $G\boxtimes G^{\prime}$ is obtained
from the union of $G$ and $G^{\prime}$ by making every vertex of $G$ adjacent
to every vertex of $G^{\prime}$. We use $P_{n}$ to denote the path of length
$n$.

######  Lemma 3.8.

Let $m,n\geq 1$ be integers. Then $P_{m}\boxtimes P_{n}$ is isomorphic to the
reduced clique graph of a chordal graph. If $n\geq 22$, then $P_{n}\boxtimes
P_{n}$ is not isomorphic to the clique graph of a chordal graph.

###### Proof.

Let $G$ be the graph obtained from the disjoint union of $P_{m}$ and $P_{n}$
and adding a new vertex that is adjacent to every vertex of the disjoint
union. It is easy to confirm that $G$ is chordal, and that $C_{R}(G)$ is
isomorphic to $P_{m}\boxtimes P_{n}$.

For the second statement, we let $H$ be a graph with disjoint induced paths
$P_{u}=u_{0},u_{1},\ldots,u_{n-1}$ and $P_{v}=v_{0},v_{1},\ldots,v_{n-1}$,
where $n\geq 22$ and every $u_{i}$ is adjacent to every $v_{j}$. Thus $H$ is
isomorphic to $P_{n}\boxtimes P_{n}$. We will assume for a contradiction that
$H$ is isomorphic to $C(G)$ for some chordal graph $G$. Because $C(G)$ is
connected it follows easily that $G$ is connected, so we can apply Theorem 3.2
and deduce that $H$ has a spanning tree $T$, where the path of $T$ from $u$ to
$v$ induces a clique of $H$ whenever $u$ and $v$ are adjacent in $H$.

######  Claim 3.8.1.

Let $i$ and $j$ be integers satisfying $0<i,j<n-1$. The path of $T$ from
$u_{i}$ to $v_{j}$ is contained in one of:
$\\{u_{i},u_{i+1},v_{j},v_{j+1}\\}$, $\\{u_{i},u_{i+1},v_{j-1},v_{j}\\}$,
$\\{u_{i-1},u_{i},v_{j},v_{j+1}\\}$, $\\{u_{i-1},u_{i},v_{j-1},v_{j}\\}$.

###### Proof.

Let $P$ be the path of $T$ from $u_{i}$ to $v_{j}$. Since $u_{i}$ is adjacent
to $v_{j}$ it follows that $P$ induces a clique of $H$. As $u_{i}$ is not
adjacent to any of the vertices in
$u_{0},\ldots,u_{i-2},u_{i+2},\ldots,u_{n-1}$, it follows that the vertices of
$P$ that are in $P_{u}$ belong to $\\{u_{i-1},u_{i},u_{i+1}\\}$. Similarly,
the vertices of $P$ that are in $P_{v}$ belong to
$\\{v_{j-1},v_{j},v_{j+1}\\}$. But $u_{i-1}$ is not adjacent to $u_{i+1}$, so
$P$ does not contain both. The claim follows by symmetry. ∎

Claim 3.8.1 implies that the path of $T$ between $u_{i}$ and $v_{j}$ has at
most three edges.

Let $P$ be a longest-possible path of $T$ and let $p_{0},p_{1},\ldots,p_{k-1}$
be the vertices of $P$. For $i=0,1,\ldots,k-1$, let $U_{i}$ be the set of
vertices in $P_{u}$ such that $u$ is in $U_{i}$ if and only if the shortest
path of $T$ from $u$ to a vertex in $P$ contains $p_{i}$. We define $V_{i}$ to
be the analogous set of vertices in $P_{v}$. Note that
$(U_{0},U_{1},\ldots,U_{k-1})$ is a partition of the vertices of $P_{u}$, and
$(V_{0},V_{1},\ldots,V_{k-1})$ is a partition of the vertices of $P_{v}$.

######  Claim 3.8.2.

Either

$\max\\{|U_{i}|\colon 0\leq i\leq k-1\\}\leq
3\quad\text{or}\quad\max\\{|V_{i}|\colon 0\leq i\leq k-1\\}\leq 3.$

###### Proof.

Assume for a contradiction that $|U_{i}|\geq 4$ and $|V_{j}|\geq 4$. Let $p$
and $q$, respectively, be the smallest (largest) integers such that
$u_{p},u_{q}\in U_{i}$. Then $q-1>p+1$ because $|U_{i}|\geq 4$. In the same
way, let $s$ and $t$ be the smallest (largest) integers such that
$v_{s},v_{t}\in V_{j}$. Then $t-1>s+1$. It is simple to see from Claim 3.8.1
that the path of $T$ from $u_{p}$ to $v_{s}$ has no vertex in common with the
path of $T$ from $u_{q}$ to $v_{t}$. But this contradicts the fact that both
paths contain $p_{i}$ and $p_{j}$. ∎

By using Claim 3.8.2, we will assume without loss of generality that
$|V_{i}|\leq 3$ for each $i=0,1,\ldots,k-1$. Since
$(U_{0},U_{1},\ldots,U_{k-1})$ is a partition of the vertices in $P_{u}$ we
can choose $i$ so that $U_{i}$ contains a vertex $x$. We claim that if $j\leq
i-4$ or $j\geq i+4$, then $V_{j}=\emptyset$. If this fails, then the path of
$T$ from a vertex in $V_{j}$ to $x$ contains at least four edges of $P$. But
this contradicts our earlier conclusion that any path of $T$ from a vertex of
$P_{u}$ to a vertex of $P_{v}$ contains at most three edges. So now the
vertices of $P_{v}$ belong to

$V_{i-3}\cup V_{i-2}\cup\cdots\cup V_{i+2}\cup V_{i+3}$

and this union has cardinality at most $7\times 3$. Thus $P_{v}$ contains at
most $21$ vertices and this contradicts $n\geq 22$. ∎

##  4\. Conclusions and open problems

Given Lemma 3.6 it might be natural to believe that reduced clique graphs
cannot have any induced cycles with five or more vertices. But Figure 3 shows
a chordal graph $G$ where $C_{R}(G)$ has an induced cycle with six vertices.

Figure 3.

Nonetheless we believe the following to be true.

######  Conjecture 4.1.

There is no chordal graph $G$ such that $C_{R}(G)$ contains an induced cycle
with seven or more vertices.

So far as we have been able to tell, every chordal graph is isomorphic to both
a clique graph, and to a reduced clique graph. We conjecture this holds
generally.

######  Conjecture 4.2.

Let $H$ be a chordal graph. There are chordal graphs $G$ and $G^{\prime}$ such
that $H$ is isomorphic to both $C(G)$ and $C_{R}(G^{\prime})$.

Szwarcfiter and Bornstein present a polynomial-time algorithm for deciding
whether a given graph is isomorphic to $C(G)$ for some chordal graph $G$
[SB94]. Their techniques do not obviously extend to recognising reduced clique
graphs. Nonetheless, we will make the following conjecture.

######  Conjecture 4.3.

There is a polynomial-time algorithm for deciding whether a given graph is
isomorphic to $C_{R}(G)$ for some chordal graph $G$.

More informally, we ask if there is a structural description for reduced
clique graphs that is analogous to Theorem 3.2.

## References


#  GPTuner: A Manual-Reading Database Tuning System via GPT-Guided Bayesian
Optimization

Jiale Lao1, Yibo Wang1, Yufei Li1, Jianping Wang2, Yunjia Zhang3, Zhiyuan
Cheng4, Wanghu Chen2, Mingjie Tang1, Jianguo Wang4 1Sichuan University,
{laojiale, wangyibo2<EMAIL_ADDRESS><EMAIL_ADDRESS>
2Northwest Normal University, {2022222119<EMAIL_ADDRESS>
3University of Wisconsin-Madison<EMAIL_ADDRESS>
4Purdue University, {cheng443<EMAIL_ADDRESS>
###### Abstract.

Modern database management systems (DBMS) expose hundreds of configurable
knobs to control system behaviours. Determining the appropriate values for
these knobs to improve DBMS performance is a long-standing problem in the
database community. As there is an increasing number of knobs to tune and each
knob could be in continuous or categorical values, manual tuning becomes
impractical. Recently, automatic tuning systems using machine learning methods
have shown great potentials. However, existing approaches still incur
significant tuning costs or only yields sub-optimal performance. This is
because they either ignore the extensive domain knowledge available (e.g.,
DBMS manuals and forum discussions) and only rely on the runtime feedback of
benchmark evaluations to guide the optimization, or they utilize the domain
knowledge in a limited way. Hence, we propose GPTuner, a manual-reading
database tuning system that leverages domain knowledge extensively and
automatically to optimize search space and enhance the runtime feedback-based
optimization process. Firstly, we develop a Large Language Model (LLM)-based
pipeline to collect and refine heterogeneous knowledge, and propose a prompt
ensemble algorithm to unify a structured view of the refined knowledge.
Secondly, using the structured knowledge, we (1) design a workload-aware and
training-free knob selection strategy, (2) develop a search space optimization
technique considering the value range of each knob, and (3) propose a Coarse-
to-Fine Bayesian Optimization Framework to explore the optimized space.
Finally, we evaluate GPTuner under different benchmarks (TPC-C and TPC-H),
metrics (throughput and latency) as well as DBMS (PostgreSQL and MySQL).
Compared to the state-of-the-art approaches, GPTuner identifies better
configurations in 16x less time on average. Moreover, GPTuner achieves up to
30% performance improvement (higher throughput or lower latency) over the
best-performing alternative.

PVLDB Artifact Availability:
The source code, data, and/or other artifacts have been made available at
%leave␣empty␣if␣no␣availability␣url␣should␣be␣sethttps://github.com/SolidLao/GPTuner.

##  1\. Introduction

Modern Database Management Systems (DBMS) expose hundreds of configurable
parameters (i.e., knobs) to control their runtime behaviours (pavlo2017self).
The selection of appropriate values for these knobs is crucial to improve DBMS
performance, constituting a long-standing challenge within the database
community (10.14778/3450980.3450992). Given the high dimensionality of the
configuration space (e.g., PostgreSQL v14.7 has 351 knobs), and the inherent
heterogeneity of these knobs (due to their continuous and categorical
domains), database administrators (DBAs) encounter substantial difficulties in
identifying promising configurations tailored to specific query workloads. The
magnitude of this challenge becomes even more pronounced in the cloud
environment, where the underlying physical configurations can significantly
vary among distinct DBMS instances (10.14778/3476311.3476411).

To reduce the manual tuning efforts of DBAs, state-of-the-art approaches
automate the knob tuning via Machine Learning (ML) techniques, including
Bayesian Optimization (10.14778/1687627.1687767; 10.1145/3035918.3064029;
10.1145/3448016.3457291; 10.14778/3457390.3457404; 10.1145/3514221.3526176;
10.1145/3318464.3380591) and Reinforcement Learning (10.1145/3299869.3300085;
10.14778/3352063.3352129; 10.1145/3514221.3517882; 10.1145/3514221.3517843).
These ML-based tuning systems follow the main concept of “trial and error” to
explore the configuration space iteratively, balancing between the exploration
of unseen regions and the exploitation of known space.

While these tuning systems do possess the potential to reach well-performing
knob configurations eventually, they still incur significant tuning costs
(10.14778/3551793.3551844; 10.1145/3318464.3380591). For example, previous
studies (10.1145/3514221.3517882; 10.1145/3448016.3457291;
10.14778/3538598.3538604) have revealed that state-of-the-art systems still
require hundreds to thousands iterations to reach an ideal configuration, with
each iteration taking several minutes or more to execute the target workload.
Such high tuning costs stem from their inefficiency in handling two
difficulties: (1) the large number of knobs that requires tuning and (2) the
wide search space of possible values for each knob. For the first difficulty,
most approaches either select a fixed subset of knobs
(10.1145/3514221.3517882; 10.14778/3551793.3551844; 10.14778/3457390.3457404;
10.14778/1687627.1687767; 10.1145/3299869.3300085; 10.1145/3127479.3128605),
sacrificing the flexibility to choose workload-relevant knobs, or execute
workloads numerous times to identify the important knobs
(10.14778/3538598.3538604; 10.1145/3035918.3064029; 10.5555/3488733.3488749),
which is resource-intensive. Regarding the second difficulty, most approaches
use the default value ranges provided by DBMS vendors
(10.14778/1687627.1687767; 10.1145/3035918.3064029; 10.1145/3448016.3457291;
10.14778/3457390.3457404; 10.1145/3514221.3526176; 10.1145/3318464.3380591;
10.1145/3299869.3300085; 10.14778/3352063.3352129; 10.1145/3514221.3517882).
However, since the default value ranges are excessively broad for flexibility,
it complicates the optimization process and introduces the risk of system
crashes (10.14778/3476311.3476411; 10.14778/3450980.3450992).

In contrast to ML-based tuning approaches that adjust the DBMS solely based on
performance statistics, human DBAs often rely on domain knowledge for tuning
(e.g., DBMS manuals and discussions from DBMS forums). Unlike performance
statistics, external domain knowledge directly reveals tuning hints, including
the important knobs and typical value ranges for each knob. First, there are
discussions on which knobs significantly impact DBMS performance. For
instance, in web forums like Hacker News, it is commonly mentioned that
parallel knobs (e.g., “max_parallel_workers_per_gather”) are crucial for OLAP
workloads, while I/O-related knobs (e.g., “max_wal_size”) are important for
OLTP workloads (hackernews). Second, there are typical value ranges summarized
for knobs. Table 1 provides two examples of extracting improved value ranges
from natural language tuning guidance. For knob “shared_buffers”, instead of
using the default value range [0.125 MB, 8192 GB], the improved value range
can be [4 GB, 6.4 GB] since the guidance suggests setting the value between
25% and 40% of the RAM (on a machine with 16 GB of RAM). For knob
“random_page_cost”, we can try out value range [1.0, 2.0] rather than [0,
1.79769 $\times~{}10^{308}$] if the machine uses SSDs as disks. We can observe
that these hints are highly valuable in reducing the search space of ML-based
methods and thus expedite convergence and achieve better performance.

Table 1. Tuning Knowledge Utilization 2 Knob |  shared_buffers |  random_page_cost
---|---|---
Default Range |  $[0.125\text{MB},~{}8192~{}\text{GB}]$ |  $[0,~{}1.79769\times 10^{308}]$
Guidance |  “shared_buffers” can be 25% of the RAM but no more than 40% …(PostgreSQL2023) |  “random_page_cost” can be 1.x if disk has a speed similar to SSDs …(PostgreSQLCONF)
DBA |  The machine has a 16 GB RAM. Thus we can set “shared_buffers” from 16 GB $\times$ 25% = 4 GB to 16 GB $\times$ 40% = 6.4 GB. |  The machine uses SSDs as disks. Thus we can set “random_page_cost” to a value from 1.0 to 2.0.
Improved Range |  [4 GB, 6.4 GB] |  [1.0, 2.0]
2 |  |

(a) TPC-H Benchmark

(b) TPC-C Benchmark

Figure 1. GPTuner vs. DB-BERT

Therefore, to mitigate the high tuning costs of ML-based techniques, it is
desirable to design a knob-tuning system leveraging domain knowledge to
enhance the optimization process. However, this is non-trivial for the
following challenges. C1. It is challenging to unify a structured view of the
heterogeneous domain knowledge while balancing a trade-off between cost and
quality. Domain knowledge typically comes in the form of DBMS manuals and
discussions on the web forums. To leverage such knowledge in the ML-based
techniques, we need to transfer it into a unified machine-readable format
(i.e., structured data). However, preparing such a structured view involves a
complex and lengthy workflow: data ingestion, data cleaning, data integration
and data extraction (nargesian2019data), and existing approaches cannot meet
our trade-off between cost and quality. They either demand domain specific
training (shin2015incremental), which is more complicated in our scenario
since it requires expert knowledge to annotate DBMS tuning knowledge, or they
rely on strong assumptions that lack of flexibility (e.g., focusing on
specific document format) (deng2022dom; lockard2019openceres;
lockard2020zeroshotceres). C2. Even with the prepared structured knowledge, we
lack a way to integrate the knowledge into the optimization process. The
inherent design of optimization algorithms like Bayesian Optimization
(snoek2012practical) and Reinforcement Learning (henderson2018deep) does not
support the integration of external domain knowledge directly, necessitating
extensive modifications to their standard workflows. For approaches that
manually summarize static rules from domain knowledge, the resulting rules
cannot capture the nuances of all workloads, and the updates of environments
can make them out of date (10.5555/1287369.1287454; Kwan2002AutomaticCF). To
address the challenges above, we propose GPTuner, a manual-reading database
tuning system that leverages domain knowledge automatically and extensively to
enhance the optimization process.

Facing the challenge C1, we develop a Large Language Model (LLM)-based
pipeline to collect and refine heterogeneous knowledge, and propose a prompt
ensemble algorithm to unify a structured view of the refined knowledge. First,
we prepare heterogeneous tuning knowledge from various resources (data
ingestion). Second, we filter out noisy knowledge (data cleaning). Third, we
summarize the multi-source knowledge by handling the possible conflict in a
priority way (data integration). Fourth, we ensure the summarization result is
factually consistent with source contents (data correction). Finally, we
develop a prompt ensemble algorithm to construct a structured view of the
knowledge (data extraction).

Regarding the challenge C2, we use the structured knowledge to (1) design a
workload-aware and training-free knob selection strategy, (2) develop a search
space optimization technique considering the value range of each knob, and (3)
propose a novel knowledge-based optimization framework to explore the
optimized space. Before the tuning process, we optimize the search space based
on data dimensionality and the values in each dimension. For data
dimensionality, we leverage the text analysis ability of LLM to simulate the
knob selection process of DBAs, considering the characteristic of DBMS,
workload, specific query and knob dependencies. For values in each dimension,
we discard meaningless regions, highlight promising space and take special
situations into consideration. Next, we develop a novel Coarse-to-Fine
Bayesian Optimization Framework. At first, since it is non-trivial to reduce
the size of search space while still retaining the potential for optimal
results (feurer2019hyperparameter), we seek help from domain knowledge to
carefully design two search spaces of different granularity. Next, the two
spaces are explored sequentially by BO from coarse granularity to fine
granularity, with a bootstrap technique to serve as a bridging mechanism. This
framework balances between the efficiency of coarse-grained search and the
thoroughness of fine-grained search.

We are aware of only one work DB-BERT (10.1145/3514221.3517843) that utilizes
a pre-trained language model to read manuals and uses the mined hints to guide
a reinforcement learning algorithm. It exhibits rapid convergence as it
benefits from the information gained via text analysis. However, it only
yields sub-optimal performance since it utilizes the domain knowledge narrowly
and suffers from the inadequate exploration of search space. GPTuner tackles
these limitations and thus achieves faster convergence and better performance
improvement. As shown in Figure 1, GPTuner significantly outperforms DB-BERT
on two representative benchmarks (TPC-H and TPC-C) with different optimization
objective (latency and throughput). It is important to note that GPTuner is a
distinct approach compared to DB-BERT, and its efficacy does not stem from
simply substituting the language model. We verify this by replacing the BERT
model in DB-BERT with GPT-4 and compare it with GPTuner again. More details
are provided in Section 2.3.

In our experiments, we compare GPTuner against DB-BERT as well as other state-
of-the-art approaches that do not use text as input. We consider different
benchmarks (TPC-C and TPC-H), metrics (throughput and latency), and DBMS
(PostgreSQL and MySQL). Compared to the state-of-the-art approaches, GPTuner
identifies better configurations in 16x less time on average. Moreover,
GPTuner achieves up to 30% performance improvement (higher throughput or lower
latency) over the best-performing alternative. In summary, we make the
following contributions:

  * •

We propose GPTuner, a novel manual-reading database tuning system that
leverages domain knowledge automatically and extensively to enhance the knob
tuning process.

  * •

We develop a LLM-based pipeline to collect and refine domain knowledge, and
propose a prompt ensemble algorithm to unify a structured view of the refined
knowledge.

  * •

We design a workload-aware and training-free knob selection strategy, develop
an optimization method for the value range of each knob, and propose a Coarse-
to-Fine Bayesian Optimization framework to explore the optimized space.

  * •

We open-source the built structured domain knowledge for PostgreSQL and MySQL
to enable the further study of broader database community.

  * •

We conduct extensive experiments to demonstrate the effectiveness of GPTuner,
considering different benchmarks, metrics and DBMS. Compared with the state-
of-the-art methods, GPTuner finds the best-performing knob configuration with
significantly less tuning rounds.

##  2\. Background and Related Work

###  2.1. Database Knob Tuning

DBMS expose tens to hundreds of configurable knobs to control their runtime
behaviours (10.14778/3450980.3450992). The DBMS knob tuning problem is to
select an appropriate value for each knob to optimize the DBMS performance
(e.g., throughput or latency) on a certain workload (e.g., a workload is a set
of SQL statements). Formally, given a set of configurable knobs
$\theta_{1},\dots,\theta_{n}$ along with their domains
$\Theta_{1},\dots,\Theta_{n}$, the configuration space is defined as
$\boldsymbol{\Theta}=\Theta_{1}\times\dots\times\Theta_{n}$. We want to find a
configuration $\boldsymbol{\theta}^{*}\in\boldsymbol{\Theta}$ to maximize DBMS
performance $f$:

(1)
$\boldsymbol{\theta}^{*}=\operatorname*{arg\,max}_{\theta\in\boldsymbol{\Theta}}f(\theta)$

Finding an optimal solution for this problem is challenging for two main
reasons. Firstly, with hundreds of adjustable knobs, each potentially
impacting performance, the complexity is immense. Secondly, the knobs
themselves vary widely – some have continuous numerical values, while others
are categorical, making the problem even more complicated since it is hard to
model heterogeneous space. To address these challenges, three kinds of
approaches are proposed: heuristic-based, Bayesian Optimization (BO)-based
(snoek2012practical) and Reinforcement Learning (RL)-based
(henderson2018deep).

• Heuristic-based. Heuristic-based methods can be classified into rule-based
and search-based. Rule-based methods rely on manually created static rules to
explore the space in a predefined way (10.5555/1287369.1287454;
Kwan2002AutomaticCF). Search-based methods explore the space according to
several heuristics (e.g., avoid to revisit explored regions and explore the
nearby regions to improve the current optimum) (10.1145/3127479.3128605;
10.1145/2628071.2628092).

• BO-based. BO-based methods (10.14778/1687627.1687767;
10.1145/3035918.3064029; 10.1145/3448016.3457291; 10.14778/3457390.3457404;
10.1145/3514221.3526176; 10.1145/3318464.3380591) follow the generic BO
framework to search for an optimal configuration: (1) fitting a probabilistic
surrogate model to map the relation between knob configuration and DBMS
performance, (2) selecting the next configuration that maximizes acquisition
function.

• RL-based. RL-based methods explore configuration space with a trial-and-
error strategy. The essence is to balance between exploring unexplored space
and exploiting known regions, which is achieved by the interactions between an
agent (e.g., neural network) and the target environment (e.g., DBMS)
(10.1145/3299869.3300085; 10.14778/3352063.3352129; 10.1145/3514221.3517882).

Performance Comparison. An experimental evaluation is conducted to compare
these approaches (10.14778/3538598.3538604). A BO-based method, Sequential
Model-based Algorithm Configuration (SMAC) (lindauer-jmlr22a) yields the best
performance because it uses Random Forest (RF) as the surrogate to leverage
its efficiency in modeling the high-dimensional and heterogeneous
configuration space. Since SMAC is evaluated as the best-performing optimizer,
we view it as the current state-of-the-art that does not take text as input
and aim to improve it further.

Figure 2. Motivating Example

###  2.2. Language Models

The field of Natural Language Processing (NLP) has undergone a significant
transformation with the advent of Large Language Models (LLMs). Starting with
the introduction of attention and transformer architecture (wolf-
etal-2020-transformers), numerous language models (LMs) have been developed,
resulting in a substantial enhancement of language processing capabilities.
Notably, BERT, which introduced the encoder-only transformer architecture,
revolutionized downstream learning tasks by improving embeddings (devlin-
etal-2019-bert). More recent additions to the GPT series, such as ChatGPT
(luo2023chatgpt) and GPT-4 (openai2023gpt4), have demonstrated greater prowess
across a wide range of tasks.

Moreover, the impact of these LLMs extends beyond the scope of NLP. The
database community has experienced a surge in the adoption of LLMs to enhance
various aspects of DBMS, including data profiling (zhang2023schema;
trummer2021can; narayan2022foundation), code generation
(trummer2023demonstrating; yu2019spider; cheng2023binding; scholak2021picard)
and table-based question answering (ye2023large; zhang2023reactable;
jiang2022omnitab). When using LLMs in practice, there are three typical design
choices: (1) training a language model from scratch, (2) fine-tuning an
existing language model, and (3) using a pre-trained language model without
parameter modifications. The first two options require a relatively large
amount of resources, including both hardware resources and training data.
Given the impressive in-context learning capabilities demonstrated by GPT-4,
we have chosen the third option and use GPT-4 as our default language model
throughout the paper unless noted otherwise.

Table 2. Comparison between DB-BERT and GPTuner Criterion |  DB-BERT |  GPTuner
---|---|---
Language Model |  BERT |  GPT-4
Workload-Aware Knob Selection |  no |  yes
Fine-Tuning |  yes |  no
Filter Noise |  no |  yes
Space Type |  Discrete |  Heterogeneous
Optimization Algorithm |  Reinforcement Learning |  Coarse-to-Fine Bayesian
Considered Knowledge |  Suggested Value |  Suggested Value Bound Constraint Special Cases

###  2.3. Enhancing DBMS Knob Tuning with LMs

With the vast corpus of tuning guidance available on the internet or provided
by DBMS vendors, language models can be harnessed to “read the manual” and
provide structured tuning hints to enhance the knob tuning approaches. As the
state-of-the-art LM-enhanced tuning approach, DB-BERT
(10.1145/3514221.3517843) models the tuning process as a series of “multiple
choice question answering problem”, and uses Reinforcement Learning to fine-
tune a pre-trained BERT model to answer these problems. While DB-BERT
converges fast as it benefits from the text analysis, it only yields sub-
optimal performance.

We summarize the main differences between GPTuner and DB-BERT in Table 2.
Firstly, the knob selection of DB-BERT is not workload-aware since it only
tune knobs mentioned in the input documents. GPTuner considers the tuning
context (e.g., the characteristic of DBMS, workload, specific query and the
knob dependencies) to select which knobs are worth tuning. Secondly, DB-BERT
requires fine-tuning of BERT model in both offline training and online tuning
stages, which requires a lot of resources. GPTuner adopts in-context learning
ability of LLM without modifying the model parameters. Thirdly, DB-BERT relies
on the input documents without filtering out noisy contents, while GPTuner
tackles this by comparing the contents with the system view from DBMS (e.g.,
pg_settings from PostgreSQL). Fourth, DB-BERT only rely on the suggested
values from documents to construct a discrete space and only explore this
space. However, such limited utilization of domain knowledge and inadequate
exploration of search space are the decisive factors leading to sub-optimal
performance. GPTuner, on the other hand, leverages more information from
domain knowledge (e.g., suggested value, bound constraint, and special cases),
and explores the search space with a novel Knowledge-based Optimization
Framework. Finally, we conduct experiments to evaluate the performance of both
methods in Section LABEL:subsec:_performance-compare. Moreover, we investigate
the effect the language model in Section LABEL:subsec:_differ-llm. Whether
using the same advanced model (both GPT-4) or a less complex one (i.e., DB-
BERT with GPT-4 and GPTuner with GPT-3.5), GPTuner consistently outperforms
DB-BERT in both scenarios.

Figure 3. System Overview of GPTuner

##  3\. Motivation

ML-based methods still incur significant tuning costs. State-of-the-art ML-
based tuning methods require hundreds to thousands of iterations to converge
to a good DBMS knob configuration. Such high tuning expenses stem from the
inefficiency of runtime feedback-based optimization algorithms. Specifically,
the feedback information is limited (i.e., a few benchmark runs cannot provide
a complete picture of the DBMS performance under all conditions) and unstable
(i.e., DBMS performance is not guaranteed to improve after each step of knob
tuning). Given such weak feedback, it takes a substantial number of
observations for ML models to have sufficient confidence in predictions,
especially when the space is complex.

Extensive domain knowledge helps, but not well-exploited. Since the early
2000s, when tuning systems take knob settings into consideration, extensive
tuning knowledge has continually accumulated in the form of natural language
and such knowledge does help in optimizing the search space. As shown in
Figure 2 (left part), by analyzing the tuning knowledge, we can identify which
knobs are worth tuning and gain insights of the typical value settings for
knobs (e.g., suggested value to try, range constraint and special value).
However, such wisdom seems exclusive to DBA and is not leveraged to mitigate
the expensive tuning costs of ML-based approaches. There are approaches that
utilize the static rules summarized by DBA to complete knob tuning.
Unfortunately, these rules cannot capture the nuances of all workloads, and
the updates of environments can make these static rules out of date. Thus we
call for a more advanced approach to utilize the knowledge.

LLM is a notable step forward, but not adequate yet. While it is widely
acknowledged that domain knowledge is useful, such wisdom is considered
inaccessible to machines due to the barriers in natural language
understanding. Recently, the advent of Large Language Model (LLM) makes it
possible to leverage such knowledge since we can utilize LLM to transfer the
knowledge into a unified machine-readable format (e.g., structured data like
JSON and relational table). However, this process is still challenging for two
main reasons. First, since domain knowledge typically comes in the form of
DBMS documents and discussions from DBMS forums, it involves a complex and
lengthy workflow to process such heterogeneous and noisy knowledge: data
ingestion, data cleaning, data integration and data extraction. Second, the
brittle nature of LLM (i.e. small modifications to the prompt can cause large
variations in the model outputs) and the hallucination problem of LLM (i.e.,
LLM generates answers that seem correct but are factually false) make this
challenge even more pronounced. For instance, as shown in Figure 2 (middle
part), LLM can generate contents that are defective and even wrong. Thus, a
reliable and effective approach to harness the power of LLM is both non-
trivial and essential.

Even if structured knowledge is developed, its integration into the
optimization process is deficient. To the best of our knowledge, no DBMS
tuning framework accounts for structured knowledge. Existing optimization
algorithms like BO and RL do not support the integration of external knowledge
directly, necessitating extensive modification to their standard workflows.
Without modification, the only information that can be used is the range
constraint (i.e., lower and upper bounds) recommended by manuals. However,
there is much more useful information available (e.g., suggested value and
special value). We present some simple ideas to utilize these values in Figure
2 (right part). Unfortunately, it is predictable that such naive ideas cannot
serve as an effective solution, especially in the context of DBMS knob tuning
where the problem is proven to be NP-hard (10.1145/1005686.1005739).
Therefore, the current situation calls for an innovative optimization
framework that inherently supports the effective utilization of the structured
domain knowledge.

##  4\. Overview of GPTuner

Workflow. GPTuner is a manual-reading database tuning system to suggest
satisfactory knob configurations with reduced tuning costs. Figure 3 presents
the tuning workflow that involves seven steps. ❶ User provides the DBMS to be
tuned (e.g., PostgreSQL or MySQL), the target workload, and the optimization
objective (e.g., latency or throughput). ❷ GPTuner collects and refines the
heterogeneous knowledge from different sources (e.g., GPT-4, DBMS manuals and
web forums) to construct Tuning Lake, a collection of DBMS tuning knowledge. ❸
GPTuner unifies the refined tuning knowledge from Tuning Lake into a
structured view accessible to machines (e.g., JSON). ❹ GPTuner reduces the
search space dimensionality by selecting important knobs to tune (i.e., fewer
knobs to tune means fewer dimensions). ❺ GPTuner optimizes the search space in
terms of the value range for each knob based on structured knowledge. ❻
GPTuner explores the optimized space via a novel Coarse-to-Fine Bayesian
Optimization framework, and finally ❼ identifies satisfactory knob
configurations within resource limits (e.g., the maximum optimization time or
iterations specified by users).

Components. GPTuner consists of three components: Knowledge Handler,
Knowledge-Based Search Space Optimizer and Knowledge-Based Configuration
Recommender and they work as follows:

Knowledge Handler. Knowledge Handler uses a DBMS tuning knowledge-oriented
data pipeline to unify a structured view of the heterogeneous domain
knowledge. At first, we propose a LLM-based pipeline to balance between cost
and quality in Section 5.1. Next, we propose a LLM-based Prompt Ensemble
Algorithm to transfer the refined knowledge into a structured format such that
it can be utilized by machines in Section LABEL:subsec:_knowledge-transform.

Knowledge-Based Search Space Optimizer. The optimizer optimizes the search
space from two aspects. Firstly, it reduces the size of the search space in
terms of dimensionality. Specifically, we propose a workload-aware and
training-free approach to select important knobs in Section
LABEL:subsec:_knob-select. Secondly, we optimize the search space by focusing
on the value range of each knob. We propose Region Discard, Tiny Feasible
Space and Virtual Knob Extension methods to discard meaningless regions,
highlight promising space and handle special situations, respectively (Section
LABEL:subsec:_space-reduction).

Knowledge-Based Configuration Recommender. The recommender uses a novel
Coarse-to-Fine BO Framework to compute optimal configurations. In the first
stage, BO only explores a discrete subspace of the whole heterogeneous space.
This subspace is small in size but promising to contain good configurations
since we generate it based on the reliable domain knowledge. In the next
stage, in order to avoid the overlooking problem of coarse-grained search
(i.e., it is inevitable to lose some useful configurations for any space
reduction technique), BO explores the heterogeneous space thoroughly with the
optimizations in Section LABEL:sec:_space-explorer. After the two stages, the
recommender outputs the best-performing knob configurations found within the
budget limits specified by users.

##  5\. Knowledge Handler

###  5.1. Knowledge Preparation

In this section, we discuss how Knowledge Handler completes Knowledge
Preparation task. As outlined in Algorithm 1, this task is to collect tuning
knowledge from various resources (data ingestion, Line 1-3), filter out noisy
contents (data cleaning, Line 4), summarize the legal parts (data integration,
Line 5-6) and make sure the summarization is factual consistent with source
contents (data correction, Line 7-10). The output is a Tuning Lake defined as
follows:

###### Definition 1 (Tuning Lake).

Tuning Lake $\mathcal{L}=\\{d_{1},d_{2},\dots d_{n}\\}$ is a set of $n$ texts,
where $n$ is the number of configurable knobs and $d_{i}$ is the natural
language tuning knowledge for $i$-th knob. For example, “set shared_buffers to
25% of the RAM” (denoted as $d_{i}$) is the tuning knowledge for knob
“shared_buffers” (the $i$-th knob).

1

2

Input: DBMS manuals $\mathcal{D}$; LLM $\mathcal{F}$; Rule $\mathcal{R}$; Knob
Set $\mathcal{K}$.

Output: Tuning Lake $\mathcal{L}$.

3

4Collect tuning knowledge $\mathcal{D}_{web}$ via a Web Crawler;

5

6Extract tuning knowledge $\mathcal{D}_{LLM}$ from $\mathcal{F}$;

7

8$\mathcal{D}$ $\leftarrow$ $\mathcal{D}$ $\cup$ $\mathcal{D}_{web}$ $\cup$
$\mathcal{D}_{LLM}$;

9

10Apply $\mathcal{R}$ and $\mathcal{F}$ on $\mathcal{D}$ to obtain legal
guidance $\mathcal{D}_{legal}$;

11

12Apply $\mathcal{F}$ on $\mathcal{D}_{legal}$ to summarize guidance $d_{i}$
for $k_{i}\in\mathcal{K}$;

13

14Candidate Tuning Lake $\mathcal{L}=\\{d_{i}\\}$;

15

16while  _$\mathcal{L}$ does not pass Factual Consistency Check by
$\mathcal{F}$_ do

17 Apply $\mathcal{F}$ to modify $\mathcal{L}$ based on feedback from check;

18 Apply $\mathcal{F}$ on modified $\mathcal{L}$ to conduct another check;

19

20 end while

21

22return $\mathcal{L}$;

23

Algorithm 1 Knowledge Preparation Algorithm

Step 1: Extracting knowledge from LLM. Except for the common tuning knowledge
sources (e.g., manuals and web contents), we propose utilizing LLM as a
knowledge source as well. Since GPT is trained on a vast corpus related to
database (ameryahia2023large), GPT itself is an informative manual and allows
us to retrieve the knowledge through prompt. In practice, we surprisingly find
that GPT can give reasonable suggestions that are not included in the manuals.
Such suggestions come from web contents summarized by DBAs and were used as
training data for GPT. Since it is impossible to provide all web contents to
any system and GPT already knows much of it, it is reasonable to use GPT as a
complementary source of knowledge. In case that GPT gives nonsense
suggestions, we utilize LLM to handle such abnormal situation in the next
step.

Figure 4. Knowledge Extraction from GPT

######  Example 0.

Figure 4 depicts the process of extracting knowledge from GPT for knob
“effective_io_concurrency”. While the manual provides no useful suggestions,
GPT recommends value 200 for SSDs and 2 for HDDs, which is available from a
blog (metis).

Step 2: Filtering noisy knowledge. The tuning knowledge comes from various
sources and its quality cannot be guaranteed. Thus we filter out noisy
knowledge by modeling this process as a “binary classification problem” and
utilize LLM to solve it. We provide LLM with the candidate tuning knowledge
for a knob and an official system view for this knob (e.g., pg_settings from
PostgreSQL and information_schema from MySQL). Moreover, we give a few
examples in the prompt to utilize the in-context learning ability of LLM (dai-
etal-2023-gpt). LLM evaluates whether the tuning knowledge conflicts with the
system view and we discard any knowledge that does conflict.