L-rigid Databases and the Expressibility of Incomplete Relational Query Languages

The class of Computable Queries (CQ) was de ned by Chandra and Harel in 1980, as functions on structures rather than functions on numbers (as recursive functions). With this formulation of the notion of a query to a relational database (db), the field of Finite Model Theory became a suitable theore...

Descripción completa

Detalles Bibliográficos
Autor principal: Turull Torres, José María
Formato: Articulo Contribucion a revista
Lenguaje:Inglés
Publicado: 1998
Materias:
Ciencias Informáticas
Computable Queries
Finite Model Theory
relational database
relational languages
Acceso en línea:http://sedici.unlp.edu.ar/handle/10915/135589
https://publicaciones.sadio.org.ar/index.php/EJS/article/view/138
Aporte de:
SEDICI (UNLP) de Universidad Nacional de La Plata
id I19-R120-10915-135589
record_format dspace
institution Universidad Nacional de La Plata
institution_str I-19
repository_str R-120
collection SEDICI (UNLP)
language Inglés
topic Ciencias Informáticas
Computable Queries
Finite Model Theory
relational database
relational languages
spellingShingle Ciencias Informáticas
Computable Queries
Finite Model Theory
relational database
relational languages
Turull Torres, José María
L-rigid Databases and the Expressibility of Incomplete Relational Query Languages
topic_facet Ciencias Informáticas
Computable Queries
Finite Model Theory
relational database
relational languages
description The class of Computable Queries (CQ) was de ned by Chandra and Harel in 1980, as functions on structures rather than functions on numbers (as recursive functions). With this formulation of the notion of a query to a relational database (db), the field of Finite Model Theory became a suitable theoretical framework for relational databases. In this framework the notion of local expressibility of a given logic is the class of queries which can be expressed in that logic. On the other hand, in 1991, Abiteboul and Vianu de fined the Generic Machine, denoted as GMloose, which they proved to be strictly included in CQ. They also proved that this class of machines behaves as complete w.r.t. the whole class CQ when working on classes of ordered db. If we consider the structures as db instances, and if we are using a GMloose machine, it means that we will not be able to compute queries such as \give me the names of the salesmen who sell to an even number of clients unless our db is ordered. In the present Thesis, we study some properties of relational db which can increase the expressive power of relational languages or formalisms which are incomplete in the general case, when working on classes of db which satisfy that properties.
format Articulo
Contribucion a revista
author Turull Torres, José María
author_facet Turull Torres, José María
author_sort Turull Torres, José María
title L-rigid Databases and the Expressibility of Incomplete Relational Query Languages
title_short L-rigid Databases and the Expressibility of Incomplete Relational Query Languages
title_full L-rigid Databases and the Expressibility of Incomplete Relational Query Languages
title_fullStr L-rigid Databases and the Expressibility of Incomplete Relational Query Languages
title_full_unstemmed L-rigid Databases and the Expressibility of Incomplete Relational Query Languages
title_sort l-rigid databases and the expressibility of incomplete relational query languages
publishDate 1998
url http://sedici.unlp.edu.ar/handle/10915/135589
https://publicaciones.sadio.org.ar/index.php/EJS/article/view/138
work_keys_str_mv AT turulltorresjosemaria lrigiddatabasesandtheexpressibilityofincompleterelationalquerylanguages
bdutipo_str Repositorios
_version_ 1764820455496089601

Ejemplares similares