Spreadsheet jako engine relačních databází. Jakub Daniel Matematicko-fyzikální Fakulta 2011

Spreadsheet jako engine relačních databází

Jakub Daniel Matematicko-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 ●

●

Využítí čisté spreadsheet funkcionality běžných implementací ●

●

●

Selection, Projection, Semijoin, Join, Cartesian Product, Union, Difference, Grouping, Aggregation 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], ““) –

●

Projekce ●

●

●

P je predikát na sloupcích relace (používající AND, OR, NOT)

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:Ry1:Cj) … ulož počet řádků jedné relace

●

IF(ROW() <= RaCb; RCj; INDEX(Rx2Ck:Ry2Ck;ROW() - RaCb));

Difference ●

●

SUMPRODUCT((Rx2Cj2:Ry2Ci2=RCi1)*(Rx2Cj2:Ry2Cj2=RCj1) ...) … 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); ““) –

●

IF(ROW() <= R1Cs * R2Cs; INDEX(RuCj:RvCj; MOD(ROW() - 1; R2Cs) + 1); ““) –

●

Vytvoří R2Cs kopií sloupce Ci (nejprve R2Cs kopií první hodnoty, pak další ...) Vytvoří R1Cs kopií sloupce Cj

SEMIJOIN ●

●

IF(ISERROR(MATCH(RCj1;RxCj2:RyCj2;0); ““; RCj1) … zahodí řádky R1, 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á ●

●

●

DML (Data Manipulation Language) ●

●

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)

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 –

●

Insert –

●

Při použití SUMIFS místo SUMPRODUCT se některé operace zrychlily z jednotek minut na jednotky sekundy

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?