Databázové modely a jazyky

Z ωικι.matfyz.cz
Přejít na: navigace, hledání

okruhy 14/15: Typy dotazovacích jazyku (procedurální, neprocedurální, jazyky pro výber dokumentu), SQL a jeho standardy. Algoritmy implementace relacních operací. Vyhodnocování a optimalizace dotazu. Algoritmy vyhodnocení dotazu v Datalogu a Datalogu s negací. Objektové rozšírení relacního modelu dat. Databáze textu - modely (Booleovský, vektorový). Vyhledávání vzorku v textech (sousmerné, protismerné). XML data v relacích, indexace XML dat, podobnost XML dat, XML a webové služby. Datový model RDF, dotazovací jazyk SPARQL, podobnostní dotazy v multimediálních databázích, metrické indexacní metody.

Obsah

Typy dotazovacích jazyků (procedurální, neprocedurální, jazyky pro výběr dokumentů)[editovat | editovat zdroj]

Procedurální[editovat | editovat zdroj]

popisují jak se dostaneme k hledanému výsledku (jednotlivé příkazy)

dotaz jako posloupnost operací nad relacemi, jsou založeny na relační algebře

💡 RA: neprocedurální, nicméně struktura výrazu navádí na pořadí a způsob vyhodnocení
  • SQL server: Transact SQL (T-SQL)
  • Oracle: PL/SQL

(také navigační, algebraické)

Neprocedurální[editovat | editovat zdroj]

popisují co chceme zjistit (specifikujeme jak má vypadat výsledek) a je na DB systému, aby řekl, jak se k výsledku dostat

dotaz se zadává jako predikát charakterizující výslednou relaci, výsledkem výběru dat je relace, která splňuje podmínky formule. Jsou založeny na relačním kalkulu.

💡 Relacniho kalkul: „více neprocedurální“ než relační algebra. Specifikuje se pouze „co má výsledek splňovat“.
  • SQL (ISO standard, dotazovací jazyk pro relační DB)
  • XQuery (standard W3C, dotazovací jazyk pro XML)

(také specifikační, deskriptivní, deklarativní)

Jazyky pro výběr dokumentů[editovat | editovat zdroj]

dokumentografické informační systémy (hledám dokumenty, které obsahují určité termy)

  • boolský model
  • vektorový model

SQL[editovat | editovat zdroj]

Sémantika SQL[editovat | editovat zdroj]

SELECT

tabulka s RČ zákazníků a počtem jejich výpůjček,

přičemž zákazníci jsou z Prahy a mají vypůjčeny aspoň dvě kopie,
tabulka je setřízená sestupně):
SELECT rod_č, COUNT(č_kopie) AS počet_kopií
  FROM Výpůjčky V, zákazníci Z
    WHERE V.rod_č = Z.rod_č AND Z.adresa LIKE ‘%Praha%‘
  GROUP BY V.rod_č
    HAVING COUNT(č_kopie) > 2
  ORDER BY počet_kopií DESC

Kde

  • výrazy mohou být sloupce, sloupce s agregačními funkcemi, výsledky dalších funkcí ...
výraz = <název sloupce>, <konstanta>, 
(DISTINCT) COUNT( <název sloupce> ),
[DISTINCT] [ SUM | AVG ]( <výraz> ),
[ MIN | MAX ]( <výraz> )
a navíc lze použít operátory +,-,*,/.
  • zdroje jsou tabulky nebo vnořené selecty
  • výrazy i zdroje být přejmenovány pomocí AS, např. pro odkazování uvnitř dotazu nebo jména na výstupu (od SQL-92)
  • podmínka je logická podmínka (spojovaná logickými spojkami AND, OR) na hodnoty dat ve zdrojích:
podmínka = <výraz> BETWEEN <x> AND <y>, <výraz> LIKE "% ... ",
<výraz> IS [NOT] NULL,
<výraz> > = <> <= < > [<výraz>/ ALL / ANY <dotaz>],
<výraz> NOT IN [<seznam hodnot> / <dotaz>], EXIST ( <dotaz> )
  • GROUP BY znamená agregaci podle unikátních hodnot jmenovaných sloupců (v ostatních sloupcích vznikají množiny hodnot, které se spolu s oněmi unikátnímí vyskytují na stejných řádkách
  • HAVING označuje podmínku na agregaci
  • ORDER BY definuje, podle hodnot ve kterých sloupcích nebo podle kterých jiných výrazů nad nimi provedených se má výsledek setřídit (ASC požaduje vzestupné setřídění, DESC sestupné)

Structured Query Language je standardní neprocedurální jazyk pro přístup k relačním databázím. Jeho syntaxe odráží snahu o co nejpřirozenější formulace požadavků -- je podobná anglickým větám.

Praci s nim lze rozdelit na dve hlavni pouziti:

Klastrovaný vs. obyčejný index
DDL - data definition language (jazyk pro definici dat)
  • CREATE/ALTER/DROP TABLE/INDEX/TRIGGER/SEQUENCE/VIEW
  • Př.: Oracle DDL syntaxe:
create table  testovaci_tabulka (
    cislo number(5,1) primary key,
    retezec varchar2(123),
    datum date not null);
vytvori tabulku testovaci_tabulka
obsahujici 3 sloupecky - cislo,
do ktereho se vejdou cisla se ctyrmi cislicemi pred a
jednou za desetinnou carkou. Sloupecek cislo je PK tabulky.
Dale retezec pro ulozeni az 123 znaku dlouheho retezce a
datum, ktere nemuze byt prazdne.
  • indexy
  • integritní omezení - CREATE DOMAIN/CONSTRAINT
  • ref.integrita - FOREIGN KEY/ON DELETE/ON UPDATE
DML - data manipulation language (manipulace s daty)
  • SELECT A₁,...,Aⱼ FROM R₁,...,Rₖ WHERE φ
    • ≅ (R₁×...×Rₖ)(φ)[A₁,...,Aⱼ]
  • INSERT INTO t (...) VALUES (...)
    • insert into testovaci_tabulka (cislo, retezec, datum) values (4.3, 'ahoj svete!', to_date('17.1.2007', 'dd.mm.yyyy'));
  • UPDATE t SET (...) WHERE ...
  • DELETE FROM t WHERE ...
  • aggregační fce: COUNT/MAX/AVG/SUM
  • hodnotové výrazy CASE-WHEN-THEN
    • COALESCE(vypujcky.cena, "vypiš tohle pokud cena IS NULL")
    • NULLIF
  • prefikáty LIKE/MATCH/UNIQUE/ANY/ALL/SOME
  • kvantifikátory EXISTS
  • množinové operace UNION/INTERSECT/EXCEPT
  • pohledy

JOINy (od SQL92)[editovat | editovat zdroj]

INNER - pouze od. řádky z obou tabulek

FULL OUTER JOIN - všechny řádky z obou tabulek, pokud chybí odpovídající na levé/pravé straně doplní se null

LEFT OUTER JOIN - všechny řádky z levé tabulky, pokud chybí odpovídající na pravé straně doplní se null

  • analogicky RIGHT

CROSS JOIN - všechno se vším, kartézský součin

SQL a jeho standardy (🎓🎓🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • SQL (2015, konzultace) - "když dostanete SQL a dáte špatně syntaxi SELECTu na papír, tak vás na tom u státnic vykostí"
  • SELECT - srovnani SQL-89 a SQL-92 (2014, Skopal) - Az ve standardu SQL-92 pribyly prikazy spojeni, do te doby se musel pouzivat kartezsky soucin jako SELECT * FROM table1, table2 Pomoci klicovych slov definovanych standardem SQL-89 neslo ziskat vysledek ekvivalentni vysledku, kde je pouzit OUTER JOIN. Vnejsi spojovani muze do vysledku zahrnout null hodnoty, ale kartezskym soucinem to neudelame.
  • SQL standardy (2011, Pokorny) - pohoda, rikam si. Nejak jsem to tam vypsal, co se ktery rok udalo. Projizdel to a pak se zarazil u rekurzivniho SQL - to byla zasadni chyba, ze jsem zminil! Hned se v tom zacal hrabat a padala slova jako Minimalni pevny bod, Tranzitivni uzaver a jine sproste vyrazy. Docela jsem si zaplaval, ptz hledat Min PB v SQL vyrazech neni zrovna moje kazdodenni hobby. Neco jsem tam nakonec vzdy vymyslel, zkousejici byl hodny a trpelivy. Nakonec se tvaril v pohode. Ne horsi nez 2, vypadal spokojene
  • SQL SELECT (2009, Skopal) - Mal to byt popis syntaxe. Teda co vsetko sa da selectom zapisat. Kolko ma casti, co robia, opytal sa ako sa vyhodnocuju, popisal som rozne spojenia a pokracovali sme pokecom nad vnorenymi dotazmi a fungovanim IN, ALL, EXIST. Tiez sme niekde po ceste chvilu kecali o agregovani riadkov, agregacnych funkciach. Tiez celkom v pohode.


SQL je neproceduralni jazyk slouzici pro praci se SRBD. Nerika jak se to, co chceme, ma udelat, ale jen co se ma udelat. Implementacni detaily nechava na databazi. Jednotlive databaze (ORACLE, MS-SQL, MySQL, ...) maji mirne odlisne dialekty SQL, i kdyz existuji standardy (sql86, sql89, sql92, sql1999, sql2003, sql2006). V zakladnich vecech se krome nazvu datovych typu ovsem moc nelisi.

Standardy SQL[editovat | editovat zdroj]

SQL je standard podle norem ANSI/ISO a existuje v několika (zpětně kompatibilních) verzích (označovaných podle roku uvedení):

  • SQL-86 - první nástřel, průnik implementací SQL firmy IBM
  • SQL-89 (SQL1) - malá revize motivovaná komerční sférou, mnoho detailů ponecháno implementaci
    • 💡 spojení je možné pouze přes SELECT ... FROM A1,A2 WHERE... což umožňuje pouze vnitřní spojení (INNER) a kart.součin (CROSS) - tj. klíč.slovo JOIN ještě není
  • SQL-92 (SQL2) významná revize (∃ ve 4 verzích: Entry, Transitional, Intermediate a Full)
    • přidán JOIN - a jeho další druhy, hlavně OUTER JOIN, ktery standardem SQL-89 neslo provest (kartezskym soucinem nelze ziskat NULL hodnoty) - viz info o JOIN
    • nove datove typy (DATE, TIME, VARCHAR, ...)
    • INFORMATION_SCHEMA.TABLES - metadata tabulek jako tabulka
    • množ.operace
    • kaskádové mazání/aktualizace podle cizích klíčů, kurzory, výjimky
    • Definovany urovne izolace transakci: READ UNCOMMITTED, READ COMMITTED, REPEATABLE READ a SERIALIZABLE
  • SQL:1999 (SQL3) - regulární výrazy, rekurzivní dotazy, triggery (procedura co se spousti v rekci na nejakou udalost), booleovské typy, ...
    • procedurální rozšíření SQL - některé objektově orientované rysy , stored procedures
    • nové datové typy -- reference, pole, full-text, boolean
    • rekurze (CTE) - konečně můžeme udělat tranzitivní uzávěr
    • podpora pro externí datové soubory, multimédia
  • SQL:2003 (některé XML rysy, generátor sekvencí, MERGE, CREATE TABLE LIKE, ...)
    • větší ARRAY, SET, MULTISET
  • SQL:2006 – definuje širší využití XML, integrace XQuery, ...
  • SQL:2008
  • SQL:2011

Komerční systémy implementují SQL podle různých norem, někdy jenom SQL-92 Entry, dnes nejčastěji SQL-99, ale nikdy úplně striktně. Některé věci chybí a naopak mají všechny spoustu nepřenositelných rozšíření -- např. specifická rozšíření pro procedurální, transakční a další funkcionalitu (T-SQL (Microsoft SQL Server), PL-SQL (Oracle) ). S novými verzemi se kompatibilita zlepšuje, často je možné používat obojí syntax. Přenos aplikace za běhu na jinou platformu je ale stále velice náročný -- a to tím náročnější, čím víc věcí mimo SQL-92 Entry obsahuje.Pro otestování, zda je špatně syntax SQL, nebo zda jen daná databázová platforma nepodporuje některý prvek, slouží SQL validátory (které testují SQL podle norem).

Rekurze v SQL. (🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Rekurze v SQL (2016, Pokorny) - Chcel vediet kedy bolo standardizovane, ako vyzera dotaz a porovnat s rekurziou v datalogu (oproti datalogu je mozna len linearna forma rekurze).
  • Rekurzivní SQL (Pokorny?) - Hned se v tom zacal hrabat a padala slova jako Minimalni pevny bod, Tranzitivni uzaver a jine sproste vyrazy. Docela jsem si zaplaval, ptz hledat Min PB v SQL vyrazech neni zrovna moje kazdodenni hobby. Neco jsem tam nakonec vzdy vymyslel, zkousejici byl hodny a trpelivy. Nakonec se tvaril v pohode. Ne horsi nez 2, vypadal spokojene


vyhody/nevyhody:
+ vše jedním dotazem
+ lze využít velkou část výsledku
- časté využití pouze malé části výsledku
- možnost zacyklení rekurze
  • novinka v SQL:99 (SQL3)
podpora v reálných DB  
 
 WITH UsersAndPosts (CreationDate, DisplayName)
 AS
 (
     SELECT p.CreationDate, u.DisplayName
     FROM Posts AS p INNER JOIN Users AS u ON p.OwnerUserId = u.Id
       [UNION ALL]       // nepovinne
       rekurzívní člen   // nepovinne
 )
 SELECT * FROM UsersAndPosts

Common Table Expression (CTE)[editovat | editovat zdroj]

  • vytvoří se dočasná tabulka (existuje pouze v době vyhodnocování dotazu)
  • deklaruje se klíčovým slovem WITH RECURSIVE jméno_CTE[(jméno_sl[,jméno_sl]…)] AS (CTE_definice_dotazu)
    • V CTE pro tabulku R se lze odkazovat na R
WITH RECURSIVE
  ukotvení (inicializační poddotaz) - spouští se jednou
  UNION ALL
  rekurzívní člen - opakovaně
    •rekurze běží pokud není přidán žádný další záznam anebo není překročený limit rekurze (MAXRECURSION)
    •pozor na zacyklení rekurzívního členu
    INNER JOIN - spojení s minulým krokem
  SELECT
    •Vnější SELECT - dá výsledek dotazu(výstup)

Příklad: Najdi všechny nadřízené Nového (včetně něho sama)

WITH RECURSIVE Nadřízení(jméno, č_nad, č_zam) AS
(SELECT jméno, č_nad, č_zam
  FROM Zaměstnanci
  WHERE jméno = 'Nový'
  UNION ALL
SELECT Z.jméno, Z.č_nad, Z.č_zam
  FROM Zaměstnanci AS Z
  INNER JOIN
  Nadřízení AS N
  ON N.č_nad = Z.č_zam)
SELECT * FROM Nadřízení
Příklady  
Příklad z přednášky

Tabulka: Zaměstnanci(č_zam, jméno, funkce, č_nad)

Najdi všechny nadřízené Nového (včetně něho sama)

WITH RECURSIVE Nadřízení(jméno, č_nad, č_zam) AS
    (SELECT jméno, č_nad, č_zam
        FROM Zaměstnanci
        WHERE jméno = 'Nový'
        UNION ALL
    SELECT Z.jméno, Z.č_nad, Z.č_zam
        FROM Zaměstnanci AS Z
            INNER JOIN
            Nadřízení AS N
            ON N.č_nad = Z.č_zam)
SELECT * FROM Nadřízení
Příklad

Mame tabulku Zamestnanci(jmeno, plat, vedouci). Najdete pomoci rekurzivniho dotazu vsechny zamestnance s platem nad 100 000, kteri jsou (i neprimi) podrizeni Ryby.

WITH RECURSIVE PodRybou(jméno) AS 
    (SELECT jméno
        FROM Zamestnanci
        WHERE vedouci = “Ryba”
        UNION ALL
    SELECT jméno
        FROM Zaměstnanci Z, PodRybou P
        WHERE Z.vedouci = P.jmeno
)
SELECT * FROM PodRybou
WHERE plat > 100 000
další zdroje  


Algoritmy implementace relacních operací. Vyhodnocování a optimalizace dotazů (🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • Algoritmy implementace operace relacni algebry (2016, Hoksza) - Bez pripravy som z hlavy popisal nieco o hniezdenych cykloch, setrideni a slevani a jemne spomenul hashovanie. Nasledne mi povedal, aby som tieto metody popisal z hladiska vyhodnosti pri rozlicnych velkostiach spojovanych tabuliek. Celkovo bez problemov.
  • SQL + vyhodnocovanie a optimalizácia dotazov (Richta) - bol super, dokonca mu nevadilo, že som zabudol popísať optimalizáciu, stačilo len 3 vetami vysvetliť, o čo ide
  • Implementace operací relační algebry (JOIN)


Vyhodnocování (Algoritmy implementace relacních operací)[editovat | editovat zdroj]

CPU je rychle a levne, RAM je taky relativne dost, dulezity je pocet pristupu na disk

indexace je delana b+ stromy s vysokym poctem nasledniku (50-100), ale tak, aby se jeden uzel vesel do jedne stranky na disku a byla nizka uroven (pocet pater) indexu

1. selekce[editovat | editovat zdroj]

SELECT * FROM R WHERE A = 'a'

ruzne vysledky podle toho, zda A je PK (unique), sekundarni klic (nemusí být unique), A je hasovany klic:

  • sekvencni vyhledavani - v průměrném případě, je- li A PK stačí prohledat půlku (PK zarucuje unikatnost, v okamžiku, kdy naleznu první záznam, nemusím pokračovat) v nejhorším musím projí celé
  • binarni vyhledavani (je-li R usporadana podle A) - log₂(#počtu stránek) pro PK, pripadne plus nacteni dalsich bloků se shodnou hodnotou, neni-li to PK
  • existuje-li index - průchod stromem + nějaké malé hledání na disku
  • vyhledani s hasovanim – přibližně 1 přístup (záleží na hašovací funkci).
2. vypocet spojeni[editovat | editovat zdroj]

SELECT * FROM R, S WHERE R.A = S.A

zakladni metody hnizdene cykly, trideni- slevani, hasovane spojeni, kartezsky soucin (spec. případ spojení)

a) hnízděné cykly[editovat | editovat zdroj]
  • po strankach
  • nejdrive selekci a pak spojeni
  • spojeni vice relaci - pro vnější cykly použiji menší data
b) setrideni-slevani ()[editovat | editovat zdroj]
  • klasicke trideni na vnejsi pameti, pak slévání (spojování)
  • varianta s ukazateli
c) hasovani (nejlepsi pro malo pameti)[editovat | editovat zdroj]
GRACE h(x) = x mod 3
💡 nejsou-li indexy pro R.A a s.A, nemusi-li byt vysledek setrizen (jde taky vyrobit vysledek a pak ho dodatecne setridit)
  • klasicke hasovani (predpokladame, ze se tabulka vejde do pameti)
  • GRACE algoritmus - rozdel pomoci hashovaci fce obě tabulky do kapes ukazatelu (skupiny ukazatelu na prvky se stejnym hashem). Pro kazdou kapsu zvlast nacti do pameti a otestuj R.A = S.A a pripadne zapis do vystupniho bufferu. Vhodne, pokud se mi jednotlive kapsy vejdou do pameti.
    • vylepseni: jednoduche hashování (hashuju na 2 půlky) - vzdy zahashuju do paměti jen 1. kapsu, zbytek (2. kapsu) hodím na disk, pokud je zbytek moc velký přehashuji na mensí, takhle postupne zahashovávám
    • vylepseni: hybridní - cyklické prehashovani pokud zaplním pamet

dalsi operace - GROUP BY, DISTINCT se resi pres hasovani, nebo rozdelenim pomoci indexu (pokud je), pripadne trizenim

Optimalizace[editovat | editovat zdroj]

aneb "Mnoho psů JOINů zajícova smrt."

Faze zpracovani dotazu:

1. prevod do vnitrni formy (typicky nejaka relacni algebra) + 2. konverze do kanonickeho tvaru

3. algebraicka optimalizace - přerovnání selekcí, projekcí, spojení

Rule-based optimalizace

A rule based optimizer is an optimizer that just applies a set of rules to a SQL statement instead of looking at cost estimates in order to determine what the best way is to execute that SQL statement. Oracle actually allows you to use either the rule based or cost based optimizer, although Oracle says that rule based optimization will be deprecated in a future release, so it highly recommends the use of cost based optimization.

Heuristiky:

  • selekce co nejdrive
    • nebo lépe: přeskupení relací ve stromu dotazu tak, aby selekce produkující menší relace byly volány dříve
  • projekce co nejdrive
    • nebo lépe: sjednotit vice operaci selekce (projekce) do jedne
  • transformace $ \times $ na *

Cost-based optimalizace

  • databáze spočítá pro všechny možné plány vyhodnocení dotazu jeho odhadovanou cenu (na základě statistik, které si ukládá – např velikost jednotlivých tabulek, blokovací faktor, poměr mezi rychlostí paměti a disku, historgram sloupců – pro rozhodnutí, zda se vyplatí použít index nebo ne, apod.) a následně vybere nejlevnější možnost, může se ukázat, že odhady nebyly správné, v průběhu prvního spuštění dotazu se počítá doba jednotlivých kroků a nakonec se přepočítá volba algoritmu s aktuálními hodnotami - při dalším spuštění již dotaz běží optimálně
  • katalogy
  • redukční faktor
  • histogramy - rozdělení dat

4. Plan vyhodnoceni - strom dotazu + algoritmus pro kazdou operaci

Pro vsechny uvazovane plany se spocita odhadovana cena dotazu. To se udela s vyuzitim statistik o tabulce(tabulkach) a znalosti existence a typu indexu. Plan s nejmensi cenou se vybere.

Priklady ruznych planu a jejich cen (selekce prvni, selekce druha)

Dotazy nad vice tabulkami se resi vybranim nejlepsiho reseni pro jednu kazdou tabulku a pak vybranim nejlepsiho spojeni. spojuje se vzdy s jednou tabulkou (1 s 1, 2 s 1, ... n-1 s 1)

Slozitejsi dotaz je rozlozen na bloky (treba hlavni cast dotazu a vhnizdeny dotaz), ktere se optimalizuji zvlast.

Objektové rozšíření relačního modelu dat (🎓)[editovat | editovat zdroj]

příklad ADT:
CREATE TYPE T_Student AS (
 Jm	CHAR(30),
 Adresa	CHAR(40),
 Zac_ studia DATE
) UNINSTANTIABLE NOT FINAL
METHOD Poc_Prednasek()
 RETURNS INTEGER;
Zážitky ze zkoušek  
  • Objektové rozšíření relačního modelu dat (2014, Pokorný) - K této otázce jsem toho upřímně zase tak moc nevěděl. Jen jsem napsal, že lze definovat vlastní typy, třídy, metody, že existují pole a reference (REF) a že je to implementováno v SQL. Pak jsem s panem Pokorným vedl diskusi, kde se vyptával na různé věci, např. chtěl vědět, jestli může existovat třída sama o sobě (ne - musí být vždy uložená v tabulce), chtěl slyšel o ID v třídách, jak jsou uložené v tabulkách, kde se definují metody (ve třídách), apod. Nějak jsem to s jeho pomocí vyplodil a celkově byl myslím spokojený.


svět db technologií

bylo potřeba nějak zlepšit práci s BLOB/CLOB ⇒ rozšiřitelnost o nové datové typy

  • Oracle - cartridges
  • SQL Server - cartridge/ASSEMBLY

Ukotveno standardem SQL:1999:

  • Uživatelské Datové Typy (UDT)
    • Abstraktní Datové Typy (ADT) - "třídy"
      • možnost vytvářet vlastní strukturované datové typy zapouzdřující data a operace (např. porovnávací operace)
      • píšou se v SQL, C, C# ...
      • mohou mít dědění a polymorfismus
      • [UN]INSTANTIABLE - povolení/zakazani vytvareni instanci
      • [NOT]FINAL - povolení/zakazani dědění
      •  ????může existovat třída sama o sobě? ne pouze v tabulce
      • Uživatelské Datové Funkce/Procedury (UDF/UDP)
        • metody svázány s typem, fce ne
      • Pojmenované řádkové typy
        • řádka je identifikována pomocí omělého klíče (OID – Object IDentificator)
    • Kolekce: ARRAY
      • LIST, BAG, SET, MULTISET (až v 2003)
    • Reference - REF - umožňuje chápat data jako objekty
      • operátory DEREF a ->
      • operátor IS DANGLING (odkazovaný objekt už neexistuje)

další řešení: ORM - nevýhoda: 15-20% pomalejší

  • př: (N)Hibernate, Entity Framework...
další zdroje  

Algoritmy vyhodnocení dotazů v Datalogu a Datalogu s negací (🎓🎓)[editovat | editovat zdroj]

přesunuto do Datalogu v "Formální základy databázové technologie"

DIS[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • DMJ - Booleovský a vektorový model (2012) - Slovy jsem popsal oba modely. U Booleovského jsem popsal, jak se indexuje, jak se vybírají termy a jak vypadají dotazy. Zmínil jsem se o složitosti počítání relevance. Dále jsem popsal vektorový model, jak vypadají dotazy apod. Zmínil jsem se, jak se počítá TF a ITF. Zkoušející se jen zeptal na pár otázek a byl spokojen.
  • DMJ - Indexace v DIS (2009, Kopecky) - Boolske systemy - reprezentace matici - moc velke, signatury, zbytek ze mne musel pan Kopecky dost pacit (invertovany soubor, jak ho ziskame - setridim dvojice (term, dokument) vnejsim tridenim a pak k nim sestrojim ten invertovany index). Vektorove systemy - formulovat vsechny vzorecky na TF, ITF, NTF, normalizovany vektor pro dokument. Takze tam jsem uz dalsi otazku nedostal..
  • DMJ - Vekt. a boolsky model (2009, Kopecky) - Zrejme oblubena otazka pana Kopeckeho. Uz som bol unaveny ale dal som boolsky model vcelku obstojne a pri vektorovom iba zaklad. Pan Kopecky ale skusa prijemnym sposobom a ak ste to nikedy vedeli tak to z vas dostane seriou lahkych otazok. Nepotrpi si na formalizmoch - staci mu to porozpravat po lopate a vediet princip :)
  • DMJ - Indexace dokumentů (2009, Skopal) - mám invertovaný soubor, index obsahuje jednotlivé termy, které pak mají seznam dokumentů, ve kterých se vyskytují - co ze mě doc. Skopal doloval bylo říct, že tyhle dokumenty jsou v tom seznamu setřízené, aby bylo urychlené vyhodnocování (problém byl v tom, že obrázek, kterej jsem k tomu nakreslil nebyl úplně jednoznačnej a každej jsme ho pochopili jinak, takže jsem za vůbec nechápal, co po mě chce, ale moh jsem si za to sám
  • DMJ - Vektorový model (2008, Pokorný) - chápal som to len intuitívne (vôbec som nevedel žiadne vzorce ITF a podobne), čo mu trochu vadilo, nakoniec to pochopil a netrápil ma
  • IDS - Vektorovy a boolovsky model (2009, Kopecky) - princip, tvar dotazu a odpovede, implementacia


Databáze textů: modely (boolský, vektorový) (7×🎓)[editovat | editovat zdroj]

+ Vyhledávání v textech: boolské a vektorové indexy a indexace, usporádání odpovedí, signatury a jejich implementace

Precission vs Recall
Precission vs Recall
vlivem víceznačností jsou v praxi oba koeficienty na sobě nepřímo závislé
vlivem víceznačností jsou v praxi oba koeficienty na sobě nepřímo závislé

Přesnost a úplnost (Precission vs Recall)[editovat | editovat zdroj]

  • $ P = \frac{\text{#vybraných relevantních záznamů}} {\text{#vybraných záznamů}} $
  • $ R = \frac{\text{#vybraných relevantních záznamů}} {\text{#relevantních záznamů v souboru}} $
  • 💡 závislost R a P je v praxi na hyperbole (zvětšující se P snižuje R a obráceně)

Boolský model DIS[editovat | editovat zdroj]

Každý dokument je popsán množinou termů, které obsahuje. Termy jsou uloženy v indexovém souboru a odtud potom probíhá vyhledávání.

Dotaz - vyraz obsahujici termy spojene logickymi spojkami ("AND", "OR", "NOT")

  • Postupne doslo k nekolika rozsirenim: 1. vyhledavani viceslovnych spojeni; 2. test na metadata dokumentu (autor, rok vydani...) 3. pouziti wildcardu (?, *)
  • Je mozne do dotazu zavest nove operatory (term1 sentence term2, term1 paragraph term2...).
  • Proximitní omezení - operátory pro blízkost termů (věta, odstavec,...)

Nevyhody: všechny termy stejně důležité, nejde řadit vysledky dle relevance (pouze hrube: uzávorkováním OR, převodem na DNF, ...), obtizne se omezuje mnozina vysledku

Vyhody: snadna implementace (ma to uz 50 let), pouziti signatur pro rychlou eliminaci hromad dokumentu

invertovaný soubor - termy jsou setřízené
Uspořádání odpovědi dle relevance[editovat | editovat zdroj]
  • ve vektorovém modelu je to ok,
  • u booleovského modelu je možné rozložit dotaz do DNF (disjunktně normální formy a ohodnotit jednotlivé výstupy podle toho, kolik je ne negovaných termů ve splňované podformuli)
    • př.: kocka AND pes => (kocka AND pes) OR (kocka AND NOT pes) OR (NOT kocka AND pes).

Rozšíření booleovského modelu – lze pokládat vážené dotazy – např kocka (0,9) AND pes (0,3), dokumenty mají také ohodnocený vektor termů. Různé metody, liší se podle toho, jak je vypočítáván AND a OR, např. ve Fuzzy logice je AND minimum a OR maximum vah.

Indexování (boolský)[editovat | editovat zdroj]

Organizace jako invertovaný seznam - pro každý term seznam dokumentů, termy jsou setřízené

  • Indexy lze nad kolekcí dokumentů vytvářet dvojím způsobem. Buď je množina termů pevně daná a pro každý nový dokument se aktualizují jen indexy (řízená indexace), nebo se s každým novým dokumentem přidávají i nové termy (neřízená indexace).
  • sestrojení: setridim dvojice (term, dokument) vnejsim tridenim a pak k nim sestrojim ten invertovany index

Vhodná předzpracování textu (indexu,dotazu):

  • Lemmatizace - Přiřazení správného lemmatu jednotlivým slovům ( Základní tvar slova, Slovní druh, osoba, číslo, čas, vid, ... , Informace z větného rozboru - podmět,předmět, ... )
  • Tezaurus - hierarchický strukturovaný slovník
    • Př.: dotaz('operační systém') -> 'Windows','Linux'
  • Stop-list - slovník nevýznamových slov (spojky, částice,...) ⇒ nevkládají se do indexu
  • Určení termů - ručně (každý může určit jiné termy) vs automaticky (jednoznačné, ale bez porozumnění textu)
vyhodnocení signatur - můžeme dostat false hit, nutno doplnit dalším přesným krokem porovnání [1]
Signatury, metody implementace signatur (vrstvené kódování)[editovat | editovat zdroj]

signatura dokumentu je k-bitový řetězec, který v sobě nese informaci o tom, které termy v dokumentu jsou

  • pro konjunktivní dotazy nad boolským modelem (∀dokumentu se priradi signatura, dotazu taky) - 💡využívá se malá časová a prostorová složitost
  • signatura dokumentu sᵢ vyhovuje signature dotazu s pokud sᵢs (po bitech) tj. s AND NOT sᵢ = 0
    • pokud nevyhovuje tak tam nejsou ∀hledane termy, pokud vyhovuje tak tam byt mohou

Přiřazení signatury slovu

  1. bitova mapa - signatury musi mit tolik bitu, kolik je termu.
  2. hashovaci fce - ktera priradi termu signaturu, jejiz bitovy zapis obsahuje prave jednu jednicku (pro 128bitove signatury tedy mame 128 moznych ruznych signatur jednotlivych termu). to se hodi pro vrstveni viz nize.

Přiřazení signatury  dokumentu - je mozno 2 zpusoby (nebo jejich kombinaci):

  • Vrstveni signatur - každý term má svou signaturu (vypočtenou pomocí hash funkce) dlouhou d bitů a signatura bloku = OR přes všechny signatury termů v bloku.
    • 💡 Pri vrstveni vetsiho poctu signatur to ztraci na efektivite - moc jednicek (same jednicky vyhovuji kazdemu dotazu). Proto se dokumenty rozdeluji na bloky se samostatnymi signaturami. Při vhodném dělení, např. na rozhraní kapitol nebo odstavců, není ztráta informace příliš důležitá. Slova nacházející se daleko od sebe spolu obvykle nesouvisí
    • Bloky se vytváří dvěma metodami: FSB (fixed size block) pro úseky s přibližně stejným počtem slov. FWB (fixed weight block) pro úseky s přibližně stejným počtem jedniček optimálně k/2 (stejne jednicek a nul).
  • Řetezeni signatur - signatury se spojují do řetězce - vhodné pro strukturovaná data (autor, rok vydání, nakladatelství...)

Uložení signatur:

  • Invertovany soubor - index organizovan pomoci signatur. Pro jednotlivé pozice v signaturách se udržují bitové sloupce. Pri porovnavani se signaturou dotazu se pak vezmou ty bitové sloupce, kde je v dotazu 1 a spustí se na nich bitové AND a mám bitový sloupec, kde tam, kde jsou jedničky, jsou potenciální hledané záznamy
  • strom signatur - podle prefixů
další info  
monotonni signatury - ma-li term t signaturu x, tak term tu (zretezeni termu t a termu u) ma signaturu v kazdem bitu >= signature x. Dobre pro nalezeni napr. sklonovanych slov pri zadani korene apod. Monotónní signatury lze vytvářet vrstvením signatur tzv. n-gramů (n po sobě jdoucích znaků) – např. pro trigramy by byla monotonni signatura slova „kocka“ – sig(„koc“) | sig(„ock“) | sig(„cka“)
  • transponovaný soubor signatur
    • namísto N řetězců délky d mám d řetězců délky N (pokud signatury bloků naskládám do matice, koukám se pak na ně místo jako na řádky jako na sloupce)
    • protože počet 1 v dotazu délky d je o mnoho menší než d a můžu porovnávat jen řetězce kde má dotaz jedničku, porovnávám toho daleko méně
    • složitější aktualizace
  • soubor indexovaných deskriptorů
    • stejně jako z termů vytvářím vrstvením signaturu bloku, můžu pro více bloků vytvořit společnou signaturu
  • dvouúrovňové vrstvené kódování
    • každý blok má dvě signatury - vnětší (délky ds) a vnitřní (délky dn) kde dn << ds, bloky jsou rozděleny do skupin a každá skupina má vrstvenou signaturu ds - podle ní se rozlišují skupiny a ve skupin se bloky rozlišují podle signatury dn (tedy najdu skupinu bloků a pak v ní blok)
  • rozdělený soubor signatur
    • signaturu bloku délky d rozdělím na dva kusy (prefix a zbytek) a pak seskupím "zbytky" se stejnými prefixy - pokud testuju, otestuju nejdřív prefix a pokud se neshoduje, do skupiny vůbec nemusím chodit, čímž ušetřím celkem dost času

Metody je možné různě kombinovat tak, aby výsledná struktura byla co nejefektivnější.

další zdroje  

Slajdy pokorny


Index ve VDIS

Vektorový model DIS[editovat | editovat zdroj]

reprezentace dokumentu pomocí množiny VAH <0,1> termů

  • mladší než boolský (asi o 20 let) a vznikl aby odstranil chyby boolského modelu - především díky možnosti ohodnotit termy jak v dotazu, tak v indexu
normalizace vektorů - eliminace vlivu délky vektoru na podobnost

Dotaz - také vektor, shoda se vyhodnocuje skalarnim součinem obou vektorů (dokumentu a dotazu)

  • protože dlouhé dokumenty by byly zvýhodněny (obsahují jistě více termů), provádí se normalizace vektorů, to lze provádět:
    • během indexace, což nezvětšuje odezvu, je však zapotřebí občas vše znovu "přenormalizovat"
    • během vyhledávání - zpomaluje odezvu, je v definici podobnostní funkce
  • Lze termu priradit zapornou vahu a tim uprednostnit dokumenty, ktere jej neobsahuji.
  • Ve vektorovovem modelu je snadne radit vysledky podle miry shody, pripadne orezat mnozinu vysledku nejakou minimalni hodnotou.
Indexace VDIS[editovat | editovat zdroj]
(N)TF: Rozložení (normalizované) frekvence termu, ITF/IDF je vložená POUZE pro ilustraci - v reálu má jinou osu x [2]

obvykle vychazi z (normalizovane) cetnosti vyskytu termu v dokumentu - čím víc, tim vyssi ma vahu

  • založena na frekvenci termu (TermFrequency) v dokumentu $ TF = \frac{\text{#výskytů termu}} {\text{#∀termů v dokumentu}} $
  • je potřeba vyřadit nevýznamová slova (stop list = {the, a, an, on ... })
  • normalizovat frekvenci termů (kvuli malým TF)
    • $ NTF_i = 0 $ pro $ TF_i < \epsilon $(💡 ignujeme termy s velmi nízkým výskytem)
    • $ NTF_i = \frac{1}{2} + \frac{1}{2} * \frac{TF_i}{max_j(TF_j)} $, jinak
    • NTF vzorec nám dostane hodnoty do int. {0} + ⟨1/2;1⟩
  • Inverzní frekvence termu v dokumentech (důležitost termu v kolekci dokumentů, značí se IDF nebo ITF)
    • $ IDF = -log\left(\frac{\text{#dok.obsahujících term}}{\text{#∀dok.}}\right) $
    • 💡 vyjde IDF ∈ ⟨0 ; ∞⟩ (počítáme log₁₀ čisel mensich nez 1 ⇒ výsledek by byl záporný, proto ten minus)
    • 💡 pro dotazování jsou nejvhodnější termy co se vyskytují v cca 1/2 dokumentů a nevhodná jsou slova vyskytující se ve většině dokumentů
    • 💡 jde prakticky o použití vzorecku entropie tj. "obrácená hodnota" - čím je znak častější tím menší má entropii = tím méně informace nese
    • def. Pokorný: $ IDF = log\left(\frac{\text{#∀dok.}}{\text{#dok.obsahujících term}}\right) + 1 $(def. Pokorný)
      • 💡 Definice jsou v podstatě matematicky ekvivalentní, akorát ta od Kopeckého téměř eliminuje málo důležité termy

Váha termu i v j-tém dokumentu se urči jako $ w_{ij} = NTF_{ij} * ITF_j $

  • Lze uplatnit i zpětnou vazbu, kdy uživatel označuje relevantní dotazy a DIS na to reaguje přehodnocením výpočtu.

Vyhledávání vzorku v textech (sousměrné, protisměrné)[editovat | editovat zdroj]

#vzorků \ směr sousměrné protisměrné
1 KMP BM
N AC CW
KA 2CKAS

je vhodné znát všechny alg. ale vysvětlit stačí cca první 3

  • algoritmy vyhledávání vzorku v textu se liší v závislosti na tom, zda je vzorek předzpracován či nikoliv
    • trivialni algoritmus - na kazde pozici zkus porovnat cely vzorek (bez předzpracování vzorku)
    • s předzpracováním vzorku – vhodné pro DIS
      • pracují jako určitý typ konečného automatu
      • dělí se dále dle počtu hledaných vzorků (1, N, nekonečno) a podle směru porovnávání vzorku s textem (sousměrné/protisměrné)
      • 💡 text se prochází vždy zleva doprava

Hledání 1 vzorku v textu[editovat | editovat zdroj]

KMP: posun pomocného pole při první neshodě

Knuth-Morris-Pratt algoritmus (→ sousměrný)[editovat | editovat zdroj]

  • porovnavame postupne vzor a text (od nějakého offsetu)
    • prvni neshoda ⇒ posun offsetu o největší postfix shodující se s prefixem (již zkontrolované části)
    • pomocné pole P, které říká odkud ve vzorku je možné porovnávat, aby již porovnaná část textu odpovídala vzorku
      • 💡 optimalizace trivialniho algoritmu aby se nevracel porad zpet o celou jiz zkontrolovanou cast
      • možný preprocess vzoru s odkazy na prefix
  • O(m + n) (délka textu + vzorku)
Boyer-Moore 1: Bad-Character SHIFT[0..n-1,x] je nejmenší posun abysme dostali na porovnávanou pozici potřebný znak, jinak posun cely vzorek za pozici

Boyer-Moore algoritmus (← protisměrný)[editovat | editovat zdroj]

BM 2: Good-Suffix SHIFT – posun tak, aby se shodovala již kontrolovaná část (kombinace posunu BM a KMP)
  • matchuje se od konce vzorku na začátek, vzorek se přikládá zleva doprava
  • prvni neshoda ⇒ posun vzorku doprava o SHIFT[pozice_kolize_vzorku, kolizni_znak_textu]
    1. varianta: Bad-Character SHIFT: když nesedí nějaká pozice, posunu vzorek doprava co nejméně tak, aby na sebe lícoval znak, který způsobil kolizi z textu a znak ve vzorku
      • dané 2-rozměrné SHIFT pole
      • po "kolizním" posunu vzorku začítám porovnávat znova od konce vzorku
      • 💡 funguje dobře na velké abecedy
    2. varianta: Good-Suffix SHIFT: posun tak, aby se shodovala již kontrolovaná část (kombinace posunu BM a KMP)
      • P1[kolizni_znak_textu] - poslední výskyt 'kolizni_znak_textu' ve vzorku (pro znaky co nejsou ve vzoru délka celého vzorku)
      • P2[pozice_kolize_vzorku] - ∀zkontrolovanou část (postfix odkonce vzorku) je dán skok na stejný podřetězec vyskytující se dříve ve vzorku.
        • délka nejmenšího posun co zarovná postfix (od j dál)
      • SHIFT'= max(P1[kolizni_znak_textu],P2[pozice_kolize_vzorku])' je vybrán větší skok z P-polí
  • O(m*n) ale v praxi O(m/n) (velké abecedy), na běžném textu je mnohem efektivnější než KMP
  • 💡 celý algoritmus lze dobře řešit konečným automatem (abeceda – znaky ve vzorku a speciální znak pro všechny ostatní znaky, stavy – pozice ve vzorku)

Hledání N (konečného počtu) vzorků v textu[editovat | editovat zdroj]

Aho-Corrasick

Aho-Corasick (→ sousměrný)[editovat | editovat zdroj]

  • předzpracování (konečný automat) + lineární průchod
    • stavy – všechny prefixy hledaných vzorků
    • postavíme strom dopředných hran podle prefixů
    • doplníme zpětné hrany podle postfixů vzorků
      • (pro znaky, pro které není def. dopředná funkce určuje zpětná funkce nejdelší vlastní prefix stavu, který se vyskytuje mezi stavy – když to nejde dopředu, vrátí se po zpětné funkci, když to nejde ani tady, vrátí se zase po zpětné funkci)
      • 💡 při dojití do přijímacího stavu je třeba zkontrolovat jestli nebylo s tímto slovem přijato i jiné, které by bylo postfixem tohoto (buď pomocí zpětné funkce, anebo definováním množiny přijímaných slov v každém přijímacím stavu)
  • časová složitost O(m+Σ(nᵢ))
Commentz-Walter

Commentz-Walter (← protisměrný)[editovat | editovat zdroj]

  • kombinace BM a AC, konečný automat jako u AC, ale stavy odpovídající postfixům. Při kolizi složitější posun (tři posouvací funkce, ze dvou se bere maximum a z výsledku a třetí se bere minimum)
  • časová složitost O(m*min(n_i))

Hledání vzorků v textu[editovat | editovat zdroj]

Konečný automat (→ sousměrný)[editovat | editovat zdroj]

  • umožňuje definovat přijímaná slova pomocí regulárních výrazů
  • nedeterministický KA -> převede se na deterministický KA

Dvoucestný konečný automat se skokem (2CKAS) (← protisměrný)[editovat | editovat zdroj]

  • konečný automat, přechází mezi stavy (pozice v hledaném vzorku) a zároveň posouvá (skáče) se vzorkem na prohledávaném textu

Odborné[editovat | editovat zdroj]

XML data v relacích, indexace XML dat, podobnost XML dat, XML a webové služby. (nové od 2011) (🎓🎓🎓)[editovat | editovat zdroj]

Zážitky ze zkoušek  
  • xPath (Pokorny) - 2009
  • XQuery a XSLT (Mlýnková) 2010 - Popsat co to je a k čemu to je. Stačí vědět jak to funguje, není nutný znát help zpaměti. Vědět jakou má který jazyk sílu a co umí. A pak vědět, že jsou vzásadě ekvivalentní. Akorát že XSLT umí přepínat mezi různými výstupními soubory.
  • Technologie XML 2010 - největší zádrhel mých státnic - přestože jsem znal co je a na co je a v principu jak se používá XML, SGML, DTD, XML Schema, XPath, XQuery, XSLT, DOM, SAX, docela chtěl zkoušející vědět, jak přesně (i když zase ne úplně syntakticky přesně) se něco konkrétního zapíše v XSLT nebo v XML Schema, což jsem přesně nevěděl; snažil jsem se říct princip (že v XML Schema např. určuju, co může daný element obsahovat skrze typy, co se může jak opakovat, atd., že v XSLT mám naskládány šablony a k nim příslušející XPath), leč to nestačilo, chtěl vidět konkrétní (polo-konkrétní) zápis a konkrétně jak se to vyhodnocuje krok za krokem, což jsem pořád nebyl schopen moc přesně napsat a popsat. Nakonec jsem to nějak ukoulel na 3 matným vzpomínáním na to, jak jsem někdy před šesti lety něco dělal v XSLT... Docela zrádná otázka, doporučuju na to dávat bacha. Viděl jsem nějaké zápisky, kde někdo tvrdí, že "stačí slajdy z 1. přednášky", no, myslím, že určitě nestačí.
    • v tehle otazce je potreba znat XSLT, XPath a to vcetne prikladu


Tato část je neúplná a potřebuje rozšířit. umravnit a zkonfrontovat

Indexace XML[editovat | editovat zdroj]

Metody indexace

Indexace úplného textu
nevýhoda: nelze dotazovat podle struktury
Indexace relací klasicky (Lore) ???
http://infolab.stanford.edu/lore/
Číselná schémata
indexování založené na pozicích
použití absolutních resp. relativních adres pro reprezentaci pozic slov a značek v XML dokumentu
Dietzovo číslování
...
...


Absolutní souřadnice regionu (ARC)
D( S, E )
D : číslo dokumentu
S : počátečni pozice, E : koncová pozice v dokumentu
výhody: pro dotazování
nevýhody: aktualizace v listu znamená, že všechny následníky je třeba změnit také
XML indexing-ARC.PNG


Relativní souřadnice regionu (RRC)
RRC uzlu n v XML stromu: [ c1, c2 ]
c1 : počet byte z počáteční pozice rodičovského uzlu k počáteční pozici n
c2 : počet byte z počáteční pozice rodičovského uzlu ke koncové pozici uzlu n
výhoda: aktualizace je menší oproti ARC
XML indexing-RRC2.PNG


Dietzovo číslování
Preorder průchod - potomci každého uzlu následují při preorder průchodu stromem za svým rodičovským uzlem
Postorder průchod - každý uzel posloupnosti je uveden až za svými potomky
Konstrukce číselného schématu
každému uzlu v∈N přiřadíme dvojici (x,y) značící preorder resp. postorder pořadí
uzel v∈N s ohodnocením L(v) = (x,y) je potomkem uzlu L(u) = (x',y') právě když x' < x & y' > y
XML indexing-Dietz.PNG

Podobnost XML dat[editovat | editovat zdroj]

Typ dat
Podobnost dokumentů
Podobnost schémat
Podobnost dokumentů a schémat

Podobnost XML dokumentů[editovat | editovat zdroj]

Idea
Vstup: Dokumenty D1 a D2
Výstup: sim(D1, D2) ∈ [0,1]
Přístupy:
  • Zjistíme jak složité je transformovat dokument D1 na D2
    • Editační vzdálenost stromů T1 na T2
  • Definujeme reprezentaci D1 a D2, která umožní efektivní vyhodnocení podobnosti
    • Př. reprezentace množinou cest, reprezentace signálem, …


Editační vzdálenost

(pro stromy) minimální počet operací pro transformaci stromu T1 na strom T2

Editační operace na XML stromech
Insert - vloží uzel n na pozici danou rodičovským uzlem p a pořadím určujícím pozici v rámci podelementů p
Delete - smaže listový uzel n
Relabel - přeznačí uzel n
InsertTree - vloží celý podstrom T na pozici danou rodičovským uzlem p a pořadím určujícím pozici v rámci podelementů p
DeleteTree - celý podstrom T s kořenem n je smazán

Minimální editační vzdálenost se jaksi vyhodnocuje pomoci dynamickeho programovani


Tree Alignment

Obdoba editační vzdálenosti

Myšlenka: Pro stromy T1 a T2 vybudujeme tzv. alignment

  • Do obou stromů vložíme uzly tak, aby výsledné stromy T1’ a T2’ měly stejnou strukturu (bez ohledu na označení), tj. pokud bychom je přiložili na sebe, překrývaly by se
Postup
Vybudujeme alignment
Každé dvojici překrývajících se uzlů přiřadíme skóre
Vzdálenost stromů = součet skóre


Obe dve transformace dokumentu jsou NP-tezke (tipl bych si, ze jsou primo slabe NP-tezke)

Hledání minimální editační vzdálenosti XML stromů je obecně NP-těžký problém
Tree Alignment: pokud je stupeň stromu omezený, lze minimální vzdálenost nalézt v polynomiálním čase, jinak je to NP-těžký problém.


Reprezentace množinami cest

Myšlenka: XML strom = množina cest

Které cesty budeme brát?

Všechny různé cesty z kořene do listu
Všechny různé cesty z kořene do listu a všechny jejich pod-cesty
Všechny různé cesty z kořene do listu a všechny jejich pod-cesty + informace o četnosti

Problém podobnosti stromů se redukuje na určení velikosti průniku množin cest

Poznámka: Přístup ignoruje uspořádání


Signál XML dokumentu

Myšlenka: XML dokument reprezentujeme jako signál (impuls = počáteční/koncový tag)

Problém podobnosti XML dokumentů jsme převedli na problém podobnosti signálů

Postup
Signály jsou periodicky zopakovány (asi aby byly stejne dlouhe)
Je na ně aplikována diskrétní Fourierova transformace
Výsledek je lineárně interpolován

Podobnost XML dokumentů a schémat[editovat | editovat zdroj]

Problém: Chceme porovnat podobnost XML dokumentu D (stromu) a XML schématu S (množina regulárních výrazů)

Možná myšlenka: z dokumentů odvodíme schéma a porovnáme schémata (prozatím se nevyužívá a potřebovali bychom hodně dokumentů)

Existující přístupy:

  • Metoda měřící počet elementů, které se vyskytují v D, ale ne v S a naopak
  • Metoda, měřící nejkratší vzdálenost mezi D a „všemi“ dokumenty validními vůči S

Podobnost XML schémat[editovat | editovat zdroj]

Problém: podobnost regulární výrazů, resp. gramatik

Typické použití je integrace XML schémat - několik systémů poskytuje stejná (podobná) data v různých formátech → chceme sjednotit do společného schématu (XML Schema, relační, objektové, …)

Obecná myšlenka
Definujeme množinu pomocných podobnostních funkcí (matchers), kde každá vyhodnocuje podobnost určité charakteristiky (např. podobnost listů, podobnost jmen kořenových elementů, podobnost kontextu, …)
Výsledky podobnostních funkcí jsou (váženě) agregovány do výsledné podobnosti

Poznámka: Velké množství metod využívá strojové učení (např. pro nastavení vah, pro vyhodnocování, …)

Algoritmy:

Cupid - dvě fáze vyhodnocování (lingvistická a strukturální)
COMA - kombinace velké množiny matcherů s uživatelskou interakcí

Matching velkých schémat

Problém: U velkých schémat nechceme matchovat každý uzel s každým
Myšlenka: Dekomponujeme problém do menších a jejich výsledky sloučíme

XML a webové služby[editovat | editovat zdroj]

Datový model RDF, dotazovací jazyk SPARQL[editovat | editovat zdroj]

RDF[editovat | editovat zdroj]

RDF (Resource Description Framework) Dátový model tvorený orientovaným grafom ( bez násobných hrán)- prostředí na popis (webovských) zdrojů. Uložený v XML

Rozlišujeme Zdroj( moze mat vlasnosti), Prázdny uzol a literál ( Dátová hodnota ktorá nie je zdroj , môže mat dátový typ )


RDF graf je možné reprezentovať : Množinou, Graficky, Slovami v abecede, Gramatikom , najčastejšie sa používa zoznam trojíc (subject,predicate,object)

Forma zápisu je N3 notácia, zložitý formalizmus alebo používanejšia Turtle:

  • Turtle : URI ( jedinečná identifikácia ) v hranatých zátvorkách , forma prefixovej skratky
  • Literály v úvodzovkách
  • Trojice uzatvorené bodkou
  • Mezery, eol, … se ignorují
  • Opakujúce hodnoty môžeme vynechať, oddeľovať nie . ale ;
  • Viac trojíc s rovnakým subjekt a predicate oddeľovať objekty ,
  • Môžeme redukovať uzly na prázdne uzly , takýto uzol má lokálne meno ale nemá url
Rdf graf
ex:index.html dc:creator ex:staffid/85740
ex:staffid/85740 ex:maJmeno “John Smith”

Prázdne uzly:

exstaff:85740 	exterms:address 	??? .  
??? 		exterms:street 		"1501 Grant Avenue" .  
??? 		exterms:city 		"Bedford" .  

RDF informuje o typoch , tz tvrdenia o tvrdeni

exproducts:triple123      rdf:type           rdf:Statement .  
exproducts:triple123      rdf:subject        ex:index.html . 

Vyuzitie pri vyhladavacoch, kniznice, eshopy

Zdroje

http://www.ksi.mff.cuni.cz/~pokorny/dj/prezentace/1_34.ppt http://www.w3schools.com/webservices/ws_rdf_example.asp

RDF Schema[editovat | editovat zdroj]

Rožšírenie RDF o triedy pre zdroje, zavedenie dedičnosti( len fw, nedefinuje žiadne triedy)

SPARQL[editovat | editovat zdroj]

Dotazovanie nad RDF datami. Hladaju sa zdroje s istymi vlastnostami . Syntax velmi podobna ako v SQL

SELECT ?(čo)
WHERE { predikat, trojica splnajuca vlastno ?(čo) má vlastnosť. }
Construct: vratia RDF graf tvoreny substituciou za premene
ASK: Vracia true/false ak bol vzor najdeny alebo nie
DESCRIBE : Vracia RDF graf, ktory popisuje najdene zdroje
OPTIONAL : Prida dodatocnu informaciu ale nefailne ked nenajde vhodne.
Data

_:a foaf:name "Alice" .
_:a foaf:knows _:b .
_:a foaf:knows _:c .
_:b foaf:name "Bob" .
_:c foaf:name "Clare" .
_:c foaf:nick "CT" .


Dotazy

 
PREFIX foaf: <http://xmlns.com/foaf/0.1/> SELECT ?nameX ?nameY ?nickY WHERE { ?x foaf:knows ?y ; ?x foaf:name ?nameX . ?y foaf:name ?nameY . OPTIONAL { ?y foaf:nick ?nickY } }

Vysledok

 ?nameX  ?nameY  ?nickY
Alice Bob Prazdny vysledok, nieje to null
Alice Clare CT

Pekne jednoduche dotazy [1]

Podobnostní dotazy v multimediálních databázích, metrické indexacní metody. (nové od 2011) (🎓)[editovat | editovat zdroj]

Podobnostní dotazy v multimediálních databázích[editovat | editovat zdroj]

Funkce podobnosti $ δ: U \times U \rightarrow R $ - libovolná fce vracející pro 2 dekriptory z univerza podobnostní skóre

základní dotazy
  • range - vezme se objekt $ Q $ a poloměr dotazu $ r $
  • k-Nearest Neigbour - vybere k nejpodobnějších objektů k dotazu (💡 lze použít i na regresi a klastrování)
Vstup
  • trénovací množina klasifikovaných vzoru $ M $
  • vzor $ v $, který chceme klasifikovat
  • a celé kladné číslo $ k $
Algoritmus
  • v množine $ M $ najdeme množinu $ N $ obsahujíci $ k $ vzoru, ktere jsou k vzoru $ v $ nejbližší ze všech vzorů z $ M $
  • vzoru $ v $ dáme klasifikaci, která je nejčastejší v množine $ N $
  • Reverse kNN - objekt Q a číslo k -> vrátí všechny objekty pro které je Q v kNN
advanced queries
  • Distinct kNN (DkNN) - vrať k nejbližších a disjunktních sousedů
  • skyline - vrať prvky z množiny vyhovující nejlépe dvěma/více atributům
  • aggregation (top-k operator)
SQL
  • nativní SQL - výhody: nemusí se měnit ex.db, nemá restrikce na range dotazy ; nevýhody: pomalé (nejsou indexy, ani optimalizace dotazů), musí se doprogramovat funkcionalita
  • SQL extensions (např. SIREN - rozšiřuje SQL o podobnostní dotazy) - nové db objekty (dat.typy, vzdálenostní fce, indexy), nativní predikáty pro WHERE, operátory - similarity JOIN
Podobnosti (vzdálenosti) v mm.db  
vektorové
  • independent dimensions
  • Lp (Minkowského) vzdálenosti - je třída vekt. vzdáleností uvažujících nezávislé dimenze
MM DB 6250395489241108110.png
  • L1 manhattanska
  • L2 eukleidovská
rychlé $ O(n) $, metrická
  • histogramy
  • vážená eukleidovská vzd. L2
  • kvadratická forma (Quadratic Form Distance)
  • dimenze prostoru se předpokládají korelované (💡 např histogram na homogenní doméně)
  • matice pro histogramy obsahuje korelace mezi reprezentanty barev vyskytujícími se v obrázcích
MM DB 954379289549314657.png
  • složitost výpočtu $ O(n^2) $, metrická
  • Earth Mover Distance
  • řeší se nejmenší přesun masy mezi histogramy (💡 nestačí pouhá korelace dimensí (sloupců))
  • EMD(x,y) = nejmenší množství práce pro přesun masy $ x $ na masu $ y $
  • složitost $ O(2^n) $, metrická

sekvence

  • časové řady
  • DTW Dynamic Time Warping - nemetrická
  • používá se pro měření podobnosti na časových řadách
MM DB 6351594138144169526.png
  • 💡 je výhodná bo představuje robustní zarovnání díky lokálnímu natahování/zkracování (time warp)
  • složitost $ O((m+n)w) $, nemetrická
  • řetězce
  • Editační (edit distance)
  • počítá se nejmenší počet operací nutných ke konverzi jednoho řetezce na druhý
  • operace: insert, delete, replace
  • náročná $ O(mn) $, metrická
  • Hammingova - Editační pouze s replace
  • levná $ O(n) $, metrická
  • LCSS Longest Common SubSequence - hledá se nejdelší společný podřetězec (💡 NE jenom substring)
  • LCSS(ABCD, ACBD) = 3 (either ABD or ACD)
  • náročná $ O(mn) $, nemetrická
  • 💡 je výhodná protože: umožňuje lokální zarovnání (tj. zarovnání pouze podposloupností)

množinové

  • obecné
  • Jaccardova - normovaná velikost průniku
MM DB 2027159719468114462.png
  • Hausdorff distance - podobnost elementů množin využívá ground distance
  • ground distance - vzdálenost dvou vlastností (např: vzdálenost obrysů)
  • HD je pak nejdelší vzdálenost od nejbližšího souseda
MM DB 573347960994207990.png
  • složitost $ O(mn)*O(ground~ dist.) $ (metrická)

Metrické indexování[editovat | editovat zdroj]

metrický model podobnostního vyhledávání[editovat | editovat zdroj]

místo metrické vzdálenosti se používá levnější spodní odhad (lower-bound)

pivoti (pro odhad vzdálenosti)
  • globální - statické indexy (platné po celý život indexu)
  • lokální - dynamické objekty zvolené během indexování (💡 centroidy klusterů)
vnitřní dimense ρ(S,d) = μ^2/2σ^2 (intrinsic dimensionality)
statistický ukazatel odvozený z distribuce vzdáleností v databázi
slouží jako indikátor indexovatelnosti db pod danou metrikou
vysoká vnitřní dimense - data netvoří shluky a tedy jsou špatně strukturovaná, 💡 prokletí dimese
nízká - dobře strukturovaná a tvoří těsné shluky

metrické přístupové metody (Metric Access Methods)[editovat | editovat zdroj]

MAM
MAM
(L)AESA range query: sekvenční průchod vzdálenostní maticí + kontrola výsledku v původním prostoru
(L)AESA range query: sekvenční průchod vzdálenostní maticí + kontrola výsledku v původním prostoru
algoritmy a/nebo datové struktury umožňující rychlé podobnostní hledání v metrickém modelu
💡! nepatří k nim R-strom
Pivotové tabulky[editovat | editovat zdroj]
třída indexů používající mapování dat na prostor pivotů
vzdálenostní matice - vzdálenosti od každého z pivotů
(L)AESA - (Linear) Approximating and Eliminating Search Algorithm
AESA - každý prvek je pivot, rychlé hledání sousedů, pomalá kontrukce tabulky
k prvků jsou pivoti, matice má rozměr O(|S|)
NN query - cyklus vylepšuje kandidáty
+spatial access methods
Stromové indexy[editovat | editovat zdroj]
gh-strom - vyber 2 pivoty (např nejvzdálenější prvky) a rozděl db na dvě partišny nadrovinou podle vzdáleností, rekurzivně pokračuj
  • gh-stromy (Generalized Hyperplane Tree) nadrovinový binární strom (hyperplane = nadrovina)
  • konstrukce - vyber 2 pivoty (např nejvzdálenější prvky) a rozděl db na dvě partišny nadrovinou podle vzdáleností, rekurzivně pokračuj
  • range query - otestuj na překrytí s query obě partišny, rekurzivně pokračuj níž a testuj stejně
příklad pro levou partišnu (podstrom)
  • pokud nejbližší možný objekt v query (vzhledem k O1) je dále než nejvzdálenější možný objekt v query (vzhledem k O6), pak neprojdeme levý podstrom (pokud spodní odhad z O1 je větší než horní odhad z O6)
MM DB 5136080282252636911.png
  • $ δ(Q, O1) - r > δ(Q, O6) + r $
  • 💡 tedy můžeme projít i oba podstromy
  • GNAT (Geometric Near-neighbor Access Tree) rozšíření na n-pivotů + tabulka vzdáleností
  • range query - příklad pro podstrom O5:
  • pokud nejbližší možný objekt v query (vzhledem k O5) je dále než nejvzdálenější možný objekt v query (vzhledem k alespoň jedné partišně O1, O3, O4), pak neprojdeme podstrom
MM DB 4281588065894422188.png
  • (P)M-tree - inspirován R-stromem (vyvážený, regiony jsou ale kruhové, data jsou v kořenech (stránky na disku), vnitřní uzly jsou routing entries se středy kruhových regionů a poloměrem)
PM-tree - obohacuje M-tree o p globálních pivotů
  • využívá hierarchické hnízdění metrických regionů a je vyvážený
MM DB 2115865289095682470.png
  • range query - traverzování překrývajícími se regiony (podstromy)
  • PM-tree - obohacuje M-tree o p globálních pivotů
  • každý kruhový region je redukován p kružnicemi se středy v pivotech
  • čímž zmenšuje regiony a tedy zlepšuje filtrování
Hashed indexes[editovat | editovat zdroj]
  • D-Index
D-Index - hashované regiony jsou organizované do přihrádek na disku
  • hashovaný index, základem jsou prstence
  • parametr 2ró je tloušťka prstence
  • parametr dm je median vzdálenosti od pivotu k jeho objektům
  • hashovaci fce bps vrací
  • 2 pokud je součástí prstence
  • 1 vně prstence (💡 tzn. není v prstenci)
  • 0 uvnitř prstence (💡 tzn. není v prstenci)
  • ruzne $ bps $ fukce se kombinují do řetězců hash kódu
  • pokud hashovací kód obsahuje 2 patří do exkluzní množiny
  • rekurzivně se zahashují znovu dokud se exkluzní množiny dostatečně nezmenší
  • struktura
  • hashované regiony jsou organizované do přihrádek na disku - parametry bps funkce se těžce určují
  • přehashování exkluzní množiny definuje další level D-indexu
další zdroje  


Státnice -- Softwarové systémy
Složitost a vyčíslitelnost -- Tvorba algoritmů (10🎓), NP-úplnost (15🎓), Aproximační algoritmy (6🎓), Vyčíslitelné funkce a rekurzivní množiny (8🎓), Nerozhodnutelné problémy (9🎓), Věty o rekurzi (6🎓)
Datové struktury -- Stromy (32🎓), Hašování (13🎓), Třídění (10🎓)
Databázové systémy -- Formální základy: Relace (12🎓), Datalog (9🎓), Ostatní (0🎓)   Modely a jazyky: SQL (7🎓), DIS (7🎓), Odborné (3)   Implementace: Transakce (5🎓), Indexace (10🎓), Komprese (3)
Softwarové inženýrství -- Programovací jazyky a překladače, Objektově orientované a komponentové systémy, Analýza a návrh softwarových systémů
Systémové architektury -- Operační systémy, Distribuované systémy, Architektura počítačů a sítí
Počítačová grafika -- Geometrické modelování a výpočetní geometrie, Analýza a zpracování obrazu, počítačové vidění a robotika, 2D počítačová grafika, komprese obrazu a videa, Realistická syntéza obrazu, virtuální realita

🎓 - znamená kolikrát byla otázka u státnic

  1. [2]
  2. [3]http://www.ms.mff.cuni.cz/~kopecky/vyuka/dis/