Relational databases and homogeneity in logics with counting

Turull Torres José María: Relational databases and homogeneity in logics with counting. In: Acta cybernetica, (17) 3. pp. 485-511. (2006)

[thumbnail of Turull_2006_ActaCybernetica.pdf]
Preview
Cikk, tanulmány, mű
Turull_2006_ActaCybernetica.pdf

Download (241kB) | Preview

Abstract

We define a new hierarchy in the class of computable queries to relational databases, in terms of the preservation of equality of theories in fragments of first order logic with bounded number of variables with the addition of counting quantifiers (Ck). We prove that the hierarchy is strict, and it turns out that it is orthogonal to the TIME-SPACE hierarchy defined with respect to the Turing machine complexity. We introduce a model of computation of queries to characterize the different layers of our hierarchy which is based on the reflective relational machine of S. Abiteboul, C. Papadimitriou, and V. Vianu. In our model the databases are represented by their Ck theories. Then we define and study several properties of databases related to homogeneity in Ck getting various results on the change in the computation power of the introduced machine, when working on classes of databases with such properties. We study the relation between our hierarchy and a similar one which we defined in a previous work, in terms of the preservation of equality of theories in fragments of first order logic with bounded number of variables, but without counting quantifiers (FOk). Finally, we give a characterization of the layers of the two hierarchies in terms of the infinitary logics CK∞ω and LK∞ω respectively.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 2006
Volume: 17
Number: 3
ISSN: 0324-721X
Page Range: pp. 485-511
Language: English
Place of Publication: Szeged
Related URLs: http://acta.bibl.u-szeged.hu/38521/
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: p. 509-511. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:25
Last Modified: 2022. Jun. 16. 10:30
URI: http://acta.bibl.u-szeged.hu/id/eprint/12778

Actions (login required)

View Item View Item