可能世界內數值型不確定數據匹配模型
2008-12-31 00:00:00申德榮于戈寇月聶鐵錚
計算機應用研究 2008年9期
摘 要：針對數值型不確定數據的匹配進行研究。將存在的數值型不確定數據歸納為range、or_set、probability、unknown、negative五種類型，并給出了形式化定義；提出匹配度和完備度概念，可精確地描述不確定數據的匹配情況，并給出了匹配模型；提出基于range數據類型的匹配度和完備度為最小粒度，定義了其他類型的不確定數據類型的匹配規則，并給出了相應的匹配規則定義。最后通過實例分析，驗證了本匹配模型的有效性。
關鍵詞：不確定數據；匹配模型；數據庫
中圖分類號：TP39 文獻標志碼：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
在可能世界中，不確定信息普遍存在，如人們只知道某一屬性取值的范圍或可能的取值，無法確定該屬性的確切值。目前流行的數據管理一直是針對完備而精確的數據管理，即普遍采用關系數據庫管理數據信息。到目前為止，已有許多有關不確定數據的管理，典型的研究可分為兩個階段：a)在20世紀80年代末到90年代初，針對擴展關系數據庫模型的研究，重點面向1值和maybe值的不確定數據信息管理[1~3]；b)最近幾年針對特定的不確定性如基于概率的面向sensor network的interval數據的研究[4，5]、基于三維的移動對象的研究[6，7]、針對不確定數據的聚集操作的研究[8~11]和數據志（data lineage）管理[12，13]等。盡管有關不確定信息的研究起步較早，但已有研究都具有一定的局限性。因為大多是針對特定一種或幾種不確定數據類型進行相對獨立的研究，沒有可共享性和通用性，也沒有統一的規范標準，導致不確定數據沒有真正得到應用。另外，由于目前支持的數據管理還主要局限于確定數據的管理，約束了其在實際場景中的數據描述，最終導致無法發現數據內更多的潛在信息。
隨著計算機技術和網絡技術的發展、數據的豐富，人們都得益于來自數據的潛在知識，如應用人工智能推理和數據挖掘技術可挖掘數據深層的語義知識。但就數據本身表示能力來說，已有精確的數據表達能力以及處理能力都顯得蒼白無力。因為在現實世界中，數據本身是不確定的，而目前所依賴的數據只是具有確定性的很少一部分，或者說只是在確定的前提下實現的數據處理。顯然，已有的確定的數據處理能力是不夠的。數據表示和處理能力的局限性同樣也體現在Web搜索過程中，如目前Web提供的還處于只支持關鍵字的模糊查詢范圍內，而普遍存在的不確定數據并沒有得到有效利用。例如：查詢“支持率高于50%領導”的信息，只能得到 “有50%”的信息，而40%~60%支持率的信息卻沒有被發現。可見，面向廣泛的具有不確定性的數據處理已迫在眉睫，并且不確定數據處理的成熟和應用將推動數據處理更上一個新臺階。
本文針對數值型不確定數據描述與匹配進行研究，目的是為用戶提供更靈活精確的實體描述形式，使其更接近于現實世界的抽象，為人們有效地描述不確定數據提供一定的參考。同時，通過實現不確定數據的匹配操作，有效地發現潛在的知識，并加以利用，達到為人們提供更準確的決策知識的目的。
1 數值型不確定數據定義
目前，有關非確定數據的定義和分類還沒有嚴格的定義，Trio中將數據分為exact 和 inexact兩種[14]。有關inexact數據的描述又有多種，如不確定的數據、概率數據、模糊集數據、近似數據、不完備數據和不精確數據等。Motro[15]將不確定信息分為不確定和不精確兩類。不確定是指屬性值的可信性，如根據疑難病人的各項檢測信息得出可能的病癥，其可信度不是100%；概率是指屬性取某一值的概率，如心臟病人中吸煙者占75%，非吸煙者占25%，其概率和為1；肥胖者得心臟病的可能性為0.7，但沒有模糊度和為1的約束；該病人的年齡在20~25歲為近似數據；不完備的數據是指有信息丟失，如一部分病人的病例中沒有記錄病人的血型；不精確數據是指數據的取值可能是集合中的數據之一，等等。
文獻[15]中除了將非確定的數據定義為不確定和不精確數據外，還包括不完備、模糊、不一致、不明確。其中除了不明確為語義模糊概念外，其他都涵蓋了Trio中的定義。
歸納已有文章中討論的數據不確定性，本文把不確定數據分為如下幾類：
a)范圍值（range），如John的年齡為[37，43]；
b)Orset值，如John的年齡或者為37或為43；
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。
在可能世界中，這些不確定數據普遍存在，并交疊在一起，如John的年齡為[37，43]的概率為0.8，而取[40，45]的概率為0.2，這是將概率值與范圍值結合表示屬性值；再如John為年輕人的可能性為0.6，而為老年人的可能性為0.3，這是將vague值與fuzzy值結合表示數據的不確定性。
本文只針對數值型的不確定數據進行定義，并基于相應的定義給出相應的匹配規則。
定義1 數值型不確定數據類型（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中包含了五種不確定數據類型（range，or_set，probability，unknown，negative）。因為vague和fuzzy通常是描述非數值型的數據，其不包括在定義1中。Unknown類型可以是不確定數據類型中的任何類型。在數據的實際匹配處理過程中，將依據其預匹配的數據動態地指定其數據類型。
2 數值型不確定數據匹配模型
在已有數值型數據的匹配中，典型的為精確匹配，不適合不確定數據間的匹配。例如，查詢價格100元的U盤，查詢結果為包含有“100元”“價格”“U盤”的信息，而無法發現價格為80~120元的信息。為此，本章針對定義1中定義的五種特定數值型不確定數據類型間的匹配規則進行研究。首先給出匹配度定義，之后以range類型間的匹配度為基礎，定義其他數值型不確定數據類型間的匹配規則。
2.1 Range數據類型間的匹配度
從外觀上看，上面給出的五種不確定數據類型的定義差別很大，很難給出統一的匹配規則。但究其實質，它們都是由單值數據組成的。為此，本文提出將各種不確定數據類型進行轉換，即均轉換為由最小粒度的數據組成，使它們具有可比性，如均由單數據值組成。然而，由于單數據值粒度最小，勢必影響數據間的匹配效率。為提高匹配效率，確定以range粒度為數據原子單位，單數據值看做是上界和下界相同的range類型值。這樣，通過將所有的數據離散化為range類型，并以range數據類型的匹配度為基本匹配單元，計算其他數據類型的匹配度。本文依據兩數據值的交疊概率計算其匹配度。
由于不確定數據間的匹配結果也一定具有不確定性。為有效地描述提供者提供的信息滿足請求的匹配程度，本文提出匹配度和完備度的概念，用來描述不確定數據的匹配結果的不確定性。匹配度描述提供者提供的數據與請求的數據信息的匹配程度，分為完全匹配、不匹配和部分匹配。如圖1所示，Vr和Vp分別為range類型的三種匹配關系。完備度表示提供者提供的數據滿足請求者需求的數據信息的程度。兩者匹配值越大越好。匹配度與完備度具體見定義2。
2.2 數值型不確定數據匹配模型
針對本文定義的五種不確定數據類型，基于定義2中的匹配度和完備度定義，定義各不確定
售價信息表
編號車名稱生產商經銷商售價/萬元
①Mazda6長春一汽經銷商120.5
②Mazda6長春一汽經銷商219~21
③Mazda6長春一汽經銷商3(19，20，21)
④Passat1.8T上海大眾經銷商4(20，0.5)(21，0.5)
⑤Passat1.8T上海大眾經銷商5(18.5，19.5，20)
⑥Passat1.8T上海大眾經銷商618~20
根據請求a）：若按匹配度、完備度降序排列，則得到的匹配結果集為{⑥⑤②③④}。分析表中的實際信息可知：⑥⑤是最好的，屬于完全匹配，它們提供的服務一定能滿足請求；而②③④為部分匹配，其中②③的匹配度大于④的匹配度，因為②③能比④提供更多的滿足請求的資源；①為不滿足的服務。進一步觀察⑥⑤可知，⑥比⑤能提供更廣泛的服務資源，因為⑤中只提供了離散的三個報價信息，并且是或的關系，實際上，相當于只提供了一個滿足服務請求的服務。而⑥提供的是連續的值，范圍比⑤大。所以，⑥的完備度比⑤大。同理，②③④也是如此。
根據請求b）：匹配結果集為{⑥②③⑤④}。因為⑥為完全匹配，完全滿足請求；②③為部分匹配，并且匹配度和完備度都相同，按range類型優先；⑤和④雖然匹配度一致，但⑤的完備度高于④，因為④中滿足部分的概率為0.5，所以⑤好于④。
根據請求c）：匹配結果集為{⑤}。只有⑤滿足服務請求。實際也是如此。
從以上結果分析可知：實際分析結果與采用匹配規則計算所獲得的結果是一致的，可見該匹配模型是有效的。
4 結束語
本文針對可能世界中廣泛存在的不確定信息進行研究。雖然已有針對不確定信息管理的相關研究，但大多是針對只支持幾種特定的不確定數據類型的模型研究，而有關不確定信息的匹配問題的研究還沒有見到。本文分析了可能世界中廣泛存在的不確定數據類型，給出了統一的形式化定義，提出了不確定數據類型間的匹配模型，并詳細定義了匹配規則。最后通過實例驗證，本匹配模型是可行的。
參考文獻：
［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.
