Computing queries with higher-order logics

AbstractIn the present article, we study the expressive power of higher-order logics on finite relational structures or databases. First, we give a characterization of the expressive power of the fragments Σji and Πji, for each i⩾1 and each number of alternations of quantifier blocks j. Then, we get as a corollary the expressive power of HOi for each order i⩾2. From our results, as well as from the results of R. Hull and J. Su, it turns out that no higher-order logic can be complete. Even if we consider the union of higher-order logics of all natural orders, i.e., ⋃i⩾2HOi, we still do not get a complete logic. So, we define a logic which we call variable order logic (VO) which permits the use of untyped relation variables, i.e., variables of variable order, by allowing quantification over orders. We show that this logic is complete, though even non-recursive queries can be expressed in VO. Then we define a fragment of VO and we prove that it expresses exactly the class of r.e. queries. We finally give a characterization of the class of computable queries through a fragment of VO, which is undecidable