主題
前言：
專題內容，自學中。
語意網 (semantic web) 在1998年提出的一個概念，它的核心是：通過給全球資訊網上的文件（如: HTML文件）添加能夠被電腦所理解的語意（元資料），從而使整個網際網路成為一個通用的資訊交換媒介。[1]
範例：Paul出生在 Dresden (Paul Schuster was born in Dresden)可以用html標記成[2]：
上面的型式可以看到：實體→定義→值。
例如: _:a → <https://schema.org/name> → "Paul Schuster" .
這種3元組(triple)的型態就是RDF (Resource Description Framework)的型態。
RDF是圖形話關聯的資料庫框架，其查詢語言SPARQL回傳的都是以triples(subject -> Predicates -> value)的型態，會回傳triple是因為triple都有相同的架構。(Tuples always has the same structure.)，方便用RDF框架的資料與不同維度的資料合併之類的操作。[原文2]
範例：
格式(subject -> Predicates -> value)
John是subject
Knows是Predicate
Tim是value
Tim是subject
phoneNo是Predicate
+23456是value
這是個subject - subject的關聯。
RDF有內建基本類別：
例如:rdfs:Class 定義類別rdfs:subClassOf 定義副類別rdfs:label 定義perdicaterdf:type 指定獨立資料為類別。
Movies rdf:type rdfs:Class.ActionMovies rdfs:subClassOf Movies.Dramas rdfs:subClassOf Movies.
SPARQL (Sparql Protocol And Rdf Query Language)
SPARQL 是一種資源描述架構 (RDF) 的查詢語言，是專為網路設計的圖形資料格式。[3]
參考影片：SPARQL in 11 minutes
規則：
prefix 定義前段網址，這樣就可以使用縮寫。
變數前面加「?」，Where子句每句話結束要加「.」
語意：
定義查詢結果?person，並回傳: http://www.w3.org/2006/vcard/ns#/family-name/Smith的結果。
SPARQL有種查詢法叫做Subgraph Matching，尋找Isomorphism(同構)的圖形：找到相同節點連接順序的資料。注意是用節點連接順序判斷，例如GraphH所有節點位置打亂但保持原連結的話也是大約等於GraphG。
Querying linked data
WLD (web of linked data):
整合了多個網站的RDF資料。WLD遵循以下規則用RDF資料建造出語意網絡:
- 所有web資源皆有它們自己本地的URIs定義。
- 資料都以三元組方式編碼成RDF格式。
- 資料集的連接是使用資料間的連結。
- 主機需要能回覆HTTP查詢。
- (LOD)資料需要公開。
在WLD執行查詢的演算法可分為: 遍歷、索引、混合。traversal-based: 遍歷
提供語意查詢，從種子URI開始遍歷與發覺相關的URI，此種演算法選擇種子URI對效能影響很大。(Traversal approaches basically implement a reachability-based semantics: starting from seed URIs, they recursively discover relevant URIs by traversing specific data links at query execution runtime.)✅優點：
- 簡單，不需要額外資料結構，如索引表。
❌缺點：index-based 索引
- 效能不佳。
- 受限制的水平執行。
索引鍵是三元組的模式，使用索引定位資料URI。，由此減少需要讀取的文件。✅優點：
- data取得可以完全平行執行。
❌缺點：Hybrid 混合
- 需注意index的獨立性。
- 建造index的延遲。
- index SELECT的限制。
- 動態web資料與index更新。
根據優先清單遍歷搜尋URI。 初始的種子來自預先準備的索引表。新發現的資料URI(不在索引表上的)會依照關聯文件的數量排行。
Clustering of physical records資料聚合
資料聚合的動作可以是定時執行，或是線上執行。The proposed periodic clustering algorithm (定時更新聚合)
online clustering algorithm (動態執行)訓練學習聚合BGP陣列：
- training:執行並蒐集資料，不會更動到原檔案。可能是使用次優聚合資料進行訓練。
- optimization: 使用在training階段的資料產生新的groupby-query聚合，且實體資料會依據此做更新。
- operation: 更新groupby-query聚合。
在執行查詢時動態產生group-by-query clustering。因為產生聚合相當耗效能，因此優化有：
- 只計算較常讀取的資料庫快取部分。
- 自動學習的局部敏感哈希locality-sensitive hash (LSH)，例如Tunable-LSH 用來在固定時間內決定資料的存放位置。
不像LSH，Tunable-LSH會自動調整來校對準確度，Tunable-LSH有2個重要特性：
嘗試確保:
- 有相似用處的三元組樣式資料要盡可能分類在相同group-by-query clusters聚合(如:分配在相同記憶體分頁上)
- 減少誤分類在同個聚合的不相似三元組資料。
以下是原文的內容(我翻譯的不太好)：
資料倉儲：
資料倉儲集中管理並整合來自於大量來源的大量資料。其分析功能可讓組織從其資料中推知寶貴的資料見解，以改善決策制定[4]。中心化方法，將全部資料整合在一個RDF資料庫，可以導出五種做法:
- 將RDF資料直接映射進關聯系統(those that map the RDF data directly into a relational system)
- 索引搭配關聯系統(those that use a relational schema with extensive indexing)
- 將triples table反規範化成複合式屬性(those that denormalize the triples table into clustered properties)
- 使用資料行存放索引。(those that use column-store organization)
- 外顯圖形配對語法。(those that exploit the native graph pattern matching semantics of SPARQL)
直接關聯映射Direct relational mappings
將RDF資料依照三元組s,p,o拆成表格欄位，並將Sparql轉成SQL查詢。範例：Sesame SQL92SAIL以下是將左邊的SPARQL 語法轉成SQL語法。❌缺點：
轉成SQL語法會參雜大量self-join。
單表索引 Single table extensive indexing
只使用一個table，但使用多個內存空間存放索引表。範例: Hexastore、RDF3X
RDF3X：
產生s,p,o組合的所有可能 (spo, sop, ops, ops, sop, pos)並做成索引(照第一欄的字母順序排列)。
✅優點：
- 有效查詢變數。
- 透過index查詢減少self-join。
- 可套用快速 merge-join
❌缺點：
- 消耗儲存空間。
- 一個更動會需更新多個indexs。
額外補充：
補充 Cluster index / non cluster index /Leaf pages
補充 Merge-join是甚麼?
利用RDF資料的規律性，儲存重複出現的patterns，因此資料都有一定的關聯性存在。
範例：Jena、DB2RDF
Jena Property Table Implementation
IBM DB2RDF將相同類型的屬性的subject放在一個屬性表，如此一個類別下的所有成員都會在一張表格上。
能自動將s,p,o三元組轉換成DPH (direct primary hash)和DSH(direct secondary hash)表格，比Jena有更動態的資料表管理。
每個表格有k個欄位，以subject為表頭，其內容為該subject關聯的property,object們。若該subject的property數量大於k，則會接續下一列，並在"spill"欄位標示。若是多值屬性，則會在原value欄位上紀載唯一id，並將對應的值存在DSH (direct secondary hash) 表格。
目標是減少欄位數量k的同時減少spill數量。範例：
✅優點：
❌缺點：
- 在單表查詢減少星狀查詢的joins數。(處理單值predicate只需查1個表，但多值predicate就需要多個joins。)
- 大量null值。
- 不易處理多值欄位。
- 除了星狀查詢效能較佳外，其他型態的查詢就沒有什麼優化效果。
補充文獻(還沒讀完)[5]
儲存RDF資料的系統可分成兩種類型：
Native stores:
Relationally-backed stores:例如：Jena-TDB、RDF-3X、4store利用進位儲存RDF資料，效率較差。
例如：Jena SDB、C-store將RDF資料存成關聯式資料庫。✅擴充性 ✅壓縮 ✅安全性 ✅企業支持困難點：如何阻止關聯式資料庫繼承自錯的RDF模型。
將RDF資料轉成關聯式資料庫的幾種方法：triple store將三元組拆成s,p,o三個欄位。type-oriented依照subject劃分表格。predicate-oriented用列儲存的方式為每種predicate建立二進位的subject-subject表。entity-oriented (DB2RDF)✅優點：
- 帶有方法1的彈性。
- 將所有predicate存在同列提供關聯式資料庫的優點，同時具備type-oriented和 predicate-oriented的特性。
- 省儲存空間。
❓問題點：
二元表 Binary tables
- 如何指派欄位(column)給predicate?
- 如何決定k的大小?
為每個property定義一個2欄表格，包含subject和object並依subject排序。
範例：p為movie:actor產生得表格。
✅優點：
❌缺點：
- column-oriented資料庫模式，減少I/O和元組長度。
- 減少null數量，不需要找出相關的property。
- 支援多值property。
- 因為用subject排序，可以使用高效能的merge-joins。
- query需要更多的joins，因為有些是subject-object joins則無法受益於merge join operation。
- 寫入操作需要更新多個表格。
- table數量在擴展性上有負面影響。
用同態映射比對圖形query。(do subgraph matching using homomorphism to evaluate the query against the RDF graph.)範例：gStore
使用VS∗-tree演算法，將實體和類別編碼成固定長度的bit string。
✅優點：❌缺點：
- 保留RDF的圖形結構
- 圖形同態映射是NP-Complete問題。
以上是資料集中管理的做法，接下來是分散式RDF處理的幾種作法。
分散式RDF處理:
Cloud-based approaches:
像Kaoudi和Manolescu提供雲端平台服務，許多方法依從著MapReduce規範，尤其是使用HDFS，且將RDF三元組儲存在HDFS。
分散式檔案系統 HDFS
MapReduce 顧名思義是以 Map 跟 Reduce 為基礎的應用程式。一般我們進行資料分析處理時，是將整個檔案丟進程式軟體中做運算出結果，而面對巨量資料時，Hadoop 的做法是採用分散式計算的技術處理各節點上的資料。在各個節點上處理資料片段，把工作分散、分佈出去的這個階段叫做 Mapping；接下來把各節點運算出的結果直接傳送回來歸納整合，這個階段就叫做 Reducing。這樣多管齊下、在上千台機器上平行處理巨量資料，可以大大節省資料處理的時間。✅優點：❌缺點：
- 擴增性、容錯性高。
使用MapReduce圖形運算效能較差。
SHARD、HadoopRDF、PredicateJoin、EAGRE 主要的差異是RDF三元組如何存在HDFS檔案裡。SHARD:
將資料存放在單一個檔案。
HadoopRDF 和 PredicateJoin :
用property劃分RDF資料，並將劃分的檔案存在HDFS裡。
EAGRE :
收集有相似property的subject成entity class，然後建構出只有entity class與之之間的edge的RDF圖形。使用METIS演算法劃分RDF圖形，entity依照劃分規劃存在HDFS檔案裡。
將RDF圖形拆成許多片段存放在不同網站上。查詢句會被拆解子查詢句，而查詢句可以被各網站回答，然後匯聚答案。範例：GraphPartition
一RDF graph G被劃分成n個片段，且每個片段包含N階層的鄰居，圖形的直徑不該大於N才能使子查詢能被本地端處理。
❌缺點：
- 分區塊的規則難界定，例如不同資料供應商提供的格式或型態不同。
分散式處理還有更多，只是我沒查太細，有興趣的可以去我的筆記看。
