【文章內(nèi)容簡介】 ,xk 的實例 ρ=o1,…,ok相同 ,那么它們的時間間隔既不能相同也不能相連。?具有相同實例 ρ的元組集合 T和它們的時間間隔集合 I表示了多個對象的一個組合 o1,…,ok，該 對象集 在 時間 I期間滿足公式 f。?根據(jù)定義 (合式公式的定義 )可知，一個 FTL公式是由若干子公式構(gòu)造而成的。求解的想法就是首先確定原子公式的關(guān)系，再自底向上求解，求解時我們將連接符轉(zhuǎn)換為相應(yīng)的關(guān)系操作。?定義 (在有限制的情況下 )合式公式定義如下 :?(1)如果 R是一個 n元謂詞符號，且 t1 ,…, tn是具有適當類型的項，則 R(t1 ,…, tn )是一個合式公式?(2)如果 f和 g是合式公式，則 f∧ g也是合式公式?(3)如果 f和 g是合式公式，則 f until g是合式公式。?(4)如果 f和 g是合式公式，則 f until_within_c g是合式公式。?(5)如果 f和 g是合式公式，則 f until_after_c g是合式公式。?(6)如果 f是合式公式， x是一個變量，且 t是一個與 x類型相同的項，則 ([x?t]f)是一個合式公式。如果公式中的變量沒有出現(xiàn)在形如 [x?t]的賦值量詞中，我們稱該變量是自由的。合式公式的定義比較? 定義 (在有限制的情況下 )? (1)如果 R是一個 n元謂詞符號，且 t1 ,…, tn是具有適當類型的項，則 R(t1 ,…, tn )是一個合式公式? (2)如果 f和 g是合式公式，則f∧ g也是合式公式? (3)如果 f和 g是合式公式，則 f until g是合式公式。? (4)如果 f和 g是合式公式，則 f until_within_c g是合式公式。? (5)如果 f和 g是合式公式，則 f until_after_c g是合式公式。? (6)如果 f是合式公式， x是一個變量，且 t是一個與 x類型相同的項，則 ([x?t]f)是一個合式公式。如果公式中的變量沒有出現(xiàn)在形如 [x?t]的賦值量詞中，我們稱該變量是自由的。? 定義 ? (1)如果 R是一個 n元謂詞符號，且 t1 ,…, tn是具有適當類型的項，則 R(t1 ,…, tn )是一個合式公式? (2)如果 f和 g是合式公式，則f∧ g和 ┐ g是合式公式? (3)如果 f和 g是合式公式，則 f until g和 nexttime f 是合式公式。? (4)如果 f是合式公式， x是一個變量，且 t是一個與 x類型相同的項，則 ([x?t]f)是一個合式公式。如果公式中的變量沒有出現(xiàn)在形如 [x?t]的賦值量詞中，我們稱該變量是自由的。依次考慮每種情況?設(shè) h是具有自由變量 x1,…,xl 的一個子公式 .?第 1種情況 :h ≡ R(x1,…,xl )?例如 :h ≡ dist(x1, x2)8?假設(shè)對于每一個這樣的原子謂詞以及一個可能的實例化 oi,oj,都有一個算法可以返回當謂詞成立時的時間間隔。?對所有這樣的元組 o1,…,ol以及與其相關(guān)聯(lián)的時間間隔，可以計算得到一個關(guān)系 Rh 。第 2種情況 H ≡ F∧ G?設(shè) Rf和 Rg是根據(jù)子公式計算得到的兩個關(guān)系，例如： Rf(x1,x2,x5 , ts,te)? Rg(x1,x4,x5 , x7,ts,te)?此時，得到的結(jié)果關(guān)系具有如下模式 :? Rh(x1,x2,x4,x5 , x7,ts,te)假設(shè)對于實例 o1,o2,o4,o5,o7,f在 I1上滿足且 g在I2上滿足。因此，通過計算 Rf 和 Rg的連接結(jié)果得到結(jié)果關(guān)系 Rh 。 Rf 和 Rg的連接條件是相同的變量必須相等，同時時間間隔必須相交；每個結(jié)果元組的時間間隔為兩個連接元組的時間間隔的交。第 3種情況 H ≡ F UNTIL G?設(shè) Rf和 Rg是根據(jù)子公式計算得到的兩個關(guān)系 ,分別具有 p+2和 q+2個屬性。?考慮 Rf的元組 t1，設(shè) T1是在前 p個屬性值相同的所有元組的集合（即實例化相同的元組）。設(shè)I1是 T1中的時間間隔集。類似，對 Rg中的 t T2以及 I2做同樣的假設(shè)。?圖為兩個時間間隔有重疊的元組 t1和 t2?如果 f對于 t1時間間隔上的實例化是成立的，則f until g在 t1和 t2時間間隔的并上成立。? t1 (f成立 )? t2 (g成立 )? ( f until g成立 )? 下圖這兩個實例在時間間隔 I1和 I2上的完整集合t1 f成立t2 g成立? ? f until g成立? 而根據(jù) f until g的語義， f until g在 t1和 t2的時間間隔鏈所對應(yīng)的時間區(qū)間上是成立的，這里的時間區(qū)間起始于t1的某個時間間隔，終止于 t2的某個時間間隔的右端。? 所以，按如下方法計算 Rh ：根據(jù)變量的實例化結(jié)果計算Rf和 Rg 的連接并得到匹配的元組對集合。對于得到的兩個時間間隔集 I1和 I2 ，計算它們的時間間隔極大鏈。對于每個極大鏈，構(gòu)造一個結(jié)果元組，它的時間間隔等于該極大鏈的時間范圍。? 另一種計算方法是：對任何有重疊的時間間隔對 t1 和 t2， 計算它們的重疊結(jié)果，然后將所有的重疊結(jié)果合并成一個時間間隔，并將它們放入結(jié)果元組中返回。第 4種情況 H ≡ F UNTIL_WITHIN_C Gf until_within_c g斷言從現(xiàn)在開始至多 c個時間單位內(nèi)存在一個未來時間使 g成立，并且在這個未來時間之前 f一直都是滿足的。? 設(shè) t1,t2是 Rf和 Rg 中具重疊時間間隔的匹配元組對 ,d=max{, },則 f until_within_c g在時間間隔 [d, ]上成立。下圖說明了這種情況：第 5種情況 H ≡ F UNTIL_AFTER_C G第 6種情況 H ≡ [Y← Q]F?Q是一個產(chǎn)生原子結(jié)果的查詢。例如：?y ← height(o)? 設(shè) Rf為 f結(jié)果關(guān)系。項 q是一個一般查詢 ,能產(chǎn)生一個原子結(jié)果，以保證它可以賦給 y，它通常含有一些自由變量。? 假設(shè)由 [y← q]產(chǎn)生的結(jié)果關(guān)系 Rq 有 p+3個屬性 ,其中前面 p個屬性與 q中的自由變量相關(guān)，第 (p+1)個屬性存儲 q的值，剩下的兩個屬性表示一個時間間隔。 q 中自由變量的每一次實例化都會產(chǎn)生一個結(jié)果值，并存儲在第 (p+1)個屬性中。? 如果這個實例化結(jié)果值在 n個不相交的時間間隔上都成立，那么我們就在 Rq中存儲 n個相應(yīng)的元組 。?我們有一個例子： (h ≡ [y← q]f)? Rq 有四個屬性。第一個屬性保存了對象標識，第三個和第四個屬性描述了一個時間間隔，第二個屬性給出了對象在這個時間間隔中的高度。?h的結(jié)果關(guān)系 Rh 是由 Rq和 Rf連接得到的，連接條件是 “ 對于 Rq 中的元組 t1和 Rf中的元組 t2,它們相同變量 上的屬性值相等，并且 Rf中相應(yīng)的 y屬性值等于 t1 中的查詢結(jié)果值 ， 同時 t1和 t2的 時間間隔相交 ” 。?輸出的結(jié)果元組包含了 t1和 t2 中所有的變量屬性值，除了對應(yīng)變量 y的屬 性以及 t1和 t2 時間間隔的交 。?結(jié)果關(guān)系 Answer(Q)可以按下面的方式來回答連續(xù)查詢和即時查詢。?對一個時鐘周期 t時的 連續(xù)查詢 Q，如果實例化后元組的時間間隔包含 t，則將這些元組顯示給用戶。例如，假設(shè) Answer(Q)包含元組(2,10,15)和 (5,12,14),那么 id=2的對象在時鐘周期 10和 15之間顯示給用戶，而 id=5的對象在時鐘周期 12和 14之間顯示給用戶。?對于 即時查詢 Q，如果實例化元組的時間間隔包含當前時鐘周期，則作為結(jié)果顯示。位置更新 平衡更新代價和不精確性 背景 ? 運動的空間對象需要將它們當前位置和速度的更新傳送給數(shù)據(jù)庫，為了數(shù)據(jù)庫中的檢索和查詢提供最新的信息，并可以將查詢結(jié)果的不確定性限定在一定范圍內(nèi)。? 頻繁更新會導(dǎo)致過高代價并會影響性能，低頻率更新可能導(dǎo)致位置查詢返回過時的數(shù)據(jù) 。? 另外，由于對象位置存儲在數(shù)據(jù)庫中 （即數(shù)據(jù)庫位置），它們不可能和對象實際位置完全一致。因此，移動對象的位置具有固有的不精確性。無論我們使用什么樣的策略更新對象的數(shù)據(jù)庫位置，這種不精確性總存在。? 這一節(jié)，我們介紹 推測定位策略 。其定義為：無論何時只要對象的實際位置和其數(shù)據(jù)庫位置的距離超過一個給定的閾值 th(100米 )就執(zhí)行一次數(shù)據(jù)庫更新。? 因此，這個閾值決定并且限定了位置不精確性的范圍 ?不確定性引出的兩個相關(guān)但不同的概念：偏離和不確定性。?移動對象 m在特定時刻 t的 偏離 是指 t時刻 m的實際位置與它的數(shù)據(jù)庫位置之間的距離。在我們的例子中，偏離是指 m的實際位置和 (x,y)之間的距離。?移動對象 m在特定時刻 t的 不確定性 是指包含 m所有可能的當前位置的區(qū)域大小。在我們的例子中，不確定性是以 100米為半徑的一個圓區(qū)域的大小。?偏離 (不確定性 )的代價與偏離 (不確定性 )的大小成比例。?因為移動對象通常裝備有全球定位系統(tǒng) (GPS),因而可以生成位置更新并通過無線網(wǎng)絡(luò)發(fā)送給數(shù)據(jù)庫。這引入了第 3個代價因素： 通信或傳輸代價 。?通信代價和不精確性之間存在著一種顯然的折中關(guān)系，因為通常通信代價越高，不精確性就越低。?由此引出移動對象數(shù)據(jù) 庫中的 信息代價模型 問題。信息代價模型用來平衡不精確性和更新代價，同時它也能處理移動對象連接斷開并且不能發(fā)送位置更新情況。 運動過程的信息代價? 移動對象的 偏離代價 依賴與 偏離的大小 以及它所 持續(xù)的時間 。? 偏離的大小影響著決策過程，偏離越大，則根據(jù)移動對象當前位置做出可靠決策的難度越大，不精確性越高。? 假設(shè)每個時間單位里有一個檢索移動對象位置的查詢。如果偏移持續(xù)了 n個時間單位，那么它的代價就是持續(xù)一個時間單位的偏離代價的 n倍，因為所有 n個查詢 (而不是一個查詢 )都必須接受偏離的懲罰。? 形式化地，對于一個給定移動對象，在開始時間 t1和終止時間 t2之間的偏離代價可通過一個返回非負數(shù)值的 偏離代價函數(shù) COSTd (t1,t2)加以描述 。 運動過程的信息代價?假設(shè)在一個時間單位里偏離一個單位的懲罰權(quán)重是