We study the expressive power of various query languages on relational databases of bounded tree-width.
Our first theorem says that fixed-point logic with counting captures polynomial time on classes of databases of bounded tree-width.
This result should be seen on the background of an important open question of Chandra and Harel [7] asking whether there is a query language capturing polynomial time on unordered databases. Our theorem is a further step
in a larger project of extending the scope of databases on which polynomial time can be captured by reasonable query languages.
We then prove a general definability theorem stating that each query on a class of databases of bounded tree-width which is
definable in monadic second-order logic is also definable in fixed-point logic (or datalog). Furthermore, for each k ≥ 1 the class of databases of tree-width at most k is definable in fixed-point logic. These results have some remarkable consequences concerning the definability of certain
classes of graphs.
Finally, we show that each database of tree-width at most k can be characterized up to isomorphism in the language Ck+3, the (k + 3)-variable fragment of firstorder logic with counting.