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