Relational databases and homogeneity in logics with counting
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...
Elmentve itt :
| Szerző: | |
|---|---|
| Dokumentumtípus: | Cikk |
| Megjelent: |
2006
|
| Sorozat: | Acta cybernetica
17 No. 3 |
| Kulcsszavak: | Számítástechnika, Kibernetika |
| Tárgyszavak: | |
| Online Access: | http://acta.bibl.u-szeged.hu/12778 |
| LEADER | 02086nab a2200217 i 4500 | ||
|---|---|---|---|
| 001 | acta12778 | ||
| 005 | 20220616103029.0 | ||
| 008 | 161015s2006 hu o 0|| eng d | ||
| 022 | |a 0324-721X | ||
| 040 | |a SZTE Egyetemi Kiadványok Repozitórium |b hun | ||
| 041 | |a eng | ||
| 100 | 2 | |a Turull Torres José María | |
| 245 | 1 | 0 | |a Relational databases and homogeneity in logics with counting |h [elektronikus dokumentum] / |c Turull Torres José María |
| 260 | |c 2006 | ||
| 300 | |a 485-511 | ||
| 490 | 0 | |a Acta cybernetica |v 17 No. 3 | |
| 520 | 3 | |a 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. | |
| 650 | 4 | |a Természettudományok | |
| 650 | 4 | |a Számítás- és információtudomány | |
| 695 | |a Számítástechnika, Kibernetika | ||
| 856 | 4 | 0 | |u http://acta.bibl.u-szeged.hu/12778/1/Turull_2006_ActaCybernetica.pdf |z Dokumentum-elérés |