Finitary Relational Calculus

We show that all relational first-order logic queries can be effectively evaluated on finitary relations. Finitary relations are finite unions of Cartesian products of finite and cofinite sets. This works without any safety restrictions on formulas as in classical relational calculus. It relies on a translation to a relational algebra that includes an unrestricted complement operator and uses term rewriting on tensor terms, which are generally useful as compact data structures, also in conventional database systems.