The computational completeness of extended database query languages
- 1 May 1989
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Software Engineering
- Vol. 15 (5) , 632-638
- https://doi.org/10.1109/32.24712
Abstract
The computational completeness is demonstrated of certain extended database query languages, namely, POSTGRES and GENESIS, and a language defined by A. Aho and J. Ullman (1979). The method used is to implement a Turing machine interpreter in each of the languages. These query languages were defined as extensions to traditional database languages in order to encompass certain specific new applications. Results show that these extensions have already encompassed all the computational power of any programming language.Keywords
This publication has 8 references indexed in Scilit:
- Extensions to query languages for graph traversal problemsIEEE Transactions on Knowledge and Data Engineering, 1990
- Probe: A Knowledge-Oriented Database Management SystemPublished by Springer Nature ,1986
- Extending the Scope of Relational LanguagesIEEE Software, 1986
- Logic and Databases: A Deductive ApproachACM Computing Surveys, 1984
- Structure and complexity of relational queriesJournal of Computer and System Sciences, 1982
- Universality of data retrieval languagesPublished by Association for Computing Machinery (ACM) ,1979
- Flow diagrams, turing machines and languages with only two formation rulesCommunications of the ACM, 1966
- Computability and λ-definabilityThe Journal of Symbolic Logic, 1937