Spreadsheet jako engine relačních databází
Jakub DanielMatematicko-fyzikální Fakulta 2011
Spreadsheet
● Jeden z nejčastěji používaných typů software● Podobnost s relačními databázovými sytémy
● Udržuje a zpracovává data
– Data
– Formule
● Odlišnost od relačních databázových systémů● Dostupný a méně zatížen potřebou rozsáhlejších znalostí uživatele
● Nižší výkonnost
● Patrnější omezení na velikost dat a relací zaznamenatelných a zpracovatelných systémem
● Odlišný způsob integrace s jiným software
Motivace
● Spreadsheet bývá součástí mnoha instalací desktopových operačních systémů
● Popř. není tolik nákladné si jej opatřit (stejně tak ale existují MySQL, PostreSQL a jiné)
● Jejich použití je koncovým uživatelům blízké, nebo alespoň není příliš komplikované
● Pro malé firmy a koncové uživatele není nízký výkon bolestný● Menší objemy dat, na nichž rozdíl není patrný
● Overhead práce se samotným systémem je nižší, jelikož je uživateli ponecháno přívětivější rozhraní
Cíle
● Implementace běžné databázové funkcionality● Selection, Projection, Semijoin, Join, Cartesian Product, Union,
Difference, Grouping, Aggregation
● Využítí čisté spreadsheet funkcionality běžných implementací● Nejen MS Excel ale i OpenOffice, LibreOffice, Gnumeric, Google docs
…
● Bez použití maker nebo scriptovacích jazyků, VB …
● Porovnání efektivity na konkrétních příkladech● V této prezentaci zmíním pouze samotný verdikt
Technické předpoklady
● Notace● R1C1 – nezávislost významu na samotném umístění formule
– R1C1, RmCn, R[i]Cn, RmC[j], R[i]C[j], RCn, RC[i], RmC, R[i]C
– Není-li u řádku resp. sloupce číslo uvedeno, jedná se o řádek resp. sloupec, v němž je umístěn výraz, jehož je odkaz součástí
– Hranaté závorky značí relativní adresování buňek (R[-1]C, buňka ve stejném sloupci o řádek výš)
● Požadované funkce● IF(cond, true_br, false_br)
● MATCH(range, cell, 0) vrátí index v range prvního výskytu hodnoty v cell nebo error
● MATCH(range, cell, 1) na vzestupně setříděném range vrátí index nejvetší menší hodnoty než cell
● INDEX(range, cell) vrátí hodnotu z range na pozici dané cell
● SUMPRODUCT vrátí skalární součin
– Lze nahradit pomocí COUNTIFS, SUMIFS v novějších implementacích (Excel 2007+)
● Relace jsou definované na celých číslech● Omezených implementací spreadsheet (maximální velikost)
● Reprezentovány v po sobě jdoucích sloupcích
● Řádky neobsahující prázdné pole (““) odpovídají n-ticím, které patří do relace
● Řádky obsahující prázdné pole (ve sloupcích reprezentace relace) jsou celé prázdné
SUMPRODUCT
Architektura spreadsheet databáze
● Worksheet● Oddělená matice, ve které lze uchovávat data i formule
● Lze mezi nimi vést reference, což umožňuje oddělovat data od formulí
● Každá tabulka / pohled odpovídá jednomu worksheet● Prázdná tabulka odpovídá téměř prázdnému worksheetu
● Vyjímkou jsou formule zajišťující vlastnosti jako
– PRIMARY KEY, FOREIGN KEY
● Worksheety jsou součástí Workbooků, mezi nimiž v některých implementacích lze také vést odkazy
● Pro tuto problematiku poskytuje možnost optimalizace přepočítávání dat a izolace dat (robustnost proti poškození tabulek, s nimiž uživatel přímo nepracuje)
Implementace užitečných funkcí
● Error trapping● Formule mohou být pro nějaký vstup „nedefinované“, v takovém případě selžou (pro nás
není důležité rozlišovat důvody chyb)
● IF(ISERROR(F), ““, F)
– Libobolné selhání je ošetřeno dle potřeby (v tomto případě prázdný výsledek v daném poli)
● Standardizace● Reprezentace relace je „volná“, resp. „standardní“, pokud uspořádání neprázdných řádků a
řádků popisujících n-tice v relaci je libovolné, resp. prázdné řádky, následují až po řádcích n-tic v relaci
● Standardizace převádí „volnou“ reprezentaci na „standardní“ reprezentaci
– Ck << SUMPRODUCT((RxCj:RCj <> ““) * 1) … počet předcházejících standardních řádků
– Cl << MATCH(ROW() - x + 1; Ck; 0) … najdi řádek, kterému předchází aktuální INDEX standardních řádků
– Cm << IF(ISERROR(RCl); ““; INDEX(Cj, RCl)) … nahraď chyby prázdnými řádky (chyby nastaly pouze na těch řádcích, jimž předcházelo málo standardních řádků, tj. prázdné řádky)
Implementace užitečných funkcí
● Třídění
ROW() ... současná pozice
+
SUMPRODUCT((RC1:RyC1 <= RC1) * 1) … počet následujících menších
-
SUMPRODUCT((R1C1:RC1 >= RC1) * 1) … počet předcházejících větších
● Mazání duplikátů● SUMPRODUCT((RCj:RyCj = RCj) * (RCk:RyCk = RCk) * …)
– Počet následujicích duplikátů řádku
● IF(RCm = 1; RCn; ““)
– Pokud je v aktuálním řádku 1, pošli na výstup, jinak vrať prázdný výsledek
Implementace základní funkcionality
● Selekce
● IF(P, RC[-počet_sloupců_relace], ““)
– P je predikát na sloupcích relace (používající AND, OR, NOT)
● Projekce
● Pouze vynechá kopírovaní sloupců (pokud není projekce přímo výstupem, pak není třeba dělat nic, pouze se v dalších výpočtech sloupce ignorují)
● Union
● RaCb << COUNT(Rx1Cj:Ry
1:Cj) … ulož počet řádků jedné relace
● IF(ROW() <= RaCb; RCj; INDEX(Rx2Ck:Ry
2Ck;ROW() - RaCb));
● Difference
● SUMPRODUCT((Rx2Cj
2:Ry
2Ci
2=RCi
1)*(Rx
2Cj
2:Ry
2Cj
2=RCj
1) ...) … počet shodných řádků
druhé relace s řádky první relace
● IF(RCk = 0; RCi1; ““) … vybere buňku řádku první relace, pokud nebyl v druhé relaci
Implementace agregačních funkcí
● SUM● SUMPRODUCT((RxCj:RyCj=RCj) * …* Ck)
● Odstranění duplikátů
● COUNT● Speciální případ SUM (přes sloupec jedniček)
● SUMPRODUCT((RxCj:RyCj=RCj) * …)
● Odstranění duplikátů
● AVG● SUM / COUNT
● MAX● Sestupné setřídění podle agregovaného sloupce
● Odstranění duplikátů přes zbylé sloupce
– Ponechá první výskyt
● Maximální hodnota ve zbylém řádku pro danou hodnotu
● MIN● Opačné hodnoty
Implementace základní funkcionality
● Kartézský součin● Nejprve relace standardizujeme
● R1Cs << COUNT(RxCi:RyCi) … počet řádků jedné relace
● R2Cs << COUNT(RuCj:RvCj) … počet řádků druhé relace● IF(ROW() <= R1Cs * R2Cs; INDEX(RxCi:RyCi; INT((ROW() - 1)/R2Cs) + 1); ““)
– Vytvoří R2Cs kopií sloupce Ci (nejprve R2Cs kopií první hodnoty, pak další ...)
● IF(ROW() <= R1Cs * R2Cs; INDEX(RuCj:RvCj; MOD(ROW() - 1; R2Cs) + 1); ““)
– Vytvoří R1Cs kopií sloupce Cj
● SEMIJOIN● IF(ISERROR(MATCH(RCj
1;RxCj
2:RyCj
2;0); ““; RCj
1) … zahodí řádky R
1,
které nejdou spojit s řádky R2
● IF(RCk = ““; ““; RCj2) … pokud šel řádek na výstup, doplní ho zbýlými
hodnotami v ostatních nespojujících sloupcích
Poznámka k příkladu
Současné implementace spreadsheetů umožňují v notaci uvést Ci, čímž se uživatel odkazuje na celý sloupec. Tato funkcionalita neexistovala v dřívějších verzích nejpoužívanějších implementací.
Pro tento příklad by to znamenalo značné zjednodušení a zobecnění zápisů „R3C[-1]:R19C[-1]“ na „C[-1]“
Implementace pokročilé funkcionality
● JOIN● Ačkoli je JOIN možné implementovat pomocí kartézského součinu a selekce,
uvádí autor článku efektivnější implementaci
● Předpokládá setříděné tabulky (třídící algoritmus již máme)
● FOREIGN KEY JOIN (Many-to-one) lze implementovat snadno, spojovací sloupec je klíčovým atributem, hodnoty v něm nejsou duplikovány
– C1:C2 JOIN C3:C4 ON C1 = C3 (C3 PRIMARY KEY)● C5:C6 << IF(RC1 = ““; ““; RC[-4]) … kopíruje C1, C2● C7:C8 << IF(RC1 = ““; ““; INDEX(C[-3]; MATCH(RC1; C3; 0)) … vyhledá odpovídající C3, C4
● Many-to-many JOIN
– Formulí popisujících toto spojení je již více než by na slidu bylo přehledné, proto snad postačí uvést ideu
● Pro tabulku R1 vytvoříme tabulku (INDEX), kde budou hodnoty RC1, první výskyt RC1 v C1, počet výskytů RC1 v C1. To samé pro druhou tabulku R2
● Provedeme I1 SEMIJOIN I2 a I2 SEMIJOIN I1, čímž vyloučíme řádky, které se nespojí● Nakonec spočteme Kartézský součin na jednotlivých blocích
User-Friendliness
Uvedené konverze nejsou příliš přehledné a proto autor článku navrhuje vytvoření webové aplikace,
která by převedla SQL zápis na “ekvivalentní“ spreadsheet implementaci
Odlišnosti od RDBMS
● V implementacích spreadsheet aplikací chybí analogie NULL● V úvodních příkladech článku se vůbec hodnoty NULL
neuvažují● Aby byly příklady operací srozumitelné a nezanášely se dalšími IF
● Avšak principiálně je lze zavést (jako specialní string hodnota), což není BÚNO
● Transakce● Nejsou potřeba, jelikož nedochází k paralelnímu přístupu
● Commit … manuální vyhodnocení po konzistentní změně
● Rollback … načtení z disku
Emulace funkcionality SQL 92
● DDL (Data Definition Language)● Oddělené vstupní a datové tabulky (filtrování vstupu – Integritní omezení)
● TYPE, LEN umožňují částečnou typovou kontrolu dat. Problematické jsou ““ a “NULL“
● DATE je řešeno formátováním, jinak je to jen číslo
● UNIQUE / PRIMARY KEY odpovída odstraňení duplikátů
● FOREIGN KEY je ověřeno přes SEMIJOIN
– ON DELETE CASCADE je automatický, jiná opatření ON DELETE nejsou možná
● Smazání klíče invaliduje záznam a ten tak neprojde filtrem a není zobrazen v datové tabulce
● Ve vstupní tabulce však vše zůstává (u těchto záznamů je možné zobrazovat varování, pokud se nepovedlo řádek vložit)
● DML (Data Manipulation Language)● Vnější interface je manuální
● DCL (Data Control Language)● Irelevantní, jelikož spreadsheet nerozlišuje uživatele a neřeší paralelní zpracování
Příklad integritních omezení
● Uvažme následující schéma● Models(ModelID, …)
● Ord(Id, ModelID, Version, Descr), ModelID odkazuje na Models.ModelID
● V spreadsheet implementaci zavedeme následující worksheety● OrdInput
– n-tice zadané uživatelem
● OrdData
– n-tice odpovídající integritním omezením
– IF(OrdInput!RC5=“Invalid Data“; ““; OrdInput!RC) … pokud na vstupních datech nedošlo k chybě, překopíruje do tabulky Ord
● ModelsData
– Data odkazované tabulky
● Pro názornost jsou na následujícím obrázku všechny tabulky v jednom worksheetu
● Omezení INT, resp. SMALLINT, pro účely ukázky jsou 1024, 512
● Opět lze v novějších implementacích nahradit „RxCj:RyCj“ výrazem „Cj“
Testy
● Excel 2010 Beta, Intel(R) Core(TM)2 Duo CPU 2.40GHz 2GB RAM● Deseti tisíce řádků
● Využití obou jader
● Operace Standardizace, Třídění, Odstraňování duplikátů, JOINy
– Při použití SUMIFS místo SUMPRODUCT se některé operace zrychlily z jednotek minut na jednotky sekundy
● Insert
– Pokud se přidává na konec tabulky, vyvolá přepočet jedné formule a podle měření zabere 20-30 milisekund
● Delete, Update
– Je potřeba přepočítat lineárně mnoho řádků s pozicí mazaného, změněného řádku
Závěr
● Výkonnost● Rozsahy (RiCj:RmCn) jsou většinou ve formulých procházeny sekvenčně
● Formule jsou často v lineárním počtu polí k velikosti vstupní tabulky
● Výsledné přepočítání pak zabere nejméně kvadratický čas
● Existuje prostor pro zlepšení, doposud tato oblast nebyla příliš prozkoumána
● Lze odkazovat i na odlišné workbooky, v nichž se nepřepočítávají formule
● Lze vypnout automatické vyhodnocování a lze si jej vyžádat explicitně
● Funkcionalita● Z povahy spreadsheet aplikací a z jejich původního účelu plynou jistá omezení
(nevykonávají se dotazy, ale vytváří se de facto pohledy)
● Spolu s překladačem SQL do spreadsheet by bylo využití velmi pohodlné a tím přístupné vetší škále uživatelů
● Je otázkou, zda lze pomocí spreadsheetů vyjádřit dotazy v SQL99, Datalogu
– WITH … SELECT
Zdroje
● Jerzy Tyszkiewicz: Spreadsheet As a Relational Database Engine. Institute of Informatics, University of Warsaw, 2010
Otázky?