Datenbankabfragesprachen für effiziente Abfragen

9

Es scheint, dass es in gängigen Abfragesprachen für relationale Datenbanken möglich ist, Abfragen zu erstellen, für deren Beantwortung viele Ressourcen erforderlich sind. In der Praxis verwalten Datenbankadministratoren dies, indem sie die Speichermenge pro Abfrage begrenzen und nach lang laufenden Abfragen suchen, wenn die Datenbank langsamer wird. Dies scheint eher ad-hoc zu sein. Gibt es eine TCS-Lösung dafür?

Gibt es Abfragesprachen, die nur effiziente Abfragen implementieren können?

Wenn es keine solchen Sprachen gibt, gibt es dafür einen theoretischen Grund?

Einige Gründe, warum ich erwarten könnte, dass solche Dinge existieren oder zumindest Sinn machen:

  • Wir haben Programmiersprachen, die speziell dafür entwickelt wurden, nur effiziente Berechnungen zu implementieren (normalerweise durch eine restriktive Logik in ihrem Typsystem).
  • Beliebte Abfragesprachen (wie SQL) sind bereits von der Logik inspiriert, sodass es für Datenbankbenutzer nicht schwierig erscheint, restriktivere Logiken in Betracht zu ziehen.
  • Ein nicht böswilliger Datenbankbenutzer versucht bereits, Abfragen vorzubereiten, die schnell ausgeführt werden. Daher sollten wir erwarten, dass diese restriktiveren Abfragesprachen nur böswillige Benutzer behindern.

Diese Frage ist inspiriert von der Überschneidung zweier vorheriger Fragen:

Programmiersprachen für eine effiziente Berechnung

Warum funktionieren relationale Datenbanken angesichts der theoretischen exponentiellen Komplexität der Antwortfindung (in der Größe der Abfrage) überhaupt?

cc.complexity-theory pl.programming-languages db.databases finite-model-theory Artem Kaznatcheev
quelle
1
Ist das nicht genau das Thema der beschreibenden Komplexität? Sie haben Sprachcharakterisierungen von Abfragen für verschiedene Komplexitätsklassen.
Kaveh
Die beschreibende Komplexität ist definitiv ein großer Teil und Leitfaden für Programmiersprachen für eine effiziente Berechnung. Aber ich denke nicht, dass es so einfach ist zu sagen, dass "beschreibende Komplexität Logik verwendet" und "Abfragen an Datenbanken Logik verwenden". Insbesondere für DC scheint die Abfragegröße fest zu sein und das 'n' ergibt sich aus den Größen endlicher Strukturen, die diese Abfragen akzeptieren. In Datenbanken ist tatsächlich die Abfragegröße variabel, und die Datenbank ist auch variabel oder möglicherweise ein fester Parameter.
Artem Kaznatcheev
3
Es gibt auch Ergebnisse für variable Abfragen. Sie sind einfach nicht so erstaunlich wie die Übereinstimmung zwischen Modellprüfung und bekannten Komplexitätsklassen. Auch das breitere Feld der endlichen Modelltheorie, zu dem die deskriptive Komplexität gehört, weist eine Reihe von Expressibilitätsergebnissen auf, die in direktem Zusammenhang mit Datenbanken stehen. Datenbanken sind schließlich fast genau endliche modelltheoretische Strukturen.
Marc Hamann
1
Ich habe nicht über diese Korrespondenz nachgedacht. Ich habe das endliche Modell-Theorie-Tag hinzugefügt. Wenn Sie oder @Kaveh Ihre Kommentare näher erläutern möchten und wissen möchten, wie Sie bestimmte Ergebnisse aus der deskriptiven Komplexität der endlichen Modelltheorie im Allgemeinen verwenden können, um solche Abfragesprachen zu erstellen, dann würde ich diese Antwort wirklich gerne sehen!
Artem Kaznatcheev

Antworten:

7

Eine Möglichkeit, Datenbankabfragesprachen zu betrachten, besteht in der Linse deduktiver Datenbanken , in denen Abfragen als Logikprogramme dargestellt werden. In dieser Einstellung ist McAllester's On the Complexity Analysis of Static Analysis die relevanteste Arbeit im Zusammenhang mit Ihrer Frage. Dabei wurde festgestellt, dass Sie über die Laufzeit einer Abfrage nachdenken können, indem Sie über die Anzahl der "Präfix-Zündungen" in den Regeln Ihrer Abfrage nachdenken Programm. Was für ein "Präfix-Feuern" ist, ist nicht besonders kompliziert, aber ich werde Sie dafür auf das Papier verweisen.

In der Welt der funktionalen Programmierung wird dies als Kostensemantik bezeichnet : Dies bedeutet nicht, dass Sie nur effiziente Abfragen (Programme) implementieren können, sondern dass Sie die asymptotische Komplexität Ihres deklarativen Programms auf vernünftige Weise begründen können .

Einige spätere Arbeiten zur Umsetzung von McAllesters Ideen umfassen Von Datenloggeregeln zu effizienten Programmen mit Zeit- und Raumgarantien (Liu und Stoller) und Dedalus: Datenlog in Zeit und Raum (Alvaro, Marczak, Conway, Hellerstein, Maier und Sears). Ich gebe jedoch zu, dass ich das letztere dieser beiden Papiere noch nicht gelesen habe.

Rob Simmons
quelle