Pourquoi les bases de données relationnelles fonctionnent-elles du tout, étant donné la complexité exponentielle théorique de la recherche de réponses (dans la taille de la requête)?

19

Il semble connu que pour trouver une réponse à une requête sur une base de données relationnelle D , il faut du temps | D | | Q | , et on ne peut pas se débarrasser de l'exposant | Q | .QD|D||Q||Q|

Comme peut être très volumineux, nous nous demandons pourquoi les bases de données fonctionnent dans la pratique.D

S'agit-il simplement du fait que les requêtes habituelles ne sont pas du tout importantes dans les applications du monde réel? (Ensuite, il est intéressant de savoir quelle est la taille habituelle des requêtes posées aux systèmes de bases de données relationnelles, et quelle est la taille "maximale" des requêtes qui devraient être effectivement répondues par un système DB dans la pratique .)

Notes sur l'exposant pas «amovible»|Q|

Pour montrer que l'exposant n'est pas amovible, on peut utiliser une requête demandant s'il existe une clique de taille n dans le graphe donné par la base de données. Vérifier si un graphe a une n -clique est un problème NP-complet. De plus, il n'est pas traitable à paramètre fixe, avec le paramètre n . Des détails peuvent être trouvés dans, par exemple, Libkin, L.: Elements Of Finite Model Theory. Springer (2004) ou Papadimitriou, CH, Yannakakis, M .: Sur la complexité des requêtes de bases de données. J. Comput. Syst. Sci. 58 (3), 407–427 (1999)|Q|nnn


imz - Ivan Zakharyaschev
la source
7
Les requêtes ordinaires (comme SELECT * FROM users WHERE username="abc" AND passwrod="xyz") sont de simples recherches qui nécessitent l'exécution de O (| D |). S'il y a un index sur les champs de base de données pertinents, cela prendra O (log | D |). Je ne suis pas dans les bases de données, mais je ne pense pas que les requêtes plus compliquées prendraient un temps exponentiel.
MS Dousti
7
O(|D|2)O(|D|k+1)
7
La complexité temporelle est exponentielle dans la longueur d'une requête dans le pire des cas . Cela ne contredit pas que certaines longues requêtes sont rapides. Les praticiens de la base de données savent quelles requêtes s'exécutent rapidement dans les moteurs de base de données typiques, et ils ne s'appuient pas sur le pire des cas en termes de longueur de la requête.
Tsuyoshi Ito le
2
@Kaveh: "Le livre de la complexité descriptive d'Immerman a eu une petite discussion au dernier chapitre": Très bonne suggestion. Nitpicking: Il est discuté dans l'avant-dernier chapitre. @imz: Le document Expressive Power of SQL peut également vous être utile.
MS Dousti
5
@imz: "Ce graphique a-t-il une n-clique" n'est pas une requête courante dans la pratique. La plupart des requêtes ressemblent davantage à celles suggérées par @Sadeq et ont une structure fortement arborescente. De plus, pour des bases de données très volumineuses, même une requête complètement linéaire est trop coûteuse, et il faut travailler avec un croquis de la base de données.
András Salamon,

Réponses:

16

Il existe de grandes classes de requêtes qui sont "faciles", même dans le pire des cas. En particulier, si la classe de requêtes contient uniquement des requêtes conjonctives et que chaque requête a une largeur limitée (par exemple, la largeur d'arbre, la largeur d'arbre de son graphique d'incidence, la largeur d'hypertree fractionnaire ou la largeur sous-modulaire), il est possible de répondre à la requête en utilisant quelque chose comme un arbre de jointure , ainsi qu'une énumération par force brute pour les parties locales de la requête qui s'écartent de l'arborescence. Cela nécessite un temps polynomial, le degré du polynôme étant déterminé par le paramètre de largeur.

Il semble que de nombreuses requêtes rencontrées dans la pratique soient à la fois conjonctives et de faible largeur. Le runtime polynomial a donc un faible degré dans ce cas.

Récemment, Dániel Marx a présenté un article au STOC 2010 sur la largeur sous-modulaire, dont la version complète comprend un joli résumé des différentes notions de largeur et comment la formulation du CSP se rapporte au formalisme de la base de données (la version de conférence manque).

  • Dániel Marx, Propriétés hypergraphiques tractables pour la satisfaction des contraintes et les requêtes conjonctives , 2010. arxiv: 0911.0801

Ce n'est pas une réponse complète, car elle ne traite pas de la complexité "typique" des requêtes de base de données, mais même avec l'analyse du pire des cas, il existe des requêtes faciles.

András Salamon
la source
6

On peut utiliser les requêtes Q_n pour vérifier si un graphe, représenté comme une base de données, contient une clique à n éléments. Vérifier si un graphique a une clique est un problème NP-complet. De plus, il n'est pas traitable à paramètre fixe, avec le paramètre n (ce qui signifie D ^ n).

mésaventure
la source
Veuillez poster des explications supplémentaires concernant l'arrière-plan de la question soit sous forme de "commentaire" (pas de "réponse") - avec le bouton "Ajouter un commentaire" sous la question, soit sous forme de suggestion de modification - avec le lien "modifier" ci-dessous la question. Les "réponses" ne sont destinées à aucune discussion ni aucun ajout à la question. (Participer ici devrait être plus pratique si vous vous inscrivez en tant qu'utilisateur non anonyme; il est alors plus facile de suivre qui a dit quoi dans les discussions.)
imz - Ivan Zakharyaschev
@imz: Il l'a mis comme réponse car il n'a pas le privilège de commenter. Il faut avoir au moins 50 représentants. pour pouvoir commenter partout.
Tomek Tarczynski
@Tomek, @imz, eh bien, il est en cours de discussion sur la méta pour le moment si nous devrions autoriser les commentaires en utilisant des réponses ou non.
Kaveh
5

Une autre façon de répondre à cette question est "ils ne le font pas!"

Si vous donnez à une implémentation de SGBD typique une requête contenant un très grand nombre de jointures, elle ne dépassera même pas la phase de planification / optimisation (sans parler d'évaluation), même si la requête est acyclique ou a une structure très simple telle que András fait allusion à ce qui précède.

Mais, pour les charges de travail SGBD "typiques", de telles requêtes semblent ne pas se produire.

tjgreen
la source
1
Pour les requêtes complexes, le résultat de la phase d'optimisation est un plan choisi au hasard. Ce n'est pas aussi mauvais qu'il y paraît, car le chemin d'exécution peut toujours être "assez bon", et il existe de nombreuses autres raisons pour lesquelles l'optimisation est difficile au-delà de la combinatoire du nombre de jointures.
Tegiri Nenashi
4

Voici une version plus réaliste de la réponse de tigreen du point de vue d'une personne qui fait un usage intensif des bases de données (relationnelles): L'intérêt et la complexité de leur application sont de les structurer de manière à ce qu'ils nécessitent aussi peu de se joint pour chaque requête toujours nécessaire que possible et qui est la raison pour laquelle ils ont fait faire un travail . En d'autres termes, ne vous attendez pas à ce que les bases de données résolvent vous-même des problèmes complexes - elles ne le feraient pas, mais si elles sont utilisées à bon escient, elles constituent un instrument vraiment pratique et applicable.

quiconque
la source
0

Les jointures ne sont que quadratiques sur des relations plusieurs-à-plusieurs. Celles-ci sont relativement rares: dans la pratique, la plupart des relations et des jointures sont de 1 à plusieurs, elles prendront donc un temps linéaire si des index / clés sont définis. Les requêtes avec plusieurs jointures plusieurs-à-plusieurs sont un problème sérieux.

reinierpost
la source