English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

In the framework of computable queries in Database Theory, there are manyexamples of queries to (properties of) relational database instances that canbe expressed by simple and elegant third order logic ($\mathrm{TO}$) formulae.In many of those properties the expressive power of $\mathrm{TO}$ is notrequired, but the equivalent second order logic ($\mathrm{SO}$) formulae can bevery complicated or unintuitive. From the point of view of the study of highlyexpressive query languages, it is then relevant to identify fragments of$\mathrm{TO}$ (and, in general, of higher-order logics of order $\geq 3$) whichdo have an $\mathrm{SO}$ equivalent formula. In this article we investigatethis precise problem as follows. Firstly, we define a general schema of$\exists$TO formulas which consists of existentially quantifying a third-orderlinear digraph of polynomial length, that is, a sequence of structures thatrepresents a computation, by explicitly stating which operations are the oneswhich can be involved in the construction of a given structure in the sequence,when applied to the previous one. Then we give a constructive proof of the factthat all $\exists$TO sub formulas of that schema can be translated into anequivalent SO formula. Secondly, aiming to formally characterize the fragmentof TO which can be translated to SO, we define a restriction of TO, which wedenote TO$^{P}$, for polynomial TO, and we give a constructive proof on thefact that it collapses to SO. We define TO$^{P}$ as the fragment of TO wherevaluations can assign to TO relation variables only TO relations whosecardinalities are bounded by a polynomial that depends on the quantifier.Moreover, we define a similar restriction for every higher order logic of order$i \geq 4$, which we denote $\mathrm{HO}^{i,P}$, and give a constructive proofof the fact that for all $i \geq 4$, $\mathrm{HO}^{i,P}$ collapses to SO.

On Higher Order Query Languages which on Relational Databases Collapse to Second Order Logic