Algebraic and calculus query languages for recursively typed complex objects
type: Item
instance of: scholarly article
title: Algebraic and calculus query languages for recursively typed complex objects
zbMATH Open document ID: 0781.68046
DOI: 10.1016/0022-0000(93)90022-O
author: Richard Hull
author: Jianwen Su
published in: Journal of Computer and System Sciences
publication date: 1993-10-10T00:00:00Z
review text: A theoretical study of the expressive power of algebraic and calculus query languages for complex objects using recursive types is conducted. In a companion paper (in preparation) analogous issues for deductive query languages are explored. The results indicate that recursive types generally increase the power of a language considerably: the algebra with iteration has the power of computable queries and the calculus has the power of an arithmetical hierarchy relativized to generic queries. A technical vehicle called ``domain Turing machine'' is introduced which is useful for proving results about the expressive power of query languages. Several classes of relational queries defined by complexity can be characterized in a natural fashion using a domain Turing machine. The investigation provides a bridge between research on the use of non- recursive complex objects in query languages and research on computable queries.
Mathematics Subject Classification ID: 68P15
zbMATH DE Number: 428586
zbMATH Keywords: recursively typed complex objects
zbMATH Keywords: query languages
MaRDI profile type: Publication
cites work: Datalog extensions for database queries and updates
cites work: Procedural languages for database queries and updates
cites work: A calculus for complex objects
cites work: Q3798291
cites work: Computable queries for relational data bases
cites work: Structure and complexity of relational queries
cites work: A relational model of data for large shared data banks
cites work: On the expressive power of database queries with intermediate types
cites work: Q5592246
cites work: On Database Logic
cites work: Q3798297
cites work: Q3041234
cites work: Extended algebra and calculus for nested relational databases
cites work: Q5573961
full work available at URL: 0022-0000(93)90022-o
OpenAlex ID: W2063323989
Recommended article: Deductive query languages for recursively typed complex objects
Recommended article: Q3735063
Recommended article: Extended algebra and calculus for nested relational databases
Recommended article: A typed, algebraic, computational lambda-calculus
Recommended article: Database query languages embedded in the typed lambda calculus
Recommended article: Algebraic optimization of object-oriented query languages
Recommended article: A Framework for Extended Algebraic Data Types
Recommended article: A Query Language for Formal Mathematical Libraries
Recommended article: Algebraic approach to formalization of deductive query languages
description: scientific article; zbMATH DE number 428586