基於SQL的數據差異：最長的公共子序列

我正在尋找研究論文或着作將Longest Common Subsquence算法應用於SQL表以獲取數據差異視圖。其他有關如何解決表差異問題的建議也受到歡迎。目前的挑戰在於SQL表有歌廳相當大的和應用設計的文字處理可能會導致，永遠不會結束程序簡單的算法，這種壞習慣......基於SQL的數據差異：最長的公共子序列

所以給定一個表Original：

Key Content 
1 This row is unchanged 
2 This row is outdated 
3 This row is wrong 
4 This row is fine as it is

並表New：

Key Content 
1 This row was added 
2 This row is unchanged 
3 This row is right 
4 This row is fine as it is 
5 This row contains important additions

我需要找出Diff：

+++ 1 This row was added 
--- 2 This row is outdated 
--- 3 This row is wrong 
+++ 3 This row is right 
+++ 5 This row contains important additions

來源

2010-07-17 Remus Rusanu

只要是明確的，在'Key'強加給行的順序，否則術語如「序列」和「子」將毫無感覺在一個無序的集合（如關係表）。 – 2010-07-17 00:41:15

不要忘記，理論上來說，表格沒有任何順序 - 這也使事情變得複雜。您必須定義表格比較的訂單。 – 2010-07-17 00:41:45

我不認爲這與通常的問題有什麼不同：你可以做的最好的是O（n^2）（忽略比較錶行的時間），其中n是行數。如果你知道沒有行移動超過k個位置，你可以通過修改通常的動態編程算法在O（nk）中完成。如果n^2太大，你可能不得不假設類似這樣的，有一些合理的小k。 – ShreevatsaR 2010-07-17 01:31:17

如果您導出tabls爲CSV文件，您可以使用http://sourceforge.net/projects/csvdiff/

報價： csvdiff是一個Perl腳本，DIFF /比較兩個CSV文件，與可能性來選擇分離器。差異將顯示如下：「記錄999中的列XYZ」不同。在此之後，將顯示此列的實際和預期結果。

來源

2010-07-23 12:15:27

這可能對於你所追求的內容太簡單了，它不是研究:-)，而只是概念。我想你正在比較不同的方法來處理開銷（？）。

- 這是你不想要什麼（A）

SELECT o.Key FROM tbl_ORIGINAL o INNER JOIN tbl_NEW n WHERE o.Content = n.Content

- 這是你不想要（B）

SELECT n.Key FROM tbl_ORIGINAL o INNER JOIN tbl_NEW n WHERE o.Content = n.Content

什麼的另一半半 - 這是你做什麼想要的（C）

SELECT '+++' as diff, n.key, Content FROM tbl_New n WHERE n.KEY NOT IN(B)

- 這是你做什麼想要的（d）的另一半半

SELECT '---' as diff, o.key, Content FROM tbl_Original o WHERE o.Key NOT IN (A)

--CombiningÇ& d

(C) 
Union 
(D) 
Order By diff, key

改進...

嘗試創建第一
嘗試減少內容的長度的基表的索引視圖字段的最小值爲唯一性（試錯），然後使用更短的結果做你的比較

- 獲得最小長度（1000是任意的 - 只需要一個出口）

declare @i int 
set @i = 1 
While i < 1000 and Exists (
Select Count(key), Left(content,@i) From Table Having Count(key) > 1) 
BEGIN 
    i = @i + 1 
END

來源

2011-03-24 23:51:09 Chains

基於SQL的數據差異：最長的公共子序列

回答

相關問題