13 - Temporální DB (modely času, generičnost dotazu a shlukování, [integritní] omezení v historii) Flashcards
Základní pojmy (relační databáze, relační algebra, relační kalkul)
Relační DB
Relační databáze je založena na tabulkách, jejichž řádky obvykle chápeme jako záznamy a eventuálně některé sloupce v nich (tzv. cizí klíče) chápeme tak, že uchovávají informace o relacích mezi jednotlivými záznamy v matematickém slova smyslu.
Relační algebra
• standardní množinové operace (průnik, sjednocení, rozdíl, kartézský součin)
• relační operace
○ selekce (výběr řádků)
○ projekce (výběr sloupců)
○ spojení (join tabulek)
○ dělení (všechny prvky A, které jsou v relaci s některým prvkem B)
Relační kalkul • dotazovací jazyk na bázi logiky • skládá se z ○ proměnných, konstant ○ odkazů na atributy ○ predikátových symbolů
Temporální databáze
- Databáze s časovou dimenzí.
- Typické použití: bankovnictví, pojišťovnictví, účetnictví, medicína, katastrální
Mají dobré vlastnosti pro archivaci a monitorování změn
Čas a časová doména
• Čas platnosti udává, po který interval jsou data platná (pravdivá v modelu)
• Čas transakce udává, kdy byla data přítomna v DB (vložena)
• Časový okamžik - bod na časové ose
• Časový úsek (interval) - doba mezi dvěma okamžiky, orientované časové trvání
• Trvání - časový úsek se známou délkou, ale neznámým začátkem či koncem
○ dopředné (pozitivní)
○ zpětné (negativní)
• Časový element - konečné sjednocení časových úseků
Časová doména
(T, menší než) - lineárně uspořádaná, neomezená množina
N, Z - diskrétní řas
Q - čas s hustotou
R - spojitý čas
Modely času - Snímkový model (snapshot)
- Je blíže výrokové TL
- Každý snapshot popisuje stav světa v konkrétním časovém okamžiku. Relace uspořádání potom definuje tok času.
○ T -> DB(D, ró) (T.. čas, D.. data, ró - schéma)
○ (každý čas se zobrazí na některý snímek databáze ve kterém je stav DB k tomuto času)
○ datové typy T -> (Dn -> bool)• Snapshot model není moc vhodný na dotazy typu {t: DB kdy platilo ró(t)} - (tj. všechny okamžiky, kdy byla podmínka v rámci DB platná - musel by se kontrolovat každý snímek databáze).
Model času platnosti (časová razítka)
Časové razítko
• atomické hodnoty bez vnitřní struktury
• základní jednotka Chronon (kvantum času)
- jedná se o prostý řádky s časovým razítkem (představ is “created” sloupec v databázi)
Temporální databáze s časovými razítky je
(D, =, T, bool (tj. ke každému řádku je přidáno ještě časové razítko z T)
Pozn.: Oba modely (razítka, snímky) jsou ekvivalentní!
Spojení času s databází (všechny druhy)
Sémantika temporální DB je nezávislá na implementaci
Snímková tabulka (snapshot)
• zaznamenává stav dat v jistém okamžiku
• Relace uspořádání nad těmito snímky tvoří tok času… historii (posloupnost stavů).
• Historie databáze je také snímkový model.
• Problém, pokud se dotazuje na “všechny okamžiky, kdy platilo, že …”.
• Příklad:
○ 1990 Asistent
○ 1995 Odborný asistent
○ 2000 Docent
Tabulka s platnými časy
• obsahuje kromě datových sloupců ještě sloupec pro platnost (možnost i nekonečno)
• možno modifikovat
• Příklad: Databáze obsahuje jeden záznam na každou změnu:
○ <1990 - 1995) Asistent
○ <1995 - 2000) Odborný asistent
○ <2000 - forever) Docent
Transakční tabulka
• obsahuje pouze časy transakcí
• data vypadají stejně jako pro tabulku platného času, ale rozdíl je v tom, že se nejedná o dobu, kdy data platila, ale kdy se vložila do DB
• Pouze připojuje data na konec
Tabulka obojího času (bitemporální)
• ukládá čas platnosti i čas transakce (vytvoření i zneplatnění!)
• pouze připojuje -> Nemění údaje od/do, ale přidá nový záznam s opravenými hodnotami.
• k historii navíc obsahuje historii změn (tabulka platného času + 2x tabulka transakce (čas vytvoření, čas zneplatnění))
Kódování intervalů (časová doména)
• Nechť Tp je časová doména, Definujeme množinu intervalů I(T) = {(a,b)| a<=b, a náleží do T sjednoceno -nekonečno, b náleží do T sjednoceno +nekonečno}
• Relace na množině I(T) ([a,b] a < a' (průnik je od a' doprava teoreticky až donekonečna) ([a,b] a < b' (průnik je úsečka a - b') ([a,b] b < a' (není žádný průnik) ([a,b] b < b' (průnik je od b doleva teoreticky až donekonečna)
Intervalová časová doména vzhledem k Tp
Ti = (I(T), < __, < _+,
Shlukování (Coalescing), generičnost dotazů a Rozdělování (partitioning)
- Někdy je potřeba spojit intervaly kvůli dalšímu zpracování (například při selekci sloupců).
- Překrývající se, či navazující intervaly tkteré nesou stejná data je možné spojit (např. každoroční výkazy při omezení na sloupec “adresa”)
- je potřebné zaručit, pokud se nad relacemi vykonávají ne-logické operace
• zjednodušují selekci, projekci, spojení • nezjednodušují temporální operace • Tj místo abychom měli dva řádky: (Hodnota1, [1,6]) (Hodnota1, [5,7]) dostaneme jediný shluknutý řádek: (Hodnota1, [1,7])
Pozn.: pro více rozměrů času je shlukování nejednoznačné -> problém
Generičnost dotazů = dotaz je generický, pokud jeho výsledek nezávisí na způsobu uložení dat v DB
* pokud je v db uložena fakta (a,[0,3]) (a platí od 0 do 3) nebo (a,[0,2]),(a,[1,3]), tak v první případě se jedná jen o shluknutí intervalů pro fakt a * ale pro dotaz: ∃i,j. ∃x(R(i,x) && R(j,x)) && i != j) platí v druhém případě, ale v prvním jen díky shluknutí ne
Rozdělování (partitioning) - opak seskupování (shlukování)
• rozdělení intervalů na několik intervalů o maximální délce x
• otázkou je v kterých bodech dělit
• v podstatě opak seskupování (shlukování)
Odsávání dat
- Data s časem transakce pořád rostou a mohou přerůst datový prostor (objem dat versus potřeby archivace)
- Data platná v okamžiku odsávání se pochopitelně neruší
- Odsávání odstraňuje stará, pravděpodobně zastaralá a nekorektní data
Indexování
Problém indexace je problém, chceme-li například najít intervaly, které mají neprázdný průnik s jiným (není běžné - většinou se do db jen zapisuje)
Stromové struktury
• R-Tree (viz prostorové DB) • AP-Tree (index jen pro přidávání dat, ISAM a B+-tree) • Time Index ○ na začátku a konci intervalu uloží seznam dalších intervalů, které obsahují tento okamžik ○ nad těmito body postav B-Tree
Temporální integritní omezení
= uzavřené formule prvního řádu temporálního dotazovacího jazyka
• Použití integritních omezení ○ zachycení sémantiky DB aplikace ○ důvod zavedení je ukládaní pouze "významých" dat ○ návrh DB - normální formy - dobrá schémata bez anomálií a dobrá dekompozice * Historie H splňuje omezení O jestliže je O pravdivé v každém stavu H * Konečná historie H potenciálně splňuje omezení O jestliže může být rozšířena do nekonečné historie tak, že splňuje O
Důvod zavedení: ukládání pouze “vyznamných” dat
Dotazovací jazyky (Výroková temporální logika (prvního řádu), Temporální relační kalkul , Jazyky temporálních DB , Jazyky s větší silou )
Nejsou standardizovány.
Výroková temporální logika (prvního řádu)
• výroková logika prvního řádu rozšířená o
○ časové spojky
○ časové proměnné a kvantifikátory
• Temporální logika TL(since, until) je shodná s TL(until) nad úplným lin. uspořádáním omezeným v minulosti
• Nemá vlastnost oddělení z výrokové logiky
Časové/temporální spojky
• X1 until X2 (X1, X2 - predikáty, tX - časy)
• X1 since X2
* ◇X - někdy v budoucnosti * ◆X - někdy v minulosti * ▫X - vždy v budoucnosti * ▪X - vždy v minulosti * ○X - v příštím kroku (pro diskrétní čas) * ●X - v předchozím kroku (pro diskrétní čas)
Temporální relační kalkul
• relační kalkul rozšířený o výrokovou temporální logiku
Jazyky temporálních DB
• je možná textová reprezentace (na rozdíl od např. prostorových DB)
• TQUEL - rozšíření jazyka QUEL o čas platnosti, čas transakce, kódování intervalů a shluky
• TSQL, TSQL2 - rozšíření SQL o čas platnosti, čas transakce, časová razítka (není formální sémantika) - více níže
• SQL/TP - rozšíření SQL o nový datový typ, intervaly
• HRDM, IXRM, ATSQL, …
Jazyky s větší silou
• podporují více časových dimenzí (ETL, μTL, TempLog)
• časové spojky vyššího řádu (množiny a podobně)
TSQL2
- Rozšíření SQL
- Oboustraně omezený lineární časový model
- Typy DATE, TIME, DATETIME, INTERVAL, PERIOD (rozdíl)
- Systém obojího času (platnost a transakce), podporuje všechny typy tabulek
- asynchronní odsávání dat (po příkazu ALTER), ale zachovávání dat pro archivaci
- časová neurčitost (granularita - zrnitost (kdy se považuje za stejné - minuty, sekundy,..)) - asi na konci září
- nejmenší časová jednotka chronon - tik hodin
Druhy tabulek
• Snímek (snapshot relation) - neukládá žádný čas
• Platný čas(stav) - AS VALID [STATE] (ukládají čas od-do)
• Čas události - AS VALID EVENT (ukládají mžikové události)
• Čas transakce - AS TRANSACTION
• Oba druhy času (stav) - AS VALID [STATE] AND TRANSACTION
• Oba druhy času (událostní) - AS VALID EVENT AND TRANSACTION
○ udalosti dostávajú časové razítka v podobe množín okamžikov
○ každý riadok udáva určitú okamžikovou udalosť, časové razítko priradené riadku hovorí, kedy daná udalosť prebehla
○ tieto tabuľky môžu byť spojené s časom transakcie
• Konvenční tabulky obdržíme z časových uvedením klíčového slova SNAPSHOT (vynechají se časové sloupce)
Dotazy
• SELECT SNAPSHOT … - vše nyní i v minulosti (bez časů)
• SELECT … - záznamy spojené s jedním nebo více časovými úseky
• SELECT VALID(A) … - součástí budou sloupce s časovými razítky s časem platnosti pro A
Verzování schématu
• TSQL narozdíl od SQL92 podporuje
• schéma se stane množinou tabulek s časem transakce
• Návrat k datu SET SCHEMA DATE
Problémy temporálních databází
Problémy s ukládáním
• intervaly a skutečné intervaly
○ interval jako kódovaní množin časových okamžiků
§ vs.
○ interval jako body v 2-rozmernom prostoru
• zhluky zjednoduhšujú selekciu,projekciu a spojenie ale nezjednoduhšujú temporálne operácie
Selhání shlukování
• nejednoznačné zhlukovanie pre viac rozmerov
• FO-úplný dotazovací jazyk sa neobíde bez n-rozmernosti v dotazoch
• dotazy sú závislé na reprezentácií - negenerické dotazy
Další problémy
• dělení intervalu (jaký bod vybrat)
• dotazy jsou optimalizovány odhadem, paralelizace není jednoduchá
• problém integrity, když se historie nemůže měnit
• databáze jsou velmi prostorově náročné
