Mining Precision Interface From Query Logs -- 学习笔记（三）
讀完第五部分，全文的重中之重也可以說是學習完畢了。前半部分是對提出的問題的 一個解決方案。接下來，作者要闡述的 是針對這個問題，有沒有更進一步的優化方案，使得生成精確界面的成本代價更小。優化也是問題研究中一個很重要的方面，當數據量龐大時，好的算法有時可以降低很大級別數量級的復雜度，提高性能。下面，來讀一讀作者關于此問題的優化方案：
先回顧一下解決問題的步驟：
（1）計算出query logs中不同成對樹之間的差異
（2）使用 語句過濾出有意義的差異
（3）將結果轉換為 交互圖
（4）執行啟發式算法導出界面
然而，這幾個步驟執行的代價太過大，尤其是在成千對queries中 尋找樹之間的差異。下面，作者基于 3個問題的本質屬性 來減少這種成對的轉換：（1）轉換的傳遞性（2）存在模板（3）所有轉換可能不相關的事實
?
6 優化
實現精確界面的過程需要4步：
（1）從 中 找出成對AST樹之間的 表
（2）用 語句來篩選 表
（3）將結果轉為交互圖
（4）執行啟發式算法導出界面
Q1： 語句的傳遞性
一個 語句可傳遞：
如果? 可傳遞，則它所匹配的程序集就形成一個集合。新的程序 只需要檢查和 任意一個程序 匹配，就可以說明和集合中任何一個都匹配。作者針對這個傳遞性，提出了一個能 直接在程序日志中 檢測 語句構成程序集合 的算法：
Data: PILANG statement: s, Programs: P result: C initialize C = {}; while p∈P do:matched = false;while c∈C do: //將與C中匹配的程序p放入小集合cif( 存在C中的程序pc，使得s(p,pc)≠? ):c.add(p);matched = true;endendif(!mathched):C.add({p});end end?利用啟發式算法識別出所寫 語句中的傳遞語句：檢查 語句的 WHERE子句 是否只包含傳遞性的邏輯表達式（e.g.，＝，≠）
事實上，交互圖不實用，因為它非常密集。對一個包含 N 個查詢的交互圖，其中有 條邊。但是這個算法可以壓縮交互圖。它把一個邊的集合壓縮成一個集合的集合，降低了一個數量級的存儲代價。這可以獲得 在主存中 處理大量查詢log 的能力。
（我的理解是 有很多重復的邊，現在要找出這些邊。我們不必一個一個區匹配這些邊，只需要在匹配程序集里匹配，如果有，那么和程序集里其他的程序也一定匹配。如果沒有。就單獨成一個程序集）
Q2：程序模板
中 經常存在 解析結構相同而值不同的 程序集合。
例如，通過改變距離閾值或者函數參數形成的查詢在任何地方都相同。把這種集合叫做 . 為了檢測這種 clique，作者采用了和 提取模板函數 一致的方法：用未命名的變量替換查詢AST樹中的值，散列結果，并通過散列值將它們分組。這樣，就可以用 一個模板 和 一個值的列表 來表示結構相同的 AST樹了。接下來就可以針對集合進行 差異的尋找 以及 語句過濾了，不用再針對單個的查詢了。對每個模板 clique，為到每個變量的路徑建立索引，并在 語句中用這個路徑表達式進行匹配 。一個匹配的 語句可以利用這個 索引 快速的識別出 AST間的改變并且 評估它們。
Q3：指定程序對優化界面生成
精確界面生成界面的依據是 不同程序之間的差異。作者認為可以根據性能和個性化目的 對這些程序對的范圍做出限制。將程序日志建模為一種關系為系統選擇程序對提供很大的靈活性。
?
7 實驗
本部分是作者進行了一系列的實驗。作者用 5 個 。4個是SQL書寫，1個是 SPARQL，而且這些日志是以人工可視化的方式生成的。做此實驗的目的是想回答精確界面生成工具的四個相關問題：
（1）精確界面能否表示
（2）運行時是否可接受
（3）是否支持多種語言
（4）和現有的以及手工設計的界面相比，用戶更喜歡哪個
?
解析樹和界面挖掘是用Java實現，組件映射和生成使用Python實現（生成了HTML+Javasprict的界面）。定義了12種組件并且人共為SQL和 SPARQL定義了 函數 和 函數。
Q1：精確界面能否表示
作者從兩個 展示界面生成和能表達出 的程度（人工生成的基于實時數據庫的OLAP日志）
作者做此實驗的目的是希望能從OLAP查詢空間中 生成一個和 Tableau相似的界面，為了模仿這個探索的過程，生成器一一個分組查詢開始然后在每一步隨機改變子句（GROUPBY，WHERE，SELECT）。維度、過濾器以及度量都叢均勻分布隨機抽樣。然后慢慢的進行改變，每一步只改變一下。作者寫了 7 個與生成器表達的結構變化和值變化相關的? 語句。
這幅圖是生成器生成的界面。左邊的兩個框用戶可以選擇度量和維度。最下方的選擇框提供了三個過濾器，每個都有一個下拉框選擇列或者文本來確定一個值。這個界面可以表達日志中所有的查詢。Tableau這個工具，它讓用戶自己拖動列到架子上來生成OLAP查詢。
這個生成界面是 通過修改代價函數的權重，來獲得簡單界面，這個界面更注重簡單。作者將界面復雜性的權重設置較高，將用戶使用性權重設置偏低。可以看到，用戶必須通過自己手動輸入來生成查詢
?
這個界面，可以看到所有的選擇都被羅列了處理。作者將權重設置反過來，界面復雜性的權重設置較低，將用戶使用性權重設置較高。它忽視了視覺上的復雜性。
?
作者通過讓12個學生用實時數據庫完成三個不同的任務專門生成了一個查詢日志（這些問題并不是直接的查詢數據的問題，而是需要查詢數據進行一些分析才能回答的問題）。作者讀取了所有這個過程中執行查詢語句所記錄的日志。一共298個語句，有148個不同。作者寫了15個 語句。這個生成的日志比合成的日志更具變化性。
這張圖顯示了界面覆蓋查詢的覆蓋率。可以看到，初始的第一個界面能覆蓋大約166（55%）的查詢，后面的生成的界面所包含的查詢都 < 10，可以看出這個日志的交互圖是個稀疏圖。
?
這幅圖對比了精確界面生成的三個界面，左邊的界面是可以讓用戶通過選擇來比較，中間的界面為始發機場和目的機場延誤數據的匯總，右邊的界面為每個航班都做了分析。 這三個界面都沒有完整覆蓋整個 日志，但卻僅用6個交互組件就表達的主要的查詢結構的變化.
Q2: 是否支持多種語言 & 運行時是否可接受
這個實驗作者要測試精確界面的語言支持性和可擴展性。作者選擇了兩個程序日志，一個是用SQL語言書寫的 SDSS（有125,603條，112,603條不同），還有一個是SRAPQL書寫的British Museum‘s web collection（11,0,667條，39,933條不同）對第一方面，作者對兩個由不同查詢語言書寫的日志進行測試。對第二方面，作者通過使用不同的優化方法測試運行時間。最后作者得出結論：界面生成的90%的時間花在了交互分析上面，因此必須優化這個地方。
作者用了兩個不同語言的日志，比較了四種不同優化方式下的運行時：
（1）無優化
（2）clique優化
（3）模板樹優化
（4） （2）+（3）
最后發現，同時使用兩種優化比不使用優化的運行時提高了兩個數量級。這使得界面能在分鐘級別內處理萬級級別的查詢日志。
?
上面這幅圖對精確界面生成界面的運行時間花費進行了分解，可以看到大部分的時間都花在了 交互分析上面
上面的圖表明對于兩個日志，運行時都呈二次方增長，這是因為精確界面必須對齊和比較?? 對程序來構造交互圖。作者做了個實驗發現比較的成本是恒定的，而這些成本來自大量的比較。
優化并不能減少算法 的復雜度，但是它可以讓系統避免比較。模板優化對比無優化已經帶來了兩個數量級的改進
上圖是界面分析器的運行時隨 語句數量變化的所變化的圖。查詢語句的數量進行了刪減，作者希望用少量樣本來讓這些算法的運行時都在一小時內。可以看到，增加 語句的數量會線性的增加運行時間。
?
上圖表明了應用 6.2節提取模板的方法后，兩個查詢日志的界面生成運行時都呈現二次方增加。
?上圖表明，交互分析的運行時隨著模板數量的增加而線性增加。這表明模板優化成功地找出了日志中的結構。日志或者越多的模板，則交互分析運行的越快。
?
Q3：用戶體驗
作者在此實驗中，引導用戶原始的SDSS界面學習SDSS，來探究兩個問題：
（1）生成的界面是否會減少響應時間和分析準確性
（2）生成的界面在用戶體驗上能否和原始的/人工定制的界面有競爭性
（一）和現有界面的比較
用戶有5分鐘時間來閱讀針對4個任務的現有界面SDSS的說明書，然后操作界面。為了避免學習的影響，將用戶隨機分為兩組，用不同的界面完成4個任務。然后作者記錄了運行時間以及結果的準確性。
從圖中可以看出，作者提出的精確界面對分析的準確性以及運行時間都有很大的改善。
（二）界面喜好
完成上面的試驗后，作者收集了被測試者對著四個界面的喜好度
從圖中可以看出，精確界面和右工程師繪制的界面都比原始界面更受被測試者喜歡。超過40人的被測試者，有70%選擇人工界面2，但只有1個選擇人工界面1，這表明人工定制的界面有很大差異。超過20%用戶選擇精確界面，沒有人選擇原始界面。這又說明精確界面可以和現有的界面進行競爭。此外，還說明在沒有特定領域知識，精確界面可以通過分析日志總結交互中顯著的操作，映射到交互界面。這比開發人員進行開發來的更容易。
?
Q4：Tableau 實驗
這個實驗直接將精確界面運用到Tableau生成查詢日志上來測試：
（1）精確界面是否能檢測到低層的交互
（2）是否能生成一個和 Tableau 相似的界面
最后得出的實驗結果是這個界面能夠只用4個組件就表達出 logs中所有的查詢
小結
第二次讀這篇文章就花了不少時間，第三第四第五部分花費的時間最長。每天讀都會有新的理解，包括對單詞，對句子的理解。
數據庫中的操作大部分都是 Query 相關。Query的速度直接影響數據庫的性能。這篇文章 根據 query log ，通過不同 query 生成的 AST樹 之間的差異， 將差異 映射到 界面的部件，生成定制界面，方便分析人員利用可視化界面 查詢數據、分析數據。
接下來說說 閱讀一篇論文 步驟：
第一步：先看摘要，摘要其實是整篇文章中最能概括文章主題的部分，此部分可以了解到作者針對什么問題提出了什么解決方案以及該方案的效果如何。
第二步，看實驗部分，可以大致了解這個問題的解決流程。
第三步，一般論文的第一部分是介紹論文研究問題的背景，可以暫且跳過。第二部分為論文的流程概述，我一般從此處開始看論文，接下來的部分則都是核心部分，需要精讀。
論文最后一部分一般為 總結，是對文章的總結。總結的前一部分一般是該領域問題的相關文獻以及前人已經有的研究，這部分可以大致帶過。
?
?
總結
以上是生活随笔為你收集整理的Mining Precision Interface From Query Logs -- 学习笔记（三）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Mining Precision Int
- 下一篇： 并行数据库 分布式数据库