Fuzzy SQL

Jaroslav Tykal, Jiří Dokulil

Proč Fuzzy Přesné vs. „nepřesné“ hodnoty

Kdo má nejvyšší plat Kdo má vysoký plat

Výhody přesnosti Jednoznačná odpověď na zadanou otázku

Nevýhody přesnosti Odpověď právě na to, na co jsme se ptali

Příklad Máme

Databáze studentů a jejich studijní průměry Hledáme

Dobré studenty (studenti s průměrem >= 3.5)

Dotaz SELECT * FROM STUDENTS WHERE GPA >= 3.5;

Příklad – modifikace Máme

Databáze studentů a jejich studijní průměry Záznamy o absenci studentů

Hledáme Dobré studenty („dobrý student“ je student, který

má GPA >= 3.5 a počet zameškaných dnů < 10)

Dotaz SELECT * FROM STUDENTS WHERE GPA >= 3.5 AND

ABSENCES < 10;

Výsledek dotazu

Příklad Dále požadujeme

Setřídit tyto studenty od nejlepšího k nejhoršímu. Zvolíme třízení podle průměru sestupně a podle

absencí vzestupně. Dotaz

SELECT * FROM STUDENTSWHERE (GPA >= 3.5) AND (ABSENCES < 10) ORDER BY GPA DESC, ABSENCES ASC;

Výsledek dotazu

Nevýhody řešení Ne zcela vyhovující řazení studentů.

Student Barry Allen má o málo horší průměr než Billy Kidd. Billy Kidd má však o mnoho horší docházku než Barry Allen.

Který z nich je však lepší student?

Ne zcela vyhovující seznam studentů Seznam neobsahuje studenty, kteří mají studijní

průměr 3.49, ale žádnou absenci. Seznam neobsahuje studenta, který má studijní

průměr 4.00 a má 10 absencí.

Cíl Definovat způsob

který využije atributy GPA a ABSENCES s jejich pomocí vytvořit hodnotu, která bude

vyjadřovat „dobrého studenta“ hodnota „dobrý student“ lépe vyjadřuje naší

představu o dobrém studentovi

Fuzzy množiny Základní pojmy

Množina – výraz (např. „dobrý prospěch“), který určuje nějakou vlastnost.

Stupeň náležení – do množiny může daný prvek patřit do dané množiny. Nabývá hodnot <0, 1>.

Funkce příslušnosti – pro daný prvek vrací hodnotu stupeň náležení.

Příklad Studenti s průměrem 4.0 budou patřit do skupiny

výborný prospěch se stupněm 1. Studenti s průměrem 3.01 budou patřit do skupiny

výborný prospěch se stupněm blízkým k nule.

Upravený dotaz Definujeme množiny

Dobrý prospěch Minimální hodnota pro náležení do množiny: 3.0 Maximální hodnota pro náležení do množiny: 4.0 Tvar křivky: klasické S

Dobrá absence Minimální hodnota: 0 Maximální hodnota: 13 Alpha Cut: 0.1 Tvar křivky: směr klesajícího S

Funkce příslušnosti Pro „dobrý prospěch“

Funkce příslušnosti Pro „dobrou absenci“

Dotaz pomocí Fuzzy množin Dotaz

SELECT * FROM STUDENTS WHERE (GPA is „Dobrý prospěch“) and (ABSENCES is „Dobrá absence“)

Výsledek studenti, kteří patří do množiny „dobrý student“ ve výsledku je sloupec, jehož hodnoty označují

stupeň náležení do „dobrý student“

Dotaz pomocí Fuzzy množin

Poznámky Řazení podle náležení do skupiny „dobrý

student“ více odpovídá naší představě o výsledku dotazu.

Studenti, kteří jsou si bližší ve smyslu být „dobrý student“, jsou vedle sebe.

Ve výsledku jsou i studenti, kteří mají horší průměr i velkou absenci. Tito studenti však mají nízkou hodnotu náležení do skupiny a proto nemá smysl je považovat za „dobré studenty“.

Aplikace v e-business Problém prohledávání elektronických katalogů

zboží Tradiční relační databáze podporují vyhledávání

na základě přesných podmínek Jsou vráceny právě výrobky přesně odpovídající zadané

podmínce Zákazník se většinou zeptá „špatně“

Příliš nepřesná podmínka vracející obrovský počet záznamů Příliš detailní specifikace (ovespecification), která nic

nevrátí Nejasná představa zákazníka

Neví, jak přesně popsat, co chce Má o tom jen nejasnou představu

„Mělo by to stát něco pod 1500“ Má to být celkem malé

„Lepší“ přístupy Nearest-Neighbour

Metriky pro jednotlivé atributy, sloučeny váženým způsobem do výsledné podobnosti

k-NN algoritmus vrátí k nejpodobnějších Fuzzy

Místo vzdálenosti používá přijatelnost (acceptance) Přijatelnost má obvykle tvar nějaké fuzzy distribuce Kombinace lokálních přijatelností probíhá pomocí

fuzzy operátorů, tedy má bohatší možnosti než NN. Výsledná hodnota přijatelnosti určí, jestli má být

výrobek zobrazen zákazníkovi Umožňuje přiřadit výrobkům fuzzy atributy

Jeden konkrétní systém Cíle

Využití existujících relačních databází Data už v nich bývají uložena Jsou již dobře zažité, odladěné a vyspělé

Umožní mimo jiné efektivní práci nad velmi rozsáhlými daty

Při použití rozšíření jazyka SQL bude možné dotazy v něm zapsané převést na běžné SQL, které tak bude efektivně vyhodnoceno

Jazyk fSQL

Architektura systému

Reprezentace dat Atributy výrobků jsou uloženy v relační

databázi, takže jsou „normální“, tedy ne fuzzy množiny

Nad nimi jsou definovány fuzzy predikáty Fuzzy predikát nad spojitou doménou Fuzzy predikát nad diskrétní doménou

Spojitá distribuce nad uspořádanou doménou Diskrétní distribuce nad neuspořádanou množinou

Nad těmito predikáty můžou být definovány fuzzy operátory

Spojité fuzzy operátory Spojitá fuzzy distribuce nad funkcí operandů (např.

jejich rozdílem) Diskrétní fuzzy operátory

Podobnost definovaná pomocí matice podobnosti

Dotazy

Z fuzzy predikátů a operátorů je pomocí logických spojek vytvořena podmínka WHERE.

Je používána fuzzy implementace logických spojek

Výsledný dotaz vypadá takto:SELECT A FROM R WHERE fc

Spojky Negace

Realizováno jako doplněk do jedné μnot A(x)=1-μA(x)

Konjunkce Minimum z obou ohodnocení μA۸B(x)=min(μA(x), μB(x))

Disjunkce Maximum z obou ohodnocení μA٧B(x)=max(μA(x), μB(x))

Výsledek dotazuSELECT A FROM R WHERE fc

Výsledkem dotazu je fuzzy relace Rf, ke které je přiřazena funkce příslušnosti (membership function) určující, jak jednotlivé řádky výsledku odpovídají podmínce fc.

μRf(a)=sup(xєR)۸(x.A=a)μfc(x) Význam: Projekce na sloupce A může způsobit,

že jeden řádek výsledku vznikne z více řádků R. Takovému řádku je přidělena největší hodnota členství ze všech odpovídajících řádků R

Vyhodnocení dotazu

Dotazy chceme vyhodnocovat pomocí relační databáze, je tedy nutné převést fuzzy relaci na běžnou relaci

Provedeme λ-řez, tedy vezmeme ty n-tice z Rf, pro které je μRf(a)≥ λ

SELECT (λ)A FROM R WHERE fc

λ-řez

Aplikace λ-řezu na různé fuzzy distribuce (a) definice predikátu ‘vysoký’ nad cenou

produktu (b) definice predikátu ‘mnohem menší’ nad

rozdílem dvou atributů

λ-řez v číslech Vezměme fuzzy podmínku C a D(C) její

fuzzy stupeň Pak lze provádět úpravy výrazu

D(cena=vysoká ۸ délka « 100)≥0,8 min(D(cena=vysoká),D(délka « 100)) ≥0,8 D(cena=vysoká)≥0,8 ۸ D(délka « 100) ≥0,8 (110≤cena≤180) ۸ (délka – 100) ≤ -18

Tuto podmínku lze již snadno přeložit do SQL

Konkrétní příklad Obchod s vínemREGION (jméno_regionu, země)PRODUCENT (jméno_prod, adresa_prod, email_prod, web_prod,

jméno_regionu)TYP_VÍNA (jméno_typu, typ, barva)VÍNO (jméno_vína, jméno_prod, jméno_typu, jméno_regionu, kategorie,

cru)LÁHEV (jméno_vína, jméno_prod, rok, dostupnost, cena)

Cizí klíče jsouPRODUCENT: foreign key (jméno_regionu) references

REGION(jméno_regionu)VÍNO: foreign key (jméno_prod) references PRODUCENT(jméno_prod)VÍNO: foreign key (jméno_typu) references TYP_VÍNA(jméno_typu)VÍNO: foreign key (jméno_regionu) references REGION(jméno_regionu)LÁHEV: foreign key (jméno_vína,jméno_prod) references

VÍNO(jméno_vína, jméno_prod)

Konkrétní příklad – pokračování Tyto tabulky jsou strukturované tak, jak to odpovídá

relačním databázím Zvolená implementace fuzzy dotazů si však lépe poradí,

když je to vše pohromadě CREATE VIEW PRODUKT (jméno_vína, rok, jméno_prod,

cena, jméno_typu, barva, kategorie, jméno_regionu, věk) ASSELECT L.jméno_vína, L.rok, L.jméno_prod, L.cena, TV.jméno_typu, TV.typ, TV.barva, V.kategorie, V.jméno_regionu, ($CURRENT_YEAR-L.rok)FROM LÁHEV L, VÍNO V, TYP_VÍNA TVWHERE V.jméno_typu=TV.jméno_typu AND L.jméno_vína=V.jméno_vína

Konkrétní příklad - fuzzy Dále definujeme fuzzy operátor podobnosti nad

REGION.jméno_regionu a TYP_VÍNA.jméno_typu, které elegantně reprezentují to, že některé druhy vín a oblasti jsou si podobné

Definujeme také některé fuzzy predikátyPoložka tabulky Fuzzy hodnotyPRODUCENT.jméno_prod norm_důležitost,

vyská_důležitostTYP_VÍNA.jméno_typu norm_důležitost,

vyská_důležitostREGION.jméno_regionu norm_důležitost,

vyská_důležitostLÁHEV.věk mladé, střední, staréLÁHEV.cena velmi levné, levné, střední,

drahé, velmi drahé Nakonec ještě definujeme z dřívějška známý

operátor mnohem menší než «p nad LÁHEV.cena

Konkrétní příklad – zadání dotazu

Dejme tomu, že zákazník hledá mladé červené víno od významného výrobce za středí cenu, která je mnohem menší než €40 a má podobné charakteristiky jako víno z Bordeaux.

Zákazník v nějakém formuláři určí tyto požadavky. Dále je potřeba určit hodnotu λ.

Konkrétní příklad – vytvoření fSQL dotazu Vezmeme-li, že byla zvolena hodnota λ=0.8 dostaneme

tento dotaz:SELECT (0.8) *FROM PRODUKT , REGIONWHERE

(PRODUKT.jméno_regionu=REGION.jméno_regionu) AND(PRODUKT.jméno_regionu |sim| ‘Bordeaux’) AND(PRODUKT.jméno_prod={vyská_důležitost}) AND(PRODUKT.cena=[střední]) AND (PRODUKT.cena «p 40) AND(PRODUKT.věk=[mladé]) AND(PRODUKT.barva=‘červené’)

Konkrétní příklad – převod na SQL Máme určenou hodnotu λ=0.8, takže si

můžeme znázornit distribuce pro cenu a věk

Konkrétní příklad – převod na SQL - pokračování Dostáváme SQL dotazSELECT *FROM PRODUKT, REGIONWHERE

(PRODUKT.jméno_regionu=REGION.jméno_regionu) AND(PRODUKT.jméno_regionu IN (‘Bordeaux’, ‘Jihozápad’)) AND(PRODUKT.jméno_prod IN (‘prod1’, ‘prod2’,… ‘prodN’) AND(PRODUKT.cena BETWEEN 19 AND 31.5) AND(PRODUKT.CENA – 40 <= -18) AND(PRODUKT.věk BETWEEN 0 and 2) AND(PRODUKT.barva=‘červené’)

prod1, prod2, … prodN jsou právě jména producentů, kteří mají míru příslušnosti do množiny vyská_důležitost větší než 0.8

Bordeaux a Jihozápad jsou jediné regiony, jejichž míra podobnosti s Bordeaux je větší než 0.8

Jiné implementace fuzzy SQL

Samozřejmě existují i jiné možnosti, jak přidat fuzzy logiku do SQL

Základ bývá stejný, ale pokročilejší funkce různé

Podívejme se na některé zajímavější rozšíření

Úvodem pár drobností Protože každému řádku výsledku je

přiřazena míra splnění podmínky, lze snadno místo λ-řezu vracet n nejlepších kandidátů

Nad fuzzy podmínkami lze užívat další modifikátory (alteration) very podmínka (x)=(μpodmínka(x))2

not podmínka (x)=1-μpodmínka(x) Agregační funkce – protože fuzzy relace

je nakonec převedena na běžnou relaci, není problém na ní pak pustit normální agregační funkce

Množinové operace nad fuzzy relacemi

unionμAυB(x)=max(μA(x), μB(x))

intesectμA B(x)=min(μA(x), μB(x))

exceptμA-B(x)= μA B(x)=min(μA(x),(1-

μB(x)))

υ

υ

group by a having V jedné z implementací bylo umožněno i

použití group by a fuzzy podmínky having, ovšem pak podmínka za where musela být klasická.

SELECT 10 číslo_oddělení FROM zaměstnanciWHERE zařazení=‘účetní’GROUP BY číslo_odděleníHAVING

around(avg(plat+bonus),1000) oddělení, ve kterých účetní berou plat kolem

1000

Řešní „kolizí“ při projekci Už dříve jsme narazili na problém, že

jeden řádek výsledné fuzzy relace může vzniknout díky projekci na vybrané atributy z více řádků, které mají různou míru splnění fuzzy podmínky.

Situaci lze řešit různě neřešit a vrátit více řádků (SELECT …) vrátit největší míru splnění (SELECT unique …) vrátit nejmenší míru splnění (SELECT unimin

…) vrátit průměr měr (SELECT uniavg …)

Neúplná informace

Mějme doménu atributu D, pak definujeme Unknown={1/d : dєD} Undefined={0/d : dєD} NULL={1/Unknown, 1/Undefined}

Poznámka ke značení: a/b znamená, že b náleží do množiny se stupněm a

Fuzzy operátory porovnání Mimo klasických operátorů porovnání jako =,>,≥,…

lze definovat i fuzzy verze Navíc je možné uvažovat dvě možnosti

porovnání na možnost porovnání na nutnostPorovnání na možnost je volnější (porovnání na nutnost vrací

méně n-tic) Příklad pro rovnost; U je doména, nad kterou je

postavena fuzzy doména D, což je doména atributů A a B

možná rovnost je definována jako μA FEQ B(x)=sup min(μd(x[A]), μd(x[B]))

nutná rovnost jakoμA NFEQ B(x)=inf max(1 – μd(x[A]), μd(x[B]))

dєU

dєU

Efektivní zpracování vnořených Fuzzy SQL dotazů

Fuzzy spojení Značení

= zkoumá podobnost predikátů a vrací hodnotu z <0, 1>

zkoumá identitu a vrací hodnoty 0 nebo 1 Spojení R R.X=S.X S

R, S relace X atribut, který může být hodnota nebo výraz pro

fuzzy množinu Pro libovolné r z R a s z S může být stupeň R.X = S.X,

tj. d(r.X = s.X), mezi 0 a 1. Dvojice je generována pokud d(…) > 0.

Fuzzy spojení Příklad

r.X = „kolem 30 let“, s.X „mladý“ Osoby reprezentované r a s tedy mohou mít stejný věk

pokud se provádí spojení pouze s touto podmínkou, pak stupeň náležení bude min(R(r), S(s), d(r.X = s.X))

Klasické metody pro spojení Spojení hašováním

využívá rozdělení menší tabulky na skupiny (pomocí hašovací funkce)

bere záznamy z větší tabulky a pomocí hašovací funkce se snaží najít záznam z menší tabulky

efektivní metoda u klasického SQL, příliš se však nehodí pro Fuzzy SQL

Spojení sléváním spojení tabulek podle sloupce, podle kterého jsou

obě tabulky řazeny modifikovaný algoritmus použijeme i pro spojení

Fuzzy SQL

Částečné uspořádání fuzzy množina v reprezentuje interval [b(v),

e(v)] b(v) – začátek intervalu, e(v) – konec intervalu jedna hodnota je definována b(v)=e(v)=v pro n-tice r z R, s z S a X použijeme r.X a s.X k

určení jejich fuzzy hodnoty. r.X s.X reprezentuje obvyklý množinový průnik

Částečné uspořádání Definice

pro dvě hodnoty v1 a v2 definujeme v1 < v2 jestliže (b(v1) < b(v2)) || ((b(v1)=b(v2)) &&

(e(v1)<e(v2))) v1 v2 jestliže v1 < v2 && v1 v2

pro n-tice r1 a r2 definujeme r1 < r2 jestliže (r1.X < r2.X) r1 r2 jestliže r1.X r2.X

Spojení sléváním - Fuzzy SQL pomocí definovaného uspořádání můžeme

získat setřízené záznamy definice pomocných funkcí

pro n-tici r z R e sml(r) nejmenší hodnota v taková, která je v S.X a r.X v a lrg(r) je největší hodnota v, která je v S.X a r.X v

rozsah n-tice Rng(r) = {s:s S a sml(r) s.X lrg(r)}, Rng(r) = jestliže r.X v pro všechna v v S.X

pokud nebude s v Rng(r), pak je d(r.X = s.X) = 0

Spojení sléváním - Fuzzy SQL Průběh

načte se jedna stránka s n-ticemi r do paměti pro každé r se berou všechna s z S, na které lze

provést spojení s R (tj. s je v Rng(r)) s jsou také seřazeny a načítány postupně

Časová složitost záznamy jsou načítány a slévány postupně časová složitost je lineární vzhledem k většímu počtu

záznamů (stránek pro uložení záznamů)

Implementace dotazů Vybrané typy SQL dotazů

Typ [A]gregate Typ [J]oin Typ [N]ot join Typ [JA] – Join, Agregate

Rozdělení na typy převzato z W.Kim, On Optimizing an SQL-Like Nested Query

Typ A - Agregate Jak vypadá

vnitřní dotaz neobsahuje podmínku na spojení tabulek a obsahuje agregační funkci na sloupečky z vnějšího dotazu

vnitřní dotaz může být vyhodnocen samostatně, do vnějšího se dosadí vypočítaná hodnota

SELECT SNO FROM SHIPMENT WHERE PNO = (SELECT MAX(PNO) FROM PART WHERE PRICE > 25)

Typ N – Not Join Jak vypadá

vnitřní dotaz neobsahuje podmínku na spojení tabulek a neobsahuje agregační funkci na sloupečky z vnějšího dotazu

výsledkem vnitřního dotazu je množina konstant vnitřní dotaz může být vyhodnocen samostatně

SELECT SNO FROM SHIPMENT WHERE PNO IS IN ( SELECT PNO FROM PART WHERE PRICE > 25 )

Typ J - Join Jak vypadá

vnitřní dotaz obsahuje podmínku na spojení tabulek a neobsahuje agregační funkci na sloupečky z vnějšího dotazu

vnitřní dotaz nemůže být vyhodnocen samostatně SELECT SNO FROM SHIPMENT WHERE PNO IS IN

( SELECT PNO FROM PROJECT WHERE SHIPMENT SNO = PROJECT.SNO AND LOCATION = „New York“)

Typ JA – Join, Agregate Jak vypadá

vnitřní dotaz může obsahovat podmínku na spojení tabulek a obsahuje agregační funkci na sloupečky z vnějšího dotazu

Typ N – implementace Fuzzy Dotaz

SELECT R.X FROM R WHERE p1 AND R.Y is in (SELECT S.Z FROM S where p2)

Zpracování vnitřní dotaz může být zpracován nezávisle stupeň náležení každé nalezené hodnoty vnitřního

dotazu je roven min(S(s), d(p2)) pokud jsou ve výsledku duplicity, pak jsou zrušeny a

u hodnoty je ponechána vždy nejvyšší hodnota náležení

Typ N – implementace Fuzzy Dotaz

SELECT R.X FROM R WHERE p1 AND R.Y is in (SELECT S.Z FROM S where p2)

Jiné zpracování převede se na ekvivalentní dotaz:

SELECT R.X FROM R, S WHERE p1 AND R.Y = S.Z AND p2

R se setřídí podle R.Y a S podle S.Z a provede se modifikované spojení sléváním

stupeň náležení je pak min(S(s), R(r), d(p1), d(p2), d(r.Y=s.Z))

Typ J – implementace Fuzzy Dotaz

SELECT R.X FROM R WHERE p1 AND R.Y is in (SELECT S.Z FROM S where p2 AND S.V=R.U)

Zpracování převede se na ekvivalentní dotaz:

SELECT R.X FROM R, S WHERE p1 AND p2 AND R.Y = S.Z AND S.V = R.U

setřídí se R a S a provede se modifikované spojení sléváním

stupeň náležení je pak min(S(s), R(r), d(p1), d(p2), d(r.Y=s.Z), d(s.V=r.U))

Typ JX – implementace Fuzzy Dotaz

SELECT R.X FROM R WHERE R.Y is not in (SELECT S.Z FROM S where S.V=R.U)

Zpracování převede se na ekvivalentní dotaz:

SELECT R.X, MIN(D) FROM R, S WHERE R(r) AND (S(s) AND R.Y = S.Z AND S.V = R.U) WITH D0 GROUP BY R.K

R.K je klíč R, D je spočtená hodnota náležení ve výsledku mohou být duplicity při odstranění duplicit pomocí distinct se bere max

MIN(D)

Typ JA – implementace Fuzzy Dotaz

SELECT R.X FROM R WHERE p1 AND R.Y op1 (SELECT AGG(S.Z) FROM S WHERE p2 AND S.V op2 R.U)

Značení AGG – agregační funkce op1 a op2 operátory (<, >, >=, <=, =)

Typ JA – implementace Přepíšeme pomocí dvou temporálních relací

T1 = SELECT R.U from R WHERE p1 T2 = SELECT T1.U, AGG(S.Z) FROM T1, S WHERE p2

AND S.V op2 T1.U GROUBY T1.U Výsledek

SELECT R.X FROM R, T2 WHERE p1 AND R.U T2.U AND R.Y op1 T2.A

Pokud je agregační funkce COUNT, pak je výsledek:

SELECT R.X FROM R, T2 WHERE p1 AND R.U + T2.U

Zdroje P. Bosc, M. Galibourg, G. Hamon: Fuzzy

querying with SQL: Extensions and implementation aspects

Luigi Portinale, Stefania Montani: A fuzzy case retrieval approach based on SQL for implementing electronic catalogs

José Galindo, Juan M. Medina, Olga Pons, Juan C. Cubero: A server for fuzzy SQL Queries

Qi Yang, Chengwen Liu, Jing Wu, Clement Yu, Son Dao, Hiroshi Nakajima: Efficient processing of nested fuzzy SQL queries

http://fuzzy.sonalysts.com http://www.lcc.uma.es/~ppgg/FSQL.html