Query-Normalisierung/Vergleich?
Verfasst: 13.02.2015, 13:54
Hallo,
ich schreibe gerade eine kleine Bibliothek zur Datenabfrage und stehe jetzt vor dem Problem, zwei Queries miteinander vergleichen zu müssen. Ein Query ist lediglich ein Ausdruck bestehend aus Variablen, booleschen Operatoren (nur and, or und not) und Vergeichsoperatoren. Ich möchte jetzt herausfinden, ob zwei Queries das gleiche Ergebnis liefern, und wenn nicht, ob der eine Query strikter als der andere ist (und dessen Ergebnis somit eine Untermenge des anderen Queries ist).
Mir fehlt jetzt irgendwie ein Ansatz. Klar ist, dass die booleschen Ausdrücke normalisiert werden müssen (vielleicht kanonische KNF/DNF? Oder (was ich gerade gefunden habe), https://en.wikipedia.org/wiki/Binary_decision_diagram?). Und dann muss ich herausfinden, ob die Constraints auf die Variablen (z.B. price < 10) beider Queries gleich sind oder ein Query strikter ist (braucht es dafür schon so was wie einen Theorem Prover? Oder geht das einfacher?).
Ist das ganze überhaupt einigermaßen Effizient lösbar?
Ich weiß, mir fehlen hier die formalen Grundlagen. Ich würde das gerne ändern, weiß aber nicht genau, worin ich mich vertiefen sollte.
Viele Grüße
David
ich schreibe gerade eine kleine Bibliothek zur Datenabfrage und stehe jetzt vor dem Problem, zwei Queries miteinander vergleichen zu müssen. Ein Query ist lediglich ein Ausdruck bestehend aus Variablen, booleschen Operatoren (nur and, or und not) und Vergeichsoperatoren. Ich möchte jetzt herausfinden, ob zwei Queries das gleiche Ergebnis liefern, und wenn nicht, ob der eine Query strikter als der andere ist (und dessen Ergebnis somit eine Untermenge des anderen Queries ist).
Mir fehlt jetzt irgendwie ein Ansatz. Klar ist, dass die booleschen Ausdrücke normalisiert werden müssen (vielleicht kanonische KNF/DNF? Oder (was ich gerade gefunden habe), https://en.wikipedia.org/wiki/Binary_decision_diagram?). Und dann muss ich herausfinden, ob die Constraints auf die Variablen (z.B. price < 10) beider Queries gleich sind oder ein Query strikter ist (braucht es dafür schon so was wie einen Theorem Prover? Oder geht das einfacher?).
Ist das ganze überhaupt einigermaßen Effizient lösbar?
Ich weiß, mir fehlen hier die formalen Grundlagen. Ich würde das gerne ändern, weiß aber nicht genau, worin ich mich vertiefen sollte.
Viele Grüße
David