Computing queries with higher-order logics

In 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 Σ j i and Π j i, for each i ⩾ 1 and each number of alternations of quantifier blocks j. Then, we get as a corollary the expressive power of HO i 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 ⩾ 2 HO i, 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.

Authors

• Lauri Hella
• José María Turull-Torres

Keywords

• Higher-order logics
• Descriptive complexity
• Complete languages