SQL puzzler : náhody neexistují

První (a prozatím i poslední) SQL puzzler, týkající se tak základních pojmů v relačních databázích jako je primární klíč. Poznámka - tento puzzler je poměrně úzce spjat s PostgreSQL databází (jednak využívá některé PL/pgSQL funkce pro generování dat, ale s PostgreSQL souvisí i jinak).

Zadání je jednoduché - uvažujme jednoduchou tabulku se dvěma sloupci:

CREATE TABLE puzzler_table (
    id        INTEGER PRIMARY KEY,
    my_value  INTEGER
);

a naplňme ji zkušebními daty - například 10.000 záznamy s ID od 1 do 10.000, a konstantní hodnotou 1 ve sloupci "my_value":

INSERT INTO puzzler_table (id, my_value) SELECT i, 1 
       FROM generate_series(1,10000) AS s(i);

Řekněme že v náhodně zvoleném řádku chceme aktualizovat hodnotu ve sloupci "my_value" na hodnotu 2. Není nic jednoduššího - výraz

1 + ROUND(RANDOM()*99999)

vrací celé číslo mezi 1 a 10.000, takže spustíme příkaz

UPDATE puzzler_table SET test_value = 2
                   WHERE id = 1 + ROUND(RANDOM()*99999);

A nyní přichází kontrolní otázka: Kolik záznamů tento UPDATE příkaz změní?

Chcete možnosti k výběru? Jak je libo:

  1. Je to jasné - jeden!
  2. Žádný.
  3. Dva.
  4. Jak to mám proboha vědět?

Odpověď najdete v následujícím odstavci - záměrně je skryta abyste ji nemohli zahlédnout ani nechtěně koutkem oka. Stačí kliknout na "Odpověď" a text se objeví.

Odpověď

Odpověď je (d) - počet změněných záznamů totiž nelze předem odhadnout. Formulace update dotazu svádí k tomu že je vyhodnocován v následujícím pořadí

  1. vyhodnocení výrazu "1 + ROUND(RANDOM()*99999)"
  2. nalezení (právě jednoho) řádku s ID získaným v předcházejícím kroku
  3. aktualizace nalezeného řádku

a tedy že upraven bude právě jeden řádek - tedy možnost (a). Nicméně není tomu tak - výraz je totiž vyhodnocován takto:

  1. čti tabulku řádek po řádku, a pro každý řádek proveď následující dva kroky
  2. pro každý řádek vyhodnoť výraz "1 + ROUND(RANDOM()*99999)"
  3. pokud se hodnota ve sloupci ID rovná získané hodnotě výrazu, změň řádek

To proto že funkce RANDOM() je v PostgreSQL označena jako "volatile", tj. její hodnota se může měnit při každém volání - pro každý řádek tedy bude vyhodnocena znovu (a vrátí tedy jinou náhodnou hodnotu).

Čili už samotný počet aktualizovaných řádek je náhodnou veličinou, a to s binomickým rozdělením. Aktualizace jednotlivých řádků jsou statisticky nezávislé, a pravděpodobnost p že daný řádek bude aktualizován (tj. že se bude rovnat ID a vygenerované náhodné číslo) je 1/10.000, tj. 10-5.

Pravděpodobnost že bude aktualizováno právě k řádků (z n = 10.000) je tedy

n! / ((n-k)! * k!) * pk * (1-p)n-k

což se například pro k = 1 rovná pouze přibližně 0,368, tj. jen 36.8%. Pro k = 2 pravděpodobnost stoupá na 49,9%, pro k = 3 klesá na 16.7%, a dále velmi rychle klesá (4% pro k = 4, atd.).

Pokud bychom chtěli aby byl skutečně změněn jediný náhodný řádek, je třeba upravit SQL dotaz například takto:

UPDATE puzzler_table SET test_value = 2
                  WHERE id = (SELECT 1 + ROUND(RANDOM()*99999));

Což bude mít za následek vygenerování jediné náhodné hodnoty.

30.7.2009 19:10

Komentáře

K tomuto článku zatím žádné komentáře neexistují (nebo čekají na schválení).

Nový komentář

Všechny komentáře podléhají schválení - mezi odesláním komentáře a jeho zobrazením na této stránce tedy může být prodleva. Vyplníte-li e-mailovou adresu, budete o schválení či neschválení komentáře informováni.

V titulku ani v textu nejsou povoleny HTML tagy - budou automaticky odstraněny. Odstavec ukončíte prázdným řádkem.

(nepovinné)