Témata diplomových prací

Řada open source projektů má vazby na prostředí univerzit a vysokých škol. PostgreSQL není výjimkou. Tento projekt vznikl v univerzitním prostředí - pod vedením profesora Computer Science Michaela Stonebrakera vznikl nový databázový systém, který sloužil jako platforma pro experimentální rozšíření klasického konceptu relačních databází o objektové principy. V rámci disertační prace Andrewa Yu a Jolly Chena byl Postgres rozšířen o jazyk SQL a vznikl tak systém PostgreSQL. Kód PostgreSQL se stále s oblibou používá v pro výuku návrhu a realizace relačních databázových systémů, případně pro ověřování některých moderních konceptů zpracování dat (např. proudové databáze). Na PostgreSQL je stále co vylepšovat, a to je zároveň příležitost pro studenty, jak spojit příjemné s užitečným - napsat kus sw, který se bude dále široce používat a zároveň pracovat na svých diplomové, bakalářských nebo disertačních pracích. Studenti studující informatiku si mohou vybírat z následujícího seznamu témat:

Implementace blokového zpracování dotazů v databázovém systému PostgreSQL

Vedoucí: Pavel Stěhule

Exekuční plán v databázovém systému PostgreSQL je v současnosti vykonáván iteracemi po řádcích, t.j. pro každý záznam, který má být součástí výsledku dotazu je vykonán celý exekuční plán. Cílem práce je implementace procedur pro vykonávání dotazu tak, aby se dotaz vykonával iteracemi po blocích a porovnání vlastností a efektivnosti nové implementace se stávající.

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. Gerhard Weikum, Gottfried Vossen: Transactional Information Systems,Morgan Kaufman 2002

Procedurální rozšíření jazyka SQL v systému PostgreSQL

Vedoucí práce: Pavel Stěhule

Cílem práce je rozšířit funkčnost SQL o procedurální konstrukce a funkce definované v SQL/PSM: proměnné, cykly, větvení, a to tak, aby tyto konstrukce bylo možné používat i mimo kontext SQL procedur a funkcí. Volně tyto konstrukce můžeme např. používat v T-SQL. V tomto pojetí je význam procedur pouze v tom, že umožňují parametrizaci (proti např. PL/SQL, kde procedurální konstrukce jsou dostupné pouze v proceduře nebo funkci).

       DECLARE a integer;
       SELECT INTO a x1
           FROM Foo;

nebo

       FOR SELECT sequence_name FROM information_schema
       DO
               DECLARE min integer;
               EXECUTE 'SELECT min_value FROM ' || sequence_name ' INTO min';
               EXECUTE 'ALTER SEQUENCE ' || sequence_name
                      || ' RESTART WITH ' || min;
       END FOR;

• podpora session proměnných:
• rozšíření příkazů DECLARE a SET
• možnost používat proměnné v SQL příkazech
• podpora řídících konstrukcí: cykly, větvení
• podpora příkazů IF, CASE
• podpora cyklů LOOP, WHILE, REPEAT
• podpora cyklu FOR

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. Jim Melton: Understanding SQL Stored Procedures: A Complete Guide to SQL/PSM, Morgan Kaufmann 1998
3. Gerhard Weikum, Gottfried Vossen: Transactional Information Systems,Morgan Kaufman 2002
4. ANSI SQL:2003 standard

Podpora SQL/PSM modulů v systému PostgreSQL

Vedoucí práce: Pavel Stěhule

Cílem práce je implementace modulů dle SQL/PSM v PostgreSQL. Moduly (jak je patrno z názvu) slouží k modularizaci kódu uložených procedur. Moduly umožňují zapouzdření procedur, tabulek, dočasných tabulek, proměnných. Zásadní rozdíl mezi modulem a schématem je možnost opakovaného použití modulů v různých databázích (tak jako se používají knihovny).

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. Jim Melton: Understanding SQL Stored Procedures: A Complete Guide to SQL/PSM, Morgan Kaufmann 1998
3. Gerhard Weikum, Gottfried Vossen: Transactional Information Systems,Morgan Kaufman 2002
4. ANSI SQL:2003 standard

Implementace cache na úrovni výsledků dotazů

Vedoucí práce: Pavel Stěhule

Cílem je navrhnout a implementovat řešení uložení výsledků SQL dotazů do cache, s cílem eliminovat vyhodnocení pokud se vstupní data (data v tabulkách) nezměnila. To v případě systémů ve kterých výrazně převažuje čtení (jako jsou např. webové aplikace apod.) výrazně přispívá ke zvýšení výkonu.

Obdobnou funkčnost má implementovánu např. MySQL pod názvem Query Result Cache.

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. MySQL Reference Manual / Query Result Cache, http://dev.mysql.com/doc/refman/5.1/en/query-cache.html

Implementace cache na úrovni výsledků funkcí

Vedoucí práce: Pavel Stěhule

Cílem je navrhnout a implementovat řešení uložení výsledků funkcí do cache, s cílem eliminovat opakované vyhodnocení funkce pokud se vstupní data (data ve čtených tabulkách a parametry funkce) nezměnily. To v případě systémů ve kterých výrazně převažuje čtení (jako jsou např. webové aplikace apod.) výrazně přispívá ke zvýšení výkonu.

Obdobnou funkčnost má implementovánu např. Oracle pod názvem Function Result Cache.

        CREATE OR REPLACE FUNCTION custfce(integer)
        RETURNS SETOF integer AS $$
           #option memcache($1) expiration 5min
        BEGIN
           RETURN QUERY SELECT a FROM foo WHERE a = $1;
           END;
        $$ LANGUAGE plpgsql;

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. Oracle Function Result Cache, http://download.oracle.com/docs/cd/B28359_01/appdev.111/b28370/subprograms.htm#BABFHACJ

Implementace kolekcí v PL/pgSQL

Vedoucí práce: Pavel Stěhule

Cílem je implementace nového datového typu (slovníku) a jeho podpora v PL/pgSQL. Tento nový datový typ by měl být použitelný i v ostatních PL jazycích PostgreSQL. Podpora kolekcí v PL/pgSQL by měla být kompatibilní s podporou kolekcí v PL/SQL.

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. ANSI SQL:2003 standard

Implementace příkazu MERGE v systému PostgreSQL

Vedoucí práce: Pavel Stěhule

Tento příkaz zajišťuje změnu specifikovaných dat. Pokud tato data neexistují, tak jsou do tabulky přidána. Příklad: inkrement materializované tabulky

       CREATE OR REPLACE FUNCTION inc(_key integer)
       RETURNS void AS $$
       DECLARE _v integer;
       BEGIN
          LOCK mattab;
          UPDATE mattab SET v = v + 1 WHERE key = _key;
          IF NOT FOUND THEN
            INSERT INTO mattab VALUES(_key, 1);
          END IF;
       END;

Ukázková implementace je robustní nicméně vzhledem k zamknutí tabulky není 'příliš efektivní. Podstatně efektivnější implementace se dosáhne implementací na úrovni indexů - souvislost s mechanismem jištění unikátnosti hodnot v unikátních indexech je zřejmá (podmínkou implementace je unikátní index v tabulce).

    MERGE INTO table_name USING table_name ON (condition)
    WHEN MATCHED THEN UPDATE SET column1 = value1 [, column2 = value2 ...]
    WHEN NOT MATCHED THEN INSERT column1 [, column2 ...]
                                            VALUES (value1 [, value2 ...])

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. ANSI SQL:2008 standard

Implementace referencování a dereferencování v PostgreSQL

Vedoucí práce: Pavel Stěhule

SQL99 obsahuje koncept podporující OOP aplikace na úrovni SQL. Tento koncept narušuje zažité zvyklosti a vzory pro základní operace s daty a skrývá jistou složitost SQL před uživateli (o totéž se snaží ORM).

       CREATE TABLE Deti (
               id serial PRIMARY KEY,
               rodic REF (Rodice) SCOPE Rodice,
               jmeno varchar(30),
                    ...
       SELECT jmeno, prijmeni, rodic->jmeno, rodic->prijmeni
           FROM Deti; -- system provede automaticky pripojeni tab. Rodice

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. Gerhard Weikum, Gottfried Vossen: Transactional Information Systems,Morgan Kaufman 2002
3. ANSI SQL:2003 standard

Porovnání databázových úložišť

Vedoucí práce: ----

Cílem práce je porovnat jednotlivé modely ukládání dat v různých SŘBD (PostgreSQL, Firebird, MySQL, Oracle ...) a popsat jejich výhody a nevýhody. Dále se zaměřit na to jak je řešena obnova po výpadku systému.

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. Gerhard Weikum, Gottfried Vossen: Transactional Information Systems,Morgan Kaufman 2002
3. Robert Mach: Design of Integrity Check And Repair Algorithms For PostgreSQL Data File, DP FEL CVUT, 2008

Rozšíření transakčních vlastností

Vedoucí práce: ----, Pavel Stěhule

Implementujte Repeatable Read Isolation Level a Autonomní transakce do PostgreSQL Autonomní transakce umožňují samostatné potvrzení subtransakce. Často se používají (a zásadně zjednodušují) práci s databázemi workflow aplikací. Další oblastí, kde se AT používají, je logování a audit databází.

       BEGIN AUTONOMOUS TRANSACTION;
       INSERT INTO log(note) VALUES('Uzivatel se pokusil o ...');
       COMMIT;

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. Gerhard Weikum, Gottfried Vossen: Transactional Information Systems,Morgan Kaufman 2002

Úprava embeded C pro rozhrani SPI

Vedoucí práce: Pavel Stěhule

PostgreSQL nabízí tzv. embeded C, což je preprocesor C umožnující integraci SQL do C. Aktuálně je podporováno pouze klientské rozhraní, tudíž tuto funkcionalitu nelze použít pro uložené procedury. Cílem je upravit stávající preprocesor tak, aby se místo klientského rozhraní použilo rozhraní SPI a vygeneroval kód, který lze spustit na straně serveru.

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf

Podpora globální dočasných tabulek

Vedoucí práce: Pavel Stěhule

Životnost dočasných tabulek je limitovaná session uživatele. Po uzavření session jsou všechny dočasné tabulky odstraněny. Takto navržené tabulky lze poměrně jednoduše implementovat, mají však několik podstatných nevýhod: a) před každým použitím je nutné tyto tabulky vytvořit znovu, což komplikuje kód aplikační kód (je třeba zjistit, zda-li tabulky existují a podle toho se zařídit) zvláště vzhledem ke skutečnosti, že PostgreSQL nepodporuje databázové triggery (trigger na událost přihlášení a odhlášení uživatele). b) díky tomu, že se neustále vytváří a ruší, tak dochází k častým operacím update v systémových tabulkách (v některých aplikacích i několik set krát během 1 sec), což si vynucuje častější vacuum, což se negativně projeví na výkonu.

Úkolem práce je navrhnout a realizovat tzv. globální dočasné tabulky, které z hlediska životního cyklu se chovají stejně jako klasické tabulky, a z hlediska obsahu se chovají jako dočasné tabulky, tj. každý uživatel má vlastní obsah, který po ukončení session zaniká. Je třeba preferovat výkon, takže je potřeba navrhnout takové řešení, kde by nedocházelo k fyzické modifikaci systémových tabulek a zároveň minimalizovat nezbytné změny v PostgreSQL (což je obvyklý požadavek).

Literatura:

1. Neil Conway, PostgreSQL hacking, http://neilconway.org/talks/hacking/ottawa/ottawa_slides.pdf
2. ANSI SQL:2003 standard

Integrace runtime Parrot do PostgreSQL

Vedoucí práce: Pavel Stěhule

Prostředí parrot vzniklo při vývoji jazyka Perl6. Parrot představuje univerzální runtime (včetne JIT) pro řadů jazyků (zejména Perl6, ale i BASIC, LUA a další). Cílem práce je napsat překladač jazyka PL/pgSQL nebo PL/pgPSM pro toto prostředí. K těmto jazykům je k dispozici parser. Výsledkem práce je překladač a posouzení rychlosti stávajícího řešení a řešení postaveného nad parrotem.

Literatura: http://www.parrotblog.org/2008/03/targeting-parrot-vm.html

Využití runtime jazyka Lua pro PL/pgSQL

Vedoucí práce: Pavel Stěhule

Jazyk Lua obsahuje malý a výkonný runtime. Cílem diplomové práce je integrace tohoto runtime do PostgreSQL včetně jeho použití pro No SQL procedury v jazyce PL/pgSQL nebo PL/pgPSM. K těmto jazykům je k dispozici parser. Výsledkem práce je překladač a posouzení rychlosti stávajícího řešení a řešení postaveného nad Lua VM.

Literatura:

1. http://www.lua.org/pil/
2. http://www.root.cz/clanky/lua-vestavitelny-minimalista/
3. http://luajit.org/
4. http://foja.dcs.fmph.uniba.sk/kompilatory/docs/compiler.pdf
5. http://docs.linux.cz/misc/skolicky/skolicka2.html

Překladač PL/pgSQL procedur do jazyka C

Vedoucí práce: Pavel Stěhule

PostgreSQL obsahuje interpret jazyka PL/pgSQL. Cílem práce je vytvoření překladače do programovacího jazyka C a demonstrace tohoto překladače pro praktické použítí. K dispozici je parser jazyka PL/pgSQL jehož výsledkem je AST (Abstract Syntax Tree). Výsledkem práce je porovnání rychlosti zpracování funkcí přeložených z C vůči stávajícímu interpretu PL/pgSQL.

Literatura:

1. http://docs.linux.cz/misc/skolicky/skolicka2.html
2. http://foja.dcs.fmph.uniba.sk/kompilatory/docs/compiler.pdf
3. http://tldp.org/HOWTO/GCC-Frontend-HOWTO.html#toc3
4. http://www.linuxjournal.com/article/7884
5. http://gcc.gnu.org/frontends.html
6. http://palestras.gustavobarbieri.com.br/gcc-front-end/fisl-2006/intro.pdf

Interpret a JIT překladač PL/pgSQL NO SQL procedur s využitím LLVM

Vedoucí práce: Pavel Stěhule

LLVM je prostředí pro tvorbu překladačů. PostgreSQL obsahuje interpret jazyka PL/pgSQL. Cílem práce je vytvoření překladače do kódu virtuálního stroje LLVM a demonstrace tohoto překladače pro praktické použítí. K dispozici je parser jazyka PL/pgSQL jehož výsledkem je AST (Abstract Syntax Tree). Výsledná práce musí obsahovat výkonnostní srovnání stávajícího stavu a řešení postaveného nad LLVM.

Literatura:

1. http://staff.polito.it/silvano.rivoira/HowToWriteYourOwnCompiler.htm

Validace XML Type proti DTD, XSD, RNG

Vedoucí práce: Petr Chmelař

Ve verzi 9 tuto možnost XML Type nemá. V práci jde o integraci těchto funkcí prostřednictvím otevřených knihoven.

Literatura:

1. http://www.postgresql.org/docs/9.0/static/datatype-xml.html
2. http://www.relaxng.org/

Návrh a implementace Překladače a exekutoru jazyka MDX pro prostředí PostgreSQL

Vedoucí práce: Pavel Stěhule

Cílem práce je navrhnout a implementovat překladač jazyka MDX (MultiDimensional eXpressions) pro RDBMS PostgreSQL. Implementace by měla končit vytvořením jednoduchého serveru protokolově kompatibilního s PostgreSQL zvládajícího přijmutí MDX dotazu, jeho zpracování a překlad na SQL příkazy zpracované určeným SQL serverem, a odeslání výsledku zpět ke klientu. Server musí zvládat nativní komunikaci s PostgreSQL klientem - tak aby bylo možné se k serveru připojit z SQL konzole psql.

Literatura:

• http://en.wikipedia.org/wiki/MultiDimensional_eXpressions
• http://www.mosha.com/msolap/mdx.htm
• http://www.databasejournal.com/article.php/1459531/
• http://developer.postgresql.org/pgdocs/postgres/protocol.html
• http://www.gnu.org/software/bison/
• http://www.antlr.org/grammar/1101743472259/mdparser.g

Návrh a implementace write once případně append only engine

Vedoucí práce: Pavel Stěhule

Velké množství dat v databázi není nikdy upravováno, a ani se nepředpokládá jejich úprava - např. naměřená data. Uložení takových to dat v Postgresu v podobě normalizovaných tabulek není příliš efektivní - každý řádek totiž obsahuje 23 byte velkou signaturu, která zajišťuje podporu MVCC, kterýžto mechanismus se ovšem u takových to dat neuplatní. Cílem je upravit Postgres tak, aby umožňoval efektivní uložení vědeckých dat, přičemž tato data se nikdy nebudou upravovat - není nutné podporovat operace UPDATE a DELETE. Pokud dojde k připojení nových dat, tak se bude jednat o větší dávkovou operaci (nad desítky KB). K implementaci je možné využít i FDW interface.

Literatura:

• https://bitbucket.org/adunstan/blackhole_fdw

Návrh a implementace loose index scanu

Vedoucí práce: Pavel Stěhule

Aktuálně PostgreSQL neumí využít index pro optimalizaci výrazů obsahující klauzuli DISTINCT. Cílem práce je zjistit důvody tohoto chování a navrhnout a připravit efektivní implementaci příkazu COUNT(DISTINCT) pokud je k dispozici index. Postgres umí využívat indexy pro agregační funkce -- např. pro funkce MIN, MAX - nicméně COUNT(DISTINCT) není zatím operace podporovaná indexem.

Další možná témata

• Použití JIT v expression executoru a SQL executoru
• Implementace pipelined DML dle ANSI SQL

SELECT oldtbl.empno FROM OLD TABLE (DELETE FROM emp WHERE deptno = 2) AS oldtbl;
SELECT newtbl.empno FROM NEW TABLE (UPDATE emp SET salary = 0 WHERE deptno = 2) AS newtbl;