Warum funktionieren relationale Datenbanken angesichts der theoretisch exponentiellen Komplexität der Antwortfindung überhaupt?

19

Es scheint bekannt zu sein , dass eine Antwort auf eine Frage zu finden über eine relationale Datenbank D , eine Zeit braucht | D | | Q | , und man kann den Exponenten | nicht loswerden Q | .QD|D||Q||Q|

Da sehr groß sein kann, fragen wir uns, warum Datenbanken in der Praxis überhaupt funktionieren.D

Geht es nur darum, dass die üblichen Abfragen in den realen Anwendungen überhaupt nicht groß sind? (Dann ist es interessant zu wissen, wie groß die bei relationalen Datenbanksystemen üblichen Abfragen sind und wie hoch die "maximale" Größe der Abfragen ist, die von einem DB-System in der Praxis voraussichtlich effektiv beantwortet werden können .)

Hinweise zum Exponenten nicht "entfernbar"|Q|

Um zu zeigen, dass der Exponent ist nicht entfernbar, kann eine Abfrage verwendet werden, ob in der von der Datenbank angegebenen Grafik eine Clique der Größe n vorhanden ist . Zu überprüfen, ob ein Graph eine Klasse hat, ist ein NP-vollständiges Problem. Darüber hinaus ist es mit dem Parameter nicht fest parametrierbar . Details finden sich zB in Libkin, L .: Elements Of Finite Model Theory. Springer (2004) oder Papadimitriou, CH, Yannakakis, M .: Zur Komplexität von Datenbankabfragen. J. Comput. Syst. Sci. 58 (3), 407–427 (1999)|Q|nnn


imz - Ivan Zakharyaschev
quelle
7
Gewöhnliche Abfragen (wie SELECT * FROM users WHERE username="abc" AND passwrod="xyz") sind einfache Suchen, für deren Ausführung O (| D |) erforderlich ist. Wenn es einen Index für relevante Datenbankfelder gibt, wird O (log | D |) verwendet. Ich mag keine Datenbanken, aber ich glaube nicht, dass kompliziertere Abfragen exponentiell viel Zeit in Anspruch nehmen würden.
MS Dousti
7
@imz: In Ihrem Beispiel ist die Komplexität , was immer noch ein Polynom ist. Es scheint, dass, wenn es k Verknüpfungen in der Abfrage gibt, die Komplexität O ( | D | k + 1 ) ist . Dies ist ein Polynom für festes k, aber ich denke, für großes k ist das Ausführen der Abfrage in der Praxis sehr langsam. Daher muss man um jeden Preis zu viele Joins vermeiden. O(|D|2)O(|D|k+1)
MS Dousti
7
Die zeitliche Komplexität ist im ungünstigsten Fall exponentiell für die Länge einer Abfrage . Dies widerspricht nicht, dass einige lange Abfragen schnell sind. Datenbank-Experten wissen, welche Abfragen in typischen Datenbank-Engines schnell ausgeführt werden, und sie verlassen sich sowieso nicht auf den Worst-Case, der in Bezug auf die Länge der Abfrage festgelegt ist.
Tsuyoshi Ito
2
@Kaveh: "Immermans Buch Descriptive Complexity hatte im letzten Kapitel eine kleine Diskussion": Sehr guter Vorschlag. Nitpicking: Es wird im vorletzten Kapitel besprochen. @imz: Möglicherweise ist auch das Papier Expressive Power of SQL hilfreich.
MS Dousti
5
@imz: "Hat dieser Graph eine n-Clique" ist eine Abfrage in der Praxis nicht so verbreitet. Die meisten Abfragen ähneln eher den von @Sadeq vorgeschlagenen Abfragen und haben eine stark baumartige Struktur. Außerdem ist für sehr große Datenbanken sogar eine vollständig lineare Abfrage zu teuer, und man muss mit einer Skizze der Datenbank arbeiten.
András Salamon

Antworten:

16

Es gibt große Klassen von Abfragen, die auch im schlimmsten Fall "einfach" sind. Insbesondere, wenn die Klasse von Abfragen nur konjunktive Abfragen enthält und jede Abfrage eine begrenzte Breite hat (z. B. Baumbreite, Baumbreite des Inzidenzdiagramms, gebrochene Hypertree-Breite oder submodulare Breite), kann die Abfrage mit einem Join-Baum beantwortet werden Zusammen mit der Brute-Force-Aufzählung für die lokalen Teile der Abfrage, die vom Baum abweichen. Dies erfordert eine Polynomzeit, wobei der Grad des Polynoms durch den Breitenparameter bestimmt wird.

Es scheint, dass viele in der Praxis auftretende Abfragen konjunktiv sind und eine geringe Breite haben. Die Polynomlaufzeit hat in diesem Fall also einen niedrigen Grad.

Dániel Marx hat kürzlich auf der STOC 2010 einen Artikel über die submodulare Breite vorgestellt, dessen Vollversion eine schöne Zusammenfassung der verschiedenen Breitenbegriffe enthält und wie sich die CSP-Formulierung auf den Datenbankformalismus bezieht (der Konferenzversion fehlt dies).

  • Dániel Marx, Tractable Hypergraph Properties für Constraint-Zufriedenheit und Conjunctive Queries , 2010. arxiv: 0911.0801

Dies ist keine vollständige Antwort, da es sich nicht um die "typische" Komplexität von Datenbankabfragen handelt, sondern auch bei der Worst-Case-Analyse um einfache Abfragen.

András Salamon
quelle
6

Mit den Abfragen Q_n kann geprüft werden, ob ein als Datenbank dargestellter Graph eine Clique mit n Elementen enthält. Zu überprüfen, ob ein Graph eine Clique enthält, ist ein NP-vollständiges Problem. Darüber hinaus ist es mit dem Parameter n (was bedeutet, D ^ n) nicht fest parametrisierbar.

Missgeschick
quelle
Veröffentlichen Sie zusätzliche Erläuterungen zum Hintergrund der Frage entweder als "Kommentar" (keine "Antwort") - mit der Schaltfläche "Kommentar hinzufügen" unter der Frage oder als Bearbeitungsvorschlag - mit dem unten stehenden Link "Bearbeiten" die Frage. "Antworten" sind nicht für Diskussionen und Ergänzungen der Frage. (Die Teilnahme hier sollte bequemer sein, wenn Sie sich als nicht anonymer Benutzer registrieren. Dann ist es einfacher zu verfolgen, wer was in den Diskussionen gesagt hat.)
imz - Ivan Zakharyaschev
@imz: Er hat es als Antwort angegeben, weil er kein Privileg hat, Kommentare abzugeben. Man muss mindestens 50 Wiederholungen haben. überall kommentieren können.
Tomek Tarczynski
@Tomek, @imz, nun, es wird momentan auf der Meta diskutiert , ob wir das Kommentieren mit Antworten erlauben sollen oder nicht.
Kaveh
5

Eine andere Möglichkeit, diese Frage zu beantworten, ist: "Sie tun es nicht!"

Wenn Sie einer typischen DBMS-Implementierung eine Abfrage mit einer sehr großen Anzahl von Verknüpfungen geben, wird die Planungs- / Optimierungsphase (geschweige denn die Auswertung) nicht abgeschlossen, auch wenn die Abfrage azyklisch ist oder auf andere Weise eine sehr einfache Struktur wie z András spielt auf das Obige an.

Bei "typischen" DBMS-Workloads scheinen solche Abfragen jedoch nicht aufzutreten.

tjgreen
quelle
1
Bei komplexen Abfragen ist das Ergebnis der Optimierungsphase zufällig gewählter Plan. Dies ist nicht so schlimm, wie es sich anhört, da der Ausführungspfad möglicherweise immer noch "gut genug" ist und es noch viele weitere Gründe gibt, warum die Optimierung jenseits der Kombinatorik der Anzahl der Verknüpfungen schwierig ist.
Tegiri Nenashi
4

Hier ist eine realitätsbezogenere Version der Antwort von tigreen aus der Sicht einer Person, die tatsächlich (relationale) Datenbanken stark nutzt: Der Sinn und die Komplexität ihrer Anwendung besteht darin, sie so zu strukturieren, dass sie so wenig wie möglich benötigen jede und jeder schließt sich immer benötigte Abfrage wie möglich und deshalb sind sie tatsächlich tun Arbeit . Mit anderen Worten, erwarten Sie nicht, dass Datenbanken komplexe Probleme für Sie selbst lösen - sie würden es nicht tun, aber wenn sie weise eingesetzt werden, sind sie ein wirklich handliches und anwendbares Instrument.

wer auch immer
quelle
0

Joins sind in vielen Beziehungen nur quadratisch. Diese sind relativ selten: In der Praxis sind die meisten Beziehungen und Verknüpfungen 1 zu viele, sodass sie bei der Definition von Indizes / Schlüsseln eine lineare Zeit in Anspruch nehmen. Abfragen mit mehreren Many-to-Many-Joins sind ein ernstes Problem.

reinierpost
quelle