# graphical DB models 介紹
###### tags: `整理paper`

---

## Integrity Constraints 完整性限制

維護資料完整性條件，其目的是確保儲存資料是合法資料。

最簡單的完整限制(Integrity Constraints)牽涉到明確定義每筆資料的資料型態。例如：限定資料表中的學生成績落於"A"到"C"之間，若更新資料為"A"，則系統無法自動發現錯誤，因為資料是有效的；然而，若更新資料為"Z"，則會被系統拒絕，因為資料無效。

較複雜的限制(Constraints)牽涉到一個檔案的紀錄必須與另一個檔案的紀錄相關聯。例如："學生"資料表中的性別欄位，必須與"學生體格"資料表相關聯，此限制又稱為參考性完整限制(Referential Integrity Constraints)。

另一種限制(Constraints)牽涉到表明每筆資料的唯一性。例如：「學生」資料表中的學號欄位，每位學生必須有相異的鍵值(key)，此限制又稱為「鍵值限制」或「唯一限制」(Key or Uniqueness Constraints)。

## Hypergraph 超圖

我們知道普通的graph中，一條邊只能連接兩個點，而邊實際上是用來表示兩點間有鄰接關係的一種符號。而超圖（hyper graph）中的邊可能會關聯（或者說包含）兩個以上的點，即在同一邊中的點均鄰接。
https://hackmd.io/

在數學上，超圖泛指邊可以關聯任意數量點的圖。確切地說，超圖是一種點-邊對（pair），表示為H=(X,E),其中X是點的集合，E是邊（下稱超邊）的集合。超圖中的邊不像普通graph的邊一樣有實體，而只是它所包含的點的集合。所以E實際上是X的非空子集。另外，一個點也可能在多條超邊中。

### 優點

1. 避免數據冗餘 超圖會導致子物件共享和結構繼承概念的自然形式化(也可以多重繼承)
2. 允許定義復雜物件（使用無向超邊）。
3. 功能依賴性（使用有向超邊）。

## Hypergraph-Based Data Model (GROOVY)

Graphically Represented Object-Oriented data model with Values
GROOVY. At the schema level (left), we model an object PERSON as a hypergraph that relates the attributes NAME, LASTNAME and PARENTS. Note the value functional dependency (VDF)
NAME,LASTNAME → PARENTS logically represented by the directed hyperedge ({NAME, LASTNAME}{PARENTS}). This VFD asserts that NAME and LASTNAME uniquely determine the set of PARENTS.

1. 在物件 value是表示一對 O= <i,v>，其中i是物件ID（身份），v是物件值（屬性）。
在值架構級別使用值功能依賴項來斷言一組屬性的值唯一地確定其他屬性的值。 確定的屬性可以是單值或多值。

2. 物件模式是三元組<N，F，S>，其中N是值，F是對N的一組值函數依賴性，而S是N的子集（包括N本身）。 S表示描述物件與主體之間潛在共享的子物件模式。
N as vertices, F as directed hyperedges, and S as undirected hyperedges

3. class模式是一個三元組<N，F，H>，因此H⊆P（N）和N∈H。H定義了一個超class模式/子class模式關係，該關係引起class模式的部分排序，即繼承晶格(inheritance lattice 一對一)。

H的所有元素都是P的元素H⊆P
N是集合H的元素 N∈H

## Simatic-XT: A Data Model to Deal with Multi-Scaled Networks


處理多規模網絡的數據模型
### 動機
動機出於對運輸網絡（火車，飛機，水，電信......等）進行建模，重點是圖的結構、數據，但不涉及要建模的實體的行為。

它定義了三種基本類型：節點類型，邊類型和網絡類型（表示成圖的）。 此外，該模型引入了主節點和主邊的概念，以分別支持子網和路徑的抽象級別，模型在邊上定義屬性，以表示到達主節點（分別為主邊）表示的子圖中（邊路徑）的邊集。 邊以相同的形式表示離開主節點或主邊的一組邊。(parent進來parent出去)

模型中的每個物件都有一個物件標識符（OID object identifier），允許進行標識和引用(identification and referencing)。 抽象級別由主節點和邊節點的巢狀層級(nested level )所確定。

它改善了節點之間路徑的表示和查詢，以及復雜節點和路徑的可視化，但是它缺乏完整性約束的定義。

續集論文[Langou and Mainguenaud 1994]提出了一組圖運算符，分為三類：基本運算符，管理抽象概念（Develop和Undevelop運算符）； 基本運算符，管理圖和子圖的概念（聯合，串聯，選擇和差異）；以及 高級運算符（路徑，包含和交集）。

## Graph Database System for Genomics (GGL)

基因組圖資料庫系統

該數據庫模型來自生物學界，並突出了將基因組圖譜存儲為圖形的優勢。 GGL包括圖論數據庫模型[Graves 1995a]，一種基因組圖語言[Graves，1995年。 1995b]，以及模型的查詢運算符[Graves， 1994年； Graves 1993]。

它們模擬簡單的概念並且可以被標記或不被標記、符號，定義無出線邊的節點；連接兩個頂點並以關係名稱標記的邊，打包的圖頂點，表示包裝（封裝）成頂點的圖。

有兩種查詢數據的方法被提出來，第一[Graves et al 1994]，將查詢圖的形式限制為具有相等約束的有向無環圖的根。此策略基於遵循查詢圖指定的路徑並返回與路徑末端相對應的值

第二種是稱為WEB的聲明性編程語言[Graves 1993]，它將查詢定義為與模型具有相同結構的圖，並在資料庫中返回與查詢圖匹配的圖。

該模型旨在支持基因組數據建模的要求，但也足夠通用以支持複雜的互連結構。 schema和instance之間的區別是模糊的。 其巢狀層級增加了建模與處理
##### 註記:有向無環圖 Directed Acyclic Graph
如果一個有向圖從任意頂點出發無法經過若干條邊回到該點，則這個圖是一個有向無環圖。
DAG 沒有環，不走回頭路、永遠不回頭、不斷向前進。 DAG 可以重新繪製，讓所有邊朝著同一個方向延伸拓展、讓所有點有著先後次序。

## Graph Object-Oriented Data Model (GOOD)
圖物件數據模型[Gyssens 。 1990a]是主要針對開發資料庫最終使用者圖型介面的提案[Gyssens。 1990b]。

schema and instances由有向標記圖表示，而data manipulation由轉換圖來表示。

該模型僅允許兩種類型的節點：nonprintable節點（以正方形表示）和printable節點（以圓圈表示）。 在原子物件，組成物件和集合物件之間沒有區別。 有兩種類型的邊線：功能性邊線（具有唯一值，由→表示）和非功能性邊線（多值且由表示）。

GOOD包含具有圖形語法和語義的數據轉換語言。

它包含四個基本的圖轉換操作：節點和邊的新增和刪除，以及稱為抽象的第五個操作，用於基於公共function或非功能屬性對節點進行分組。

printable和nonprintable節點的概念與圖形界面的設計有關。 它具有多值關係的簡單定義，並允許遞迴關係。 它以平衡的方式解決了數據冗餘問題。

# Graph-oriented Object Manipulation (GMOD)
圖導向的物件操作
Schema and instance are 有標籤的digraph(有向圖)
GMOD [Andries et al. 1992]是針對物件資料庫概念的通用模型的提議，該模型集中於圖導向的資料庫使用者介面。

Schema圖具有兩個class節點，代表class名稱的抽像物件（矩形）和代表基本類型的原始物件（橢圓形）。後者俱有一個附加標籤，指向其值

邊代表抽像物件的屬性。 不考慮單值屬性和多值屬性之間的區別。

模式中定義的相同邊用於表示實例物件的屬性，但不一定需要使用它們（允許使用不完整的信息）。(ex: person不一定要用parent)

該模型使用圖形模式匹配作為統一的物件操作，以進行查詢，指定，更新，操作，查看和瀏覽。

該模型允許簡單地表示物件和關係，不完整的信息，並可以避免數據冗餘。 屬性相關身份和物件ID的概念不完全透明的問題在建模過程中引入了一些複雜性。

G-Log [Paredaens et al. 1995] 是一種針對圖的宣告查詢語言的提議，該語言適用於GMOD定義的數據結構。 G-log中的查詢由程序表示，該程序由許多規則組成，並使用模式（表示為在節點中帶有變量且在謂詞(predicates)中為邊來表示圖）來匹配實例中的子圖。

### 補充:Predicate
即判斷輸入的物件是否符合某個條件，可以使用這個進行過濾。
### 補充:態射（morphism)

數學上，態射（morphism）是兩個數學結構之間保持結構的一種映射。

許多當代數學領域中都有態射的身影。例如，在集合論中，態射就是函數；在群論中，它們是群同態；而在拓撲學中，它們是連續函數；在泛代數（universal algebra）的範圍，態射通常就是同態。

對態射和它們定義於其間的結構（或物件）的抽象研究構成了範疇論的一部分。在範疇論中，態射不必是函數，而通常被視為兩個物件（不必是集合）間的箭頭。不像映射一個集合的元素到另外一個集合，它們只是表示域（domain）和對應域（codomain）間的某種關係。

儘管態射的本質是抽象的，多數人關於它們的直觀（事實上包括大部分術語）來自於具體範疇的例子，在那裡物件就是有附加結構的集合而態射就是保持這種結構的函數。

## Object Oriented Pattern Matching Language (PaMaL)
面向象的模式匹配語言
Gemis和Paredaens [1993]提出了這種基於模式的查詢語言，該查詢語言基於圖形化的物件導向的資料庫模型通過元組(tuples)和集合，對GOOD進行了擴展。

該模式定義了四種類型的節點：class節點（大寫標籤），基本類型節點（小寫標籤），tuple節點和set節點。

邊有四種，分別表示tuple的屬性，集合中元素的類型（用∈標記），class的類型（用typ標記）和層次關係（用isa標記 relations of subclass and superclass (ISA)）。

PaMaL提供了用於新增，刪除（節點和邊）的運算符，以及一種減少實例圖的特殊操作。 它結合了循環，過程和程序構造，使其成為計算上完整的語言。該模型的亮點包括對集合和元組的明確定義，多重繼承以及使用圖形描述查詢。

# Graph-based Object and Association Language (GOAL)
基於圖物件和關聯語言（GOAL）
出於引入更複雜的db-model（ex:物件導向的db-model）的動機，並且旨在為用戶提供一致的圖形界面，Hidders和Paredaens [1993]提出了一種基於圖的db-model，用於描述物件資料庫的Schema和instance。
GOAL通過添加關聯節點的概念擴展了GOOD模型（類似於實體關係模型）。 關聯和物件之間的主要區別在於，物件的身份獨立於其屬性，而如果關聯具有相同的屬性，則認為它們是相同的。

Schema允許定義三種類型的節點：物件節點、代表物件（矩形節點）、值節點，代表可print的值，例如字符串，整數或布林值（圓形節點），以及關聯節點，代表兩個以上節點（菱形節點）之間的關聯或關係

物件和關聯可能具有由邊表示的屬性。該模型允許表示功能屬性（單頭邊）和多值屬性（雙頭邊），以及ISA關係（雙未標記箭頭）。

GOAL中的實例將值分配給值節點，並為物件和關聯節點創建實例。

GOAL引入了一致模式的概念，以確保物件僅屬於它們所標記的class及其超class。另外，GOAL提出了一種圖形數據操作語言，該語言具有基於模式匹配的新增和刪除操作，新增（刪除）操作在實例級別新增（刪除）節點和/或邊。

### THE "ISA" RELATIONSHIP

在使用實體/關係模型建立class層次結構之後，使用一般化原則(generalization)來標識class層次結構以及與每個class相關聯的抽象級別。

一般化意味著對class的連續改進，從而允許物件的超class繼承適用於該class下層的數據屬性和行為。

一般化建立了“分類層次結構”，這些層次結構通常根據詳細程度，根據其特徵來組織class。 一般化從非常一般的級別開始，然後進行到特定的級別，每個子級別都有其自己獨特的數據屬性和行為。

## Graph Data Model (GDM)

GDM [Hidders 2002，2001]是基於GOOD的基於圖的db模型，它添加了顯式的複雜值，繼承和n元對稱關係。

允許三種類型的class節點：物件，複合值和基本值。 用雙線箭頭表示的邊定義了class節點之間的ISA關係。

我們可以有物件節點（描繪為正方形），複合值節點（舍入為空）和基本值節點（以基本類型名稱標記）。

物件節點用零個或多個class名稱標記，表明它們是某些class的成員。 如果具有相同標籤的多個邊離開一個節點，則它是單個設置值屬性。((ex: PC有parent跟child標記的邊，只出去的標記只會有一個屬性

GDM引入了格式良好的圖的概念，定義了四個約束：

（IBVA）沒有從基本值節點離開的邊。
（I-BVT）每個基本值節點都分配有一個實際值，該值在該節點的基本類型的域中。
（I-NS）對於每個class-free節點n，都有一條路徑以n結尾，並以一個帶有class-labeled的節點開始。
（I-REA）複合值節點要嘛僅具有一個傳入邊，要嘛僅帶有一個class name，但不能同時具有兩者。

另外，模型考慮了定義擴展關係的一致性的概念，擴展關係是data圖中的節點與schema圖中的節點之間的多對多關係，表示entities和class之間的對應關係。

獨立的定義schema和instance概念允許instance存在而沒有schema，從而可以表示半結構化數據。

有一種稱為GUL的基於圖形的更新語言，該語言基於模式匹配， GUL允許新增和刪除操作，以及通過合併相似的基值節點和相似的複合值節點的reduction operation，將格式良好的數據圖簡化為實例圖。
## Gram: A Graph Data Model and Query Language


受超文本查詢(hypertext querying)的激勵，Amann和Scholl [1992]引入了Gram，它是一種圖型資料庫模型，其中data被組織為圖。
each node is labeled with a symbol called a type該符號與值的域相關聯
每個邊都分配了一個標籤，用於表示類型之間的關係。 Gram的一個功能是使用正則表達式來明確定義路徑，稱為walks。 節點和邊的交替序列代表一個walk，與其他walk相結合，符合稱為hyperwalks的特殊物件。

為了查詢模型（特別是路徑查詢），提出了一種基於正則表達式的代數語言。為此，定義了hyperwalk代數，該代數呈現一元運算（投影，選擇，重命名）(projection, selection, renaming)和二進制運算（聯接，串聯，設置運算）(join, concatenation, set operations)，在hyperwalks集合裡運算。

## Object Exchange Model (OEM)

OEM [Papakonstantinou et al. 1995]是一個半結構化的DB模型，它允許使用來自物件導向的DB模型的嵌套(nesting)和物件標識的複雜特徵進行簡單而靈活的建模（省略了classes，methods和inheritance之類的功能）。

OEM的主要動機是集合資訊(information integration)的問題，因此，它定義了一種非常適合在異構動態(heterogeneous dynamic)環境中進行資訊交換的語法。

OEM中的數據可以表示為一個有根，有向連接的圖形，其中物件ID代表節點標籤，而OEM標籤則代表邊標籤。 原子物件是葉節點，其中OEM值是節點值。主要特徵是自我描述(self-describing)，即可以在不重複外部架構的情況下對其進行解析，並且使用人類可理解的標籤來添加有關物件的語義信息。由於沒有schema或object class的概念（儘管每個物件都定義了自己的schema），因此OEM提供了異構動態環境中所需的靈活性。

## Resource Description Framework (RDF)

RDF [Klyne and Carroll 2004]是W3C的推薦，最初旨在表示metadata。 RDF的主要目標是定義一種描述資源的機制，該機制不對特定的應用程序域進行任何假設，主要優點（特徵）之一是其以可擴展方式互連資源的能力。
因此，RDF使用圖式結構來建模信息，其中圖論的基本概念（如節點，邊，路徑，鄰域，連接性，距離，程度(degree)等）起著核心作用。

原子RDF表達式是由subject（正在描述的資源），謂詞(predicate)（屬性）和物件（屬性值）組成的三元組。每個三元組代表主體和客體之間關係的陳述。
另外，已經提出並實現了幾種用於查詢RDF數據的語言，它們遵循數據庫查詢語言，如SQL，OQL和XPath [Furche et al。 2006]。

SPARQL [Prud’hommeaux and Seaborne 2005]是一種協議和查詢語言的提議，設計來方便存取RDF的儲存。

它定義了一種類似SQL風格的查詢語言，其中一種簡單的查詢基於圖形模式(graph patterns)，而查詢處理則包括綁定變量以產生pattern solutions（圖形模式匹配）。

## 補充 GraphGrep: A Fast and Universal Method for Querying Graphs
將路徑作為特徵結構，從而構建索引，針對基於路徑的算法的優點是其對路徑的操作比樹和圖更簡單,其索引空間也可以提前定義,其缺點是圖數據庫中的路徑太多形成的集合太大,路徑過於簡單從而不能包含充足的信息。
Shasha等人提出的GraphGrep算法是一種典型的基於路徑的索引算法，也是非數據挖掘索引技術的代表性算法，主要應用於節點含標籤的多圖匹配問題中。GraphGrep在簡歷路徑索引的特徵提取過程中，通過枚舉圖數據中所有長度不超過預設閾值MaxL的路徑，將路徑上的節點按搜索順序排列得到標籤路徑特徵。對於數據圖中的每個節點，採用深度優先搜索，枚舉出由該節點出髮長度為1至固定值MaxL的所有路徑。算法將構成相同標籤路徑的節點序列放在相同集合中。之後採用Hash表存儲每個數據圖與標籤路徑的對應關係。該Hash表被稱作數據圖對應的指紋。 在模式匹配過程中，首先依據模式圖與Hash表篩選備選圖（備選圖包含模式圖所有的Hash值，且不小於對應標籤路徑的數量）；在精確匹配階段，需要對備選圖中的所有標籤路徑進行合併，對於每一個備選圖，該算法選擇H對應的所有節點序列，刪除序列中重複節點後獲得與模式圖匹配的子圖。


### 補充 Transitive closure
用來紀錄由一點能不能走到另一點的關係，如果能走到，則兩點之間以邊相連。
要找出一張圖的 Transitive Closure ，也就是要找出圖上每一個點，走過一條、兩條、…… 、無限多條道路之後，會到達圖上哪些點。
例子:Transitive Closure: Warshall's Algorithm

bool map[9][9]; // 一張圖，資料結構為adjacency matrix。
bool tc[9][9]; // Transitive Closure

void warshall()
{
// 先把原圖複製到要進行DP計算的陣列
for (int i=0; i<9; i++)
for (int j=0; j<9; j++)
tc[i][j] = map[i][j];

for (int k=0; k<9; k++) // 嘗試每一個中繼點
for (int i=0; i<9; i++) // 計算每一個i點與每一個j點
for (int j=0; j<9; j++)
if (tc[i][k] && tc[k][j])
tc[i][j] = true;
}
參考文章:Survey of Graph Database Models