Polynomially bounded valuations in higher-order logics over relational databases

• Flavio Ferrarotti
• Loredana Tec
• José María Turull-Torres

• Atif Mashkoor
• Qing Wang
• Bernhard Thalhiemn

There are many examples of queries to relational database instances that can be expressed by simple and elegant third-order logic (TO) formulae. For many of those queries the expressive power of TO is not required, but the equivalent second-order logic (SO) formulae can be very complicated or unintuitive. From the point of view of the study of highly expressive query languages is then relevant to identify fragments of TO (and, in general, of higher-order logics of order >3) which do have an SO equivalent formula. In this article we investigate this precise problem as follows. Firstly, we define a general schema of existential third-order (9TO) formulae and show that all 9TO-formulae of this schema can be translated into equivalent SO-formulae. We give examples which show that this is a very usual, intuitive, and convenient schema in the expression of database queries. Secondly, aiming to characterize the fragment of TO which can be translated to SO, we de_ne TOP as the restriction of TO to valuations of polynomially bounded cardinality. We show constructively that TOP collapses to SO. Moreover, we define a similar restriction for every higher-order logic of order i > 4 (HOi) and show that they also collapse to SO.