查詢結果可用性研究綜述

柳 晴 高云君,2

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

查詢結果可用性研究綜述

柳 晴1高云君1,2

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

(liuq@zju.edu.cn)

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

數據庫可用性；why-not問題；why問題；causality與responsibility；why-few問題；why-many問題

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

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

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

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

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

1 查詢結果可用性問題描述

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

Fig. 1 The basic framework of database圖1 數據庫工作基本框架

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

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

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

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

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

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

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

2 Causality & Responsibility問題研究現狀

2.1 問題定義

當查詢結果中包含了用戶不想要的對象或者用戶想要的對象沒有出現在查詢結果中，如果用戶想知道是哪些原因導致了現有的查詢結果，這些原因的影響有多大，便可以利用Causality和Responsibility問題來分析.

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

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

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

(1)

2.2 研究現狀

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

Fig. 4 The statistics of studies on Causality & Responsibility圖4 Causality & Responsibility研究工作統計

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

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

3 Why-not & Why問題研究現狀

3.1 Why-not & Why問題定義

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

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

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

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

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

3.2 Why-not問題研究現狀

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

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

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

Table 1 The Summary of Studies on Why-not Questions表1 現有Why-not問題工作總結

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

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

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

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

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

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

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

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

3.3 Why問題研究現狀

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

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

3.4 Why-not & Why問題其他研究現狀

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

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

4 Why-few & Why-many問題研究現狀

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

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

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

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

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

目前，Why-few & Why-many問題的研究工作主要可以分為三大類：1)能夠單獨解決Why-few問題，即原查詢結果太少，研究如何使查詢結果變大；2)能夠單獨解決Why-many問題，即原查詢結果太多，研究如何使查詢結果變小；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問題研究工作統計

4.2 Why-few問題研究現狀

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

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

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

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

4.3 Why-many問題研究現狀

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

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

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

4.4 Why-few & Why-many問題其他研究現狀

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

5 查詢結果可用性分析系統

當前有一些系統實現了查詢結果可用性分析的若干功能.這些系統可以分為2類：1)基于內容的查詢結果可用性分析系統;2)基于數量的查詢結果可用性分析系統.表2總結了現有的查詢結果可用性分析系統.下面分別介紹這2類系統.

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

Table 2 The Summary of Systems of Database Usability for Query Results表2 查詢結果可用性分析系統總結

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

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

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

6 未來工作展望

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

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

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

2) 大數據環境下的查詢結果可用性研究

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

3) 查詢結果可用性分析系統研發

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

7 總 結

數據庫可用性研究在數據庫領域受到了越來越多的關注，而查詢結果可用性研究就是數據庫可用性研究的一個重要方面，這對于改善用戶使用數據庫的情況以及提高數據庫的可用性都是至關重要的.本文介紹了查詢結果可用性研究的背景；系統地對查詢結果可用性研究問題進行了闡述；從Causality & Responsibility問題、Why-not & Why問題以及Why-few & Why-many問題3方面將現有的工作進行了歸類分析比較；同時對現有的查詢結果可用性分析系統進行了介紹；最后在綜合分析現有工作的技術基礎上給出了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

國家“九七三”重點基礎研究發展計劃基金項目(2015CB352502)；國家自然科學基金優秀青年科學基金項目(61522208)；國家自然科學基金項目(61379033,61472348)；NSFC-浙江兩化融合聯合基金重點項目(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