可能世界內(nèi)數(shù)值型不確定數(shù)據(jù)匹配模型
2008-12-31 00:00:00申德榮于戈寇月聶鐵錚
計(jì)算機(jī)應(yīng)用研究 2008年9期
摘 要：針對數(shù)值型不確定數(shù)據(jù)的匹配進(jìn)行研究。將存在的數(shù)值型不確定數(shù)據(jù)歸納為range、or_set、probability、unknown、negative五種類型，并給出了形式化定義；提出匹配度和完備度概念，可精確地描述不確定數(shù)據(jù)的匹配情況，并給出了匹配模型；提出基于range數(shù)據(jù)類型的匹配度和完備度為最小粒度，定義了其他類型的不確定數(shù)據(jù)類型的匹配規(guī)則，并給出了相應(yīng)的匹配規(guī)則定義。最后通過實(shí)例分析，驗(yàn)證了本匹配模型的有效性。
關(guān)鍵詞：不確定數(shù)據(jù)；匹配模型；數(shù)據(jù)庫
中圖分類號：TP39 文獻(xiàn)標(biāo)志碼：A
文章編號：1001-3695(2008)09-2607-03
Matching model on numerical uncertain data in possible world
SHEN Derong，YU Ge，KOU Yue，NIE Tiezheng
(School of Information Science Engineering， Northeastern University， Shenyang 110004， China)
Abstract:This paper focused on the matching model of uncertain data.Firstly，classified existing uncertain data into 5 types， and gave normal definitions，proposed the concepts of matching degree and completeness degree to describe their matching effectively and gave the matching model.Then，presented the idea of matching degree and completeness degree between range types as minimum granularity to define the matching rules between others， and defined their detail matching rules.Lastly， cases demonstrated the availability of the matching model.
Key words:uncertain data; matching model; database
在可能世界中，不確定信息普遍存在，如人們只知道某一屬性取值的范圍或可能的取值，無法確定該屬性的確切值。目前流行的數(shù)據(jù)管理一直是針對完備而精確的數(shù)據(jù)管理，即普遍采用關(guān)系數(shù)據(jù)庫管理數(shù)據(jù)信息。到目前為止，已有許多有關(guān)不確定數(shù)據(jù)的管理，典型的研究可分為兩個(gè)階段：a)在20世紀(jì)80年代末到90年代初，針對擴(kuò)展關(guān)系數(shù)據(jù)庫模型的研究，重點(diǎn)面向1值和maybe值的不確定數(shù)據(jù)信息管理[1~3]；b)最近幾年針對特定的不確定性如基于概率的面向sensor network的interval數(shù)據(jù)的研究[4，5]、基于三維的移動對象的研究[6，7]、針對不確定數(shù)據(jù)的聚集操作的研究[8~11]和數(shù)據(jù)志（data lineage）管理[12，13]等。盡管有關(guān)不確定信息的研究起步較早，但已有研究都具有一定的局限性。因?yàn)榇蠖嗍轻槍μ囟ㄒ环N或幾種不確定數(shù)據(jù)類型進(jìn)行相對獨(dú)立的研究，沒有可共享性和通用性，也沒有統(tǒng)一的規(guī)范標(biāo)準(zhǔn)，導(dǎo)致不確定數(shù)據(jù)沒有真正得到應(yīng)用。另外，由于目前支持的數(shù)據(jù)管理還主要局限于確定數(shù)據(jù)的管理，約束了其在實(shí)際場景中的數(shù)據(jù)描述，最終導(dǎo)致無法發(fā)現(xiàn)數(shù)據(jù)內(nèi)更多的潛在信息。
隨著計(jì)算機(jī)技術(shù)和網(wǎng)絡(luò)技術(shù)的發(fā)展、數(shù)據(jù)的豐富，人們都得益于來自數(shù)據(jù)的潛在知識，如應(yīng)用人工智能推理和數(shù)據(jù)挖掘技術(shù)可挖掘數(shù)據(jù)深層的語義知識。但就數(shù)據(jù)本身表示能力來說，已有精確的數(shù)據(jù)表達(dá)能力以及處理能力都顯得蒼白無力。因?yàn)樵诂F(xiàn)實(shí)世界中，數(shù)據(jù)本身是不確定的，而目前所依賴的數(shù)據(jù)只是具有確定性的很少一部分，或者說只是在確定的前提下實(shí)現(xiàn)的數(shù)據(jù)處理。顯然，已有的確定的數(shù)據(jù)處理能力是不夠的。數(shù)據(jù)表示和處理能力的局限性同樣也體現(xiàn)在Web搜索過程中，如目前Web提供的還處于只支持關(guān)鍵字的模糊查詢范圍內(nèi)，而普遍存在的不確定數(shù)據(jù)并沒有得到有效利用。例如：查詢“支持率高于50%領(lǐng)導(dǎo)”的信息，只能得到 “有50%”的信息，而40%~60%支持率的信息卻沒有被發(fā)現(xiàn)。可見，面向廣泛的具有不確定性的數(shù)據(jù)處理已迫在眉睫，并且不確定數(shù)據(jù)處理的成熟和應(yīng)用將推動數(shù)據(jù)處理更上一個(gè)新臺階。
本文針對數(shù)值型不確定數(shù)據(jù)描述與匹配進(jìn)行研究，目的是為用戶提供更靈活精確的實(shí)體描述形式，使其更接近于現(xiàn)實(shí)世界的抽象，為人們有效地描述不確定數(shù)據(jù)提供一定的參考。同時(shí)，通過實(shí)現(xiàn)不確定數(shù)據(jù)的匹配操作，有效地發(fā)現(xiàn)潛在的知識，并加以利用，達(dá)到為人們提供更準(zhǔn)確的決策知識的目的。
1 數(shù)值型不確定數(shù)據(jù)定義
目前，有關(guān)非確定數(shù)據(jù)的定義和分類還沒有嚴(yán)格的定義，Trio中將數(shù)據(jù)分為exact 和 inexact兩種[14]。有關(guān)inexact數(shù)據(jù)的描述又有多種，如不確定的數(shù)據(jù)、概率數(shù)據(jù)、模糊集數(shù)據(jù)、近似數(shù)據(jù)、不完備數(shù)據(jù)和不精確數(shù)據(jù)等。Motro[15]將不確定信息分為不確定和不精確兩類。不確定是指屬性值的可信性，如根據(jù)疑難病人的各項(xiàng)檢測信息得出可能的病癥，其可信度不是100%；概率是指屬性取某一值的概率，如心臟病人中吸煙者占75%，非吸煙者占25%，其概率和為1；肥胖者得心臟病的可能性為0.7，但沒有模糊度和為1的約束；該病人的年齡在20~25歲為近似數(shù)據(jù)；不完備的數(shù)據(jù)是指有信息丟失，如一部分病人的病例中沒有記錄病人的血型；不精確數(shù)據(jù)是指數(shù)據(jù)的取值可能是集合中的數(shù)據(jù)之一，等等。
文獻(xiàn)[15]中除了將非確定的數(shù)據(jù)定義為不確定和不精確數(shù)據(jù)外，還包括不完備、模糊、不一致、不明確。其中除了不明確為語義模糊概念外，其他都涵蓋了Trio中的定義。
歸納已有文章中討論的數(shù)據(jù)不確定性，本文把不確定數(shù)據(jù)分為如下幾類：
a)范圍值（range），如John的年齡為[37，43]；
b)Orset值，如John的年齡或者為37或?yàn)?3；
c)否定值（negative），如John的年齡不是37；
d）未知值（unknown），如1值；
e)模糊值（vague），如John為年輕人；
f)概率值（probability），如John的年齡為20歲的概率是0.6，為22歲的概率是0.4；
g)模糊集值（fuzzy），如John的工資是high的可能性為0.6，low的可能性為0.3。
在可能世界中，這些不確定數(shù)據(jù)普遍存在，并交疊在一起，如John的年齡為[37，43]的概率為0.8，而取[40，45]的概率為0.2，這是將概率值與范圍值結(jié)合表示屬性值；再如John為年輕人的可能性為0.6，而為老年人的可能性為0.3，這是將vague值與fuzzy值結(jié)合表示數(shù)據(jù)的不確定性。
本文只針對數(shù)值型的不確定數(shù)據(jù)進(jìn)行定義，并基于相應(yīng)的定義給出相應(yīng)的匹配規(guī)則。
定義1 數(shù)值型不確定數(shù)據(jù)類型（UN_IM_Element_Type）
UN_IM_Element_Type::=〈or_set〉|〈range〉|〈probability〉|〈negative〉|〈unknown〉
〈range〉::=〈rd〉-〈rd〉
〈p_element〉::=〈rd〉|〈range〉
〈probability〉::=〈p_element〉，〈p〉[〈p_element〉，〈p〉]
〈or_set〉::=〈p_element〉[，〈p_element〉]
〈negative〉::=〈O〉〈p_element〉
〈unknown〉::=〈or_set〉|〈range〉|〈probability〉|〈negative〉|
〈p〉::=0.d*
〈rd〉::=d*.d*
〈O〉::=〈〉| not in|
〈d〉::=0|1|2|3|4|5|6|7|8|9
定義1中包含了五種不確定數(shù)據(jù)類型（range，or_set，probability，unknown，negative）。因?yàn)関ague和fuzzy通常是描述非數(shù)值型的數(shù)據(jù)，其不包括在定義1中。Unknown類型可以是不確定數(shù)據(jù)類型中的任何類型。在數(shù)據(jù)的實(shí)際匹配處理過程中，將依據(jù)其預(yù)匹配的數(shù)據(jù)動態(tài)地指定其數(shù)據(jù)類型。
2 數(shù)值型不確定數(shù)據(jù)匹配模型
在已有數(shù)值型數(shù)據(jù)的匹配中，典型的為精確匹配，不適合不確定數(shù)據(jù)間的匹配。例如，查詢價(jià)格100元的U盤，查詢結(jié)果為包含有“100元”“價(jià)格”“U盤”的信息，而無法發(fā)現(xiàn)價(jià)格為80~120元的信息。為此，本章針對定義1中定義的五種特定數(shù)值型不確定數(shù)據(jù)類型間的匹配規(guī)則進(jìn)行研究。首先給出匹配度定義，之后以range類型間的匹配度為基礎(chǔ)，定義其他數(shù)值型不確定數(shù)據(jù)類型間的匹配規(guī)則。
2.1 Range數(shù)據(jù)類型間的匹配度
從外觀上看，上面給出的五種不確定數(shù)據(jù)類型的定義差別很大，很難給出統(tǒng)一的匹配規(guī)則。但究其實(shí)質(zhì)，它們都是由單值數(shù)據(jù)組成的。為此，本文提出將各種不確定數(shù)據(jù)類型進(jìn)行轉(zhuǎn)換，即均轉(zhuǎn)換為由最小粒度的數(shù)據(jù)組成，使它們具有可比性，如均由單數(shù)據(jù)值組成。然而，由于單數(shù)據(jù)值粒度最小，勢必影響數(shù)據(jù)間的匹配效率。為提高匹配效率，確定以range粒度為數(shù)據(jù)原子單位，單數(shù)據(jù)值看做是上界和下界相同的range類型值。這樣，通過將所有的數(shù)據(jù)離散化為range類型，并以range數(shù)據(jù)類型的匹配度為基本匹配單元，計(jì)算其他數(shù)據(jù)類型的匹配度。本文依據(jù)兩數(shù)據(jù)值的交疊概率計(jì)算其匹配度。
由于不確定數(shù)據(jù)間的匹配結(jié)果也一定具有不確定性。為有效地描述提供者提供的信息滿足請求的匹配程度，本文提出匹配度和完備度的概念，用來描述不確定數(shù)據(jù)的匹配結(jié)果的不確定性。匹配度描述提供者提供的數(shù)據(jù)與請求的數(shù)據(jù)信息的匹配程度，分為完全匹配、不匹配和部分匹配。如圖1所示，Vr和Vp分別為range類型的三種匹配關(guān)系。完備度表示提供者提供的數(shù)據(jù)滿足請求者需求的數(shù)據(jù)信息的程度。兩者匹配值越大越好。匹配度與完備度具體見定義2。
2.2 數(shù)值型不確定數(shù)據(jù)匹配模型
針對本文定義的五種不確定數(shù)據(jù)類型，基于定義2中的匹配度和完備度定義，定義各不確定
售價(jià)信息表
編號車名稱生產(chǎn)商經(jīng)銷商售價(jià)/萬元
①M(fèi)azda6長春一汽經(jīng)銷商120.5
②Mazda6長春一汽經(jīng)銷商219~21
③Mazda6長春一汽經(jīng)銷商3(19，20，21)
④Passat1.8T上海大眾經(jīng)銷商4(20，0.5)(21，0.5)
⑤Passat1.8T上海大眾經(jīng)銷商5(18.5，19.5，20)
⑥Passat1.8T上海大眾經(jīng)銷商618~20
根據(jù)請求a）：若按匹配度、完備度降序排列，則得到的匹配結(jié)果集為{⑥⑤②③④}。分析表中的實(shí)際信息可知：⑥⑤是最好的，屬于完全匹配，它們提供的服務(wù)一定能滿足請求；而②③④為部分匹配，其中②③的匹配度大于④的匹配度，因?yàn)棰冖勰鼙娶芴峁└嗟臐M足請求的資源；①為不滿足的服務(wù)。進(jìn)一步觀察⑥⑤可知，⑥比⑤能提供更廣泛的服務(wù)資源，因?yàn)棰葜兄惶峁┝穗x散的三個(gè)報(bào)價(jià)信息，并且是或的關(guān)系，實(shí)際上，相當(dāng)于只提供了一個(gè)滿足服務(wù)請求的服務(wù)。而⑥提供的是連續(xù)的值，范圍比⑤大。所以，⑥的完備度比⑤大。同理，②③④也是如此。
根據(jù)請求b）：匹配結(jié)果集為{⑥②③⑤④}。因?yàn)棰逓橥耆ヅ洌耆珴M足請求；②③為部分匹配，并且匹配度和完備度都相同，按range類型優(yōu)先；⑤和④雖然匹配度一致，但⑤的完備度高于④，因?yàn)棰苤袧M足部分的概率為0.5，所以⑤好于④。
根據(jù)請求c）：匹配結(jié)果集為{⑤}。只有⑤滿足服務(wù)請求。實(shí)際也是如此。
從以上結(jié)果分析可知：實(shí)際分析結(jié)果與采用匹配規(guī)則計(jì)算所獲得的結(jié)果是一致的，可見該匹配模型是有效的。
4 結(jié)束語
本文針對可能世界中廣泛存在的不確定信息進(jìn)行研究。雖然已有針對不確定信息管理的相關(guān)研究，但大多是針對只支持幾種特定的不確定數(shù)據(jù)類型的模型研究，而有關(guān)不確定信息的匹配問題的研究還沒有見到。本文分析了可能世界中廣泛存在的不確定數(shù)據(jù)類型，給出了統(tǒng)一的形式化定義，提出了不確定數(shù)據(jù)類型間的匹配模型，并詳細(xì)定義了匹配規(guī)則。最后通過實(shí)例驗(yàn)證，本匹配模型是可行的。
參考文獻(xiàn)：
［1］ZIMANYI E.Incomplete and uncertain information in relational databases[EB/OL].（2005-03-01）.http://code.ulb.ac.be/dbfiles/.
[2]ABITEBOUL S，PARIS K，GOSTA G.On the representation and querying of sets of possible worlds[C]//Proc of ACM SIGMOD International Conference on the Management of Data.New York:ACM Press，1987:34-48.
[3]BARGA R S，PU C.Accessing imprecise data:an approach based on intervals[J].IEEE Data Engineering Bulletin，1993，16(2):1215.
[4]CHENG R，PRABHAKAR S.Managing uncertainty in sensor databases[J].SIGMOD Record Issue on Sensor Technology，2003，32(4):41-46.
[5]CHENG R，SINGH S，PRABHAKAR S.UDBMS:a database system for managing constantlyevolving data[C]//Proc of the 31st VLDB Conference on Very Large Databases.2005:12711274.
[6]TRAJCEVSKI G，WOLFSON O，HINRICHS K，et al.Managing uncertainty in moving objects databases[J]. ACM Trans on Database Systems，2004，29(3):463-507.
[7]CHENG R，PRABHAKAR S，KALASHNIKOV D V.Querying imprecise data in moving object environments[J]. IEEE Trans on Knowledge and Data Engineering Archive，2004，16(9):11121127.
[8]ROSS R，SUBRAHMANIAN V S.Aggregate operators in probabilistic databasess[J].Journal of the ACM，2005，52(1):54101.
[9]SCOTNEY B，McCLEAN S.Database aggregation of imprecise and uncertain evidence[J].Journal of Information Sciences，2003，155(3-4): 245-263.
[10]MORRISSEY J M.Imprecise information and uncertainty in information systems[J].ACM Trans on Information Systems，1990，8(2):159180.
[11]HONG X，McCLEAN S，SCOTNEY B，et al.Evidential integration of semantically heterogeneous aggregates in distributed databases with imprecision[C]//LNCS4224.2006:961-969. [12]WIDOM J.Trio:a system for integrated management of data，accuracy， and lineage[C]//Proc of the 2nd Biennial Conference on Innovative Data Systems Research.2005.
[13]MUTSUZAKI M，THEOBALD M，DeKEIJZER A，et al.Trioone:layering uncertainty and lineage on a conventional DBMS[C]//Proc of CIDR.Monterey:[s.n.]，2007:269-274.
[14]SARMA A D，BENJELLOUN O，HALEVY A，et al.Working models for uncertain data [EB/OL].(2006-03-02).http://twikiedlab.cs.umass.edu/pub/.
[15]MOTRO A.Management of uncertainty in database systems[EB/OL].(2005-0315).http://ise.gmu.edu/~ami/research/publications /pdf/modern94.pdf.
