Erweiterung der SQL-Erfassung

20

Laut Immerman ist die mit SQL- Abfragen verbundene Komplexitätsklasse genau die Klasse der sicheren Abfragen in (Abfragen erster Ordnung plus ): SQL erfasst sichere Abfragen. (Mit anderen Worten, alle SQL-Abfragen haben eine Komplexität in , und alle Probleme in können als SQL-Abfrage ausgedrückt werden.)Q(FO(COUNT))Q(FO(COUNT))Q(FO(COUNT))

Basierend auf diesem Ergebnis gibt es aus theoretischer Sicht viele interessante Probleme, die effizient gelöst werden können, aber in SQL nicht zum Ausdruck gebracht werden können. Interessant erscheint daher eine noch leistungsfähige Erweiterung von SQL. Also hier ist meine Frage:

Gibt es eine SQL-Erweiterung ( die in der Branche implementiert und verwendet wird ), die erfasstP (dh alle polynomiell berechenbaren Abfragen und keine anderen ausdrücken kann)?

Ich möchte eine Datenbank-Abfragesprache, die alle drei Bedingungen erfüllt. Es ist einfach, eine Erweiterung zu definieren, die SQL erweitert und . Meine Frage ist jedoch, ob eine solche Sprache aus praktischer Sicht sinnvoll ist, und ich möchte eine Sprache, die in der Praxis verwendet wird. Wenn dies nicht der Fall ist und es keine solche Sprache gibt, würde ich gerne wissen, ob es einen Grund gibt, der eine solche Sprache aus praktischer Sicht uninteressant macht. Sind beispielsweise die in der Praxis auftretenden Fragen in der Regel so einfach, dass eine solche Sprache nicht benötigt wird?P

Kaveh
quelle
1
@JD, sorry, aber basierend auf deinem Kommentar denke ich, dass du die Frage nicht verstehst. Die Frage ist klar definiert. Die Erfassung einer Komplexitätsklasse durch eine Sprache ist eine Standardterminologie. (Was nicht genau definiert ist, ist meine Präferenz, dass die Sprache eine Abfragesprache sein sollte, aber das ist nur eine Präferenz und ich habe dir gesagt, dass ich mit einer in Ordnung wäre, was nicht der Fall ist, wenn es keine mit dieser Präferenz gibt.)
Kaveh
1
@Shog9, darauf habe ich schon geantwortet. JD versteht die Frage nicht, er wusste nicht einmal, was Erfassung bedeutet, und ist sich nicht bewusst, dass eine Spracherfassung P per Definition nicht vollständig sein kann. Er erwartet, dass es so angegeben wird, wie es ihm gefällt, ich habe es in der üblichen beschreibenden Komplexitätsterminologie und Komplexität von Abfragesprachen angegeben und ihm sogar erklärt. Was ist hier nicht klar?
Kaveh
1
@ Shog9, die Motivation kommt von der beschreibenden Komplexität . Ich versuche herauszufinden, ob es in der Branche eine Sprache gibt, die SQL erweitert und P erfasst. Die ursprüngliche SQL-Sprache ist ziemlich schwach, wie Immermanns Ergebnisse zeigen. Aus theoretischer Sicht sind viele effiziente Berechnungen darin unmöglich anzugeben. Andererseits möchten wir die Sprache effizient halten (zB ). Gibt es so eine Sprache? (Ich denke, diese sind wahrscheinlich für Leute klar, die mit der beschreibenden Komplexität vertraut sind). P
Kaveh
4
@ Shog9: Ich verstehe nicht, warum diese Frage ein Eingreifen des Moderators erfordert und geschlossen wurde. Ich bin mit der beschreibenden Komplexität zufrieden genug, um zu sagen, dass dies eine echte Frage ist (obwohl sie möglicherweise besser für TCS geeignet ist - es ist eine etwas schwierige Frage).
Alex ten Brink
1
Als ich bemerkte, dass eine andere Frage ebenfalls geschlossen wurde (die auch enge Abstimmungen hatte), stellte ich eine Frage zu Meta: meta.cs.stackexchange.com/questions/97/…
Alex ten Brink

Antworten:

5

Was Ihre Hauptfrage betrifft, empfehle ich diese kurze Umfrage von Martin Grohe.


Sind die in der Praxis benötigten Abfragen in der Regel so einfach, dass keine stärkere Sprache benötigt wird?

Ich würde sagen, dass dies die meiste Zeit der Fall ist, da die gängigen Abfragesprachen (transitives Schließen, arithmetische Operatoren, Zählen usw.) ziemlich viele Erweiterungen hinzugefügt haben. Dies kommt aus der Sicht von jemandem, der als freiberuflicher Entwickler relativ einfacher Websites und anderer Anwendungen gearbeitet hat. Daher bin ich mir nicht sicher, wie SQL in größeren Branchen / größeren Datenbanken wirklich eingesetzt wird.

In den seltenen Fällen wird möglicherweise eine leistungsstärkere Sprache benötigt. Ich vermute, dass Softwareentwickler mit ihnen umgehen, indem sie die Sprache verwenden, in der sie die Anwendung schreiben, nicht die Abfragen (wie C ++ oder Java).

Janoma
quelle
3

Erstens ist die Ausdruckskraft von SQL weniger eindeutig als es scheint. Die Aggregations-, Gruppierungs- und Rechenfunktionen von SQL haben sehr subtile Auswirkungen. A priori scheint es machbar, dass durch eine Codierung von algebraischen Operatoren, die diese Funktionen verwenden, die Erreichbarkeit in SQL ausgedrückt werden kann. Es stellt sich heraus, dass dies bei SQL-92 , das "lokal" ist, nicht der Fall ist.

Dies bedeutet, dass SQL-92 eine Erweiterung benötigt, um PTIME zu erfassen, und eine Erweiterung, die es der resultierenden Sprache ermöglicht, "nicht lokal" zu sein.

Der Nachweis, dass SQL-92 die Erreichbarkeit nicht ausdrücken kann, wenn geordnete Strukturen und eine realistisch begrenzte Arithmetik zulässig sind, würde jedoch bedeuten, dass einheitlich ist und daher wahrscheinlich recht schwierig ist. (Es könnte argumentiert werden, dass für die Datentypen in SQL-92 immer eine natürliche lineare Reihenfolge besteht und daher angenommen werden kann, dass die zugrunde liegenden Strukturen geordnet sind.)TC0NLOGSPACE

Dann änderte sich die Landschaft erneut, da SQL: 1999 (SQL3) eine Rekursion beinhaltete. SQL: 1999 scheint also mindestens so aussagekräftig zu sein wie die Festkomma-Logik beim Zählen (obwohl ich denke, dass die Details, einschließlich der Frage der Reihenfolge, wieder etwas knifflig sein könnten). Ob die neuen Konstrukte die Logik aussagekräftiger gemacht haben, als es für die Erfassung von PTIME erforderlich ist, weiß ich nicht, und einige Studien wären erforderlich, um dies zu ermitteln. In der Zwischenzeit wurden in den Jahren 2003 , 2006 , 2008 und 2011 weitere Überarbeitungen vorgenommen(Da es sich um ISO-Dokumente handelt, sind nur Entwürfe frei verfügbar.) Diese Überarbeitungen fügten eine ganze Reihe neuer Funktionen hinzu, darunter das Zulassen von XQuery als "Teil" von SQL-Abfragen. Ich vermute, dass "SQL" jetzt aussagekräftiger ist, als es für die Erfassung von PTIME erforderlich ist, aber dass die dazu erforderliche Codierung möglicherweise umfangreiche und ziemlich unnatürliche Abfragen erfordert, die in realen Systemen möglicherweise nicht unterstützt werden.

Es gibt also Anzeichen dafür, dass es keine industrielle Erweiterung von SQL gibt, die PTIME präzise erfasst und Ihre Frage auf unscharfe Weise beantwortet. Kurz gesagt, die industriellen Erweiterungen sind ziemlich leistungsfähig und haben möglicherweise bereits PTIME überschritten. Wenn es stimmt, dass SQL: 1999 bereits leistungsfähig genug ist, um mindestens PTIME zu erfassen, ist auch nicht klar, was "SQL" in Ihrer Frage wirklich bedeutet, da man "SQL" definieren müsste, um eine Version vor SQL zu bezeichnen: 1999.

Schließlich zeigt Grohes Umfrage zur Suche nach Logiken, die PTIME erfassen (ebenfalls von Janoma erwähnt), dass es nicht nur schwierig ist, PTIME zu erfassen, es sei denn, wir haben eine lineare Reihenfolge als Teil der Sprache, sondern auch den Beweis, dass es keine solche Logik geben könnte implizieren .PNP

András Salamon
quelle
Vielen Dank, András, besonders für die Erwähnung, dass SQL3 "Rekursion" unterstützt. Ich muss nachsehen, was darüber bekannt ist. :)
Kaveh
ps: Ich nehme an, dass Sie die Diskussion über die Beziehung zwischen Komplexitätstheorie und Logik, die P erfasst, für die Leser aufgenommen haben, lassen Sie mich jedoch als Randnotiz und zur Verdeutlichung hinzufügen: Ich verwende SQL in dem Sinne, dass Immerman es im Ergebnis verwendet hat und dass Ergebnis verwendet eine genaue Definition von SQL. Ich kenne die Beziehungen zu Komplexitätsklassen-Trennungen und die Frage, ob eine Logik P erfasst, aber ich glaube nicht, dass sie die Antwort auf meine Frage bewirken.
Kaveh,
Die Antwort auf meine Frage kann positiv (oder negativ) sein und sie würde mit allen möglichen Antworten auf P vs. NP und der Existenz einer ordnungsinvarianten Logik für P.
Kaveh,
Kaveh, wenn Sie SQL wie Immerman definieren, dann lautet die Antwort meiner Meinung nach "wahrscheinlich nein", da die vorhandenen industriellen Erweiterungen entweder zu schwach oder zu mächtig zu sein scheinen. Aber (AFAIK) wir haben keinen strengen Beweis dafür. Möglicherweise erfasst eine Untergruppe der Erweiterungen PTIME genau, aber ich bin nicht sicher, ob ich die Spezifikationen durchforsten möchte, um sie zu isolieren ...
András Salamon
-1

PPPPP

P=NPP=NPPPNPC

PNP

P=NP

Obwohl es wahrscheinlich nicht für echte Zwecke existiert, existiert es sicherlich und ist konstruierbar und umsetzbar. Sie könnten diese Sprache mit etwas definieren, das eine Turing-Maschine bis zu einer bestimmten Anzahl von Schritten simulieren kann. IE, in der Lage, ein P-vollständiges Problem zu lösen . Wenn Sie jedoch so etwas konstruieren, ist es fast vollständig, bis auf die Einschränkung "bei einer unären Anzahl von Schritten", die in einer SQL-ähnlichen Sprache eine sehr seltsame Art wäre, es auf nur sichere Abfragen zu beschränken. Sie könnten dies tun, wenn die Schritte Aufzeichnungen einer Tabelle sind, aber dies sieht für praktische Zwecke immer noch nicht wertvoll aus.

Victor Stafusa
quelle
2
FOAC0
1
NPPPFO(LFP)P