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

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 | .$Q$$D$$|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|$$n$$n$$n$

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.

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

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.

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.

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.