SQL ou même TSQL Turing est-il complet?

Question

Ceci est arrivé au bureau aujourd'hui. Je n'ai pas l'intention de faire une telle chose, mais théoriquement, pourriez-vous écrire un compilateur en SQL? À première vue, il me semble être complet, bien qu’extrêmement lourd pour de nombreuses catégories de problèmes.

Si ce n'est pas complet, que faudrait-il pour le devenir?

Note: Je n'ai aucun désir de faire quelque chose comme écrire un compilateur en SQL, je sais que ce serait une chose stupide à faire, donc si nous pouvons éviter cette discussion, je l'apprécierais.

Answer 1

Il s'avère que SQL peut être Turing, même sans une véritable "script" extension comme le PL/SQL ou PSM (qui sont conçus pour être vrai langages de programmation, c'est un peu de la triche).

Dans cette série de diapositives Andrew Gierth prouve qu'avec de la CCE et le Fenêtrage SQL Turing, par la construction d'une cyclique système de tag, qui a été prouvé pour être Turing. Le CTE fonction est le plus important, néanmoins, il vous permet de créer nommé sous-expressions qui peuvent se référer à eux-mêmes, et de ce fait de manière récursive à résoudre les problèmes.

La chose intéressante à noter est que le CCE n'a pas vraiment été ajouté à tour de SQL dans un langage de programmation -- de mettre simplement déclaratif langage d'interrogation dans un plus puissant déclarative langage d'interrogation. Un peu comme en C++, dont le modèle s'est avéré être Turing même s'ils n'ont pas pour but de créer un méta-langage de programmation.

Oh, l' ensemble de Mandelbrot dans SQL exemple est très impressionnant, aussi bien :)

Answer 2

http://channel9.msdn.com/forums/TechOff/431432-SQL-Turing-Completeness-question/

Est une discussion à ce sujet.

Une citation:

SQL en tant que tel (c'est à dire le standard SQL92) n'est pas turing. Cependant, la plupart des langues du dérivé de SQL, tels que Oracle PL/SQL et SQL Server T-SQL et les autres sont de turing.

PL/SQL et T-SQL certainement qualifier que les langages de programmation, si SQL92 lui-même qualifie le débat est ouvert. Certaines personnes prétendent que n'importe quel morceau de code qui indique à l'ordinateur que faire se qualifie comme un langage de programmation; par cette définition SQL92 est un, mais si, par exemple, est HTML. La définition est assez vague, et c'est de l'omi, une chose inutile d'argumenter.

Answer 3

À proprement parler, SQL est maintenant un langage complet, car le dernier standard SQL inclut les «modules mémorisés persistants» (PSM). En bref, un PSM est la version standard du langage PL / SQL sous Oracle (et d’autres extensions procédurales similaires du SGBD actuel).

Avec l’inclusion de ces PSM, SQL est devenu complet

Answer 4

Une instruction de sélection ANSI, telle que définie à l'origine dans SQL-86, n'est pas terminée car elle se termine toujours (sauf pour les CTE récursifs et uniquement si l'implémentation prend en charge la récursivité arbitraire). Il n'est donc pas possible de simuler une autre machine de turing. Les procédures stockées sont complètes mais c'est de la triche ;-)