Selon Immerman , la classe de complexité associée aux requêtes SQL est exactement la classe des requêtes sécurisées dans (requêtes de premier ordre plus opérateur de comptage): SQL capture les requêtes sécurisées. (En d'autres termes, toutes les requêtes SQL ont une complexité dans , et tous les problèmes dans peuvent être exprimés comme une requête SQL.)Q ( F O ( C O U N T ) ) Q ( F O ( C O U N T ) )
Sur la base de ce résultat, d'un point de vue théorique, il existe de nombreux problèmes intéressants qui peuvent être résolus efficacement mais ne sont pas exprimables en SQL. Une extension de SQL encore efficace semble donc intéressante. Voici donc ma question:
Existe-t-il une extension de SQL (implémentée et utilisée dans l'industrie ) qui capture (c'est-à-dire qui peut exprimer toutes les requêtes calculables en temps polynomial et aucune autre)?
Je veux un langage de requête de base de données qui remplit les trois conditions. Il est facile de définir une extension qui étendrait SQL et capturerait . Mais ma question est de savoir si une telle langue a un sens du point de vue pratique, donc je veux une langue qui est utilisée dans la pratique. Si ce n'est pas le cas et qu'il n'y a pas un tel langage, alors je voudrais savoir s'il y a une raison qui rend un tel langage inintéressant du point de vue pratique? Par exemple, les requêtes qui augmentent dans la pratique sont-elles généralement assez simples pour qu'il n'y ait pas besoin d'une telle langue?
Réponses:
Quant à votre question principale, je recommande cette courte enquête de Martin Grohe.
Je dirais que cela tient la plupart du temps, étant donné la quantité d'extensions ajoutées aux langages de requête courants (fermeture transitive, opérateurs arithmétiques, comptage, etc.). Cela vient du point de vue de quelqu'un qui a fait du travail en tant que développeur indépendant de sites Web relativement simples et d'autres applications, donc je ne suis pas sûr des utilisations réelles de SQL dans de plus grandes industries / bases de données plus grandes.
Dans les rares cas, un langage plus puissant pourrait être nécessaire, je suppose que les développeurs de logiciels les traitent en utilisant le langage dans lequel ils écrivent l'application, pas les requêtes (comme C ++ ou java).
la source
Premièrement, la puissance expressive de SQL est moins claire qu'il n'y paraît. Les fonctionnalités d'agrégation, de regroupement et d'arithmétique de SQL s'avèrent avoir des effets assez subtils. A priori, il semble possible que par un certain encodage d'opérateurs algébriques utilisant ces fonctionnalités, on puisse réellement exprimer l'accessibilité en SQL. Il s'avère que ce n'est pas le cas pour SQL-92 , qui est "local".
Cela signifie qu'une extension est requise pour que SQL-92 capture PTIME, et une extension permettant au langage résultant d'être "non local".
Cependant, autoriser des structures ordonnées et avec une arithmétique réaliste limitée, prouver que SQL-92 ne peut pas exprimer l'accessibilité impliquerait que et est donc susceptible d'être assez difficile. (On pourrait faire valoir qu'un ordre linéaire naturel existe toujours sur les types de données dans SQL-92, et que l'on pourrait donc supposer que les structures sous-jacentes sont ordonnées.)TC0⊊ NLOGSPACE
Le paysage a ensuite changé à nouveau, car SQL: 1999 (SQL3) incluait la récursivité. Ainsi, SQL: 1999 semble être au moins aussi expressif que la logique à virgule fixe avec le comptage (bien que je pense que les détails pourraient encore être assez délicats, y compris la question de l'ordre). Je ne sais pas si les nouvelles constructions ont rendu la logique plus expressive qu'il n'est nécessaire pour capturer PTIME, et une étude serait nécessaire pour établir cela. Entre-temps, de nouvelles révisions ont été apportées en 2003 , 2006 , 2008 et 2011(étant des documents ISO, seuls les projets sont librement disponibles). Ces révisions ont ajouté toute une série de nouvelles fonctionnalités, notamment l'autorisation de XQuery comme «partie» des requêtes SQL. Je suppose que "SQL" est maintenant plus expressif que ce qui est nécessaire pour capturer PTIME, mais que l'encodage requis pour ce faire pourrait nécessiter des requêtes volumineuses et peu naturelles qui pourraient ne pas être prises en charge dans les systèmes réels.
Je pense donc qu'il y a des preuves qu'il n'y a pas d'extension industrielle de SQL qui capture précisément PTIME , répondant à votre question de manière floue. Bref, les extensions industrielles sont assez puissantes et peuvent déjà avoir dépassé PTIME. S'il est vrai que SQL: 1999 est déjà suffisamment puissant pour capturer au moins PTIME, alors il n'est pas clair non plus ce que "SQL" signifie vraiment dans votre question, car il faudrait définir "SQL" pour signifier une version antérieure à SQL: 1999.
Enfin, l'enquête de Grohe sur la recherche de logiques capturant PTIME (également mentionnée par Janoma) indique non seulement que la capture de PTIME est délicate à moins que nous ayons un ordre linéaire dans le langage, mais qu'une preuve qu'il ne pourrait y avoir une telle logique serait également implique .P ≠ NP
la source
Bien qu'il n'existe probablement pas à des fins réelles, il existe sûrement et est constructible et réalisable. Vous pouvez définir ce langage avec quelque chose capable de simuler une machine de Turing jusqu'à un nombre unaire donné d'étapes. IE, capable de résoudre un problème P-complet . Cependant, si vous construisez une telle chose, c'est presque Turing-complete, sauf pour la restriction "étant donné un nombre unaire d'étapes", qui dans un langage de type SQL serait une façon très étrange de la limiter aux seules requêtes sécurisées. Vous pouvez le faire si les étapes sont des enregistrements d'une table, mais cela ne semble toujours pas utile pour des raisons pratiques.
la source