Mining Precision Interface From Query Logs -- 学习笔记（二）
4 交互mining
?????? 前面說到解決最終問題的步驟之一：分析日志以識別有意義的結構更改，因為如果單純用成對AST之間的差異表 會導致不相關的差異，所以并不是所有從logs中分析出的差異對生成精確界面都是有意義的。
本節作者提出的 語句以及編寫 語句的工具：就是一種可以指定 有意義的結構改變的特定于域的語言。
Q1：為什么不使用 來分析所有 中的差異？
答：有三個方面：
（1）出現不想關的結構改變：像函數重命名，更改project clause的別名，重排 子句中的表，對查詢語義沒有任何的影響，而這些差異在 表中也是有記載的。
（2）誤導性差異，舉個栗子：
① SELECT a FROM T WHERE 1=1
② SELECT a FROM T GROUPBY a
上面這兩個查詢語句，樹對齊算法分析出的可能是在①中用GROUPBY子句替換WHERE子句形成了②。但事實上這并不是有意義的能夠映射到小部件的變化。有可能①②是通過將 WHERE子句和GROUPBY子句添加到一個基礎的查詢語句 SELECT a FROM T上的。
（3）有特殊情況，再舉個栗子：
① SELECT b FROM T WHERE a>5 AND a<10
② SELECT b FROM T WHERE c>5 AND a=10
第一個查詢通過整數來過濾值，我們很自然的就能想到它可以用范圍滑塊來映射。但是范圍滑塊卻不能用于第二個查詢，為了區別這兩個語句，精確界面需要額外的語義來說明更改的常量是共享相同屬性的不等表達式的一部分。
基于上面的原因，應該根據應用程序和開發人員的需求，篩選有意義的查詢結構變化
Q2： 語句？
1、 語句是一種特定于域的語言，基于此語言，用戶可以指定查詢結構變化的位置和方式，一個 語句通過一對查詢 進行計算，返回一個輸出表，如果不匹配則返回一個?。等價于通過 對 進行過濾，并對子樹 進行轉換
2、 子句的結構組成：
?FROM子句：用來定義精確界面在搜索時 結構變化的范圍，并對 中的 子樹 進行轉換。 < path expression > 由 能確定祖先孩子關系的運算符 組成。path 總是和 匹配，它還指定要返回的祖先子樹；FROM子句返回與路徑匹配，并包含子樹的最深子樹。路徑 //* 表示不對 中的子樹進行轉換。
總之，FROM子句就相當于把范圍變量綁定到下面的語句：
SELECT id, pid1, pid2, extract(,path),ancestor( ,path),ancestor( ,path)
FROM
WHERE matches( , path)
WHERE子句：是對FROM子句中定義的范圍變量的布爾表達式；可以用路徑操作符來操作子樹
MATCH子句：match子句用來給 語句命名，這樣就可以用成功的匹配標記交互圖中的邊。
Q3：怎么執行和寫語句？
被轉換成SQL查詢，并在一對由 定義的 分區上執行，執行的結果集中到一個叫做? 的表中。是為開發者設計的，沒有 一定處理抽象語法樹的基礎的用戶使用起來有點困難。針對這個問題，作者開發了一個簡化書寫 語句的工具：這個工具可以檢測成對樹中最普遍的差異，然后讓用戶來選擇他們認為重要的差異。具體操作過程：（1） 用戶指定一些可能的成對差異或者一些可能會不同的結點（2）工具從日志中提取樣本，比較樣本中所有成對樹，并且指出滿足指定條件的樹（通過還原語法樹，高亮那些變化的子句，這樣使無基礎用戶更易懂）。
這個工具對任何的查詢轉換都能生成 語句，為了幫助用戶優化搜索，工具還可以把與現有 語句匹配的差異從要搜索的后序集合中排除，減小搜索范圍。
?
?
?5 交互映射
前面交互mining輸出一個 表，表示日志中成對查詢所表示子樹之間有意義的差異。把這個? 表映射到一個交互圖 ，圖中每個頂點代表一個查詢，每個記錄都是一條用交互描述的有向邊 。圖是一個稠密圖，因為每對查詢之間可能會被多條轉換邊連接。目標是生成一個可以表達交互圖中所有查詢的一個界面集合 .
要實現這個目標，有三個挑戰：
（1）要為圖中每條邊選擇合適的部件來表達交互（也就是查詢語句的變化）
（2）提取域和模板函數來具體化這些部件
（3）在界面上映射交互圖
下面的部分則是作者針對這些問題，提出的解決方案：
Q1：對交互圖進行預處理
前面說過一個部件 是由一個域? ，一個交互 ，一個模板函數 確定。如何從 ? 中提取模板函數和域呢？方法是從 的子樹中提取參數化的模板樹，然后利用參數來構造域，還使用這些結果來標記交互圖中的邊。具體操作：
對于模板函數：
用 個參數代替子樹 中 原來的 個值，構建參數化的模板樹 ；表? 用參數化的樹模型 和 參數值 確定。然后通過這些模板把樹進行分組，對每個組 ，收集組內所有樹的參數值，然后找到一個參數至少變化了一次的下標集合 ，然后生成每個組的表 ，這個表代表了在相同的參數化子樹中變化的參數值。
每個部件 都有一個k維的域。如果表 中的屬性和 域的維度之間一一映射，則參數化子樹可以被映射到部件 ，從而使每個映射都在 范圍內。這樣的話，那模板函數 只是小部件原狀態到值表中的屬性的一一映射，然后這些屬性綁定到了模板子樹的參數。
對標記邊：
交互圖中每條邊 都代表 表中的一條記錄 。我們用 路徑和模板子樹 標記邊 ，還有其參數值 .
一個邊可以被映射到界面的多個部件，把這個候選部件集叫做 .
Q2：部件映射
下一步生成可以 表示 log 中所有查詢的界面集合 .
（1）首先，定義界面閉包集合 ，根據交互圖確定它的代價 ，從集合覆蓋問題出發，通過松弛，證明了界面生成問題是個NP問題。作者提出了一個帶優化的圖松弛啟發式算法來加快這個過程。作者假定每條邊都有一個候選部件，每個轉換都是標準的，并且每個 語句在任何成對查詢之間最多生成一條邊。然后對這些約束進行松弛。
（2）一個界面 包括一個初始的查詢 和一個部件集合。定義這個界面的閉包為一個可達查詢的集合。
（可達：存在一些從初始查詢 到 的路徑，這些路徑可以由 中的部件表達）
（邊 可以用部件 表示：邊 的路徑和模板子樹 和部件的相同，則可以表示）
（3）部件 的域定義為在 中它表示的邊的值的集合。這個域用來計算它的代價 以及后續的界面集合 的代價。
Q3：解決NP-Hardness
從集合覆蓋到界面生成描述松弛方法：
給定一個總體 和 一個能覆蓋 的 包含 m 個子集合的集合 。集合覆蓋識別子集中的最小子集 ，那么 .（我的理解是最小不重疊的子集）
可以構造一個交互圖 ， 每個子集 形成一個最大子圖? （我理解的是這個子集中的查詢結構差異是相似的），這個圖的邊由子集的id 標識。最大子圖中的邊由一個唯一的候選組件 表示（也就是說這個子集中的界面是可以用一個候選部件表示的），若其域為空則代價為0，否則為1。往一個界面中添加組件 就把子集 中的所有元素添加到閉包中，最終界面集的部件集一起構成最終界面的候選部件集。
Q4：啟發式算法
作者之前提出一種貪心啟發式算法解決界面生成問題。通過為查詢集中每個查詢 分配一個界面 初始化 最終界面集合集 ，然后使用貪心法合并界面，直到這些界面的總代價不再減少為止。
如果存在0個或更多的邊 連接查詢 ? 和 則可以合并 界面 ，用邊 合并界面。
最終合并的界面 使用 的初始查詢，把來自兩個界面的部件和邊 的部件結合起來構成部件集 .
可以通過合并 表示相同轉化的部件 來減少 。（表示相同轉化的部件定義：兩個有相同路徑和特征函數的部件 可以合并成一個部件 ，其域值為 ）.
針對每次迭代k，作者發現合并界面可以減少總代價：
?Q4：針對多個候選部件，怎么選擇合適的？
在實際操作過程中，一個給定的邊 e 有多種候選組件 .
作者選擇用啟發式算法（合并界面）處理候選部件而不是在初始界面集就將邊綁定到特定的組件上。為了完成這個任務，需要定義兩個部件如何進行合并，以及他們的代價應該怎樣估計。一旦完成對界面的合并，就可以從每個候選集選擇代價最小的界面。
合并候選集 和 要合并兩個集合 ，執行上述過程的域合并的過程。候選部件集的代價通過集合中代價最小的部件確定，即? .
Q5：對交互圖中兩個頂點間的多條邊的處理：
表中包括 至少一個記錄，每個都代表圖中成對查詢之間的一條路徑，為了能完全將查詢 轉換到 ，將 邊 建模為一個超級邊 “super—edge” ，它的候選部件集是 每條邊的候選部件集的叉乘積 .
Q6：基于集合的交互：
大多語言支持集合表達。前述的模型沒有考慮集合操作的交互建模。例如，一個查找數字差異的語句輸出了一個成對差異的集合。多數情況下，把這些成對差異映射到一個多選擇的部件。
為了自動的將 這種 表轉換成基于集合的交互，作者使用一種類似于提取模板函數的方法：
（1）首先收集 里所有的子樹
（2）針對每棵子樹，尋找 它最近的祖先結點(祖先結點是list類型）為根的子樹 .
（3）如果不存在這樣的子樹，就停止。否則，用一個參數變量代替 中的 ? 生成一個模板祖先子樹
（4）若所有的模板祖先都相同，就將這些子樹作為一個集合，然后將這個 映射到一個集合邊，這條邊的候選部件是集合部件。
Q7：界面生成：
一旦確定了最優的界面集集合 ，就從候選集合中根據每個部件的域 選出代價最低的部件。這時就可以運行標準界面布局算法，然后為每個界面在web應用程序中呈現一個選項卡。
?
?
小結：
對整篇文章來說，最重要的部分就是 第 3/4/5 部分，這三部分重點講了作者對提出問題的解決方案，通過建模，運用合適的算法進行解決。
這部分的內容是最晦澀難懂的，因為涉及很多數學專業名詞和計算機專業名詞，還有很多數學建模的過程。第二遍看，看了接近兩天，還是有一部分意思理解的不太準確！可能需要多讀幾遍文章才能真的理解吧！
?
印象比較深的應該是把部件映射問題建模成集合覆蓋問題來求解了，數學真的博大精深，任何現實問題都可以用數學思維解決，學好數學真的太重要啦！
?
2019.8.18
綠色為今日閱讀新的認識
總結
以上是生活随笔為你收集整理的Mining Precision Interface From Query Logs -- 学习笔记（二）的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Apache Spark概述
- 下一篇： Mining Precision Int