Polynomially bounded valuations in higher-order logics over relational databases

Authors Flavio Ferrarotti
Loredana Tec
José María Turull-Torres
Editors Atif Mashkoor
Qing Wang
Bernhard Thalhiemn
Title Polynomially bounded valuations in higher-order logics over relational databases
Booktitle Models: Concepts, Theory, Logic, Reasoning, and Semantics - Essays Dedicated to Klaus-Dieter Schewe on the Occasion of His 60th Birthday
Type in book
Publisher College Publications
Series Tributes
Volume 34
ISBN 978-1-84890-276-3
Month April
Year 2018
Pages 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.