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]
Előnézet
Cikk, tanulmány, mű
Turull_2006_ActaCybernetica.pdf

Letöltés (241kB) | Előnézet

Absztrakt (kivonat)

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.

Mű típusa: Cikk, tanulmány, mű
Befoglaló folyóirat/kiadvány címe: Acta cybernetica
Dátum: 2006
Kötet: 17
Szám: 3
ISSN: 0324-721X
Oldalak: pp. 485-511
Nyelv: angol
Kiadás helye: Szeged
Befoglaló mű URL: http://acta.bibl.u-szeged.hu/38521/
Kulcsszavak: Számítástechnika, Kibernetika
Megjegyzések: Bibliogr.: p. 509-511. ; összefoglalás angol nyelven
Szakterület: 01. Természettudományok
01. Természettudományok > 01.02. Számítás- és információtudomány
Feltöltés dátuma: 2016. okt. 15. 12:25
Utolsó módosítás: 2022. jún. 16. 10:30
URI: http://acta.bibl.u-szeged.hu/id/eprint/12778
Bővebben:
Tétel nézet Tétel nézet