Polynomially bounded valuations in higher-order logics over relational databases

Autoren Flavio Ferrarotti
Loredana Tec
José María Turull-Torres
Editoren Atif Mashkoor
Qing Wang
Bernhard Thalhiemn
Titel Polynomially bounded valuations in higher-order logics over relational databases
Buchtitel Models: Concepts, Theory, Logic, Reasoning, and Semantics - Essays Dedicated to Klaus-Dieter Schewe on the Occasion of His 60th Birthday
Typ in Buch
Verlag College Publications
Serie Tributes
Band 34
ISBN 978-1-84890-276-3
Monat April
Jahr 2018
Seiten 92-121
SCCH ID# 18017

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.