Konceptuální graf

Konceptuální grafy (angl. Conceptual Graphs (CGs), pův. z lat. conceptus – „sebrání, pojetí, shrnutí“, významově pak vycházející ze slova koncepce („pojetí, rozvržení, představa“). Jedná se o model sloužící k formální reprezentaci znalostí. Byly zavedeny Johnem F. Sowou v článku „Conceptual Graphs for a Data Base Interface“ (1976). Popudem ke vzniku konceptuálních grafů byl fakt, že se použití databázových systémů začalo rozšiřovat mezi běžné uživatele, kteří neměli odbornost k přímé práci s databázovým systémem. Dle Sowy tito uživatelé měli dostat prostředek k pokládání databázových dotazů tak, aby nemuseli znát konkrétní způsob vázání databázových objektů (konkrétní vazby je nutné znát například při dotazování v jazyce SQL). Přišel tedy s pojmem konceptuálních grafů jako prostředku popisu dat a jejich vzájemných vazeb, který je ale abstrahován nad konkrétní způsob uložení dat v databázovém systému. Výhodou také je, že konceptuální grafy stojí někde mezi dotazováním v přirozeném jazyce a surovými databázovými dotazy, přičemž z přirozeného jazyka je možné (byť stále poměrně obtížné) generovat konceptuální graf, a z konceptuálního grafu následně generovat databázový dotaz. V prvních pracích na toto téma Sowa konceptuální grafy aplikoval na témata z oborů umělé inteligence, počítačových věd a kognitivních věd.

Konceptuální graf V terminologii konceptuálních grafů existují dva základní stavební kameny, takzvané koncepty (angl. concepts) a vztahy (relations). Význam nějakého vztahu se pak nazývá intenze a soubor všech dat v databázi se nazývá extenze. Extenze je z hlediska konceptuálních grafů poměrně nezajímavá, protože pro přístup k datům byly vyvinuty efektivní jazyky jako je SQL nebo QBE. Naopak to co konceptuální grafy řeší je spojování informací – vztahy dat, intenze. Vztahy jsou pak používány jednak při dotazování, kdy je dotaz uživatele do nich rozkládán, a také při vkládání dat, kdy je jejich cílem udržovat logickou integritu informací.

Vlastnosti konceptuálního grafu Na model jsou kladeny následující požadavky:

Intuitivnost (orig. familiar conventions) – Běžný uživatel by měl být schopen pokládat systému dotazy aniž by se musel zaobírat technickými detaily systému. Automatická inference – Systém je schopný odvozovat vztahy, které v něm nejsou explicitně zabudované. Přirozenost – Formalizmus zápisu vztahů by měl být podobný sémantice přirozeného jazyka. Sémantická integrita – Omezení datové domény by měla pomoci udržet databázi v takovém stavu, aby co nejlépe odrážela realitu. (Sowa, „Conceptual Graphs for a Data Base Interface“, 1976)

Grafická podoba Z pohledu zápisu je konceptuální graf neorientovaným souvislým konečným bipartitním grafem. Jeho bipartita vypadá tak, že v jedné množině vrcholů bipartitního grafu jsou koncepty, v druhé vztahy. Lidově řečeno, v konceptuálním grafu lze hranou spojit vždy jen koncept se vztahem, ale nikoli dva vztahy nebo dva koncepty navzájem.

Základním stavebním kamenem je koncept, který se značí obdélníkem s názvem typu konceptu (v originále „sort label“). Koncept je pouze jakýsi obecný objekt, který může reprezentovat cokoli chceme, např. ČÍSLO, ČLOVĚK nebo ÚČET jsou koncepty. Pokud bychom si chtěli koncept nějak přiblížit, dá se říci že je to analogie datových typů které se vyskytují v programovacích jazycích, obecněji, že jde o entity. Dalším kamenem jsou konceptuální vztahy, jinak též nazývané relace. Konceptuální vztahy se zapisují do kroužků. Ke každému konceptuálnímu vztahu existuje alespoň jedna hrana v grafu (tzv. link), která ho spojuje s nějakým konceptem. Jednoduchý konceptuální graf můžeme vidět na následujícím obrázku.

rám|střed|Příklad jednoduchého konceptuálního grafu.

Tento konceptuální graf vyjadřuje fakt, že „chlapec jde“. Obsahuje dva koncepty – „chlapec“ a „chůze“ a vztah „agent“, který říká že chlapec je entitou, která provozuje nějakou činnost (chůzi). Tento obrázek je klasickým příkladem tzv. dyadického vztahu (vztahu přesně dvou entit). Podle počtu linků mezi vztahem a na něj vázanými koncepty potom mluvíme o vztazích ternárních (triadických), kvaternárních, … a obecně tedy n-árních.

Částečné uspořádání V realitě se objevují koncepty, které mají různou úroveň obecnosti a jejichž konkrétní prvky mohou být vzájemnými podmnožinami. Například ZVÍŘE je podtypem ŽIVOČICH. Tomuto vztahu se říká podtyp a vyjadřuje vzájemnou povahu konkrétních prvků určitých typů konceptů. Samotný konstrukt konceptu není ale ovlivněn – každý typ konceptu je jedinečný i přesto, že oba mohou reprezentovat stejná data. Na množině všech typů konceptů definujeme částečné uspořádání za pomoci operátoru ≤ tak, jak je pro částečné uspořádání zvykem.

Společný podtyp Dva koncepty mohou mít jeden nebo více společných podtypů (angl. common subsort). Například pokub bychom měli koncepty CELÉ-ČÍSLO a KLADNÉ-ČÍSLO jejich společným podtypem bude CELÉ-KLADNÉ-ČÍSLO. Je vidět, že ačkoliv CELÉ-ČÍSLO i KLADNÉ-ČÍSLO jsou koncepty existující samy o sobě, jejich „sloučením“ dostaneme nový, úžeji specifikovaný koncept. Tento koncept lze formálně definovat s použitím relace částečného uspořádání takto:

Společný podtyp Společným podtypem (common subsort) konceptů a a b je koncept c, právě tehdy pokud platí typ(c) ≤ typ(a) a zároveň typ(c) ≤ typ(b). Funkce typ vyjadřuje typ (orig. sort label) daného konkrétního konceptu.

Pravidla tvorby (formation rules) Pomocí konceptů a vztahů modelujeme základní sémantiku naší problémové domény. Pro tvorbu konceptuálních grafů platí sada pravidel, jejichž dodržení má za následek vznik validního (tzv. well-formed) grafu. Rozšiřování či zmenšování existujícího konceptuálního grafu podle těchto pravidel nemůže jeho validitu poškodit. Pravidla pro tvorbu CG jsou následující:

Definice Za předpokladu, že máme množinu well-formed konceptálních grafů, získáme z nich well-formed koncetpuální graf(y) opakovanou aplikací těchto kroků. Graf skládající se z jednoho osamoceného kontextu je validní (well-formed).

Kopírování – Identická kopie validního konceptuálního grafu je taktéž validní konceptuální graf. Oddělení – Všechny souvislé grafy, které jsou výsledkem vymazání konceptuálního vztahu (relace) z grafu, jsou validní. Tedy: smažeme-li z grafu uzel vztahu, graf se nám sice může rozpadnout na více samostatných souvislých grafů, ale z pohledu validity CG nic tím nerozbijeme. Restrikce – Nahradíme-li v grafu konkrétní typ konceptu jeho podtypem, konceptuální graf zůstane validní. Spojení – Mějme dva různé konceptuální grafy, přičemž v obou se vyskytuje stejný typ konceptu. Tyto grafy můžeme sloučit tak, že z jednoho daný uzel typz konceptu smažeme a všechny hrany, které do něj vedly, napojíme na stejný typ konceptu v druhém grafu. Výsledkem je sloučený graf, který je opět validní.

rám|střed|Pravidlo restrikce aplikované na koncept ČLOVĚK.

Obrázek ukazuje princip restrikce. Z původního konceptuálního grafu, který vyjadřoval fakt „člověk jde“ jsme vytvořili „chlapec jde“ pomocí restrikce typu ČLOVĚK na typ CHLAPEC. Protože CHLAPEC ≤ ČLOVĚK, validita grafu je zachována.

rám|střed|Pravidlo spojení aplikované na dva konceptuální grafy. SPojení je provedené na konceptu CHŮZE.

Obrázek zachycuje princip spojení. Původní konceptuální grafy vyjadřující fakty „chlapec jde ráno“ a „chlapec jde do školy“ jsme sloučili nad konceptem CHŮZE a dostali jsme fakt „chlapec jde ráno do školy“.

rám|střed|Pravidlo oddělení aplikované na relaci ČAS.

Obrázek zachycuje princip oddělení. Původní konceptuální graf vyjadřující „chlapec jde ráno do školy“ jsme roztrhli odebráním vztahu ČAS. Výsledný graf vyjadřuje fakt „chlapec jde do školy“, přičemž koncept RÁNO je samostatný a informaci o chlapci jdoucím do školy již nijak neovlivňuje.

Odvozená pravidla Protože konceptuální grafy podporují automatickou inferenci (odvozování závěrů z předpokladů), z výše zmíněných základních pravidel mohou automaticky vznikat pravidla další. Mezi nejvýznamnější patří projekce, která má nezastupitelné místo v prostředí relačních databází. V řeči CG je výsledkem projekce dvou konceptuálních grafů na sebe jejich největší společný podgraf, přičemž v úvaze musíme vzít i podtypy jednotlivých konceptů.

rám|střed|Projekce dvou konceptuálních grafů a její výsledek (dole).

Na obrázku vidíme projekci dvou konceptuálních grafů (fakty „člověk jde“ a „chlapec jde ráno do školy“), jejichž výsledkem je největší společný podgraf, který vyjadřuje fakt „chlapec jde“.

Hodnoty a kvantifikátory V konceptuálních grafech se vyskytují nejen obecné koncepty, ale i koncepty s konkrétní hodnotou nebo s kvantifikátorem. Tyto informace se zapisují jako TYP-KONCEPTU: REFERENT. V případě obecných (angl. indefinite) konceptů pak najdeme například CHLAPEC: * což je formálně správným vyjádřením konceptu „(nějaký) chlapec“. Pokud bychom ovšem do konceptu napsali konkrétní hodnotu (konstantní koncept), například CHLAPEC: Pavel, už jsme vytvořili chlapce Pavla. Konkrétní konstantě (v tomto případě „Pavel“) se také říká designátor. Zapisovat můžeme i množinu hodnot, např. CHLAPEC: {Petr, Pavel}. Pokud bychom použili třeba obecný kvantifikátor, koncept (kvantifikovaný koncept) by vypadal CHLAPEC: ∀ a reprezentoval by fakt „všichni chlapci“. Dalším povoleným kvantifikátorem je kvantifikátor existenční. V analogii na programovací jazyk, koncepty si můžeme představit jako datové typy a nyní řešíme, jakou mohou skutečně nabývat hodnotu, přičemž již máme (díky konstruktu podtypů) i hierarchii nadtyp-podtyp. Poslední možností reprezentace hodnoty je tzv. deskriptor. V sekci o vnořených modelech je vysvětleno, že konceptuální grafy lze do sebe vnořovat. Deskriptor je konceptuální graf, který vysvětluje daný koncept.

Lambda výrazy Lambda výrazy nám umožňují definovat složitější vztahy libovolné arity. Lambda výraz je šablonou (makrem), ze které se po dosazení proměnných stává konkrétní fakt.

rám|střed|Příklad lambda výrazu, který tvoří unární relaci.

Takovýto lambda výraz můžeme číst jako „chlapec λ jde“ a sám o sobě nemá žádný pořádný význam. Teprve pokud dosadíme λ = Pavel, obdržíme fakt „chlapec Pavel jde“. Námi vytvořený lambda výraz je unární relací, protože obsahuje pouze jednu volnou proměnnou. Kdybychom ještě nahradili CHŮZE: * za CHŮZE: λ, dostali bychom relaci binární. Ta by nám například pak umožňovala vytvářet fakty jako „chlapec Pavel jde pomalu“ pro λ = Pavel a λ = pomalá.

Převod do predikátové logiky a funkční závislosti Konceptální grafy jsou poměrně lehce převoditelné do predikátové logiky. Například fakt vyjádřený konceptem CHLAPEC: Pavel bychom převedli následovně: ∃x Chlapec(x) ∧ Jméno(x,Pavel) Každou relaci (konceptuální vztah) pak převádíme jako n-ární predikát.

V predikátové logice má každá logická proměnná svoje označení. Pokud spojujeme dvě nebo více tvrzení predikátové logiky, nevyhneme se přeznačování logických proměnných. To u konceptuálních grafů odpadá, protože logické proměnné mají pouze svou grafickou podobu (obdélníček s konceptem), nikoli přiřazené formální označení – to v predikátové logice slouží stejně jen k tomu, abychom věděli, o které proměnné je zrovna řeč. Sowa ve svém základním textu zmiňuje následující jev: ∀x ∀y ∃z (z=rozdíl(x,y))

Formule predikátové logiky nám říká, že pro každá dvě čísla x,y existuje číslo z, které je jejich rozdílem. Ve formě konceptuálního grafu tento fakt vypadá následovně:

rám|střed|Příklad zobrazení funkčních závislostí v konceptuálním grafu.