Treewidth and Cliquewidth. Treewidth describes how
similar a graph (in our case: a database) is to a tree, and
cliquewidth does the same for cliques
[1]}. Due to space restrictions and since this article focuses on
cliquewidth, we provide the definition of treewidth only in the
appendix.
Databases of cliquewidth \(k\)  can be constructed by a \(k\) -expression as
defined below, where \(k\)  refers to the number of labels in the
expression. For convenience, we use a reservoir of fresh concept names
\(L_1,L_2,\dots \)  as labels that may occur in databases, but not
in ontologies and queries.
We say that
a constant \(c \in {adom}()\)  is labeled \(i\)  if \(L_i(c) \in \) .
An expression \(s\)  defines a
database \(_s\)  built from four operations, as follows:
