Langages de requête de base de données pour des requêtes efficaces

9

Il semble que dans les langages de requête populaires pour les bases de données relationnelles, il est possible de créer des requêtes qui nécessiteront beaucoup de ressources pour répondre. En pratique, les administrateurs de base de données gèrent cela en limitant la quantité de mémoire par requête et en recherchant les requêtes de longue durée en cas de ralentissement dans la base de données. Cela semble plutôt ponctuel, existe-t-il une solution TCS à cela?

Existe-t-il des langages de requête qui ne peuvent implémenter que des requêtes efficaces?

S'il n'y a pas de telles langues, y a-t-il une raison théorique à cela?

Certaines raisons pour lesquelles je pourrais m'attendre à ce que ce genre de choses existent ou au moins aient un sens:

  • nous avons des langages de programmation qui sont spécifiquement conçus pour implémenter uniquement des calculs efficaces (généralement en ayant une logique restrictive dans leur système de type)
  • les langages de requête populaires (tels que SQL) sont déjà inspirés par la logique, il ne semble donc pas exagéré pour les utilisateurs de bases de données de considérer des logiques plus restrictives.
  • un utilisateur de base de données non malveillant essaie déjà de préparer des requêtes qui s'exécutent rapidement, nous devons donc nous attendre à ce que ces langages de requête plus restrictifs ne gênent que les utilisateurs malveillants.

Cette question est inspirée de l'intersection de deux questions précédentes:

Langages de programmation pour un calcul efficace

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

cc.complexity-theory pl.programming-languages db.databases finite-model-theory Artem Kaznatcheev
la source
1
N'est-ce pas exactement le sujet de la complexité descriptive? ils ont des caractérisations de langage des requêtes pour diverses classes de complexité.
Kaveh
La complexité descriptive est certainement une partie énorme et un guide pour les langages de programmation pour un calcul efficace. Mais je ne pense pas que ce soit aussi simple que de dire "la complexité descriptive utilise la logique" et "les requêtes vers les bases de données utilisent la logique". En particulier, pour DC, il semble que la taille de la requête soit fixe et le «n» provient des tailles des structures finies acceptées par ces requêtes. Dans les bases de données, c'est vraiment la taille de la requête qui est variable et la base de données est également variable ou peut-être un paramètre fixe.
Artem Kaznatcheev
3
il existe également des résultats pour les requêtes variables, ils ne sont tout simplement pas aussi étonnants que la correspondance entre la vérification de modèle et les classes de complexité bien connues. Le domaine plus large de la théorie des modèles finis, dont la complexité descriptive fait partie, a également un certain nombre de résultats d'expressibilité directement liés aux bases de données. Les bases de données sont après tout des structures théoriques de modèle presque exactement finies.
Marc Hamann
1
Je n'ai pas pensé à cette correspondance. J'ai ajouté la balise de théorie des modèles finis. Si vous ou @Kaveh souhaitez approfondir vos commentaires et savoir comment adopter des résultats spécifiques de la complexité descriptive de la théorie des modèles finis en général pour produire de tels langages de requête, alors j'aimerais vraiment voir cette réponse!
Artem Kaznatcheev

Réponses:

7

Une façon d'examiner les langages de requête de base de données est à travers la lentille des bases de données déductives , où les requêtes sont représentées comme des programmes logiques. Dans ce cadre, le travail le plus pertinent lié à votre question est l'analyse de la complexité des analyses statiques de McAllester , qui a observé que vous pouvez raisonner sur le temps d'exécution d'une requête en raisonnant sur le nombre de "cuissons de préfixe" dans les règles de votre programme. Qu'est-ce qu'un "tir de préfixe" n'est pas terriblement compliqué, mais je vous renvoie à l'article pour cela.

Dans le monde de la programmation fonctionnelle, ce genre de chose s'appelle une sémantique des coûts : cela ne signifie pas que vous pouvez uniquement implémenter des requêtes (programmes) efficaces, mais cela signifie que vous pouvez raisonner de manière raisonnable sur la complexité asymptotique de votre programme déclaratif. .

Certains travaux ultérieurs sur la mise en œuvre des idées de McAllester incluent De règles de journal de données à des programmes efficaces avec des garanties de temps et d'espace (Liu et Stoller) et Dedalus: Journal de données dans le temps et l'espace (Alvaro, Marczak, Conway, Hellerstein, Maier et Sears). J'avoue cependant que je n'ai pas encore lu le dernier de ces deux articles.

Rob Simmons
la source