查詢結(jié)果可用性研究綜述

柳 晴 高云君,2

1(浙江大學計算機科學與技術(shù)學院 杭州 310027)2(浙江省大數(shù)據(jù)智能計算重點實驗室(浙江大學) 杭州 310027)

查詢結(jié)果可用性研究綜述

柳 晴1高云君1,2

1(浙江大學計算機科學與技術(shù)學院 杭州 310027)2(浙江省大數(shù)據(jù)智能計算重點實驗室(浙江大學) 杭州 310027)

(liuq@zju.edu.cn)

數(shù)據(jù)庫可用性研究在數(shù)據(jù)庫領(lǐng)域受到了廣泛的關(guān)注.其目標在于幫助用戶更加高效、方便地使用數(shù)據(jù)庫，從而提高用戶對數(shù)據(jù)庫的滿意度.主要關(guān)注查詢結(jié)果可用性研究.當前的數(shù)據(jù)庫查詢僅僅向用戶返回查詢結(jié)果.如果查詢結(jié)果不是用戶想要的，現(xiàn)有的數(shù)據(jù)庫系統(tǒng)既不能向用戶解釋為什么會得到這樣的結(jié)果，也無法給出有效的建議以幫助用戶得到滿意的查詢結(jié)果.查詢結(jié)果可用性研究正是針對當前數(shù)據(jù)庫系統(tǒng)的這一不足而展開.在數(shù)據(jù)庫可用性的視角之上，以查詢結(jié)果為中心，對當前查詢結(jié)果可用性工作的最新動態(tài)進行了綜述.梳理了當前查詢結(jié)果可用性相關(guān)研究中問題的類型及其特點，并從Causality & Responsibility問題、Why-not & Why問題、Why-few & Why-many問題這3個方面對該領(lǐng)域的研究工作現(xiàn)狀進行了分類、介紹和總結(jié).最后對該研究領(lǐng)域未來可能的研究方向進行了展望，為相關(guān)研究提供參考.

數(shù)據(jù)庫可用性；why-not問題；why問題；causality與responsibility；why-few問題；why-many問題

隨著信息技術(shù)的不斷發(fā)展，近幾十年來數(shù)據(jù)庫性能(capability)得到了大幅度的提升，例如：數(shù)據(jù)庫所能支持的查詢類型越來越豐富，如多媒體查詢、關(guān)鍵字查詢、基于路網(wǎng)查詢等；數(shù)據(jù)庫所能處理的數(shù)據(jù)量越來越大，能夠支持TB甚至更高的數(shù)據(jù)量.盡管如此，但用戶有時候還是覺得數(shù)據(jù)庫難以使用.究其原因，一方面是數(shù)據(jù)庫的性能還有待進一步提高(特別是處理大數(shù)據(jù)的能力)，另一方面是數(shù)據(jù)庫的可用性(usability)還沒有滿足用戶的需求.

通常，可用性指的是用戶是否能很好地使用系統(tǒng)的功能.ISO 9241-11國際標準對可用性作了如下定義：產(chǎn)品在特定使用環(huán)境下為特定用戶用于特定用途時所具有的有效性、效率和用戶主觀滿意度[1].其中有效性指用戶完成特定任務和達到特定目標時所具有的正確和完整程度;效率指用戶完成任務的正確和完整程度與所使用資源(如時間)之間的比率;主觀滿意度指用戶在使用產(chǎn)品過程中所感受到的主觀滿意和接受程度.

文獻[1]中可用性的定義是一個廣義上的概念.在IT領(lǐng)域內(nèi)可用性定義的對象包括計算機軟硬件.數(shù)據(jù)庫作為計算機領(lǐng)域必不可少的一部分，其可用性問題也受到了廣泛的關(guān)注.根據(jù)ISO 9241-11的定義，可以對數(shù)據(jù)庫可用性作如下定義：數(shù)據(jù)庫可用性是指數(shù)據(jù)庫為用戶提供數(shù)據(jù)管理等功能時所具有的有效性、效率和用戶主觀滿意度.通俗地講，數(shù)據(jù)庫可用性指的是數(shù)據(jù)庫對用戶來說有效、易學、高效和令人滿意的程度，即用戶能否用數(shù)據(jù)庫完成他的任務、效率如何、主觀感受怎樣.實際上這是從用戶角度所看到的數(shù)據(jù)庫質(zhì)量.這表明數(shù)據(jù)庫可用性是以用戶為中心的，更是直接決定了數(shù)據(jù)庫的好壞.由于數(shù)據(jù)庫可用性有著如此重要的作用，近年來受到了專家學者的廣泛關(guān)注.ACM Fellow、密西根大學的Jagadish教授指出：“當前的數(shù)據(jù)庫仍不完美，可用性是完善數(shù)據(jù)庫的關(guān)鍵點之一[2]”.另外，數(shù)據(jù)庫領(lǐng)域三大頂級國際學術(shù)會議：數(shù)據(jù)管理國際會議(ACM SIGMOD)、超大型數(shù)據(jù)庫會議(VLDB)、數(shù)據(jù)工程國際會議(ICDE)，都關(guān)注了數(shù)據(jù)庫可用性.譬如從2016年開始，SIGMOD會議將數(shù)據(jù)庫可用性作為其主題之一.

數(shù)據(jù)庫可用性貫穿數(shù)據(jù)庫生命周期的各個階段，其研究內(nèi)容包括查詢構(gòu)造、即時查詢、查詢結(jié)果可用性等[2-3].例如：1)通常用戶必須掌握查詢語言才能寫查詢語句.然而，對于非專業(yè)人員就很難寫出正確、完整的查詢語句，因而無法進行查詢.為了解決這個問題，查詢構(gòu)造研究旨在能夠使用戶無需掌握查詢語言也能進行查詢.2)當前的查詢往往需要提交完整的查詢語句，等它全部執(zhí)行完畢后才能得到查詢結(jié)果，即“所見非所得”模式.但用戶往往希望在寫查詢語句時，即使沒有寫完全部的語句，也能看到當前語句的查詢結(jié)果，即“所見即所得”模式.針對這種問題，即時查詢結(jié)果研究旨在及時幫助用戶了解查詢結(jié)果.3)由于查詢的參數(shù)設(shè)置不當或者對數(shù)據(jù)集不了解，有時候查詢所得到的結(jié)果并不是用戶想要的.在這種情況下，查詢結(jié)果可用性研究旨在幫助用戶得到想要的查詢結(jié)果.

數(shù)據(jù)庫可用性研究涵蓋眾多方面，本文將綜述視角放在查詢結(jié)果可用性研究，內(nèi)容緊密圍繞查詢結(jié)果可用性所涉及的3個問題，即Causality & Responsibility問題、Why-not & Why問題、Why-few & Why-many問題.對于數(shù)據(jù)庫可用性其他方面的相關(guān)研究工作，由于篇幅問題，本文不作涉及.下面首先介紹查詢結(jié)果可用性研究所涉及的3個問題；再針對每個問題討論分析最新的研究進展；接著介紹相關(guān)的查詢結(jié)果可用性分析系統(tǒng)；最后在綜合分析現(xiàn)有工作的基礎(chǔ)上展望未來研究工作.

1 查詢結(jié)果可用性問題描述

從系統(tǒng)來看，數(shù)據(jù)庫的底層是各種數(shù)據(jù)源，如地理空間數(shù)據(jù)、社交數(shù)據(jù)、多媒體數(shù)據(jù)等；數(shù)據(jù)層上面是查詢層，用戶可以根據(jù)不同的需求進行各種查詢，如偏好查詢、SQL查詢等；查詢層再往上則是查詢結(jié)果分析層，這一層根據(jù)查詢返回的結(jié)果并結(jié)合用戶的反饋意見進行相應分析；最上層是各種實際應用.圖1給出了數(shù)據(jù)庫工作基本框架.由圖1可知，查詢結(jié)果可用性研究屬于查詢結(jié)果分析層.具體來說，查詢結(jié)果可用性研究的研究對象是預料之外的查詢結(jié)果(unexpected query results).當查詢返回相應的查詢結(jié)果時，如果當前的結(jié)果跟用戶預先期望的結(jié)果有所出入(即預料之外)，那么就需要對現(xiàn)有的結(jié)果進行相關(guān)分析.根據(jù)對預料之外的查詢結(jié)果的分類，查詢結(jié)果可用性研究可以分為3類問題，即Causality & Responsibility問題、Why-not & Why問題以及Why-few & Why-many問題.下面作具體介紹.

Fig. 1 The basic framework of database圖1 數(shù)據(jù)庫工作基本框架

Fig. 2 The analysis of usability problems for unexpected query results圖2 對預料之外的查詢結(jié)果可用性問題分析

如圖2所示，查詢結(jié)果可用性研究所針對的預料之外的查詢結(jié)果主要可以分為2類：1)基于內(nèi)容的預料之外的查詢結(jié)果(content-based unexpected query results);2)基于數(shù)量的預料之外的查詢結(jié)果(cardinality-based unexpected query results).基于內(nèi)容的預料之外的查詢結(jié)果是指用戶想要的對象沒有出現(xiàn)在查詢結(jié)果中，或者不想要的對象出現(xiàn)在查詢結(jié)果中.針對這種情況，首先，用戶可能想要知道導致現(xiàn)有查詢結(jié)果產(chǎn)生的原因以及它們相應的責任大小，從而能更好地理解原有的查詢.那么，這所對應的就是查詢結(jié)果可用性研究的第1類問題，即Causality & Responsibility問題研究.其次，除了相應的解釋外，用戶還可能會讓想要的對象出現(xiàn)在查詢結(jié)果中或者讓不想要的對象不出現(xiàn)在查詢結(jié)果中，從而得到滿意的查詢結(jié)果.查詢結(jié)果可用性研究的第2類問題，即Why-not & Why問題，正是幫助用戶得到他們滿意的查詢結(jié)果.

基于數(shù)量的預料之外的查詢結(jié)果是指用戶得到的答案對象個數(shù)太少(甚至為空集)或者答案對象個數(shù)太多.為此，用戶可能想要讓查詢返回的答案對象個數(shù)滿足用戶指定的要求(既不能太少又不能過多).這就是查詢結(jié)果可用性研究的第3類問題，即Why-few & Why-many問題，旨在減少或增加查詢結(jié)果中的答案對象個數(shù).下面具體結(jié)合反Top-k查詢來進一步說明這3類問題.

Fig. 3 Example of reverse Top-k queries圖3 反Top-k查詢示例

給定一個數(shù)據(jù)集P、一個向量集W、一個參數(shù)k和一個查詢點q，反Top-k查詢從向量集W中返回其Top-k結(jié)果包含查詢點q的所有向量.如圖3所示，圖3(a)為數(shù)據(jù)集P={p1,p2,p3,p4,p5}和3個查詢點{q1,q2,q3}；圖3(b)為向量集W={w1,w2,w3,w4,w5}；圖3(c)為數(shù)據(jù)集P中所有數(shù)據(jù)點在不同向量下的得分值(假設(shè)值越小越好).如果用戶以q1為查詢點進行反Top-3查詢，根據(jù)圖3(c)可以得到q1的反Top-3查詢結(jié)果(記作RTOP3(q1))為RTOP3(q1)={w3,w4,w5}.假設(shè)向量w1是用戶期望的查詢結(jié)果之一，但它卻沒有出現(xiàn)在查詢結(jié)果中.這時，用戶可能想知道是什么原因?qū)е铝讼蛄縲1沒有出現(xiàn)在查詢結(jié)果中，這就可以通過Causality & Responsibility問題進行分析.此外，如果用戶想要讓向量w1成為反Top-3查詢結(jié)果，那么Why-not問題分析就可以給出合理的建議.同樣，假設(shè)查詢結(jié)果中向量w4是用戶不想要的，但它卻返回給了用戶.這時，用戶可以通過Causality & Responsibility問題分析向量w4成為結(jié)果的原因，并通過Why問題尋求合理的建議以使得向量w4排除在反Top-3查詢結(jié)果中.

另外，假設(shè)用戶以q2和q3為查詢點進行反Top-3查詢，根據(jù)圖3(c)可以得到q2和q3的反Top-3查詢結(jié)果分別為RTOP3(q2)={w1,w2,w3,w4,w5}，RTOP3(q3)=?.可以看到，q2的反Top-3查詢結(jié)果等于整個向量集，這結(jié)果對于用戶來說太多；而q3的反Top-3查詢結(jié)果等于空集，這個結(jié)果對于用戶來說又太少.這2種情況都不能為用戶提供足夠有效的信息以幫助用戶作決策支持.這時，用戶可以指定期望的答案對象個數(shù)(如大于等于2且小于等于4)，并利用Why-few(對于q2)和Why-many(對于q3)問題分析以使得查詢返回用戶想要的查詢結(jié)果對象個數(shù).

針對上述描述的預料之外的查詢結(jié)果，如果數(shù)據(jù)庫系統(tǒng)能夠向用戶提供相應的解釋和建議來幫助用戶得到滿意的查詢結(jié)果，這能夠使用戶免于通過人工方式尋求答案從而幫他們節(jié)省大量的時間.這樣就能讓用戶更加方便而有效地使用數(shù)據(jù)庫，提高用戶使用數(shù)據(jù)庫的滿意度，進而提高數(shù)據(jù)庫的可用性.下面分別介紹查詢結(jié)果可用性分析的3類問題.

2 Causality & Responsibility問題研究現(xiàn)狀

2.1 問題定義

當查詢結(jié)果中包含了用戶不想要的對象或者用戶想要的對象沒有出現(xiàn)在查詢結(jié)果中，如果用戶想知道是哪些原因?qū)е铝爽F(xiàn)有的查詢結(jié)果，這些原因的影響有多大，便可以利用Causality和Responsibility問題來分析.

Causality研究源于哲學領(lǐng)域，具有很長的研究歷史[4-5].直到如今，其在哲學(philosophy)、人工智能(AI)、認知科學(cognitive science)等領(lǐng)域仍被廣泛地研究.Halpern和Pearl[6]首次形式化定義了Causality的概念，它能夠?qū)σ恍┚哂幸蚬?lián)系的事物進行精確的建模.Chockler和Halpern[7]對Causality的概念進行了進一步擴展并提出了Responsibility來量化Causality的作用，從而對Causality提供了更深層次的分析.從此Causality與Responsibility在包括計算機領(lǐng)域在內(nèi)的各個領(lǐng)域得到了廣泛的研究.

Meliou等人首次將Causality與Responsibility的概念引入到數(shù)據(jù)庫領(lǐng)域.在文獻[8]中，Meliou等人針對輸入數(shù)據(jù)定義了查詢結(jié)果的Causality.具體地說，如果一個輸入數(shù)據(jù)p的存在與否會導致查詢結(jié)果的改變，那么輸入數(shù)據(jù)p就是查詢結(jié)果的一個原因(cause).Responsibility的大小則根據(jù)p所對應的集合(contingency set)進行計算.接著，在文獻[9]中，Meliou等人結(jié)合Halpern和Pearl的工作對Causality定義進行了進一步細化.下面的定義1和定義2給出了文獻[9]中Causality與Responsibility的形式化定義以便更好地理解這一問題.

定義2. 假設(shè)p′是p的Causality，Γ是p′所對應的Contingency set，那么p′對于p的Responsibility，記作ρ(p′,p)，可計算得到[9]：

(1)

2.2 研究現(xiàn)狀

自從Causality與Responsibility被引入數(shù)據(jù)庫領(lǐng)域，便引起了眾多研究者的關(guān)注.Meliou等人還在數(shù)據(jù)庫領(lǐng)域頂級國際學術(shù)會議VLDB 2014上舉行了Causality與Responsibility相關(guān)的Tutorial對其進行了系統(tǒng)地介紹[10].下面對數(shù)據(jù)庫領(lǐng)域中的Causality與Responsibility問題研究進展進行全面地介紹.圖4總結(jié)了近年來所發(fā)表的Causality與Responsibility研究論文數(shù)量.

Fig. 4 The statistics of studies on Causality & Responsibility圖4 Causality & Responsibility研究工作統(tǒng)計

文獻[11]首次探討了帶有等式的連接查詢(conjunctive queries with equalities)上的Causality與Responsibility.作者研究了2種情況的Causality與Responsibility，即“Why so”和“Why no”.其中“Why so”是對查詢結(jié)果研究它們的Causality與Responsibility，“Why no”則是對非查詢結(jié)果研究它們的Causality與Responsibility.此外，作者還分析了針對連接查詢計算Causality與Responsibility的復雜度.針對帶有不等式的連接查詢(conjunctive queries with inequalities)的溯源信息(即Causality)，文獻[12]研究了如何計算其Responsibility的大小.為了減少計算Responsibility的代價，文獻[12]首先將溯源信息轉(zhuǎn)換成相應的矩陣，從而將Responsibility的計算轉(zhuǎn)換成最短路徑問題并通過動態(tài)規(guī)劃算法來解決.文獻[13]研究了概率反Skyline查詢上的Causality與Responsibility問題.給定一個對象p(p不是概率反Skyline查詢結(jié)果)，文獻[13]從概率數(shù)據(jù)集中找到導致p成為非概率反Skyline查詢結(jié)果的數(shù)據(jù)(即p的Causality)，并計算它們的Responsibility大小.為了找到p的所有Causality，文獻[13]提出了基于過濾-精煉框架的CP算法.值得一提的是，文獻[13]同時考慮了離散和連續(xù)2種概率模型，并擴展了CP算法以處理反Skyline查詢上的Causality與Responsibility問題.在社交網(wǎng)絡中，2個對象之間的信息傳播(diffusion)可能存在著多條路徑.文獻[14]利用Causality與Responsibility對所有的歷史傳播路徑進行排序，以方便用戶了解自己在信息傳播過程中所處的位置以及重要性(即如果把自己從社交網(wǎng)絡中刪除，2個對象之間的信息傳播是否還能順利進行).

上述工作都是針對傳統(tǒng)的Causality與Responsibility定義進行研究.此外，一些研究者根據(jù)具體的應用和查詢對傳統(tǒng)的Causality與Responsibility定義進行相應的擴展.例如，傳統(tǒng)的Causality與Responsibility僅僅判斷一個數(shù)據(jù)對象是否是查詢結(jié)果的Causality.文獻[15]則判斷多個數(shù)據(jù)對象是否是查詢結(jié)果的Causality，并提出了P樹來有效地計算Responsibility大小.在數(shù)據(jù)轉(zhuǎn)換應用中，結(jié)合數(shù)據(jù)轉(zhuǎn)換后的錯誤信息，文獻[16]提出了View-Conditioned Causality以及相應的Responsibility以定位源數(shù)據(jù)集中的錯誤.為了有效地找出View-Conditioned Causality并計算相應的Responsibility，文獻[16]將View-Conditioned Causality查找和Responsibility計算分別轉(zhuǎn)換成可滿足性問題(SAT problem)和最大可滿足性問題(MAX-SAT problem)，而這2個問題目前都有有效的算法來解決.Lian和Chen首次將Causality與Responsibility引入了基于離散概率模型的概率數(shù)據(jù)庫.在原來的Causality與Responsibility定義的基礎(chǔ)上，根據(jù)概率數(shù)據(jù)庫特性，文獻[17]提出了預期的Responsibility的概念.具體而言，在離散概率模型下，概率數(shù)據(jù)庫可以看成是一系列可能世界(possible world)的集合.假設(shè)p1是p2的Causality，可以利用原有的Responsibility定義來計算每個可能世界下p1對p2的Responsibility大小.預期的Responsibility則是對所有可能世界中p1對p2的Responsibility大小的累加之和.在文獻[17]中，預期的Responsibility被用來協(xié)助概率最近鄰查詢處理并同時鑒別出數(shù)據(jù)集中的低質(zhì)量或者可能有誤的概率數(shù)據(jù).

3 Why-not & Why問題研究現(xiàn)狀

3.1 Why-not & Why問題定義

現(xiàn)有的查詢僅僅返回查詢結(jié)果，如果查詢結(jié)果包含了用戶不想要的結(jié)果或者用戶想要的結(jié)果沒有出現(xiàn)，卻不能提供一些建議以幫助用戶得到其想要的查詢結(jié)果.Why-not與Why問題研究正是針對數(shù)據(jù)庫中這一不足展開.下面，定義3和定義4分別給出了Why-not問題和Why問題的定義.

定義3. 給定一個原始查詢Q和一個Why-not集合W1(W1不是Q的查詢結(jié)果)，Why-not問題研究如何使W1成為Q的查詢結(jié)果.

定義4. 給定一個原始查詢Q和一個Why集合W2(W2是Q的查詢結(jié)果)，Why問題研究如何使W2不成為Q的查詢結(jié)果.

Fig. 5 The statistics of studies on Why-not and Why questions圖5 Why-not問題和Why問題研究工作統(tǒng)計

簡而言之，Why-not問題就是幫助用戶把想要但是沒出現(xiàn)在查詢結(jié)果中的對象包含在查詢結(jié)果中；Why問題就是幫助用戶把不想要但是卻出現(xiàn)在查詢結(jié)果中的對象排除.當前，Why-not問題和Why問題研究工作可以分為3類：1)單獨研究Why-not問題；2)單獨研究Why問題；3)同時研究Why-not問題和Why問題，即既把用戶想要但是沒出現(xiàn)在查詢結(jié)果中的對象包含在查詢結(jié)果中，又把用戶不想要但是卻出現(xiàn)在查詢結(jié)果中的對象排除.圖5中左邊的餅圖所示的就是目前這3類工作所占的比例.由圖5可知，Why-not問題相關(guān)的工作占了絕大多數(shù)，另外2類的相關(guān)研究較少.下面一一介紹這3類工作的研究現(xiàn)狀，首先介紹Why-not問題的研究現(xiàn)狀.

3.2 Why-not問題研究現(xiàn)狀

為了有效地回答Why-not問題，研究者們提出了多種不同的策略，包括操作定位(manipulation identification)、數(shù)據(jù)修改(database modification)、查詢修改(query refinement)、基于本體論(ontology)的方法以及混合方法等.圖5中右邊的餅圖顯示了各種策略在當前研究工作中所占的比例.另外，表1總結(jié)了Why-not問題的研究工作并根據(jù)其所采用的策略對它們進行了分類.

如果用戶想要的對象(即Why-not對象)沒有包含在當前的查詢結(jié)果中，一種最直接的方法就是找到導致Why-not對象成為非查詢結(jié)果的操作，即操作定位法.文獻[18]首次提出用操作定位策略來回答SPJU(select-project-join-union)查詢上的Why-not問題.文獻[18]先利用數(shù)據(jù)溯源相關(guān)技術(shù)找到與Why-not對象相關(guān)的數(shù)據(jù)，而后從查詢中定位是哪些操作把這些相關(guān)的數(shù)據(jù)排除在查詢結(jié)果中.然而，文獻[18]所返回的操作定位存在著錯誤.文獻[19]重新定義了基于操作定位的解釋并給出了更高效的算法，從而大大降低了操作定位的錯誤率.以上2項工作都是利用查詢樹(query tree)產(chǎn)生相應的操作定位解釋.這就導致了得到的解釋依賴于給定查詢樹的拓撲結(jié)構(gòu).換句話說，對于同一個查詢語句，如果給定的查詢樹不一樣，返回的查詢解釋也不一樣.更糟糕的是，根據(jù)查詢樹計算得到的查詢解釋甚至可能是不完整的.為此，文獻[20]提出了以多項式(polynomial)的形式返回操作定位解釋并給出了最基本的算法Ted.基于多項式的操作定位解釋不僅獨立于查詢樹，而且能夠保證解釋的完整性.但文獻[20]所提出算法Ted的計算代價相當大.為此，文獻[21]利用空間劃分、并行計算等技術(shù)提出了一個更有效的算法Ted++.

另外，文獻[22]提出了基于本體論的解釋方法，它們所針對的查詢是連接查詢(conjunctive queries).根據(jù)所針對的本體類型的不同，又可將所產(chǎn)生的解釋分為基于內(nèi)本體的解釋方法和基于外本體的解釋方法.

Table 1 The Summary of Studies on Why-not Questions表1 現(xiàn)有Why-not問題工作總結(jié)

Notes:“√” means yes; “×” means no.

操作定位和基于本體論的解釋僅僅將導致Why-not對象成為非查詢結(jié)果的操作或數(shù)據(jù)找出來.但這往往還無法使Why-not對象成為查詢結(jié)果.于是，一些研究者提出了通過修改數(shù)據(jù)使得Why-not對象成為查詢結(jié)果.文獻[23]通過插入新的數(shù)據(jù)或修改現(xiàn)有的數(shù)據(jù)來使Why-not對象成為查詢結(jié)果.該工作所針對的查詢是SPJ(select-project-join)查詢，并且只考慮一個Why-not對象.文獻[24]針對SPJAU(select-project-join-aggregation-union)查詢和多個Why-not對象研究了Why-not問題.但是，文獻[23-24]返回的數(shù)據(jù)修改建議都存在著一些不足之處，如返回的修改建議中包含不正確、不合理的修改建議，或者返回的修改建議太多使得用戶無法選擇.為此，文獻[25]提出了新的技術(shù)來提高數(shù)據(jù)修改建議的正確性并降低返回修改的個數(shù).盡管文獻[25]返回結(jié)果的正確性提高了且數(shù)量也減少了，但它所針對的查詢僅僅是等值連接查詢(equi-join queries).當查詢中帶有關(guān)系復制語句(relation copy)或循環(huán)語句時(query cycle)，返回的結(jié)果還是不正確的.因此，文獻[26]探討了帶有關(guān)系復制語句或循環(huán)語句的等值連接查詢上的Why-not問題，使得返回的數(shù)據(jù)修改建議不僅正確且盡可能少.值得注意的是，文獻[23-26]均將數(shù)據(jù)分為可信數(shù)據(jù)(trusted data)和非可信數(shù)據(jù)(untrusted data).數(shù)據(jù)修改操作只針對非可信數(shù)據(jù)，而對于可信數(shù)據(jù)則不允許修改.

很明顯，如果數(shù)據(jù)庫的數(shù)據(jù)允許被任意修改的話，數(shù)據(jù)修改這一策略是比較靈活有效的.然而，在實際應用中，用戶一般很難直接接觸到數(shù)據(jù)庫中的數(shù)據(jù)，更不用說修改數(shù)據(jù)了.此外，數(shù)據(jù)庫中的數(shù)據(jù)通常是固定的，都不允許直接修改的.鑒于此，數(shù)據(jù)修改的方法在很多應用中無法使用.所以，研究者提出了一種更加可行的策略，即修改原始查詢.文獻[27]首次通過修改原始查詢來回答Why-not問題.它所針對的查詢是SPJA(select-project-join-aggregation)查詢.文獻[27]提出了2種標準來衡量修改查詢的好壞:第1個標準是相似性(similarity)，即和原查詢相比，修改查詢對于選擇謂詞的修改越少則與原查詢越相似;第2個標準是精確性(precision)，即除原有的查詢結(jié)果和Why-not對象外，修改查詢結(jié)果所包含的其他對象越少則越精確.隨后的工作也基本采用了這2個標準來判斷修改查詢的好壞.

文獻[28,35]研究了Top-k查詢(Top-kqueries)上的Why-not問題.該工作通過同時修改Top-k查詢的輸入?yún)?shù)k和向量w使得Why-not對象成為Top-k查詢結(jié)果.文獻[28,35]在判斷修改查詢的好壞時，僅僅使用了相似性.文獻[33]擴展了文獻[28]中的工作，研究了Top-kSQL查詢(即基于SQL的Top-k查詢)上的Why-not問題.其所提出的方案包括同時修改SQL語句(如修改、增加Where語句中的選擇謂詞，增加、減少Where語句中的聯(lián)接謂詞，增加、減少From語句中的關(guān)系等)和修改Top-k查詢所涉及的參數(shù)(包括參數(shù)k和向量w).同樣，文獻[33]采用了相似性和精確性2個標準來衡量修改后的Top-kSQL查詢并最終返回相似性和精確性最優(yōu)的修改查詢.值得注意的是，文獻[33]最終有可能無法得到相應的修改查詢以使得查詢結(jié)果包含所有的Why-not對象.

另外，一些研究者利用查詢修改策略探討了圖像查詢和關(guān)鍵字查詢上的Why-not問題.文獻[29]研究了社交圖像查詢(social image search)上的Why-not問題.給定一組查詢標簽(query tag)，社交圖像查詢返回與標簽最匹配的圖片.對于用戶在返回的結(jié)果里面沒有看到自己想要的圖片，文獻[29]提出了3種模型來修改查詢:1)對原查詢結(jié)果進行重排序.該模型針對的情況是用戶想要的圖片已經(jīng)在返回的結(jié)果中，但是它們的排序很靠后.這樣，只要對返回的圖片進行重排序便能讓用戶盡早看到想要的圖片.2)對某些查詢標簽進行刪除，這些被刪除的標簽都導致用戶想要的圖片沒有出現(xiàn).3)用1組新的標簽來替代原有的查詢標簽從而使得用戶想要的圖片出現(xiàn).其中模型2和模型3所針對的情況是用戶想要的圖片并沒有返回給用戶.文獻[30]探討了相似圖查詢(similar graph queries)上的Why-not問題.給定一個查詢圖，相似圖查詢返回與查詢圖(query graph)最相似的圖.針對用戶想要的圖沒有出現(xiàn)在查詢結(jié)果中，文獻[30]通過對查詢圖進行修改以使得用戶想要的圖出現(xiàn)在查詢結(jié)果中.其中，查詢圖的修改只限于對圖中的邊進行增加或刪除，而對頂點則不作任何修改.

文獻[31-32]研究了空間關(guān)鍵字Top-k查詢(spatial keyword Top-kqueries)上的Why-not問題.空間關(guān)鍵字Top-k查詢同時考慮了查詢對象的空間位置信息和關(guān)鍵字信息，根據(jù)與查詢點的空間位置距離和文本相似性來計算每個數(shù)據(jù)對象的得分，最終返回得分最小的k個數(shù)據(jù)對象.針對空間關(guān)鍵字Top-k查詢的特點，文獻[31]對空間關(guān)鍵字Top-k查詢中的得分計算函數(shù)進行修改，使Why-not對象的得分變小從而達到讓它們成為查詢結(jié)果的目的.但該文作者認為，與關(guān)鍵字信息相比，這種方法并不能很好地反映用戶真正的偏好.因此，在文獻[32]中，作者對空間關(guān)鍵字Top-k查詢的輸入關(guān)鍵字信息進行修改(如增加或減少輸入的關(guān)鍵字信息)，從而使得Why-not對象出現(xiàn)在查詢結(jié)果中.值得注意的是，文獻[31-32]中用來衡量修改查詢好壞的標準僅僅考慮了原查詢與修改查詢的相似性，并沒有考慮精確性.此外，文獻[31-32]所得到的修改查詢不僅可能會丟失原有的查詢結(jié)果，還可能會包含其他新的查詢結(jié)果.

以上工作均采用了一種策略來回答Why-not問題.另外，一些研究者結(jié)合了上述3種已有的策略來回答Why-not問題.文獻[34-37]針對反Skyline查詢(reverse skyline queries)、Top-k支配查詢(Top-kdominating queries)、反Top-k查詢(reverse top-kqueries)查詢、概率度量區(qū)域查詢(metric probabilistic range queries)分別研究了Why-not問題,它們均采用了數(shù)據(jù)修改和查詢修改2種策略來回答Why-not問題.通過2種策略的不同組合，文獻[34,36]均提出了3類方案來回答Why-not問題：1)通過單獨修改數(shù)據(jù)來回答Why-not問題.如文獻[34,36]都通過修改Why-not對象使得修改后的Why-not對象出現(xiàn)在查詢結(jié)果中.2)通過單獨修改查詢(即修改查詢所涉及的參數(shù))來回答Why-not問題.如針對反Skyline查詢的Why-not問題，文獻[34]修改的是查詢點q；針對概率度量區(qū)域查詢的Why-not問題，文獻[36]同時修改查詢點q、查詢半徑r和概率閾值θ這3個參數(shù).3)對上述2種方案的集成，即同時修改Why-not對象和查詢所涉及的參數(shù)，以回答Why-not問題.文獻[35]僅給出了方案3來回答Top-k支配查詢上的Why-not問題，即同時修改Why-not對象和Top-k支配查詢參數(shù)k.結(jié)合反Top-k查詢上Why-not問題的實際應用，文獻[37]僅提出了方案1(即修改查詢點q)和方案3(即修改參數(shù)k和Why-not對象，或修改查詢點q、參數(shù)k和Why-not對象)，并沒有單獨修改數(shù)據(jù).值得一提的是，文獻[34-37]中數(shù)據(jù)修改這一策略僅僅限制于對Why-not對象的修改，其他數(shù)據(jù)對象則不允許被修改.

另外，文獻[38-39]集成了操作定位、數(shù)據(jù)修改、以及查詢修改3種策略來回答SPJA查詢上的Why-not問題.然而，文獻[38-39]所考慮的場景是：1)數(shù)據(jù)不完整；2)原查詢中存在錯誤.該場景在實際應用中不是很常見，從而限制了文獻[38-39]所提出算法的應用范圍.

3.3 Why問題研究現(xiàn)狀

本節(jié)介紹現(xiàn)有的Why問題研究工作.目前，Why問題研究工作還很少.文獻[40]研究了在信息提取(extraction)過程中，根據(jù)用戶反饋的提取錯誤信息(即用戶不想要的信息)對提取規(guī)則進行修改，從而使這些錯誤的信息不再被提取.對提取規(guī)則進行修改的時候，文獻[40]保證了用戶所反饋的正確信息不丟失.另外，文獻[41]探討了反Top-k查詢上的Why問題.該文作者結(jié)合了數(shù)據(jù)修改和查詢修改2種策略來回答Why問題.在回答Why問題時，文獻[41]首先盡可能地保證原有的查詢結(jié)果不丟失.如果保證原有查詢結(jié)果不丟失的解決方案不存在，那么就僅僅考慮如何使用戶不想要的對象排除在查詢結(jié)果外.同樣，文獻[41]利用了相似性來衡量修改查詢的好壞，最終返回相似性最好的修改查詢.

雖然當前的Why問題研究工作較少，但是現(xiàn)有的數(shù)據(jù)溯源(data provenance,data lineage)技術(shù)可以用來幫助解決某些查詢(如SQL查詢)上的Why問題.數(shù)據(jù)溯源是根據(jù)追蹤路徑重現(xiàn)數(shù)據(jù)的歷史狀態(tài)和演變過程，以實現(xiàn)數(shù)據(jù)歷史檔案的追溯[42].其方法主要有標注法[43-44]和非標注法[45-46].給定Why對象(即用戶不想要的查詢結(jié)果對象)，首先可以利用數(shù)據(jù)溯源技術(shù)計算出Why對象是如何產(chǎn)生的;再對導致Why對象產(chǎn)生的數(shù)據(jù)或操作進行相應的修改，便可使Why對象排除在查詢結(jié)果外.當然，這其中還涉及一些其他問題，譬如:如何根據(jù)數(shù)據(jù)溯源得到的結(jié)果來修改數(shù)據(jù)或操作；修改的時候如何保證不丟失其他現(xiàn)有的查詢結(jié)果等，這都有待進一步研究.

3.4 Why-not & Why問題其他研究現(xiàn)狀

3.2節(jié)和3.3節(jié)工作都是單獨研究Why-not問題或Why問題.對用戶來說，如果既能幫助他們把想要但是沒出現(xiàn)在查詢結(jié)果中的對象包含在查詢結(jié)果中，又能把他們不想要但卻出現(xiàn)在查詢結(jié)果中的對象排除，這將會更加有用.文獻[47]同時考慮了SPJ查詢上的Why-not問題和Why問題.該文作者利用決策樹(decision tree)來對原查詢進行修改，從而得到用戶想要的結(jié)果.然而，決策樹實際上是一種基于信息增益理論的線性分類器(linear classifier).它的好壞很大程度上取決于數(shù)據(jù)的分布.對于關(guān)系型數(shù)據(jù)，決策樹的效果不是很好.因此，文獻[48-49]利用Skyline操作來找到可行的查詢修改方案.該方法的優(yōu)勢在于它不僅和數(shù)據(jù)的分布無關(guān)，而且該方法返回的修改方案能讓用戶根據(jù)自己的偏好進行權(quán)衡.

同時回答Why-not問題和Why問題最基本的方法就是先依次回答Why-not問題和Why問題，而后兩類問題返回答案的交集便是最終的結(jié)果.但是，這種方法的效率肯定不高，因為中間可能存在著冗余的計算或操作.當前同時考慮Why-not問題和Why問題的研究還很少，所以，該工作也尚待進一步研究.

4 Why-few & Why-many問題研究現(xiàn)狀

第2節(jié)和第3節(jié)分別總結(jié)了Causality & Responsibility問題和Why-not & Why問題的研究現(xiàn)狀.這兩大塊工作都是基于內(nèi)容的預料之外的查詢結(jié)果可用性研究.本節(jié)將回顧基于數(shù)量的預料之外的查詢結(jié)果可用性研究工作.首先分別定義Why-few問題和Why-many問題;接著介紹Why-few問題和Why-many問題的現(xiàn)有研究工作.

4.1 Why-few & Why-many問題定義

由于對數(shù)據(jù)集不了解，在構(gòu)造查詢時用戶可能會過分嚴苛(over-specify)或過分寬松(under-specify).如果查詢過分嚴苛，返回的結(jié)果可能會很少甚至為空集,這樣用戶就得不到足夠的信息;如果查詢過分寬松，返回的結(jié)果可能會太多.同樣，過多的信息對用戶來說用處也不大.針對以上2種情況，如果系統(tǒng)能夠幫助用戶把查詢結(jié)果大小控制在用戶的期望范圍之內(nèi)，這樣就能讓用戶得到適量的信息，以便于他們利用返回的信息進行相應的決策.這恰恰就是Why-few & Why-many問題研究所要解決的.下面定義5和定義6分別給出了Why-few問題和Why-many問題.

定義5. 給定一個原始查詢Q(Q的查詢結(jié)果太少甚至為空)和一個用戶期望的查詢結(jié)果大小，Why-few問題研究如何使Q的查詢結(jié)果變大以滿足用戶期望.

定義6. 給定一個原始查詢Q(Q的查詢結(jié)果太多)和一個用戶期望的查詢結(jié)果大小，Why-many問題研究如何使Q的查詢結(jié)果變小以滿足用戶期望.

目前，Why-few & Why-many問題的研究工作主要可以分為三大類：1)能夠單獨解決Why-few問題，即原查詢結(jié)果太少，研究如何使查詢結(jié)果變大；2)能夠單獨解決Why-many問題，即原查詢結(jié)果太多，研究如何使查詢結(jié)果變小；3)既能解決Why-few問題又能解決Why-many問題.圖6顯示了這3類工作所占的比例.下面分別闡述這3類工作.

Fig. 6 Statistics of studies on Why-few and Why-many questions圖6 Why-few問題和Why-many問題研究工作統(tǒng)計

4.2 Why-few問題研究現(xiàn)狀

現(xiàn)有的Why-few問題研究主要采用查詢修改這一方法來增加查詢結(jié)果大小.具體而言，查詢修改主要是對查詢所涉及的參數(shù)或查詢中的條件進行修改，從而使查詢結(jié)果變大.根據(jù)不同的修改方式，查詢修改可進一步分為基于機器學習的查詢修改、非交互式的查詢修改以及交互式的查詢修改.

基于機器學習的查詢修改方法中，文獻[50]給出了一個基于數(shù)據(jù)驅(qū)動的算法LOQR來修改查詢.LOQR通過發(fā)現(xiàn)不同域?qū)傩灾g的潛在聯(lián)系來對原查詢中的限制條件進行放松.具體地說，LOQR首先從數(shù)據(jù)庫中隨機抽取小部分數(shù)據(jù)進行判定規(guī)則(decision rules)的學習;接著，LOQR利用最近鄰技術(shù)找到與原查詢最相近的判定規(guī)則，并用該規(guī)則對原查詢進行修改.LOQR的不足之處在于當數(shù)據(jù)集較小時，其修改的查詢與原查詢會相差很大(即相似性不高).為此，文獻[51]提出了基于貝葉斯網(wǎng)絡(Bayesian network)的方法TOQR對查詢進行修改，從而解決了上述的缺點.TOQR首先初始化一個不帶任何限制條件的查詢;接著，再往其中逐漸增加限制條件直至查詢結(jié)果大小滿足要求.其中這些限制條件均來自于原查詢，而添加的順序是通過貝葉斯分類算法TAN(tree augmented Bayes network)在小數(shù)據(jù)集上學習獲得.

除了基于機器學習的查詢修改方法外，文獻[52-54]提出了非交互式的查詢修改方法.文獻[52]研究了如何修改連接查詢和選擇查詢使得空查詢結(jié)果不為空.為此，文獻[52]提出了一種基于點陣(lattice)的算法.首先，算法將可能的放松條件映射成點陣中的節(jié)點，那么每一節(jié)點就代表對查詢的某一處修改；接著，算法對點陣進行遍歷，并最終得到一種修改方案使得查詢不為空.文獻[53]探討了區(qū)域查詢(range query)上的Why-few問題，通過對給定區(qū)域的放縮以及位置的變化來增加查詢結(jié)果.另外，文獻[54]研究了子圖查詢上的Why-few問題.當子圖查詢結(jié)果為空集時，作者通過對查詢圖的修改，如點/邊的插入、刪除操作，使得子圖查詢不為空.此外，文獻[54]還給出了基于數(shù)量的圖形編輯距離(cardinality-based graph edit distance)來衡量查詢圖的修改代價.

非交互式的查詢修改方法的不足之處在于該方法可能會返回大量的查詢修改方案.這對用戶來說顯然不是他們想要的.所以，文獻[55-56]提出了一種交互式的框架對連接查詢進行修改以使得其結(jié)果不為空.具體而言，當查詢結(jié)果為空時，系統(tǒng)一步步引導用戶對查詢進行修改，每一次對查詢的修改都是比較細微的.這過程一直持續(xù)下去直至查詢結(jié)果不為空，或者無論怎么修改，查詢均不可能返回結(jié)果為止.此外，文獻[55-56]所提出的框架還允許集成不同的目標函數(shù).在系統(tǒng)引導用戶進行查詢修改時，根據(jù)實際應用中的目標函數(shù)，將最優(yōu)的修改建議(即對應目標函數(shù)值最大或最小的修改方案)返回給用戶.

4.3 Why-many問題研究現(xiàn)狀

Why-few問題研究主要針對的是查詢結(jié)果少的情況.相反，Why-many問題研究則是針對查詢結(jié)果太多的情況.現(xiàn)有的Why-many問題研究工作可以分為基于分面搜索(faceted navigation)的方法和基于排序(ranking-based)的方法.

一般地，事物包含多個屬性，這些屬性即稱為分面(faceted).分面搜索是指通過事物的這些屬性不斷篩選、過濾搜索結(jié)果的方法，可以將分面搜索看成搜索和瀏覽的結(jié)合.分面搜索過程中，用戶選擇某個條件后，分面結(jié)果會在該條件限定下的結(jié)果集中動態(tài)獲取，從而能夠從不同的角度對數(shù)據(jù)進行歸類整合，以幫助用戶進一步了解需要獲取的數(shù)據(jù)信息.然而，事物的分面可能有很多，如何向用戶提供合適的分面是需要重點解決的挑戰(zhàn)之一.為此，文獻[57]先通過向用戶提問，而后根據(jù)用戶的反饋向用戶提供相應的分面.文獻[58]根據(jù)代價模型選擇一部分分面給用戶，以使得分面搜索的代價盡可能小.文獻[59]在維基百科中實現(xiàn)了分面搜索.該工作利用了維基百科中的協(xié)同詞匯庫(collaborative vocabulary)來向用戶提供合適的分面.

另一類的Why-many問題研究利用的是排序的方法，即利用相應的排序函數(shù)對所得到的查詢結(jié)果進行排序，并返回前k個結(jié)果給用戶.一種最直接的方法就是讓用戶提供相應的排序函數(shù)，再利用Top-k查詢得到排序最靠前的k個對象.然而，用戶的排序函數(shù)往往很難得到，有時甚至連用戶自己也無法給出正確的排序函數(shù).所以，一些研究者研究了如何自動地對查詢結(jié)果進行排序.文獻[60]擴展了信息檢索與數(shù)據(jù)挖掘的常用加權(quán)技術(shù)TF-IDF(term frequency-inverse document frequency)，并提出了一種用于數(shù)據(jù)庫查詢結(jié)果排序的函數(shù).該函數(shù)同時考慮了數(shù)據(jù)分布和系統(tǒng)負荷(workload)兩個因素.另外，文獻[61-62]提出了用2種得分來決定查詢結(jié)果的排序，即全局得分(global score)和條件得分(conditional score).其中，全局得分反映了某屬性的全局重要性，而條件得分則體現(xiàn)了指定屬性與非指定屬性之間的關(guān)聯(lián)度.

4.4 Why-few & Why-many問題其他研究現(xiàn)狀

以上2方面工作都是單獨研究了Why-few問題或者Why-many問題.另外，一些研究者也同時考慮了Why-few問題和Why-many問題.文獻[63]探討了模糊查詢(fuzzy queries)上的Why-few問題和Why-many問題.為了得到適量的查詢結(jié)果，該文作者提出了通過修改查詢中所涉及的模糊條件(fuzzy conditions)的方法.文獻[64]研究了如何修改SPJ查詢來滿足查詢結(jié)果大小約束.該文作者提出了一種統(tǒng)一的框架SnS(StretchnShrink)來對查詢進行修改.其中，Stretch是指對查詢的條件進行放松，以增加查詢結(jié)果；Shrink是對查詢的條件進行緊縮，以減少查詢結(jié)果.通過n次的修改與用戶的反饋來最終得到滿足查詢結(jié)果約束條件的查詢.文獻[65]研究了如何找到與原查詢相似度高又能滿足查詢結(jié)果約束的新查詢，而原查詢的查詢結(jié)果可能太多也可能太少.該工作從2方面來考慮新查詢的好壞：1)考慮查詢結(jié)果對查詢結(jié)果大小約束條件滿足的情況；2)考慮新查詢與原查詢的相似性.為此，該文作者提出了算法SAQR來有效地找到滿足條件的最優(yōu)新查詢.文獻[66]探討了子圖查詢上的Why-few問題和Why-many問題.該工作試圖從圖數(shù)據(jù)中找到查詢圖的最大相似子圖來解釋為什么會產(chǎn)生太多或太少的查詢結(jié)果.文獻[66]的工作只是向用戶給出相應的解釋，卻并沒有向用戶提供修改建議來消除查詢結(jié)果太多或太少的現(xiàn)象.

5 查詢結(jié)果可用性分析系統(tǒng)

當前有一些系統(tǒng)實現(xiàn)了查詢結(jié)果可用性分析的若干功能.這些系統(tǒng)可以分為2類：1)基于內(nèi)容的查詢結(jié)果可用性分析系統(tǒng);2)基于數(shù)量的查詢結(jié)果可用性分析系統(tǒng).表2總結(jié)了現(xiàn)有的查詢結(jié)果可用性分析系統(tǒng).下面分別介紹這2類系統(tǒng).

基于內(nèi)容的查詢結(jié)果可用性分析系統(tǒng)包括：Artemis[67],EFQ[68],YASK[69].這3個系統(tǒng)的工作流程比較相似.首先，用戶向系統(tǒng)提交一個原始查詢，用戶得到查詢結(jié)果后進行分析.若自己想要結(jié)果沒有出現(xiàn)，則指定相應的Why-not對象并向系統(tǒng)觸發(fā)Why-not問題.當系統(tǒng)收到Why-not問題后進行處理，并最終向用戶返回2類信息：1)解釋為什么Why-not對象沒有出現(xiàn)在查詢結(jié)果中；2)提供不同的建議，以使得Why-not對象出現(xiàn)在查詢結(jié)果中.根據(jù)查詢的不同和回答Why-not問題策略的不同，系統(tǒng)所提供的建議也不一樣.Artemis實現(xiàn)的是SPJU查詢上的Why-not問題，它向用戶提供的修改建議是如何對數(shù)據(jù)集進行修改.EFQ實現(xiàn)的是連接查詢上的Why-not問題，它向用戶提供的修改建議是如何對原查詢中的操作算子或條件進行修改.YASK實現(xiàn)的是空間關(guān)鍵字Top-k查詢上的Why-not問題，它向用戶返回的建議是如何對用戶偏好函數(shù)和查詢關(guān)鍵字進行修改.

Table 2 The Summary of Systems of Database Usability for Query Results表2 查詢結(jié)果可用性分析系統(tǒng)總結(jié)

基于數(shù)量的查詢結(jié)果可用性分析系統(tǒng)包括IQR[70]和DebEAQ[71].這2個系統(tǒng)都是針對查詢結(jié)果為空集的情況.IQR漸進式地對查詢進行修改，每一次系統(tǒng)向用戶返回細小的查詢修改；而后根據(jù)用戶的反饋意見(同意或不同意修改)再進行下一次修改.這種過程一直持續(xù)下去，直到查詢不為空或者再怎么修改查詢也不可能返回結(jié)果為止.DebEAQ解決了圖模式匹配查詢上的Why-few問題.如果圖模式匹配查詢?yōu)榭?，DebEAQ會向用戶解釋為什么查詢結(jié)果為空，并提供相關(guān)的建議對查詢圖進行修改，以使得圖模式匹配查詢結(jié)果不為空.

最近，IS2R[72]同時集成了基于內(nèi)容和基于數(shù)量的查詢結(jié)果可用性分析.具體地說，IS2R能夠有效地回答反Top-k查詢上的Why-not問題、Why問題以及Why-few問題(即查詢結(jié)果為空這一情況).

當前的這些系統(tǒng)僅僅實現(xiàn)了查詢結(jié)果可用性分析的部分功能，還沒有一個系統(tǒng)能夠完整地實現(xiàn)查詢結(jié)果可用性分析的全部功能，即同時集成Causality & Responsibility問題分析、Why-not & Why問題分析和Why-few & Why-many問題分析.因此，查詢結(jié)果可用性分析系統(tǒng)的實現(xiàn)還有待進一步展開.

6 未來工作展望

學術(shù)界圍繞查詢結(jié)果可用性這一主題展開了多層次、多方位的理論與技術(shù)探索，并取得了一定的研究成果.但是實現(xiàn)全面提高數(shù)據(jù)庫查詢結(jié)果可用性的目標，依然存在著許多挑戰(zhàn).下面，對未來在數(shù)據(jù)庫查詢結(jié)果可用性研究領(lǐng)域有待進一步突破的研究問題進行展望.

1) 對不同查詢類型進行查詢結(jié)果可用性研究

目前，查詢結(jié)果可用性研究主要集中在SQL查詢.其他如Top-k查詢、反Skyline查詢、反Top-k查詢、空間關(guān)鍵字Top-k查詢、度量查詢等也有研究.然而，數(shù)據(jù)庫領(lǐng)域的查詢類型繁多，現(xiàn)有查詢結(jié)果可用性研究所針對的查詢只是冰山一角.而其他的查詢在實際應用中也會碰到預料之外的查詢結(jié)果.此外，查詢結(jié)果可用性技術(shù)往往是查詢依賴的.不同查詢之間的查詢結(jié)果可用性技術(shù)是不能通用的.所以，有必要對其他的查詢(如不完整數(shù)據(jù)查詢、圖查詢等)展開查詢結(jié)果可用性研究.

2) 大數(shù)據(jù)環(huán)境下的查詢結(jié)果可用性研究

隨著以博客、社交網(wǎng)絡、基于位置的服務LBS為代表的新型信息發(fā)布方式的不斷涌現(xiàn)，以及云計算、物聯(lián)網(wǎng)等技術(shù)的興起，數(shù)據(jù)正以前所未有的速度在不斷地增長和累積.增長迅速、龐大繁雜的數(shù)據(jù)資源，不僅給傳統(tǒng)的數(shù)據(jù)分析、處理技術(shù)帶來了巨大的挑戰(zhàn)，同時也給查詢結(jié)果可用性研究帶來了挑戰(zhàn).現(xiàn)有的查詢結(jié)果可用性研究都針對常規(guī)大小的數(shù)據(jù)集，這些技術(shù)在大數(shù)據(jù)環(huán)境下通常無法有效地使用.因此，在大數(shù)據(jù)平臺(如Hadoop,Spark等)上探索查詢結(jié)果可用性也顯得尤為重要.

3) 查詢結(jié)果可用性分析系統(tǒng)研發(fā)

目前許多的數(shù)據(jù)庫系統(tǒng)(如MySQL,SQL Server,Oracle等)主要向用戶提供數(shù)據(jù)的存儲和管理功能，但它們幾乎沒有向用戶提供查詢結(jié)果可用性分析.這不僅對用戶來說非常有實際用途，而且對于提高數(shù)據(jù)庫的可用性來說也至關(guān)重要.所以，在現(xiàn)有的數(shù)據(jù)庫系統(tǒng)基礎(chǔ)上集成查詢結(jié)果可用性分析功能或者開發(fā)新的查詢結(jié)果可用性分析系統(tǒng)也是未來研究工作的重點之一.

7 總 結(jié)

數(shù)據(jù)庫可用性研究在數(shù)據(jù)庫領(lǐng)域受到了越來越多的關(guān)注，而查詢結(jié)果可用性研究就是數(shù)據(jù)庫可用性研究的一個重要方面，這對于改善用戶使用數(shù)據(jù)庫的情況以及提高數(shù)據(jù)庫的可用性都是至關(guān)重要的.本文介紹了查詢結(jié)果可用性研究的背景；系統(tǒng)地對查詢結(jié)果可用性研究問題進行了闡述；從Causality & Responsibility問題、Why-not & Why問題以及Why-few & Why-many問題3方面將現(xiàn)有的工作進行了歸類分析比較；同時對現(xiàn)有的查詢結(jié)果可用性分析系統(tǒng)進行了介紹；最后在綜合分析現(xiàn)有工作的技術(shù)基礎(chǔ)上給出了3個未來的研究方向.

[1]ISO/DIS 9241-11. Ergonomic requirements for office work with visual display terminals-Part Ⅱ guidance on usability[S]. London: International Organization for Standardization, 1998

[2]Jagadish H V, Chapman A, Elkiss A, et al. Making database systems usable[C] //Proc of ACM SIGMOD’07. New York: ACM, 2007: 13-240

[3]Li Fei, Jagadish H V. Usability, databases, and HCI[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2012, 35(3): 37-45

[4]Lewis D. Causation[J]. The Journal of Philosophy, 1973, 70(17): 556-567

[5]Menzies P. Counterfactual theories of causation[OL]. 2014 [2016-11-07]. http://stanford.library.sydney.edu.au/entries/causation-counterfactual/#Bib

[6]Halpern J Y, Pearl J. Causes and explanations: A structural-model approach. Part Ⅰ: Causes[J]. The British Journal for the Philosophy of Science, 2005, 56(4): 843-887

[7]Chockler H, Halpern J Y. Responsibility and blame: A structural-model approach[J]. Journal of Artificial Intelligence Research, 2004, 22: 93-115

[8]Meliou A, Gatterbauer W, Halpern J Y, et al. Causality in databases[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2010, 33(3): 59-67

[9]Meliou A, Gatterbauer W, Moore K F, et al. WHY SO? or WHY NO? Functional causality for explaining query answers[C] //Proc of MUD’10. New York: ACM, 2010: 3-17

[10]Meliou A, Roy S, Suciu D. Causality and explanations in databases[C] //Proc of ACM VLDB’14. New York: ACM, 2014: 1715-1716

[11]Meliou A, Gatterbauer W, Moore K F, et al. The complexity of causality and responsibility for query answers and non-answers[C] //Proc of ACM VLDB’11. New York: ACM, 2011: 34-45

[12]Qin Biao, Wang Shan, Zhou Xiaofang, et al. Responsibility analysis for lineages of conjunctive queries with inequalities[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(6): 1532-1543

[13]Gao Yunjun, Liu Qing, Chen Gang, et al. Finding causality and responsibility for probabilistic reverse skyline query non-answers[J]. IEEE Trans on Knowledge and Data Engineering, 2016, 28(11): 2974-2987

[14]Wang Zheng, Wang Chaokun, Pei Jisheng, et al. Causality based propagation history ranking in social networks[C] //Proc of IJCAI’16. Menlo Park, CA: AAAI, 2016: 3917-3923

[15]Qin Biao, Wang Shan, Du Xiaoyong. Efficient responsibility analysis for query answers[C] //Proc of DASFAA’13. Berlin: Springer, 2013: 239-253

[16]Meliou A, Gatterbauer W, Nath S, et al. Tracing data errors with view-conditioned causality[C] //Proc of ACM SIGMOD’11. New York: ACM, 2011: 505-516

[17]Lian Xiang, Chen Lei. Causality and responsibility: Probabilistic queries revisited in uncertain databases[C] //Proc of ACM CIKM’13. New York: ACM, 2013: 349-358

[18]Chapman A, Jagadish H V. Why not?[C] //Proc of ACM SIGMOD’09. New York: ACM, 2009: 523-534

[19]Bidoit N, Herschel M, Tzompanaki K. Query-based why-not provenance with NedExplain[C] //Proc of ACM EDBT’14. New York: ACM, 2014: 145-156

[20]Bidoit N, Herschel M, Tzompanaki K. Immutably answering why-not questions for equivalent conjunctive queries[C/OL] //Proc of TAPP’14. New York: ACM, 2014 [2016-11-07]. https://www.usenix.org/conference/tapp2014/agenda/presentation/bidoit

[21]Bidoit N, Herschel M, Tzompanaki K. Efficient computation of polynomial explanations of why-not questions[C] //Proc of ACM CIKM’15. New York: ACM, 2015: 713-722

[22]ten Cate B, Civili C, Sherkhonov E, et al. High-level why-not explanations using ontologies[C] //Proc of ACM PODS’15. New York: ACM, 2015: 31-43

[23]Huang Jiansheng, Chen Ting, Doan A H, et al. On the provenance of non-answers to queries over extracted data[C] //Proc of ACM VLDB’08. New York: ACM, 2008: 736-747

[24]Herschel M, Hernandez M. Explaining missing answers to SPJUA queries[C] //Proc of ACM VLDB’10. New York: ACM, 2010: 185-196

[25]Zong Chuanyu, Yang Xiaochun, Wang Bin, et al. Minimizing explanations for missing answers to queries on databases[C] //Proc of DASFAA’13. Berlin: Springer, 2013: 254-268

[26]Zong Chuanyu, Wang Bin, Sun Jing, et al. Minimizing explanations of why-not questions[C] //Proc of DASFAA’14 Workshops. Berlin: Springer, 2014: 230-242

[27]Tran Q T, Chan C Y. How to ConQueR why-not questions[C] //Proc of ACM SIGMOD’10. New York: ACM, 2010: 15-26

[28]He Zhian, Lo E. Answering why-not questions on top-kqueries[C] //Proc of IEEE ICDE’12. Piscataway, NJ: IEEE, 2012: 750-761

[29]Bhowmick S S, Sun A, Truong B Q. Why not, WINE?: Towards answering why-not questions in social image search[C] //Proc of ACM MM’13. New York: ACM, 2013: 917-926

[30]Islam M S, Liu Chengfei, Li Jianxin. Efficient Answering of why-not questions in similar graph matching[J]. IEEE Trans on Knowledge and Data Engineering, 2015, 27(10): 2672-2686

[31]Chen Lei, Lin Xin, Hu Haibo, et al. Answering why-not questions on spatial keyword top-kqueries[C] //Proc of IEEE ICDE’15. Piscataway, NJ: IEEE, 2015: 279-290

[32]Chen Lei, Xu Jianliang, Lin Xin, et al. Answering why-not spatial keyword top-kqueries via keyword adaption[C] //Proc of IEEE ICDE’16. Piscataway, NJ: IEEE, 2016: 697-708

[33]Xu Wenjian, He Zhian, Lo E, et al. Explaining missing answers to top-kSQL queries[J]. IEEE Trans on Knowledge and Data Engineering, 2016, 28(8): 2071-2085

[34]Islam M S, Zhou Rui, Liu Chengfei. On answering why-not questions in reverse skyline queries[C] //Proc of IEEE ICDE’13. Piscataway, NJ: IEEE, 2013: 973-984

[35]He Zhian, Lo E. Answering why-not questions on top-kqueries[J]. IEEE Trans on Knowledge and Data Engineering, 2014, 26(6): 1300-1315

[36]Chen Lu, Gao Yunjun, Wang Kai, et al. Answering why-not questions on metric probabilistic range queries[C] //Proc of IEEE ICDE’16. Piscataway, NJ: IEEE, 2016: 767-778

[37]Gao Yunjun, Liu Qing, Chen Gang, et al. Answering why-not questions on reverse top-kqueries[C] //Proc of ACM VLDB’15. New York: ACM, 2015: 738-749

[38]Herschel M. Wondering why data are missing from query results?: Ask conseil why-not[C] //Proc of ACM CIKM’13. New York: ACM, 2013: 2213-2218

[39]Herschel M. A hybrid approach to answering why-not questions on relational query results[J]. Journal of Data and Information Quality, 2015, 5(3): 10:2-10:29

[40]Liu Bin, Chiticariu L, Chu V, et al. Automatic rule refinement for information extraction[C] //Proc of ACM VLDB’10. New York: ACM, 2010: 588-597

[41]Liu Qing, Gao Yunjun, Chen Gang, et al. Answering why-not and why questions on reverse top-kqueries[J]. The VLDB Journal, 2016, 25(6): 867-892

[42]Tan W C. Provenance in databases: Past, current, and future[J]. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, 2007, 30(4): 3-12

[43]Bhagwat D, Chiticariu L, Tan W C, et al. An annotation management system for relational databases[J]. The VLDB Journal, 2005, 14(4): 373-396

[44]Chiticariu L, Tan W C, Vijayvargiya G, et al. A post-it system for relational databases based on provenance[C] //Proc of ACM SIGMOD’05. New York: ACM, 2005: 942-944

[45]Buneman P, Khanna S, Tan W C. Why and where: A characterization of data provenance[C] //Proc of ICDE’01. Berlin: Springer, 2001: 316-330

[46]Cui Yingwei, Widom J. Lineage tracing for general data warehouse transformations[J]. The VLDB Journal, 2003, 12(1): 41-58

[47]Islam M S, Liu Chengfei, Zhou Rui. On modeling query refinement by capturing user intent through feedback[C] //Proc of ADC’12. New York: ACM, 2012: 11-20

[48]Islam M S, Liu Chengfei, Zhou Rui. User feedback based query refinement by exploiting skyline operator[C] //Proc of ER’12. Berlin: Springer, 2012: 423-438

[49]Islam M S, Liu Chengfei, Zhou Rui. FlexIQ: A flexible interactive querying framework by exploiting the skyline operator[J]. Journal of Systems and Software, 2014, 97: 97-117

[50]Muslea I. Machine learning for online query relaxation[C] //Proc of ACM KDD’04. New York: ACM, 2004: 246-255

[51]Muslea I, Lee T J. Online query relaxation via bayesian causal structures discovery[C] //Proc of AAAI’05. Menlo Park, CA: AAAI, 2005: 831-836

[52]Koudas N, Li Chen, Tung A K H, et al. Relaxing join and selection queries[C] //Proc of ACM VLDB’06. New York: ACM, 2006: 199-210

[53]Kadlag A, Wanjari A V, Freire J, et al. Supporting exploratory queries in databases[C] //Proc of DASFAA’04. Berlin: Springer, 2004: 594-605

[54]Vasilyeva E, Thiele M, Mocan A, et al. Relaxation of subgraph queries delivering empty results[C] //Proc of ACM SSDBM’15. New York: ACM, 2015: 28:1-28:13

[55]Mottin D, Marascu A, Roy S B, et al. A probabilistic optimization framework for the empty-answer problem[C] //Proc of ACM VLDB’13. New York: ACM, 2013: 1762-1773

[56]Mottin D, Marascu A, Roy S B, et al A holistic and principled approach for the empty-answer problem[J]. The VLDB Journal, 2016, 25(4): 597-622

[57]Basu Roy S, Wang Haidong, Das G, et al. Minimum-effort driven dynamic faceted search in structured databases[C] //Proc of ACM CIKM’08. New York: ACM, 2008: 13-22

[58]Kashyap A, Hristidis V, Petropoulos M. Facetor: Cost-driven exploration of faceted query results[C] //Proc of ACM CIKM’10. New York: ACM, 2010: 719-728

[59]Li Chengkai, Yan Ning, Roy S B, et al. Facetedpedia: Dynamic generation of query-dependent faceted interfaces for Wikipedia[C] //Proc of ACM WWW’10. New York: ACM, 2010: 651-660

[60]Agrawal S, Chaudhuri S, Das G, et al. Automated ranking of database query results[C/OL] //Proc of CIDR’03. New York: ACM, 2003 [2016-11-07]. http://www-db.cs.wisc.edu/cidr/cidr2003/program/p9.pdf

[61]Chaudhuri S, Das G, Hristidis V, et al. Probabilistic ranking of database query results[C] //Proc of ACM VLDB’04. New York: ACM, 2004: 888-899

[62]Chaudhuri S, Das G, Hristidis V. Probabilistic information retrieval approach for ranking of database query results[J]. ACM Trans on Database Systems, 2006, 31(3): 1134-1168

[63]Bosc P, HadjAli A, Pivert O. Empty versus overabundant answers to flexible relational queries[J]. Fuzzy Sets and Systems, 2008, 159(12): 1450-1467

[64]Mishra C, Koudas N. Interactive query refinement[C] //Proc of ACM EDBT’09. New York: ACM, 2009: 862-873

[65]Albarrak A, Sharaf M A, Zhou X. SAQR: An efficient scheme for similarity-aware query refinement supporting exploratory queries in databases[C] //Proc of DASFAA’14. Berlin: Springer, 2014: 110-125

[66]Vasilyeva E, Thiele M, Bornh?vd C, et al. Answering “Why Empty?” and “Why So Many?” queries in graph databases[J]. Journal of Computer and System Sciences, 2016, 82(1): 3-22

[67]Herschel M, Hernandez M A, Tan W C. Artemis: A system for analyzing missing answers[C] //Proc of ACM VLDB’09. New York: ACM, 2009: 1550-1553

[68]Tzompanaki K, Bidoit N, Herschel M. EFQ: Why-not answer polynomials in action[C] //Proc of ACM VLDB’15. New York: ACM, 2015: 1980-1991

[69]Chen Lei, Xu Jianliang, Jensen C S, et al. YASK: A why-not question answering engine for spatial keyword query services[C] //Proc of ACM VLDB’16. New York: ACM, 2016: 1501-1504

[70]Mottin D, Marascu A, Basu Roy S, et al. IQR: An interactive query relaxation system for the empty-answer problem[C] //Proc of ACM SIGMOD’14. New York: ACM, 2014: 1095-1098

[71]Vasilyeva E, Heinze T, Thiele M, et al. DebEAQ-debugging empty-answer queries on large data graphs[C] //Proc of IEEE ICDE’16. Piscataway, NJ: IEEE, 2016: 1402-1405

[72]Liu Qing, Gao Yunjun, Zhou Linlin, et al. IS2R: A system for refining reverse top-kqueries[C] //Proc of IEEE ICDE’17. Piscataway, NJ: IEEE, 2017: 1371-1372

Liu Qing, born in 1988. PhD candidate. His main research interests include spatial databases, database usability, and data provenance.

Gao Yunjun, born in 1977. PhD. Professor, PhD supervisor in the College of Computer Science and Technology, Zhejiang University, China. Member of ACM and IEEE, and senior member of CCF. His main research interests include spatial and spatio-temporal databases, database usability, metric and incompleteuncertain data management, and geo-social data processing.

Survey of Database Usability for Query Results

Liu Qing1and Gao Yunjun1,2

1(CollegeofComputerScienceandTechnology,ZhejiangUniversity,Hangzhou310027)2(KeyLaboratoryofBigDataIntelligentComputingofZhejiangProvince(ZhejiangUniversity),Hangzhou310027)

Database usability has

much attention in the database community because of its importance. The goal of database usability is to help users utilize database more efficiently and conveniently, and thus improving the user’s satisfaction for the database. In this survey, we focus on the database usability for query results. Currently, the queries only return the query results to users. If the query result is unexpected for the users, it will frustrate users. However, the database system neither gives explanations for the unexpected query results, nor offers any suggestion on how to get the expected results for users. The users only can debug the queries by themselves, which is cumbersome and time-consuming. If the database system can offer such explanations and suggestions, it helps the users understand initial query better, and know how to change the query until the satisfactory results are found, hence improving the usability of the database. Towards this, the studies on unexpected query results have been explored. In this paper, we provide a comprehensive survey of the most recent research on database usability for query results. The paper first analyses the unexpected query results, and introduces the corresponding three problems, i.e., causality & responsibility, why-not & why questions, and why-few & why-many questions, and highlights the importance of these three problems. Then, the state of the art progresses of the unexpected query result research have been surveyed and summarized. Finally, the paper raises some directions for the future work.

database usability; why-not questions; why questions; causality & responsibility; why-few questions; why-many questions

2016-11-10；

2017-03-22

國家“九七三”重點基礎(chǔ)研究發(fā)展計劃基金項目(2015CB352502)；國家自然科學基金優(yōu)秀青年科學基金項目(61522208)；國家自然科學基金項目(61379033,61472348)；NSFC-浙江兩化融合聯(lián)合基金重點項目(U1609217) This work was supported by the National Basic Research Program of China (973 Program) (2015CB352502), the National Natural Science Foundation of China for Excellent Young Scientists (61522208), the National Natural Science Foundation of China (61379033, 61472348), and the Key Project of the NSFC-Zhejiang Joint Fund (U1609217).

高云君(gaoyj@zju.edu.cn)

TP311.13