基于眾包的數(shù)據(jù)庫(kù)信息查詢處理方法

王凡

摘要：為解決傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)中，數(shù)據(jù)不完整或需語(yǔ)義理解時(shí)系統(tǒng)返回錯(cuò)誤應(yīng)答的問(wèn)題，提出了基于眾包的數(shù)據(jù)庫(kù)信息查詢處理方法。研究給出了基于眾包的數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)框架，并給出適用于該系統(tǒng)查詢的類SQL語(yǔ)句，有效提高了數(shù)據(jù)庫(kù)系統(tǒng)的信息處理能力。

關(guān)鍵詞：眾包；數(shù)據(jù)庫(kù)系統(tǒng)；SQL語(yǔ)句；類SQL語(yǔ)句

中圖分類號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2016）16-0025-03

Abstract： In order to solve the problem of the data is incomplete or when needs semantic understanding the traditional database system returns an error response， this paper put forward the database information query processing method based on the crowdsourcing. Research shows the architecture framework of database system based on crowdsourcing， and given query types of SQL statements suitable for the system， which effectively improve the information processing capacity of database system.

Key words： crowdsourcing； database system； SQL semantics； SQL-like semantics

1 緒論

關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)不僅在最初預(yù)期的商業(yè)環(huán)境，而且在許多結(jié)構(gòu)化數(shù)據(jù)如個(gè)人的、社會(huì)的，甚至科學(xué)信息等其他領(lǐng)域中得到普遍的應(yīng)用[1]。然而，因?yàn)閿?shù)據(jù)的創(chuàng)新和使用通過(guò)WEB網(wǎng)絡(luò)，移動(dòng)手機(jī)和其他技術(shù)變得越來(lái)越大眾化，科學(xué)技術(shù)的限制越加明顯。關(guān)系數(shù)據(jù)庫(kù)管理系統(tǒng)對(duì)它們存儲(chǔ)的數(shù)據(jù)做了幾個(gè)關(guān)鍵的關(guān)于正確性、完整性和無(wú)歧義性的假設(shè)。當(dāng)這些假設(shè)不被贊成，相關(guān)的系統(tǒng)會(huì)對(duì)用戶的請(qǐng)求返回不正確的和不完整的應(yīng)答，如果它們返回任何應(yīng)答的話。

在關(guān)系數(shù)據(jù)庫(kù)模型中，主要包括查詢操作和插入、刪除和修改操作兩大部分。其中，因?yàn)殛P(guān)系的查詢表達(dá)能力很強(qiáng)，是關(guān)系數(shù)據(jù)庫(kù)操作中最主要的部分。然而，傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)中存儲(chǔ)的數(shù)據(jù)都是結(jié)構(gòu)化的，其查詢也多為精確匹配。當(dāng)數(shù)據(jù)庫(kù)中所存信息不完整或需語(yǔ)義理解時(shí)，數(shù)據(jù)庫(kù)常會(huì)對(duì)查詢返回一個(gè)錯(cuò)誤的應(yīng)答。因此，僅僅依靠機(jī)器是不能應(yīng)答所有的查詢的。處理這些查詢需要人的輸入，以提供丟失的信息或加入人的判斷。

現(xiàn)有的兩種明顯的狀況是，數(shù)據(jù)不完整或需要對(duì)語(yǔ)義進(jìn)行分析理解時(shí)。其中，數(shù)據(jù)不完整即信息的缺失。例如查詢：

Select * from Student

Where name=”Wang Fan”；

會(huì)返回一個(gè)空的應(yīng)答，如果在當(dāng)時(shí)的數(shù)據(jù)庫(kù)中，Student表中不包含一個(gè)“Wang Fan”的記錄。這樣一個(gè)記錄的缺失，原因有多種：

1）遺漏。當(dāng)錄入Student表信息的時(shí)候，可能由于人為的輸入而造成遺漏；

2）刪除?？赡茉谀承┎僮鬟^(guò)程中，無(wú)意中刪除了這一記錄；

3）輸入有誤。如在本例中，“Wang Fan”這一記錄，有可能被錯(cuò)誤的輸入為“Wang Fen”。

另一個(gè)問(wèn)題是需要對(duì)語(yǔ)義進(jìn)行分析理解時(shí)，例如查詢：

Select * from SS

Where name=”CS”；

會(huì)返回一個(gè)空的應(yīng)答，如果在當(dāng)時(shí)的數(shù)據(jù)庫(kù)中，“CS”被輸入為“Computer Science”。對(duì)于人來(lái)講，能夠快速識(shí)別“CS”和“Computer Science”在現(xiàn)實(shí)世界中指的是同一實(shí)體，但對(duì)于機(jī)器而言，卻無(wú)法進(jìn)行識(shí)別。這其實(shí)也是判斷的一種。另一種判斷是，如查詢：

Select idea from paper

Order By practical LIMIT 5；

找到5個(gè)最具實(shí)踐性的想法，傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)無(wú)法應(yīng)答這樣的查詢，除非關(guān)于這些想法的實(shí)踐性已經(jīng)事先獲得并存儲(chǔ)在數(shù)據(jù)庫(kù)中。

以上這些查詢僅僅通過(guò)機(jī)器是不能被應(yīng)答的，但可以容易的被人所應(yīng)答。機(jī)器和人各有所長(zhǎng)，因此，通過(guò)引入眾包，來(lái)借助人的網(wǎng)絡(luò)去完成不適合計(jì)算機(jī)執(zhí)行的任務(wù)，從而有效的擴(kuò)展傳統(tǒng)關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)的信息處理能力。

2 眾包

2.1眾包

眾包是繼長(zhǎng)尾理論后又一重要的商業(yè)概念，近年來(lái)得到廣泛的關(guān)注。眾包 （crowdsourcing） 這一概念是由美國(guó)《連線》雜志的記者杰夫·豪（Jeff Howe）在 2006年6 月提出的[2]。杰夫·豪對(duì)“眾包”的定義是：“一個(gè)公司或機(jī)構(gòu)把過(guò)去由員工執(zhí)行的工作任務(wù)，以自由自愿的形式外包給非特定的（而且通常是大型的）大眾網(wǎng)絡(luò)的做法。具有低成本生產(chǎn)、聯(lián)動(dòng)潛在生產(chǎn)資源、提高生產(chǎn)效率，以及滿足用戶個(gè)性化需求等優(yōu)勢(shì)。

自眾包概念提出以來(lái)，學(xué)術(shù)界對(duì)眾包的定義一直沒(méi)有公認(rèn)的統(tǒng)一的界定。但是，從學(xué)者們對(duì)眾包的概念分別從大眾、企業(yè)、外包以及價(jià)值等多角度所進(jìn)行的界定，我們可以總結(jié)出眾包的基本特征：

1） 通過(guò)公開(kāi)的方式來(lái)召集網(wǎng)絡(luò)大眾；

2） 眾包任務(wù)一般是計(jì)算機(jī)單獨(dú)難以完成的工作；

3） 大眾通過(guò)協(xié)作或者獨(dú)立的方式完成任務(wù)；

4） 是一種分布式的問(wèn)題解決機(jī)制。

2.2眾包的工作流程

眾包的參與者主要有任務(wù)請(qǐng)求者[3]，眾包平臺(tái)以及任務(wù)完成者。任務(wù)請(qǐng)求者需要通過(guò)眾包平臺(tái)來(lái)完成自己的任務(wù)，其工作流程為：

1）產(chǎn)生任務(wù)；

2）通過(guò)眾包平臺(tái)發(fā)布任務(wù)，等待任務(wù)的答案；

3）拒絕或接受任務(wù)完成者的答案；

4）整理任務(wù)完成者所返回的答案，完成自己的任務(wù)。

任務(wù)完成者的工作流程：

1）查找任務(wù)；

2）接受任務(wù)；

3）執(zhí)行任務(wù)；

4）提交答案。

其具體流程如圖1所示：

2.3眾包應(yīng)用于關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)

人類擅長(zhǎng)某些特定的任務(wù)（如圖像識(shí)別），但相對(duì)而言不擅長(zhǎng)其他的一些任務(wù)（如數(shù)值計(jì)算）。同樣，機(jī)器也有擅長(zhǎng)與不擅長(zhǎng)的工作。因此人和機(jī)器的能力可很好的相互補(bǔ)充。通過(guò)在傳統(tǒng)的關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中引入眾包，可以很好的應(yīng)答關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)無(wú)法應(yīng)答的查詢。

現(xiàn)有的微任務(wù)眾包平臺(tái)如亞馬遜的土耳其機(jī)器人（AMT）[4]可以使人們以一種隨需應(yīng)變的方式來(lái)訪問(wèn)眾包。這個(gè)平臺(tái)提供基礎(chǔ)設(shè)施，連通性和支付機(jī)制，允許成千上萬(wàn)的人在互聯(lián)網(wǎng)上進(jìn)行有償工作。它提供了一種請(qǐng)求和管理工作的應(yīng)用程序界面，其中任務(wù)請(qǐng)求者提供任務(wù)，工作者接受和執(zhí)行任務(wù)。在我們這個(gè)基于眾包的混合數(shù)據(jù)庫(kù)系統(tǒng)中，通過(guò)使用一小部分請(qǐng)求人機(jī)輸入的運(yùn)算符來(lái)擴(kuò)展傳統(tǒng)的查詢引擎，從而更好的使用這個(gè)平臺(tái)。

3基于眾包的數(shù)據(jù)庫(kù)信息查詢處理方法

在基于眾包的數(shù)據(jù)庫(kù)信息查詢處理系統(tǒng)中，我們采用人機(jī)結(jié)合的處理模式，并采用類SQL語(yǔ)句來(lái)進(jìn)行查詢處理。

3.1數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)框架

圖2 展示了基于眾包的數(shù)據(jù)庫(kù)系統(tǒng)的體系結(jié)構(gòu)的總體框架[5]。如果可能的情況下，會(huì)首先使用存儲(chǔ)在本地表格的數(shù)據(jù)去應(yīng)答查詢，否則會(huì)調(diào)用眾包。也即我們圖中的機(jī)器可自動(dòng)完成的傳統(tǒng)數(shù)據(jù)庫(kù)部分和需要人工輸入的人工部分。如果傳統(tǒng)機(jī)器數(shù)據(jù)庫(kù)部分可以正確應(yīng)答，則查詢返回結(jié)果；否則，使用人工部分來(lái)調(diào)用眾包，并且將通過(guò)眾包所獲得的數(shù)據(jù)存儲(chǔ)在數(shù)據(jù)庫(kù)中以便在未來(lái)的使用中無(wú)需重復(fù)操作。

如圖中中間的傳統(tǒng)數(shù)據(jù)庫(kù)部分所示，眾包數(shù)據(jù)庫(kù)合并了傳統(tǒng)數(shù)據(jù)庫(kù)的解析器、優(yōu)化器和執(zhí)行部件，這些部件被擴(kuò)展到處理人為的輸入。在圖中右半部分，是與眾包平臺(tái)相互作用的新部件。

工作關(guān)系管理器，在眾包的使用中涉及人類工作者，與計(jì)算機(jī)處理器不同，因此眾包工作者是不可代替的資源，并且任務(wù)請(qǐng)求者與任務(wù)工作者的關(guān)系會(huì)隨著時(shí)間而發(fā)生改變，所以應(yīng)注意培養(yǎng)和維持一個(gè)有效的工作池。工作關(guān)系管理器模塊協(xié)助請(qǐng)求者及時(shí)的支付工人工資、發(fā)放獎(jiǎng)金和報(bào)告并應(yīng)答一些工人的意見(jiàn)。從長(zhǎng)遠(yuǎn)來(lái)看，在改進(jìn)結(jié)果質(zhì)量，更好的反應(yīng)時(shí)間和更低的代價(jià)方面起到很重要的作用。

與物理IO請(qǐng)求相比，眾包的接口數(shù)據(jù)由自然語(yǔ)言的HTML表單和指令組成。CrowdDB用可獲得的數(shù)據(jù)庫(kù)模式信息生成HTML表單。這三個(gè)組件，UI設(shè)計(jì)，表格編輯器，UI模板管理器，負(fù)責(zé)創(chuàng)建、管理和編輯用戶界面模板。

任務(wù)管理器提供了一個(gè)抽象層，它管理混合數(shù)據(jù)庫(kù)與眾包平臺(tái)之間的交互。它實(shí)例化用戶界面，使應(yīng)用程序界面發(fā)布任務(wù)，評(píng)估他們的地位，并獲得結(jié)果。任務(wù)管理器也與存儲(chǔ)器進(jìn)行交互，獲取值預(yù)先加載到用戶界面，并最終存儲(chǔ)來(lái)自眾包的應(yīng)答結(jié)果。

3.2類SQL語(yǔ)句

在基于眾包的數(shù)據(jù)庫(kù)系統(tǒng)中，由于眾包的引入，在對(duì)數(shù)據(jù)庫(kù)進(jìn)行操作時(shí)， 我們采用SQL語(yǔ)言的一個(gè)小的擴(kuò)展即類SQL語(yǔ)句[6]。類SQL 語(yǔ)句與SQL語(yǔ)句的編寫(xiě)代碼以基本相同的方式。即在大多數(shù)情況下，開(kāi)發(fā)人員不需要知道他們的代碼涉及眾包。

對(duì)于傳統(tǒng)數(shù)據(jù)庫(kù)中數(shù)據(jù)不完整而導(dǎo)致查詢錯(cuò)誤的情況，有兩種處理方式。第一，元組的特定屬性可以被眾包。第二，整個(gè)元組可以被眾包。通過(guò)在SQL語(yǔ)言中添加關(guān)鍵字CROWD，即可完成這兩種情況的處理。

例1：眾包某一屬性：在本例中的院系表中，URL屬性被標(biāo)記為眾包。這種模型適合于新的院系自動(dòng)生成時(shí)，其中，URL常不提供但可在其他的地方獲得。

Create table Dept

University varchar（20）

Name varchar（20）

Url crowd varchar（20）

Phone varchar（11）

Primary key（university name）；

例2：眾包表：本例中模擬一個(gè)教師名單為一個(gè)眾包表。這個(gè)例子對(duì)于人們只希望代表性的獲得一個(gè)部分的教師的子集是適用的。即，如果要求處理特定的查詢，那么眾包數(shù)據(jù)庫(kù)需要通過(guò)眾包增加更多的教師。

Create crowd table teacher

Name varchar（20） primary key

Email varchar（11） unique

Dept varchar（20）

Foreign key （university，dept）

references dept（university，name）

為了表示眾包列中還沒(méi)有獲得的值，類SQL語(yǔ)言擴(kuò)展了SQL語(yǔ)言中的NULL為CNULL，它與NULL等價(jià)，用于表示當(dāng)?shù)谝淮问褂盟臅r(shí)候該值應(yīng)該被眾包。另外，刪除和更新語(yǔ)句在類SQL語(yǔ)句中沒(méi)有改變。而對(duì)于查詢語(yǔ)句，允許兩個(gè)眾包表格的連接和子查詢。

除了找到不完整的數(shù)據(jù)，在基于眾包的數(shù)據(jù)庫(kù)系統(tǒng)中，另一個(gè)主要的應(yīng)用是客觀的進(jìn)行比較。為了支持這種函數(shù)的功能，眾包數(shù)據(jù)庫(kù)新建了兩個(gè)函數(shù)Crowdequal和Crowdorder。Crowdequal有兩個(gè)參數(shù)（左值和右值），并訪問(wèn)Crowd去決定兩個(gè)值是否相等。正如語(yǔ)法所說(shuō)的，使用～=和一個(gè)插入表示法。正如在下列中顯示的：

例3：當(dāng)需要查詢關(guān)于“CS”的所有信息時(shí)，可形成包含“～=”符號(hào)的查詢，在數(shù)據(jù)庫(kù)中，查詢的編寫(xiě)者用可能的計(jì)算機(jī)科學(xué)的名稱去請(qǐng)眾包平臺(tái)來(lái)進(jìn)行解析。

Select * from SS

Where name ～=”CS”；

當(dāng)排序或整理結(jié)果需要眾包時(shí)，會(huì)用到Crowdorder。如以下例子：

例4：當(dāng)需要查詢最具實(shí)踐性的5個(gè)想法時(shí)，可通過(guò)Crowdorder來(lái)實(shí)現(xiàn)。

Create table idea（

Idea varchar（20），

Subject varchar（20）；

Select Idea from paper

Order by crowdorder（idea，which idea has the better practical）

LIMIT 5；

當(dāng)完成這些查詢時(shí)，其結(jié)果將會(huì)被存儲(chǔ)在數(shù)據(jù)庫(kù)中，以便眾包被相同的查詢只訪問(wèn)一次，從而提高系統(tǒng)的效率。

4 結(jié)束語(yǔ)

本文中，數(shù)據(jù)庫(kù)和新興的眾包技術(shù)是我們研究的重要領(lǐng)域?；诒姲臄?shù)據(jù)庫(kù)信息查詢處理方法的提出，很好地解決了傳統(tǒng)數(shù)據(jù)庫(kù)系統(tǒng)中無(wú)法應(yīng)答的查詢請(qǐng)求，有效的擴(kuò)展了數(shù)據(jù)庫(kù)系統(tǒng)的信息處理能力。人機(jī)結(jié)合來(lái)處理問(wèn)題是未來(lái)應(yīng)該關(guān)注的重要發(fā)展方向，具有很好的應(yīng)用前景。

參考文獻(xiàn)：

[1] Franklin M， Kossmann D，Kraska T， et al.CrowdDB： Answering Queries with Crowdsourcing[C]. In SIGMOD， 2011： 61-72.

[2] HOWEJ.The rise of crowdsourcing[J].Wired Magazing，2006，14（6）：176-183.

[3] 馮劍紅，李國(guó)良，馮建華.眾包技術(shù)研究綜述[J].計(jì)算機(jī)學(xué)報(bào)，2014，37（106）：1-16.

[4] Feng M， Franklin D， Kossmann T， et al. Crowd DB： Query Processing with the VLDB Crowd[C]. Proceeding of the VLDB Endowment，2011，12（4）.

[5] Trushkowsky B，Kraska T，F(xiàn)ranklin M J.A Framework for Adaptive Crowd Query Processing[C]. AAAI，2013.

[6] 王珊，薩師煊.數(shù)據(jù)庫(kù)系統(tǒng)概論[M].4版.北京：高等教育出版社，2006.