Extension de capture SQL

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.) $\mathsf{Q(FO(COUNT))}$ $\mathsf{Q(FO(COUNT))}$ $\mathsf{Q(FO(COUNT))}$

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 $\mathsf{P}$ (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? $\mathsf{P}$

database-theory complexity-theory finite-model-theory descriptive-complexity Kaveh
la source

@JD, désolé, mais sur la base de votre commentaire, je pense que vous ne comprenez pas la question. La question est bien définie. La capture d'une classe de complexité par un langage est une terminologie standard. (ce qui n'est pas bien défini est ma préférence pour que la langue soit une langue de requête, mais ce n'est qu'une préférence et je vous ai dit que je serais d'accord avec une langue qui ne l'est pas s'il n'y en a pas avec cette préférence.)

Kaveh

@ Shog9, j'ai déjà répondu à cela. JD ne comprend pas la question, il ne savait même pas ce que signifie la capture et ne sait pas qu'un langage capturant P ne peut pas être Turing complet par définition. Il s'attend à ce qu'il soit énoncé comme il l'aime, je l'ai énoncé dans la terminologie de complexité descriptive habituelle et la complexité des langages de requête, et je lui ai même expliqué cela. Qu'est-ce qui n'est pas clair ici?

Kaveh

@ Shog9, la motivation vient de la complexité descriptive . J'essaie de voir s'il existe un langage d'extension SQL utilisé dans l'industrie qui capture P. Le langage SQL d'origine est plutôt faible comme le montre le résultat d'Immermann, du point de vue théorique, de nombreux calculs efficaces sont impossibles à énoncer. D'un autre côté, nous aimerions garder le langage efficace (ie ). Existe-t-il une telle langue? (Je pense que ceux-ci sont probablement clairs pour les personnes familiarisées avec la complexité descriptive).

P

$\mathsf{P}$

Kaveh

@ Shog9: Je ne vois pas pourquoi cette question a nécessité une intervention du modérateur et a été fermée. Je suis assez à l'aise avec la complexité descriptive pour dire que c'est une vraie question (bien qu'elle soit peut-être mieux adaptée au TCS - c'est un peu une question difficile).

Alex ten Brink

Comme j'ai remarqué qu'une autre question a également été fermée (qui avait également des votes serrés), j'ai posé une question sur meta à ce sujet: meta.cs.stackexchange.com/questions/97/…

Alex ten Brink

Réponses:

Quant à votre question principale, je recommande cette courte enquête de Martin Grohe.

Les requêtes qui sont nécessaires dans la pratique sont-elles généralement assez simples pour qu'il n'y ait pas besoin d'un langage plus fort?

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).

Janoma
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".

Leonid Libkin. Puissance expressive de SQL , TCS 296 (3), 379–404. doi: 10.1016 / S0304-3975 (02) 00736-3 ( préimpression )

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.) $\text{TC}^0 \subsetneq \text{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 . $\text{P} \ne \text{NP}$

Martin Grohe, La quête d'une logique capturant PTIME , LICS 2008, 267-271. doi: 10.1109 / LICS.2008.11 ( préimpression )

András Salamon
la source

Merci András, surtout pour avoir mentionné que SQL3 supporte la "récursivité", je dois vérifier et voir ce que l'on sait à ce sujet. :)

Kaveh

ps: Je suppose que vous avez inclus la discussion sur la relation avec la théorie de la complexité et la logique de capture de P pour les lecteurs, mais permettez-moi d'ajouter une note latérale et pour des éclaircissements: j'utilise SQL dans le sens où Immerman l'a utilisé dans le résultat et result utilise une définition précise de SQL. Je connais les relations avec les séparations de classes de complexité et la question d'une logique capturant P, mais je ne pense pas qu'elles affectent la réponse à ma question,

Kaveh

la réponse à ma question peut être positive (ou négative) et elles seraient cohérentes avec toutes les réponses possibles à P vs NP et à l'existence d'une logique invariante d'ordre pour P.

Kaveh

Kaveh, si vous définissez SQL comme Immerman l'a fait, alors je pense que la réponse est "probablement non", car les extensions industrielles existantes semblent être soit trop faibles, soit trop puissantes. Mais (AFAIK) nous n'avons aucune preuve rigoureuse pour cela. Peut-être qu'un sous-ensemble des extensions capture précisément PTIME, mais je ne suis pas sûr que je voudrais parcourir les spécifications en essayant de l'isoler ...

András Salamon

-1

$P$ $P$ $P$ $P$ $P$

$P = NP$ $P = NP$ $P$ $P$ $NPC$

$P \ne NP$

$P = NP$

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.

Victor Stafusa
la source

F O

$\mathsf{FO}$

A C^{0}

$\mathsf{AC^0}$

N P

$\mathsf{NP}$

P

$\mathsf{P}$

P

$\mathsf{P}$

F O (L F P)

$\mathsf{FO(LFP)}$ $\mathsf{P}$