柳 晴 高云君,2

1(浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310027)2(浙江省大數(shù)據(jù)智能計(jì)算重點(diǎn)實(shí)驗(yàn)室(浙江大學(xué)) 杭州 310027)

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

柳 晴1高云君1,2

1(浙江大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 杭州 310027)2(浙江省大數(shù)據(jù)智能計(jì)算重點(diǎn)實(shí)驗(yàn)室(浙江大學(xué)) 杭州 310027)

(liuq@zju.edu.cn)

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

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

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

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

數(shù)據(jù)庫可用性研究涵蓋眾多方面，本文將綜述視角放在查詢結(jié)果可用性研究，內(nèi)容緊密圍繞查詢結(jié)果可用性所涉及的3個(gè)問題，即Causality & Responsibility問題、Why-not & Why問題、Why-few & Why-many問題.對(duì)于數(shù)據(jù)庫可用性其他方面的相關(guān)研究工作，由于篇幅問題，本文不作涉及.下面首先介紹查詢結(jié)果可用性研究所涉及的3個(gè)問題；再針對(duì)每個(gè)問題討論分析最新的研究進(jìn)展；接著介紹相關(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ù)不同的需求進(jìn)行各種查詢，如偏好查詢、SQL查詢等；查詢層再往上則是查詢結(jié)果分析層，這一層根據(jù)查詢返回的結(jié)果并結(jié)合用戶的反饋意見進(jìn)行相應(yīng)分析；最上層是各種實(shí)際應(yīng)用.圖1給出了數(shù)據(jù)庫工作基本框架.由圖1可知，查詢結(jié)果可用性研究屬于查詢結(jié)果分析層.具體來說，查詢結(jié)果可用性研究的研究對(duì)象是預(yù)料之外的查詢結(jié)果(unexpected query results).當(dāng)查詢返回相應(yīng)的查詢結(jié)果時(shí)，如果當(dāng)前的結(jié)果跟用戶預(yù)先期望的結(jié)果有所出入(即預(yù)料之外)，那么就需要對(duì)現(xiàn)有的結(jié)果進(jìn)行相關(guān)分析.根據(jù)對(duì)預(yù)料之外的查詢結(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 對(duì)預(yù)料之外的查詢結(jié)果可用性問題分析

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

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

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

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

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

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

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

2.1 問題定義

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

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

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

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

(1)

2.2 研究現(xiàn)狀

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

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

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

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

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

定義4. 給定一個(gè)原始查詢Q和一個(gè)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)計(jì)

簡而言之，Why-not問題就是幫助用戶把想要但是沒出現(xiàn)在查詢結(jié)果中的對(duì)象包含在查詢結(jié)果中；Why問題就是幫助用戶把不想要但是卻出現(xiàn)在查詢結(jié)果中的對(duì)象排除.當(dāng)前，Why-not問題和Why問題研究工作可以分為3類：1)單獨(dú)研究Why-not問題；2)單獨(dú)研究Why問題；3)同時(shí)研究Why-not問題和Why問題，即既把用戶想要但是沒出現(xiàn)在查詢結(jié)果中的對(duì)象包含在查詢結(jié)果中，又把用戶不想要但是卻出現(xiàn)在查詢結(jié)果中的對(duì)象排除.圖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中右邊的餅圖顯示了各種策略在當(dāng)前研究工作中所占的比例.另外，表1總結(jié)了Why-not問題的研究工作并根據(jù)其所采用的策略對(duì)它們進(jìn)行了分類.

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

另外，文獻(xiàn)[22]提出了基于本體論的解釋方法，它們所針對(duì)的查詢是連接查詢(conjunctive queries).根據(jù)所針對(duì)的本體類型的不同，又可將所產(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.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

當(dāng)前有一些系統(tǒng)實(shí)現(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個(gè)系統(tǒng)的工作流程比較相似.首先，用戶向系統(tǒng)提交一個(gè)原始查詢，用戶得到查詢結(jié)果后進(jìn)行分析.若自己想要結(jié)果沒有出現(xiàn)，則指定相應(yīng)的Why-not對(duì)象并向系統(tǒng)觸發(fā)Why-not問題.當(dāng)系統(tǒng)收到Why-not問題后進(jìn)行處理，并最終向用戶返回2類信息：1)解釋為什么Why-not對(duì)象沒有出現(xiàn)在查詢結(jié)果中；2)提供不同的建議，以使得Why-not對(duì)象出現(xiàn)在查詢結(jié)果中.根據(jù)查詢的不同和回答Why-not問題策略的不同，系統(tǒng)所提供的建議也不一樣.Artemis實(shí)現(xiàn)的是SPJU查詢上的Why-not問題，它向用戶提供的修改建議是如何對(duì)數(shù)據(jù)集進(jìn)行修改.EFQ實(shí)現(xiàn)的是連接查詢上的Why-not問題，它向用戶提供的修改建議是如何對(duì)原查詢中的操作算子或條件進(jìn)行修改.YASK實(shí)現(xiàn)的是空間關(guān)鍵字Top-k查詢上的Why-not問題，它向用戶返回的建議是如何對(duì)用戶偏好函數(shù)和查詢關(guān)鍵字進(jì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個(gè)系統(tǒng)都是針對(duì)查詢結(jié)果為空集的情況.IQR漸進(jìn)式地對(duì)查詢進(jìn)行修改，每一次系統(tǒng)向用戶返回細(xì)小的查詢修改；而后根據(jù)用戶的反饋意見(同意或不同意修改)再進(jìn)行下一次修改.這種過程一直持續(xù)下去，直到查詢不為空或者再怎么修改查詢也不可能返回結(jié)果為止.DebEAQ解決了圖模式匹配查詢上的Why-few問題.如果圖模式匹配查詢?yōu)榭?，DebEAQ會(huì)向用戶解釋為什么查詢結(jié)果為空，并提供相關(guān)的建議對(duì)查詢圖進(jìn)行修改，以使得圖模式匹配查詢結(jié)果不為空.

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

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

6 未來工作展望

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

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

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

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

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

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

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

7 總 結(jié)

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

[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

國家“九七三”重點(diǎn)基礎(chǔ)研究發(fā)展計(jì)劃基金項(xiàng)目(2015CB352502)；國家自然科學(xué)基金優(yōu)秀青年科學(xué)基金項(xiàng)目(61522208)；國家自然科學(xué)基金項(xiàng)目(61379033,61472348)；NSFC-浙江兩化融合聯(lián)合基金重點(diǎn)項(xiàng)目(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