Kollisionswahrscheinlichkeit bei Datenbank-Updates

Neue Frage »

Calvin Auf diesen Beitrag antworten »
Kollisionswahrscheinlichkeit bei Datenbank-Updates
Hallo zusammen,

ich brauche einen Ansatz bei der Berechnung einer Kollisions-Wahrscheinlichkeit. Leider stehe ich mit Stochastik ziemlich auf Kriegsfuß, weshalb ich noch nichts selbst bieten kann. Ich würde mich aber über ein paar Stichworte freuen, die mir einen ersten eigenen Ansatz ermöglichen.

Ich habe 1000 Einträge in einer Datenbank. Über einen Zeitraum von 12 Stunden kommen gleichverteilt geschätzt 100000 Update-Statements auf einen der 1000 Datensätze (d.h. alle 0,43 Sekunden). Welcher Datensatz aktualisiert wird, soll auch gleichverteilt sein.

Wenn ein Update-Vorgang 0,5 Sekunden dauert, wie hoch ist die Wahrscheinlichkeit, dass "zeitgleich" der gleiche Datensatz aktualisiert wird?

Ich habe versucht, das irgendwie auf das Geburtstags-Paradoxon zu übertragen. Aber das ist mir nicht gelungen. Liege ich mit diesem Ansatz überhaupt richtig?

Zusatz-Frage:
Wie verändert sich die Wahrscheinlichkeit, wenn bei jedem Update-Vorgang zusätzlich noch ein neuer Datensatz erzeugt wird, der theoretisch auch wieder aktualisiert werden kann?

Gruß
Calvin
HAL 9000 Auf diesen Beitrag antworten »

Halten wir die Parameter fest:

... betrachteter Zeitraum (hier )
... Dauer Updatevorgang (hier )
... Anzahl Udatevorgänge im betrachteten Zeitraum (hier )
... Anzahl Datensätze (hier )

Nimm zwei beliebige Update-Vorgänge, mit Wahrscheinlichkeit überschneiden die sich zeitlich, mit Wahrscheinlichkeit betreffen sie auch denselben Datensatz, insgesamt haben wir mit Wahrscheinlichkeit eine Kollision dieser beiden Update-Vorgänge.

Die nun insgesamt Paare von Update-Vorgängen sind zwar nicht unabhängig, allerdings kann man in erster Näherung so rechnen. Das ergibt dann mit Wahrscheinlichkeit



keine Kollision im betrachten Zeitraum, mit deinen Daten wäre das , d.h., du kannst mit ziemlicher Sicherheit davon ausgehen, dass in deinem Zeitraum 12h solche Kollisionen passieren.


P.S.: Rechnet man statt mit mit einer Rate von Update-Vorgängen pro Zeit, also , so ergibt sich mit (*) dann Wahrscheinlichkeit für keine Kollision im Zeitraum . Das ganze läuft dann darauf hinaus, dass die Kollisionszeitpunkte selbst (zumindest näherungsweise) einen Poisson-Prozess bilden.
Calvin Auf diesen Beitrag antworten »

Wow, danke dir. Auch wenn ich lieber ein anderes Ergebnis gelesen hätte Augenzwinkern

Ich muss mich jetzt mal in Ruhe hinsetzen und den Ansatz verstehen. Vor allem das mit dem Poisson-Prozess.
HAL 9000 Auf diesen Beitrag antworten »

Hmm, ich sehe gerade noch einen Denkfehler bei mir:

Wenn man den Start des Update-Zeitpunktes zeitstetig im Intervall gleichverteilt annimmt, dann ist die Kollisionswahrscheinlichkeit bzgl. der Zeit nicht , sondern ... der fehlende Faktor 2 zieht sich dann durch alle Formeln.
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »