diff de données SQL: plus longue sous-séquence commune

Je recherche des documents de recherche ou des écrits en appliquant l'algorithme Longest Common Subsquence aux tables SQL pour obtenir une vue diff de données. D'autres suggestions sur la façon de résoudre un problème de table diff sont également les bienvenues. Le défi étant que les tables SQL ont cette mauvaise habitude de geting assez grand et d'appliquer des algorithmes simples conçus pour le traitement de texte peut donner lieu à un programme qui ne finit jamais ...diff de données SQL: plus longue sous-séquence commune

donc donné une table 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

et la table 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

Je dois trouver le 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

Source

2010-07-17 Remus Rusanu

Pour être clair, le 'key' rend une ordonnance sur les lignes, sinon des termes comme « séquence » et « séquence » ne changerait rien sens sur un ensemble non ordonné (comme une table relationnelle). –

N'oubliez pas que les tables n'ont pas, en théorie, d'ordre pour les lignes - ce qui complique aussi les choses. Vous devez définir un ordre pour les comparaisons de table. –

Je ne pense pas que ce soit différent du problème habituel: le mieux que vous pouvez faire est O (n^2) (en ignorant le temps de comparer les lignes de table) où n est le nombre de lignes. Si vous savez qu'aucune ligne ne se déplace de plus de k positions, vous pouvez le faire en O (nk) en modifiant l'algorithme de programmation dynamique habituel. Vous devrez probablement supposer quelque chose comme ceci, avec un k raisonnablement petit, si n^2 est trop grand. – ShreevatsaR

Si vous exportez vos tabls dans des fichiers csv, vous pouvez utiliser http://sourceforge.net/projects/csvdiff/

Quote: csvdiff est un script Perl pour diff/comparer deux fichiers csv avec la possibilité pour sélectionner le séparateur. Les différences seront montrées comme: "La colonne XYZ dans l'enregistrement 999" est différente. Après cela, le résultat réel et le résultat attendu pour cette colonne seront affichés.

Source

2010-07-23 12:15:27

Ceci est probablement trop simple pour ce que vous recherchez, et ce n'est pas la recherche :-), mais juste conceptuel. J'imagine que vous cherchez à comparer différentes méthodes de traitement des frais généraux (?).

--Ce est la moitié de ce que vous ne voulez pas (A)

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

--Ce est l'autre moitié de ce que vous ne voulez pas (B)

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

--Ce est la moitié de ce que vous ne voulez (C)

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

--Ce est l'autre moitié de ce que vous voulez (D)

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

--Combining C & D

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

... Améliorations

essayer de créer des vues indexées sur les tables de base premier
essayez de réduire la longueur du contenu champ à son min pour unicité (essai/erreur), puis utiliser cette résultat plus court pour faire vos comparaisons

- par exemplepour obtenir la longueur min (1000 est arbitraire - juste besoin d'une sortie)

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

Source

2011-03-24 23:51:09 Chains

diff de données SQL: plus longue sous-séquence commune

Répondre

Questions connexes