11 Karel Poledna

Vyhledávání podle klíčových slov v relačních databázích Dotazovací jazyky I ZS 2010/11 Karel Poledna

Vyhledávání podle klíčových slov 

Uživatel zadá jedno nebo více slov a jsou mu zobrazeny výsledky. Uživatel nemusí používat žádný dotazovací jazyk.  Uživatel nemusí znát strukturu dat. Nejpopulárnější metoda vyhledávání 

(viz vyhledávání na webu)

2

Vyhledávání podle klíčových slov v relační databázi 

Vstup:  



Relační databáze neprázdná množina slov

Výstup:  

„kvalifikované sítě spojení entic“ (qualified joining networks of tuples)

3

Co je relační databáze? 

Pro naše účely:  

relace, tabulky ~ množiny entic, řádek relace, tabulky spojeny podle primárních a cizích klíčů 

graf schématu databáze

4

Graf schématu databáze 1/2 

Orientovaný graf schématu databáze (schema graph)  



Vrchol pro každou relaci / tabulku. Hrana z tabulky s primárním klíčem do tabulky s cizím klíčem.

Neorientovaný graf schématu databáze 

zřejmé

5

Graf schématu databáze 2/2 

Pro zjednodušení se předpokládá, že atributy tvořící primární a cizí klíče se jmenují stejně a graf neobsahuje smyčky a vícenásobné hrany.

6

Co je výstupem?  



entice (tuple) ~ prvek relace, řádek tabulky (ze vstupní relační databáze) síť spojení entic (joining network of tuples) ~ množina entic spojených přes primární a cizí klíče kvalifikované (qualified) ~ entice dohromady obsahují všechna klíčová slova dotazu 7

Příklad: schéma databáze ZBOŽÍ(kód_zboží, jméno_zboží, cena_zboží) DODAVATEL(kód_dodavatele, jméno_dodavatele, kód_státu) DODAVATEL_ZBOŽÍ(kód_zboží, kód_dodavatele, množství_k_dispozici) ZÁKAZNÍK(kód_zákazníka, jméno_zákazníka, kód_státu) OBJEDNÁVKA(kód_objednávky, kód_zákazníka, celková_cena, jméno_prodavače) POLOŽKA(kód_objednávky, číslo_položky, kód_zboží, kód_dodavatele, množství) STÁT(kód_státu, jméno_státu)

Příklad: graf schématu

OBJEDNÁVKA

ZÁKAZNÍK

STÁT

POLOŽKA

DODAVATEL_ZBOŽÍ

DODAVATEL

ZBOŽÍ

Příklad: data 1/2 ZÁKAZNÍK kód_zákazníka jméno_zákazníka kód_státu

z1 10001 z2 10002 z3 10003

Jiří Novák Marie Černá Petr Svoboda

101 101 101

STÁT kód_státu jméno_státu

s1 101

Česká Republika 10

Příklad: data 2/2 OBJEDNÁVKA kód_ kód_ celková_ jméno_ objednávky zákazníka cena prodavače

o1 o2 o3 o4

100001 100002 100003 100004

10001 10001 10002 10003

5.000,00 3.000,00 7.000,00 8.000,00

Eva Procházková Martin Dvořák Martin Dvořák Hana Kučerová

11

Příklad: systém DISCOVER 1/7 

Klíčová slova  

keywords zadána uživatelem 

Procházková, Dvořák

12


Základní množiny entic  

basic tuple sets získány z celkového fulltextového indexu 

Master index

OBJEDNÁVKA

Procházková

={o1 }, OBJEDNÁVKA

Dvořák

={o2 ,o3 } 13


Množiny entic  

tuple sets profiltrovány „Postprocesorem množin entic“ 

Tuple Set Post-Processor

OBJEDNÁVKA

Procházková

={o1 }, OBJEDNÁVKA

Dvořák

={o2 ,o3}

14


Kandidátní sítě  

candidate networks „Generátor kandidátních sítí“ 

Candidate network generator

OBJEDNÁVKA

Procházková

{}

⇔ZÁKAZNÍK ⇔OBJEDNÁVKA

Procházková

{}

Dvořák

{}

OBJEDNÁVKA ⇔ZÁKAZNÍK ⇔STÁT ⇔ {} Dvořák ZÁKAZNÍK ⇔OBJEDNÁVKA 15


Plán vyhodnocení  

execution plan „Generátor plánů“ 

Plan Generator

T 1 OBJEDNÁVKA

Procházková

C 1 T 1 ⇔OBJEDNÁVKA {}

⇔ZÁKAZNÍK

{}

Dvořák

{}

C 2 T 1 ⇔STÁT ⇔ZÁKAZNÍK ⇔OBJEDNÁVKA

Dvořák 16


Provedení plánu 

plan execution

C REATE TABLE T 1 AS SELECT * FROM Procházková OBJEDNÁVKA , ZÁKAZNÍK W HERE ... SELECT * FROM T 1 , OBJEDNÁVKA

Dvořák

W HERE ...

SELECT * FROM T 1 , STÁT , ZÁKAZNÍK , Dvořák OBJEDNÁVKA W HERE ... 17


Výsledky 

Posloupnosti spojení entic

o 1 ⇔ z 1 ⇔o 2





Prodavači Procházková a Dvořák oba obsluhovali zákazníka Jiřího Nováka.

o 1 ⇔ z 1 ⇔n 1 ⇔ z 2 ⇔ o 3

Prodavačka Procházková obsluhovala zákazníka Jiřího Nováka z Česka a prodavač Dvořák obsluhoval zákaznici Marii Černou, která je také z Česka. 18

Příklad: výsledek 

Minimální posloupnost spojení (minimal joining sequence)  



značení: a ⇔b 



obsahující slova Procházková a Dvořák minimální, protože žádnou entici nelze vynechat a přitom stále mít všechna slova entice jsou spojeny přes primární a cizí klíč

Výsledky setříděny podle počtu spojení. 19

Síť spojení entic  



Joining network of tuples Strom entic, ve kterém pro každou dvojici sousedních entic existuje hrana v grafu schématu mezi odpovídajícími relacemi. Velikost sítě spojení je počet spojení v síti, tj. o jedna méně než počet vrcholů stromu. 20

Posloupnost spojení entic  

Joining sequence of tuples Speciální případ, když každý vnitřní vrchol má právě dva syny.

21

Dotaz na klíčová slova  

keyword query Množina klíčových slov

22

Výsledek dotazu na klíčová slova 

množina všech sítí spojení entic, které jsou: 



 

úplné: každé klíčové slovo dotazu je obsaženo alespoň v jedné entici sítě minimální: nelze vynechat žádnou entici a stále mít úplnou síť spojení entic

Minimální úplné sítě spojení entic MTJNT, Minimal Total Joining Network of Tuples 23

Výsledek dotazu na klíčová slova - doplnění  

Součástí dotazu může být omezení maximální velikosti MTJNT. Výsledkem dotazu na dvě klíčová slova jsou vždy posloupnosti spojení entic.

24

Systém DISCOVER 1 

Hlavní index 



pro množinu klíčových slov vrátí množinu základních množin entic k Základní množina entic R 

pro relaci R a klíčové slovo k obsahuje všechny entice R obsahující slovo k.

25


Postprocesor množin entic 



Ze základních množin entic vytvoří množiny entic pro každou relaci R a podmnožinu klíčových slov tak, že entice v nmožině obsahují všechna klíčová slova v podmnožině a neobsahují klíčová slova, která nejsou v podmnožině. Dále postupují jen neprázdné množiny entic a celé relace, tzv. volné množiny. 26


Síť spojení množin entic  



Strom množin entic Hrany podle grafu schématu

„Síť spojení entic patří do sítě spojení množin entic.“

27

Kandidátní síť 

 

Síť spojení množin entic taková, že existuje instance databáze, ve které existuje MTJNT, která do ní patří a žádná entice z volné množiny neobsahuje klíčové slovo dotazu. JNT není minimální, pokud má jako list entici neobsahující žádné klíčové slovo JNT není minimální, pokud obsahuje dvakrát stejnou entici. 28

Kandidátní síť - prořezávání 

Prořezávací podmínka 

Kandidátní síť neobsahuje podstrom 



R–S–R

pokud orientovaný graf schématu obsahuje hranu R -> S.

29


Plán vyhodnocení 



 

Seznam spojení množin entic a předchozích mezivýsledků. Předpoklad: jiné než volné množiny entic jsou malé, spojení malé množiny s jinou je také malé. Vždy se spojují právě dvě množiny entic. NP-úplný problém => Hladový algoritmus 30

Řazení výsledků podle Information Retrieval   

Dokument i dotaz jako vektor termů (slov) v prostoru termů. Skóre pro každý výsledek (dokument) Podobnost (similarity) vektoru výsledku a vektoru dotazu.

SimQ , D = ∑k ∈Q , D weight k ,Q∗weight k ,D 31

Řazení výsledků 2/4 ntf ∗idf ndl ntf = 1ln 1ln tf  N idf = ln df 1 s∗dl ndl = 1 – s  avgdl weight k , D  =

32

Řazení výsledků 3/4  



tf ... frekvence termu (term frequency), počet výskytů termu v dokumentu df ... frekvence dokumentů (document frequency), počet dokumentů, ve kterých se term vyskytuje N … počet dokumentů

33

Řazení výsledků 4/4   

dl ... délka dokumentu (počet termů nebo bajtů, …) s ... konstanta, většinou s = 0,2 avgdl ... průměrná délka dokumentu

34

Aplikace na dotazy do relační databáze  

T … superdokument ~ strom entic D1, D2, … dokumenty ~ všechny textové hodnoty sloupců v T

Sim Q ,T  = ∑k ∈Q ,T weight k , Q ∗weight k , T 

35

Váha stromu entic



size(T) … počet entic v T weight k , D i  weight k , T  = ∑ D ∈ T size T  i

36

Vylepšení 1/3  

používat frekvence globální přes všechny textové hodnoty v databázi normalizace

weight k ,T  = Combweight k , D 1 ,,weight k , D m 

 

Combx 1 ,, x m = max x i ∗ 1ln 1ln

∑ xi max xi

 37

Vylepšení 2/3 

avgsize ... průměrná velikost stromu entic výledku g

ntf ∗idf weight k , D i  = ndl∗Nsize T 

size T  Nsize T  = 1 – ss∗ avgsize 38

Vylepšení 3/3  

dfg ... globální frekvence výskytu slova v databázi Ng … celkový počet textových hodnot v celé databázi





dl ndl = 1 – s s∗ ∗1ln av gdl  av gdl g

N idf = ln g df 1 g

39

Termíny ze schématu 1/4 

Klíčová slova z dotazu mohou být dvojího typu: 

hodnotová  



např. Procházková, Dvořák vyskytují se v hodnotách atributů

pocházet ze schématu  

např. prodavač, zákazník jména sloupců nebo tabulek nebo jejich synonyma 40

Termíny ze schématu 2/4 

Předpoklad: každé slovo dotazu má právě jeden z těchto významů.

41

Termíny ze schématu 3/4  

Slovo vyskytující se jen v názvu tabulky nebo sloupce má zatím nulovou váhu. Frekvence dokumentů podle schématu 

pro název sloupce nebo tabulky s jedním textovým sloupcem 



dosadit největší frekvenci dokumentů z daného sloupce

pro název tabulky s více textovými sloupci 

dosadit největší frekvenci dokumentů ze sjednocení všech sloupců tabulky

42

Termíny ze schématu 4/4  

Frekvence termu ve schématu je v odpovídajících sloupcích 1 Pro každé slovo se spočítá jeho váha, je-li hodnotový a jeho váha, je-li ze schématu, použije se maximum.

43

Zdroje 

DISCOVER: Keyword Search in Relational Databases  



Vagelis Hristidis, Yannis Papakonstantinou Proceedings of the 28th VLDB Conference, Hong Kong, China, 2002

Effective Keyword Search in Relational Databases  

Fang Liu, Clement Yu, Weiyi Meng, Abdur Chowdhury SIGMOD 2006, June 27-29, 2006, Chicago, Illinois, USA 44

11 Karel Poledna

Recommend Documents