Problem in Firma: Datenbankabfrage (SQL)

[acidBURN66]

Hallo Allerseits,

ich bin nicht nur hier im Forum "neu" :), sondern habe auch meinen ersten Job als "Aushilfs-Informatiker" in einem kleinen Unternehmen angetreten.

Hier gibt es ein Problem mit einer zu erstellenden effizienten DB-Abfrage, welche bisher noch nicht so läuft, wie sie sollte - die anderen Mitarbeiter haben die DB bisher nur "nebenbei" betreut und haben dafür auch keine Lösung parat...

Problemstellung:

1)
Tabelle (sehr simpel):

[ID] [Fremd_ID] [Sequenz_Nr]


2) Einträge in der Tabelle ergeben mittels Sequenz-Nummer einen Datensatz:

ID1, ID2, ID3, ... , IDx, IDx+1 usw...

Diese Zahlenkette gehört einer Person, der Fremd_ID. Um die Reihenfolge zu erhalten, gibt es die Spalte Sequenz_NR! Ergo:

[ID] [Fremd_ID] [Sequenz_Nr]
1-------1-----------1
2-------1-----------2
8-------1-----------3
23------1-----------4
6-------1-----------5
...------...----------...
xyz-----1-----------300

1-------2 (!!)-------1
3-------2-----------2
8-------2-----------3
23------2-----------4
6-------2-----------5

- Es können Tausende von Nutzern (Fremd_ID) enthalten sein, welche in einer Reihenfolge (Sequenz) bestimmte IDs durchlaufen! (Eine ID steht für einen Vorgang...)

3)
Das Ziel es es nun, bei einen gegebenen Kunden mit einer Sequenz an IDs einen anderen Kunden aus der Datenbank zu finden, welcher ebenfalls ALLE IDs in der selben Sequenz durchläuft ODER aber wenigstens Abschnitte in der richtigen Reihenfolge durchläuft, => dann den Kunden, welcher am "längsten" übereinstimmt!

geg in der richtigen Reihenfolge: ---= ID99, ID86, ID3, ID8, ID23 =---

Angewandt auf obige Bsp.-Tabelle wäre das Ergebnis der Kunde Nr. 2 !!! (Übereinstimmung 3, 8, 23)



Wie kann man so etwas effizient abfragen? Man bedenke, dass die Anfrage auch aus einer Sequenz mit über 300 IDs bestehen kann! Und andere Kunden in der DB auch Sequenzen mit über 300 Einträgen enthalten können!


Lösung???:
A)
Wäre es vielleicht besser, ALLE potentiellen Kunden aus der DB zu suchen, welche EINES der zu suchenden IDs enthält?

Ergebnis: Kunde 3, Kunde 8, Kunde 22, Kunde 333, Kunde 9988

B)
Danach die komplette Sequenz von Kunde 3, 8, 22, 333 und 9988 nachladen und dann mittels Algorithmus im Arbeitsspeicher suchen lassen???

----------------------------------------------------------------------
Weiß hier einer vielleicht eine gute Lösung für das Problem? Dies DARF auch GERN eine Neuanordnung der Tabellenstruktur sein!!! Vielleicht so:

Tabelle:
[KUNDE] [ID1] [ID2] [ID3] [...] [IDx] //x = bis zu 500

Dann muss man halt horizontal suchen, was aber in Datenbanken nicht soo gut zu meistern ist, oder?

Viele Grüße,
AB

[Gast]

Ich glaube, eine SQL-Datenbank ist für dieses Problem denkbar ungünstig. Ich würde alle Nutzer-Daten im Arbeitsspeicher halten und dann mit dem hier beschriebenen Algorithmus arbeiten:
http://en.wikipedia.org/wiki/Longest_common_substring_problem

[Monger]

Zuerst einmal: Willkommen im Forum!

Zweitens: Nach Ähnlichkeiten zu suchen ist immer höllisch. Nach Gleichheiten zu suchen, ist wesentlich einfacher.

Drittens: die zentrale Frage hier ist eigentlich, was denn hinter diesen kryptischen Sequenznummern liegt, und was dein eigentliches Ziel ist. Ohne das zu wissen, wird es schwierig sich über das Datenmodell Gedanken zu machen.

[acidBURN66]

Ok. Ich versuche noch ein wenig genauer zu werden, d.h. ein wenig das Datenmodell erklären:

1)
Wir haben ein Nutzerverhalten, welches durch eine bestimmte Aktion defniert und durch eine eindeutige ID dargestellt wird.
Tabelle mit 2 Spalten:

[ID][description_verhalten]

2)
Ein Nutzer "verhält" sich nach einiger Zeit auf eine ganz bestimmte, individuelle Art und Weise, ...ein anderer Nutzer verhält sich halt anders... es entsteht eine Sequenz von Verhaltensweisen:
Bspw.:
Nutzer 1: ID3, ID9, ID333, ID2, ID45, ID9, ID12, ID15, ID22
Nutzer 2: ID5, ID4, ID23, ID92, ID34, ID9, ID12, ID15, ID299
Nutzer x: ...............................

Wichtig ist die Reihenfolge der IDs.

3)
Jetzt kommt das, was ich bereits im ersten Post darstellte:

Das "Verhalten" der Nutzer wird quasi durch die ID-Sequenz in einer bestimmten REIHENFOLGE wiedergegeben. Speichern kann man dies in einer Tabelle folgendermaßen: (wie oben im 1. Post schon erwähnt...)

[ID] [Nutzer_ID] [Sequenz_Nr]
1-------1-----------1
2-------1-----------2
8-------1-----------3
23------1-----------4
6-------1-----------5
...------...----------...
xyz-----1-----------300

1-------2 (!!)-------1
3-------2-----------2
8-------2-----------3
23------2-----------4
6-------2-----------5

Diese Tabelle gibt nun das Verhalten eines Nutzers wieder und gibt mir Auskunft über

a) die Reihenfolge (durch Spalte Seqzenz_Nr) und
b) das Verhalten (durch die Spalte ID)


4)
Das erklärte Ziel besteht nun darin: Gegeben sei ein Verhaltensmuster (Sequenz), finde nun Nutzer, welche INSGESAMT zueinander identisch in ihrem Verhalten sind ODER aber, finde Nutzer, welche wenigstens mit einem Abschnitt dieser Sequenz übereinstimmen.

That's it.. ;D ;(:|


Ich hoffe nun sehr, dass die Problemstellung jetzt klarer ist, und wir eine SQL-basierte Lösung finden können. Wenn nicht, muss man wahrscheinlich wirklich Gigabyte-weise im RAM halten und Suchbäume basteln...

[Monger]

Das erklärte Ziel besteht nun darin: Gegeben sei ein Verhaltensmuster (Sequenz), finde nun Nutzer, welche INSGESAMT zueinander identisch in ihrem Verhalten sind

Das an sich wäre ja noch ganz simpel. Nehmen wir mal an, du hättest keine kryptischen IDs, sondern schlicht ein Feld namens "Benutzerverhalten", in dem auf irgendeine Weise die Historie dieses Benutzers eincodiert ist. Dann filterst du einfach auf genau dem Feld was dich interessiert, und bekommst alle gleichartigen Einträge gleich mit.
Wie gesagt: Gleichheit festzustellen geht rasend schnell.


ODER aber, finde Nutzer, welche wenigstens mit einem Abschnitt dieser Sequenz übereinstimmen.

An dem Punkt dagegen stellen sich automatisch so einige Fragen: wie genau definierst du denn Ähnlichkeit? Ist ABCF zu ABCD ähnlicher als FBCD?

Daraus wird ganz schnell ein komplexer Algorithmus, und eine Datenbank ist nicht dazu da, um Programmlogik zu implementieren.
Selbst wenn du das programmatisch umsetzt, wird sowas wahrscheinlich höllisch rechenintensiv. Das Problem mit Ähnlichkeitsalgorithmen ist, dass man nie weiß ob nicht irgendwas doch ähnlich zueinander ist, solange man es nicht ausgerechnet hat. Und somit kannst du bis zuletzt keinen der Kandidaten ausschließen.

[acidBURN66]

Das an sich wäre ja noch ganz simpel. Nehmen wir mal an, du hättest keine kryptischen IDs, sondern schlicht ein Feld namens "Benutzerverhalten", in dem auf irgendeine Weise die Historie dieses Benutzers eincodiert ist. Dann filterst du einfach auf genau dem Feld was dich interessiert, und bekommst alle gleichartigen Einträge gleich mit.
Wie gesagt: Gleichheit festzustellen geht rasend schnell.


An dem Punkt dagegen stellen sich automatisch so einige Fragen: wie genau definierst du denn Ähnlichkeit? Ist ABCF zu ABCD ähnlicher als FBCD?

Daraus wird ganz schnell ein komplexer Algorithmus, und eine Datenbank ist nicht dazu da, um Programmlogik zu implementieren.
Selbst wenn du das programmatisch umsetzt, wird sowas wahrscheinlich höllisch rechenintensiv. Das Problem mit Ähnlichkeitsalgorithmen ist, dass man nie weiß ob nicht irgendwas doch ähnlich zueinander ist, solange man es nicht ausgerechnet hat. Und somit kannst du bis zuletzt keinen der Kandidaten ausschließen.

Mhh, ich denke das mit der Ähnlichkeit in Bezug auf das Nutzerverhalten sollte ich noch mal an einem Beispiel erklären, es ist nämlich ganz EINFACH... ;)

Nutzer 1:
Verhalten A1: Aufstehen (ID1)
Verhalten A2: Zähne putzen (ID2)
Verhalten A3: Frühstücken (ID....)
Verhalten A4: Sich ärgern (Zähne schmutzig)
Verhalten A5: Zähne putzen
Verhalten A6: Anziehen
Verhalten A7: Schuhe zubinden
Verhalten A8: Tür zuschließen
Verhalten A9: Ins Auto einsteigen (ID9)

-----------------------------------------------
Tabelle:
[Nutzer]---[Verhalten_ID]---[Sequenz]
1----------A4---------------1
1----------A3---------------2
1----------A6---------------3
1----------A9---------------4
2----------A1---------------1
2----------A3---------------2
2----------A6---------------3
2----------A9---------------4
2----------A7---------------5

Man erkennt, dass Nutzer 2 ab der Sequenz-Nr. 2 das selbe Verhalten wie Nutzer 1 hat. Zwar stimmt nicht das GESAMTE Verhaltensmuster überein, aber ein Ausschnitt davon.

Nun gibt es aber 100.000e Nutzer und jeweils ein Verhaltensmuster der Länge 500 (Sequenz 1 bis 500).

1) Entweder man findet Nutzer, welche INSGESAMT das selbe Verhalten haben (selbe Sequenz; Reihenfolge) oder...

2) Man findet Nutzer, welche wenigstens einen (möglichst langen) Teil einer Sequenzkette "treffen"...


Mir fällt aber auch zu 1) keine effiziente SQL-Abfrage ein:
gegeben: Nutzer mit einer Sequenz (Reihenfolge) an IDs (Verhalten). Suche nun Nutzer, welche das selbe Verhalten in der gleichen Reihenfolge haben...

Oh man, :|:confused: :tongue:

[Gast]

Wieso willst du das denn mit einer SQL-Datenbank machen?
Schreib einfach ein Programm in C++, welches die einzelnen Nutzerdaten als ByteString hält und verwende den von mir oben erwähnten Algorithmus. Hier sogar als fertige Version für C++: http://en.wikibooks.org/wiki/Algorithm_implementation/Strings/Longest_common_substring#C.2B.2B

Du wirst es in SQL niemals nur annähernd so performant hinbekommen. Gerade wenn du über 100.000 Nutzer hast.

[DavChrFen]

1. Muß es denn unbedingt eine DAtenbank sein?
2. Was für eine SQL-Version wird benutzt? Und welche Indexstrukturen unterstütz diese Version?

[acidBURN66]

@ meine letzten beiden Vorposter:

"Leider" werden diese Daten in einer Datenbank erhoben bzw. persistiert. Das ganze ist ein Java EE Umfeld -> inkl. MySQL.

Ich weiß nicht, ob es eine gute Idee ist, (@Gast) die ganzen Nutzerdaten aus der DB zu lesen (bzw. auch nach einem Reset, Ausfall, o.ä.) bzw. diese Datenmengen mittels EJB's überhaupt in dem Ressourcenpool des EJB-Containers zu halten...?! Ich glaube fast, das dürfte zu viel werden...


Dann wahrscheinlich eher so:

1) Gegebener Nutzer mit gegebenen Verhalten (sagen wir 400 IDs)
2) System fragt bei Datenbank alle Nutzer an, welche auch nur ein Element dieser gegebenen IDs besitzen... (ineffektiv...)
3) Aus dem Request (evtl. mehrere tausend Nutzer...) wird dann ein Suchbaum erstellt.

Prinzipiell ok, ABER der Punkt 2 muss optimiert werden: Wenn irgendein Nutzer auch nur eines der gegebenen IDs besitzt, so MUSS wenigstens die darauf folgende ID des Nutzers in der DB auch der ID des gegebenen Nutzers entsprechen... DENN sonst wäre ja eh keine sequentielle Gemeinsamkeit vorhanden...

bsp:
Nutzer DB: a-b-c-D-E-F-g-h-i-j-k-l-m-n-o-p-q-r
Nutzer geg: x-z-k-D-E-F-G-m-l-o-y-x-z

Es müsste also der Nutzer aus der DB zurückgegeben werden, weil ein Teil der Sequenz mit der geg. Sequ. übereinstimmt.
Wenn allerdings nur EIN Element übereinstimmen würde, wäre alles weitere sinnlos, da das Ziel darin besteht eine komplette ODER größtmögliche Übereinstimmung zu finden...

[Berni]

Was spricht denn dagegen, es nicht in der Datenbank zu erheben bzw. davon einen Komplettdump zu machen und dann in ein spezielles Auswertungsprogramm zu importieren? SQL ist dafür halt nicht gemacht und schon gar nicht optimiert, da kannst du machen was du willst und uns auch noch 10x fragen. Eventuelle Konstruktionen mit Subquerys kannst du in dem Zusammenhang vergessen weil das einfach zu langsam wird. Wenn du SQL unbedingt verwenden willst könntest du aber den Source von MySQL oder PostgreSQL nehmen und die Funktion dort implementieren. Viel Spass :D

[Gast]

Ich würd mir da auch schnell ein Programm in Visual Studio zusammenklicken.
Dann haste auch eine schöne Oberfläche.

[Gast]

VisualStudio??? Weiter oben steht etwas von Java EE Umgebung...