13 - Temporální DB (modely času, generičnost dotazu a shlukování, [integritní] omezení v historii) Flashcards

1
Q

Základní pojmy (relační databáze, relační algebra, relační kalkul)

A

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ů
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
2
Q

Temporální databáze

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
3
Q

Čas a časová doména

A

• Č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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
4
Q

Modely času - Snímkový model (snapshot)

A
  • 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.
    • Temporální DB je potom funkce typu
    ○ 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).
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
5
Q

Model času platnosti (časová razítka)

A

Č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í!

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
6
Q

Spojení času s databází (všechny druhy)

A

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í))

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
7
Q

Kódování intervalů (časová doména)

A

• 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), < __, < _+,

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
8
Q

Shlukování (Coalescing), generičnost dotazů a Rozdělování (partitioning)

A
  • 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í)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
9
Q

Odsávání dat

A
  • 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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
10
Q

Indexování

A

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
How well did you know this?
1
Not at all
2
3
4
5
Perfectly
11
Q

Temporální integritní omezení

A

= 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
12
Q

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 )

A

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ě)

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
13
Q

TSQL2

A
  • 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

How well did you know this?
1
Not at all
2
3
4
5
Perfectly
14
Q

Problémy temporálních databází

A

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é

How well did you know this?
1
Not at all
2
3
4
5
Perfectly