1、25.1n數據庫中的時間n空間與地理數據n多媒體數據庫n移動性與個人數據庫25.2n多數數據庫只刻畫現實世界在某個時間點(當前時間)的狀態(tài), 而時態(tài)數據庫時態(tài)數據庫刻畫現實世界在時間流中的所有狀態(tài).n時態(tài)關系中的事實具有關聯(lián)的表達其有效性(即在現實世界中為真)的有效時間有效時間, 通常表示為時間段(interval, 有開始和結束時刻)的集合.n事實的事務時間事務時間是指該事實出現在數據庫系統(tǒng)中的時間段. n時態(tài)關系時態(tài)關系: 每條元組都具有關聯(lián)的表達其何時為真的時間; 該時間可以是有效時間或事務時間.n雙時態(tài)關系雙時態(tài)關系既存儲有效時間也存儲事務時間.25.3n時態(tài)關系例:n人們提出了時態(tài)查

2、詢語言以便簡化對時間的建模以及與時間有關的查詢.25.4ndate: 四位表示年(1-9999), 兩位表示月(1-12), 兩位表示日(1-31).ntime: 兩位表示小時, 兩位表示分鐘, 兩位(加可選的小數位)表示秒.ntimestamp: 包含date和 time的域, 秒域可另加六位小數位.n時間規(guī)范為世界協(xié)調時(Universal Coordinated Time), 簡稱為UTC (源自法語); 還支持time with time zone和timestamp with time zone.ninterval: 指一段時間(例如2天, 5小時), 不用說明這段時間的特定開始時刻

3、和結束時刻; 更準確地應稱為span.25.5n作用于時間段上的謂詞precedes, overlaps, 和contains.nIntersect 可作用于兩個時間段, 產生單個(可能為空)時段; 但兩個時段的 union可能是也可能不是單個時段.n時態(tài)關系在時刻 t 的快照快照由那些在時刻 t有效的元組組成, 并去掉時間段屬性. n時態(tài)選擇時態(tài)選擇: 涉及時間屬性的選擇操作n時態(tài)投影時態(tài)投影: 投影結果中的元組繼承其在原關系中的時間段.n時態(tài)連接時態(tài)連接: 連接結果中元組的時間段是導致產生該元組的諸元組的時段的交集. 若該交集為空, 則從連接結果中去掉該元組.25.6n函數依賴必須小心使用

4、: 增加時間域可能使函數依賴失效n時態(tài)函數依賴時態(tài)函數依賴X Y 在關系模式在關系模式R上成立, 如果對R的所有合法實例r , r 的所有快照都滿足函數依賴X Y.nSQL:1999 Part 7 (SQL/Temporal) 是擴充SQL:1999以改善對時態(tài)數據的支持的建議標準.25.8n空間數據庫支持基于空間位置的數據的高效存儲, 索引和查詢.l例如:多邊形DB,查詢與給定多邊形相交的多邊形l需要專門的索引結構:如R樹.n兩類空間數據:lCAD數據庫:存儲關于物體如何構造的信息4例如: 建筑設計,飛機設計, 集成電路布局設計l地理數據庫:存儲地理信息4如:道路圖,土地利用圖,地形海拔圖,

5、土地所有權地圖4常稱為地理信息系統(tǒng)地理信息系統(tǒng)(GIS).25.9n各種幾何結構都可在數據庫中以規(guī)范的方式表示.n線段表示為端點的坐標.n折線(或線串)由相連的線段序列組成l端點的有序列表, 或l每個線段表示為單獨的元組, 附上曲線的標識符.n曲線:用折線或圓弧序列近似25.1025.11n封閉多邊形l有序頂點列表, 開始頂點與結束頂點相同, 或者l每條邊表示為單獨元組, 附上多邊形的表識符, 或者l三角剖分三角剖分:多邊形劃分成若干三角形4每個三角形需附上多邊形標識符.n圓和橢圓l提供相應類型l用多邊形近似25.12n三維點和線段的表示:類似二維, 只是點具有z分量n多面體的表示l分割成四面

6、體來表示:類似三角剖分多邊形.l列出它的面(都是多邊形), 附帶指示該面的哪一側屬于多面體的內部.25.13nOODB的一個主要動機是CAD系統(tǒng)的需求l設計部件表示為對象(一般是幾何對象); 對象之間的連接表明了設計結構.n簡單二維對象: 點, 線, 三角形, 矩形, 多邊形.n復雜二維對象: 由簡單對象通過并, 交, 差運算形成.n復雜三維對象: 由簡單三維對象(如球體,柱體, 長方體)通過并, 交, 差運算形成.l三維表面也可用線框(Wireframe)模型表示為簡單對象(如線段, 三角形, 矩形)的集合.25.14n設計數據庫還存儲對象的非空間信息 (如建造材料, 顏色等), 用標準數據

7、建模技術即可.n空間完整性約束非常重要.l例如, 管道不能相交, 線不能互相靠的太近, 等等.(a) 圓柱體的差(b) 圓柱體的并25.15n地理數據:是空間數據l位置信息4地圖4衛(wèi)星圖像l與位置相關的各種信息4海拔4土壤類型4土地使用4年降雨量25.16n在線地圖服務l生成特定區(qū)域的地圖,可縮放l附屬的非空間信息:如道路狀況n車輛導航系統(tǒng)l與GPS結合n公共服務(電力,電話,供水)的分布網絡信息l鋪設的管線信息n用于生態(tài)環(huán)境和規(guī)劃的土地使用信息25.17n柵格數據柵格數據由兩維或更多維的位圖或像素圖組成.l2D柵格圖像:如衛(wèi)星圖像l其它維可包括不同高度不同區(qū)域的溫度, 或者在不同時刻采集的測

8、量值.n設計數據庫一般不按柵格數據存儲.25.18n矢量數據矢量數據是從基本幾何對象構造出的:l二維的點, 線段, 三角形及其他多邊形l三維的圓柱體, 球體, 長方體及其他多面體n地圖數據常用矢量格式表示:l道路可表示為折線l國家,湖泊等可表示為多邊形l河流視其寬度是否相關,可表示為曲線或多邊形25.19n區(qū)域相關的地理信息(如年降水量)可表示為l陣列(即柵格形式)l矢量形式:具有相同柵格值的區(qū)域用一個多邊形表示. n地形信息(表面上點的高度)可表示為l柵格數據l矢量數據:用多邊形表示等高區(qū)域l三角剖分不規(guī)則網絡25.20n向用戶顯示地理信息時可以合并柵格數據與矢量數據l地圖應用通常包含地標圖

9、像和矢量數據l層疊(overlay)4地圖通常由多個層構成:高層數據在低層數據之上n矢量數據發(fā)送到用戶界面時也可轉換成柵格數據25.21n鄰近查詢:查找位于指定位置附近的對象l例如,某位置周邊1km范圍內所有的飯店.n最近鄰查詢:查找距指定點最近的對象l例如,距離當前位置最近的加油站n區(qū)域查詢:查詢完全或部分位于指定區(qū)域的對象l例如, 指定區(qū)域中所有零售店25.22n區(qū)域的并/交l例如,查詢具有低降水量和高人口密度的區(qū)域4兩個空間對象關系(降水量和人口密度)的空間連接:空間位置重疊的空間對象可以配對4空間位置起到連接屬性的作用.n空間數據查詢一般是空間和非空間條件的組合l例如,查詢提供素食的,

10、每餐10元之內的,最近的餐館25.23n空間數據查詢一般使用圖形化的查詢語言;查詢結果也以圖形方式顯示.n前端圖形界面可使用戶:l選擇區(qū)域l放大縮小l選擇顯示內容l多圖疊置25.24nSQL擴展l能夠高效存取空間信息l允許查詢混合空間與非空間條件l支持抽象數據類型, 如線, 多邊形和位圖l支持空間條件:如contains,overlaps25.25CREATE TABLE County(Name varchar(30),State varchar(30),PopInteger,ShapePolygon);CREATE TABLE River(Name varchar(30),Sourcevar

11、char(30),Distance Integer,ShapeLineString);25.26n與Contra Costa接壤的縣SELECT C1.Name FROMCounty C1, County C2WHERE Touch(C1.Shape, C2.Shape) = 1 AND C2.Name = Contra Costa;nMerced河經過的縣SELECT C.Name, R.NameFROMCounty C, River RWHERE Intersect(C.Shape, R.Shape) = 1 AND R.Name = Merced;25.27n回顧:一維數據的索引l例如二

12、叉樹和B樹l不斷將空間劃分成更小的部分25.28nk-d樹的每一層將空間一分為二l在根節(jié)點處選擇一維來劃分;在下一層節(jié)點處選擇另一維來劃分;如此循環(huán)使用各維來劃分空間l每個節(jié)點上的劃分應使該節(jié)點上存儲的點大致平分在下層兩部分空間中.4當一節(jié)點的點數少于給定最大值時劃分終止.nk-d-B樹樹推廣了k-d 樹, 允許每個內節(jié)點具有多個子節(jié)點; 更適合次級存儲器.25.29n圖中每條線對應于k-d 樹中的一個節(jié)點n葉節(jié)點中的最大點數被設置成1n圖中線的編號表示對應節(jié)點的層數25.30n四叉樹的每個節(jié)點都與空間的一個矩形區(qū)域相關聯(lián)n根節(jié)點與整個目標空間相關聯(lián)n每個非葉節(jié)點將其區(qū)域等分成四個象限l對應地

13、, 每個節(jié)點有四個子節(jié)點,分別代表每個象限n葉結點的點數為0到max (例中max=1).l節(jié)點上多于max個點時,就要劃分25.31nPR四叉樹:存儲的是點; 空間劃分是基于區(qū)域的, 而不是基于實際點集.25.32n區(qū)域四叉樹區(qū)域四叉樹存儲陣列(柵格)信息.l若節(jié)點覆蓋的區(qū)域中所有陣列元素值都相同, 則該節(jié)點是葉結點; 否則劃分成四個相等區(qū)域, 該節(jié)點是內節(jié)點l每個節(jié)點對應于一個值的子陣列.l對應于葉節(jié)點的子陣列要么只包含單個陣列元素, 要么有多個具有相同值的陣列元素.25.33n人們提出了k-d 樹和四叉樹的擴展來索引線段和多邊形n線段和多邊形可能跨越區(qū)域的分界線l需要將線段/多邊形分割4

14、同一線段/多邊形可能需在多個葉節(jié)點處表示4存儲和查詢效率低下25.34nR樹樹是B+-樹的N維推廣,適用于點,線,矩形及其他多邊形的索引.n很多現代數據庫系統(tǒng)都支持R樹及其變種R+樹和R*樹.n基本思想: 將與B+樹節(jié)點關聯(lián)的一維區(qū)間的思想推廣到N維區(qū)間, 即N維矩形.n我們只考慮二維的情況(N = 2) lN 2時的推廣是直接的,但R樹只適合較小的N25.35n被索引的對象存儲在葉節(jié)點上n每個節(jié)點都與一個邊與坐標軸平行的矩形邊界框邊界框相關聯(lián).l葉節(jié)點的邊界框是包含所有存儲于該葉節(jié)點的對象的最小矩形.4一個空間對象(任意形狀)的邊界框是包含它的最小矩形4葉節(jié)點也可以存儲對象的邊界框l非葉節(jié)點

15、的邊界框是包含它的所有子節(jié)點的邊界框的最小矩形.l一個節(jié)點的邊界框相當于它的父節(jié)點中的鍵值l一個節(jié)點的各子節(jié)點的邊界框可以重疊n邊界框有利于快速判斷矩形區(qū)域是否重疊nR-樹的存儲效率比k-d樹和四叉樹好, 因為一個多邊形只存儲在一個節(jié)點上25.36n矩形(實線):表示空間對象n邊界框(虛線):不同層次的邊界框構成了R樹25.37n給定p(點/區(qū)域),要查找與之重疊的數據項(空間對象),從根節(jié)點開始做以下步驟:l如果是葉節(jié)點, 輸出鍵值與p相交的數據項.l否則,遞歸搜索當前節(jié)點的每一個其限定框與p重疊的子節(jié)點n在最壞情況下可能效率很低, 因為可能需要搜索多條路徑l兄弟節(jié)點的邊界框可能重疊25.3

16、8n為了插入一個數據項:l找到存儲它的葉節(jié)點, 并將它加入該葉節(jié)點4為找到葉節(jié)點, 沿著其限定框包含該數據項的限定框的子節(jié)點(若有的話)下行, 否則沿著其限定框與數據項限定框具有最大重疊的子節(jié)點下行l(wèi)通過分裂處理溢出(同B+ -樹) 4但分裂過程不同 (見下)l從葉節(jié)點向上調整限定框n分裂過程:l目標: 將溢出節(jié)點中的項分成兩個集合, 使得限定框具有最小總面積4這是啟發(fā)式. 其他如最小重疊也是可能的l尋求“最佳”分裂開銷很大, 可用啟發(fā)式4見后25.39n二次分裂二次分裂(Quadratic split): 將節(jié)點中的項如下劃分到兩個新節(jié)點1.找出一對具有“最大間距”的項4即, 使得兩者的限定

17、框具有最大浪費空間(限定框面積 兩項的面積之和)2.將它們分別放入兩個新節(jié)點3.重復為兩個新節(jié)點之一找出具有 “最大選擇機會”的項, 并將該項放入該節(jié)點H項對一節(jié)點的選擇機會是指如果它加入到另一節(jié)點中會導致限定框面積的增加量4.當一半項已經加入到一個節(jié)點中時停止H再將剩余項加入到另一節(jié)點n更便宜的線性分裂線性分裂啟發(fā)式導致開銷與項數呈線性關系,l便宜但分裂效果稍差.25.40n從R-樹中刪除項類似于B+-樹的刪除.l如果導致節(jié)點項數不足, 如果可能的話從兄弟節(jié)點借一些項, 否則合并兄弟節(jié)點l另一種方法是刪除項數不足的節(jié)點中的所有項, 再刪除該節(jié)點, 然后重新插入所有項25.42n多媒體數據通常

18、存儲在DB外的文件系統(tǒng)中n對海量多媒體數據,需要DB功能:查詢,索引和事務更新等lDB存儲多媒體數據的描述性屬性并跟蹤多媒體對象文件l多媒體數據存儲在DB中25.43n數據庫必須支持大對象l如blob,clob類型l超過限度的lob: 拆分或文件指針lSQL/MED:外部數據(如文件)是DB的一部分n對連續(xù)媒體數據必須提供穩(wěn)定的檢索速率l視頻,音頻n支持基于相似性的檢索l例如:指紋比對25.44n以壓縮方式存儲與傳送多媒體數據lJPEG是最廣泛使用的圖像數據格式.lMPEG利用視頻幀序列之間的共同性來達到較高的壓縮度.nMPEG-1的質量可與VHS錄像帶比較.l存儲一分鐘的30幀每秒的視頻和音

19、頻需要大約12.5 MB(JPEG為75MB)nMPEG-2是為數字廣播系統(tǒng)和數字視盤(DVD)而設計; 視頻質量的損失可忽略.l壓縮1分鐘音視頻大約需要17MB.nMPEG-4支持在各種帶寬的網絡上發(fā)送視頻數據n音頻編碼格式lMPEG-1 Layer 3 (MP3)lRealAudiolWindows Media Audion高清視音頻編碼格式: MPEG-4 AVC, AVCHD25.45n視頻和音頻數據n特點是實時信息投送l數據投送必須足夠快,不能間斷l(xiāng)數據投送速率不能導致系統(tǒng)緩沖區(qū)溢出l必須維護不同數據流之間的同步4例如,口形與音頻同步n從磁盤取數據:周期性循環(huán)25.46nVideo-

20、on-demand 系統(tǒng)從視頻服務器通過網絡將視頻發(fā)送到終端l必須保證點到點傳送速率n當前的video-on-demand服務器基于文件系統(tǒng); 現有數據庫系統(tǒng)不能滿足實時響應要求.l多媒體數據存儲于若干磁盤上 (RAID), 或者將不常用數據存儲在三級存儲器上.l終端 泛指用于觀看多媒體數據的設備, 如PC和連接了稱為機頂盒的小型廉價計算機的TV.25.47n許多多媒體應用中,數據只能在數據庫中近似描述l圖片數據: 兩幅在數據庫中的表示略有不同的圖形或圖像在用戶看來視為相同.例如, 注冊新商標時查找相似設計.l音頻數據: 基于語音的用戶界面允許用戶通過說話來發(fā)命令或找數據項. 測試用戶輸入與存

21、儲命令的相似性.l手寫數據: 查找存儲于數據庫中的手寫數據項或命令n相似度測試比語音識別,手寫識別更成功,因為輸入與系統(tǒng)中已有數據的比較選擇更受限25.49n傳統(tǒng)大規(guī)模商業(yè)數據庫都存儲在中央計算設施,在分布式數據庫應用中通常也有強大的中央數據庫和網絡管理.n一些新技術導致的新應用中,中央控制與管理不再是完全正確:l筆記本,上網本之類計算機的廣泛使用l具有計算機功能的手機的廣泛使用l相對廉價的無線數字通信基礎設施25.50n移動計算應用:l商務旅客在路上辦公,存取數據l投遞服務利用移動計算機跟蹤包裹l應急響應服務利用移動計算機獲取信息,登入現場數據l手機不僅是電話設備,也是移動計算機,可上網25

22、.51n無線計算場景下,設備不再有固定位置和網絡地址l位置相關查詢:用戶(設備)的位置是查詢參數之一l位置參數的值可由GPS之類系統(tǒng)提供l例如:導航應用25.52n能量(電池電量)對移動計算機來說是稀缺資源,影響系統(tǒng)設計的許多方面n一個后果是:移動設備多數時間處于休眠狀態(tài),不時醒來檢查進來的數據及發(fā)送出去的數據.l這種行為對與移動設備的通信協(xié)議有重要影響n定時數據廣播是減少移動系統(tǒng)發(fā)送查詢從而節(jié)省能量的另一種方法25.53n越來越多的數據駐留在由用戶而非DBA管理的機器上n用戶機器可能時不時地斷開網絡連接.n用戶在斷網狀態(tài)下繼續(xù)工作的需求與全局數據一致性的需求之間有沖突25.54n移動計算環(huán)境

23、由移動計算機(稱為移動宿主移動宿主)和有線計算機網絡組成.n移動宿主通過稱為移動支持基站移動支持基站的計算機與有線網絡通信l每個基站管理其覆蓋的地理區(qū)域(蜂窩)內的移動宿主l移動宿主可在不同蜂窩之間移動,這就需要基站之間移交控制4不一定是相鄰蜂窩,因為移動主機可能關閉電源,然后在很遠的另一個蜂窩內開機l小范圍內的移動宿主可通過無線LAN連接:更廉價l鄰近的移動宿主可不經基站介入而相互通信:藍牙25.55n藍牙:10米,721kb/sn無線LAN:801.11,802.16(Wi-Max)n基于分組的蜂窩電話網l模擬技術:語音通信l2G數字系統(tǒng):語音l2.5G和3G:分組網絡,更適合數據應用l4

24、G:25.56n移動計算機的尺寸和能量限制導致l不同的存儲技術:閃存l顯示器,用戶界面lWeb數據需求導致新標準:WAP,WML25.57n移動性影響路由:一對移動宿主之間的路由可能隨時間改變n移動性影響查詢:導致動態(tài)變化的通信代價.還需考慮以下代價l用戶時間l連接時間 在某些蜂窩系統(tǒng)中是計費單位.l傳送的字節(jié)或報文數 在某些數字蜂窩系統(tǒng)中是計費單位l基于每天使用時段的計費 根據高峰或非高峰時段而變化l能量 接收無線電信號比發(fā)送無線電信號需要較少能量.25.58n移動支持基站可以廣播被頻繁請求的數據,而不是按需發(fā)送l典型應用:股價信息n理由l移動宿主不用花費能量來發(fā)送請求l廣播數據可被大量移動

25、宿主同時接收,更有效利用帶寬l支持沒有發(fā)送能力的移動主機25.59n移動宿主可將接收的數據存入本地非易失存儲器作為緩存l將來可通過確定一個查詢是否可以只用緩存數據來回答來優(yōu)化能量使用代價l如果不可以則可:等待廣播數據或發(fā)送數據請求n廣播數據發(fā)送時間表l固定時間表:移動宿主根據時間表來確定何時有相關數據發(fā)送l可變時間表: 廣播時間表本身必須在周知的無線電頻率和時間廣播25.60n移動宿主經常處于斷開連接狀態(tài), 但在斷開期間仍處于操作狀態(tài).n斷開期間如果用戶對本地駐留的或本地緩存的數據發(fā)出查詢和更新, 則會產生問題:l可恢復性可恢復性: 若斷開連接的移動宿主發(fā)生故障, 則其上登入的更新可能丟失. 4由于移動主機是單故障點, 無法很好地模擬穩(wěn)定存儲器.l一致性一致性: 本地緩存的數據可能過時, 但移動主機在重新連接以前無法發(fā)現. 同樣, 發(fā)生在移動主機的更新在重新連接之前也不能傳播.25.61n在移動計算中, 因斷開連接而產生的網絡分割是運行常態(tài),應當允許數據存取,即使這會導致不一致性n對于只被移動宿主更新的數據, 當重新連接時傳播更新.n如果移動宿主緩存了可能被其他計算機更新的只讀數據副本, 則緩存數據可能不一致.l如果移動宿主在線,可用無效性報告通知它已過時的緩存數據l如果移動宿主不在線,可能漏掉報告.25.62n當移動宿主和其他地方都可發(fā)生更新, 則發(fā)現沖突