Datalog is a popular query language with applications in several
domains. Like any complex piece of software, Datalog engines may
contain bugs. The most critical ones manifest as incorrect
results when evaluating queries—we refer to these as
\emph{query bugs}. Given the wide applicability of the language,
query bugs may have detrimental consequences, for instance, by
compromising the soundness of a program analysis that is
implemented and formalized in Datalog. In this paper, we present
the first metamorphic-testing approach for detecting query bugs
in Datalog engines. We ran our tool on three mature engines and
found 13 previously unknown query bugs, some of which are deep
and revealed critical semantic issues.