Unique Key nachtraeglich ermitteln

[roli]

Hi Leute,

ich sitze hier vor einer riesigen CSV Datei, und versuche ohne weitere Informationen zu ermitteln ob es darin einen Unique Key gibt, und wenn ja welcher. In meinem konkreten Fall habe ich bislang noch keine einzelne Spalte gefunden die alleine der Key sein könnte. Wenn es hier einen gibt, dann erstreckt er sich über mehrere Spalten.
Kennt jemand ein Tool das das kann?

[roli]

Hallo,

da allem anschein nach solch ein Tool nicht existiert, werde ich mich wohl wenn die Schmerzen mit der Datei gross genug sind mal selber drann setzen muessen.
Hat denn jemand vielleicht eine bessere Idee, als mittels einer vollstaendigen Permutation an das ganze ran zu gehen, bzw. kennt eine effektive implementation in Perl dafuer?

[123456]

Versuch doch erstmal quick&dirty die .csv in Excel einzulesen mit den verschiedenen Möglichkeiten, die das bietet. Vielleicht hilft Dir das bei der Mustererkennung...

[roli]

Hi,

Excel und co. sind ja ganz nett, aber bei 600 Spalten spielen die nicht mehr mit. Ausserdem könnten in dem Fall wofuer ich's gebrauchen koennte, die 65000 Zeilen was wenig sein.

[123456]

Nicht schlecht. Grosses unbekanntes Teil. Social Hacking: frag die Leute, die das Teil erstellt haben.

Mit "unique key" meinst Du den Primärschlüssel, ja? Ohne das Datenmaterial zu kennen wird das etwas schwierig werden.

Algorithmus kenne ich keinen - würde aber an Deiner Stelle mal Google anwerfen. Es gibt Foren und Sammlungen mit Programmier Allgorithmen in diversen Sprachen. Einen Link habe ich nicht parat - bin ja auch kein Programmierer.

[roli]

Nicht schlecht. Grosses unbekanntes Teil. Social Hacking: frag die Leute, die das Teil erstellt haben.

Ok, in diesem Fall waere das (sogar) moeglich, aber es gab auch schon SItuationen da war es das nicht, leider.

Mit "unique key" meinst Du den Primärschlüssel, ja? Ohne das Datenmaterial zu kennen wird das etwas schwierig werden.

Jeep, den Primaerschluessel meine ich. Das Datenmaterial habe ich vor mir, aber ich suche halt einen Weg das "so" zu schaffen.

Algorithmus kenne ich keinen - würde aber an Deiner Stelle mal Google anwerfen. Es gibt Foren und Sammlungen mit Programmier Allgorithmen in diversen Sprachen. Einen Link habe ich nicht parat - bin ja auch kein Programmierer.

Bei Google habe ich schon gesucht, bin aber zu nix verwertbarem gekommen. Ich weiss zwar nicht wann man sich Programmierer nennen darf, aber das sind so die Aufgabe die ich mir dann immer wieder mal suche, oder suchen die etwa mich, an denen ich meine "persoenliche exzelenz Offensive" starte, damit halt mal was aus mir wird

[123456]

Hmmh. Normalerweise sollte die .csv Datei ja in Zeile 1 die Spaltenüberschriften haben...

Unabhängig von den Algorithmen, die Du noch findest würde ich die .csv Datei für jede Spalte auf Doppler durchsuchen. Alle Spalten, bei denen es keine gibt wären Kandidaten für einen Primärschlüssel - findest Du nur eine Spalte für die das gilt hast Du ihn.

So ein Algorithmus sollte sich im Netz finden lassen. Ist bei mir aber zu lange her, um mich noch daran zu erinnern. Das sollte sowas wie ineinandergeschachtelte for Schleifen mit if Abfrage sein...

[gms]

In meinem konkreten Fall habe ich bislang noch keine einzelne Spalte gefunden die alleine der Key sein könnte. Wenn es hier einen gibt, dann erstreckt er sich über mehrere Spalten.

bei 600 Spalten hast du die Summe über 600!/n!(600-n!) ( n geht von 1 bis 600) an Möglichkeiten. Die ersten 600 davon hast du bereits abgehackt, sollte der Primarykey also aus zwei Spalten bestehen, mußt du 179700 Kombinationen durchsuchen, bei 3 Spalten dann 35820200, ..usw.
Wenn allerdings ein Index über n Spalten nicht unique ist, dann gibt es auch keinen der mit k<n Spalten unique ist. Daher würde ich als nächstes den Index über alle Spalten versuchen.

würde ich die .csv Datei für jede Spalte auf Doppler durchsuchen. Alle Spalten, bei denen es keine gibt wären Kandidaten für einen Primärschlüssel - findest Du nur eine Spalte für die das gilt hast Du ihn.

wenn mehrere solcher Spalten gefunden werden, dann kann über jede dieser Spalten auch ein Unique-Key definieren kann. Man könnte also auch bei der ersten Spalte, welche keine doppelten Werte enthält, aufhören.

Gruß
gms

[roli]

Hmmh. Normalerweise sollte die .csv Datei ja in Zeile 1 die Spaltenüberschriften haben...

Ok, und?

Unabhängig von den Algorithmen, die Du noch findest würde ich die .csv Datei für jede Spalte auf Doppler durchsuchen. Alle Spalten, bei denen es keine gibt wären Kandidaten für einen Primärschlüssel - findest Du nur eine Spalte für die das gilt hast Du ihn.

So ein Algorithmus sollte sich im Netz finden lassen. Ist bei mir aber zu lange her, um mich noch daran zu erinnern. Das sollte sowas wie ineinandergeschachtelte for Schleifen mit if Abfrage sein...

Gefunden habe ich solch einen Algorithmus halt noch nicht...
Aber bin ich denn wirklich der einzigste, der vor diesem Problem steht, wenn es den Algorithmus irgendwo gibt, dann sollte es doch auch ein Programm drum herum geben ;-}

[gms]

Gefunden habe ich solch einen Algorithmus halt noch nicht...
Aber bin ich denn wirklich der einzigste, der vor diesem Problem steht, wenn es den Algorithmus irgendwo gibt, dann sollte es doch auch ein Programm drum herum geben ;-}

mir ist irgendwie unklar, wer ein solches Programm benötigen könnte. Kannst du dein Problem näher erläutern ?
Unter der Annahme, daß es sich bei der csv Datei nicht um "nicht interpretierbaren Datenmüll" handelt, sollte der Primary Key aus fachlicher Sicht eigentlich bekannt sein. Daher jeder der mit dem nötigen fachlichen Know-How ausgestattet ist, sollte wissen, welcher Key als Primary Key verwendet werden kann.
Falls es fachlich keinen Primary Key gibt, bleibt noch immer die Lösung einen solchen zu generieren ( z.B über die Zeilennummer )

Gruß
gms

[123456]

Hmmh. Normalerweise sollte die .csv Datei ja in Zeile 1 die Spaltenüberschriften haben...

Ok, und?

Im Kontext des Datenmaterials könnte Dich das auf den Primärschlüssel schliessen lassen...

So ein Algorithmus sollte sich im Netz finden lassen.

Hier findest Du die Basis für Dein Skript:
http://www.informatik-forum.at/showthread.php?t=40740

[roli]

Hi,

Unter der Annahme, daß es sich bei der csv Datei nicht um "nicht interpretierbaren Datenmüll" handelt, sollte der Primary Key aus fachlicher Sicht eigentlich bekannt sein. Daher jeder der mit dem nötigen fachlichen Know-How ausgestattet ist, sollte wissen, welcher Key als Primary Key verwendet werden kann.

Nein Datenmuell ist es nicht. Wenn es denn den Key in diesen Daten ueberhaupt gibt, wovon ich aber ausgehe, ist er auch bekannt, nur leider nicht mir
Natuerlich koennte ich fragen, aber sobald ein "Verein" eine kritische Masse/Groesse erreicht, spielt nicht mehr jeder mit jedem, so das ich mir das ersparen moechte. Ich bin halt nur voruebergehend hier, und moechte mich soweit es geht aus den "politischen Machtspielchen" raushalten. Ausserdem sehe ich's mittlerweile als nette programmier Uebung fuer mich, das ist wenigestens mal wieder eine Aufgabe aus dem/meinen Leben.

@ub13: danke fuer den Link, mal sehen was ich damit anfangen kann

[gms]

Ausserdem sehe ich's mittlerweile als nette programmier Uebung fuer mich, das ist wenigestens mal wieder eine Aufgabe aus dem/meinen Leben.

von der Programmierung her ist das sicherlich eine nette Übungsaufgabe und gerade in Perl ist das auch relativ einfach zu implementieren.
Problematisch wird es nur dann, wenn der Primary Key aus 4 oder noch mehr Spalten zusammengesetzt ist. Bei 4 Spalten mußt du schon 5346164850 potentielle Schlüssel mit jeweils mit 65000 Zeilen auf Doppelte durchsuchen, das könnte dann schon einige Zeit dauern

Gruß
gms

[roli]

von der Programmierung her ist das sicherlich eine nette Übungsaufgabe und gerade in Perl ist das auch relativ einfach zu implementieren.

Mein reden ;-}

Problematisch wird es nur dann, wenn der Primary Key aus 4 oder noch mehr Spalten zusammengesetzt ist. Bei 4 Spalten mußt du schon 5346164850 potentielle Schlüssel mit jeweils mit 65000 Zeilen auf Doppelte durchsuchen, das könnte dann schon einige Zeit dauern

Um das ganze noch zu steigern, bislang hatte ich nur erwaehnt, das 65000 Zeile nicht reichen, aber nicht das wir hier von ca. 4.500.000 Records sprechen
Aber da sind wir wieder bei der alten Weisheit: "Der Tag hat 24 Std., und wenn's nicht reicht nimmt man halt die Nacht dazu". Egal, im Zweifelsfall lasse ich's als ersten Versuch mal uebers Wochenende laufen. bzw. nehme erstmal nur 1000 Recods, um zu sehen was passiert

[HELLinG3R]

Ein dauernder Verlgeich ist doch nicht zwangsläufig nötig - je nach Implementierung lässt sich das vielleicht schon durch geschicktes Sortieren in einen hash lösen. Entspricht am Ende die Anzahl an Schlüsseln im Hash der Anzahl an records, gab es keine Duplikate:
(Pseudocode)

Code: Alles auswählen

Int datensaetze = 0;
Int spalte = 1; //welche Spalte auf Duplikate untersucht werden soll
Hash h;

foreach (datensatz) {
    datensaetze++;
    h[datensatz[spalte]]++;
}
if (datensaetze != anzahl(Hash) ) {
    print "Duplikate gefunden!";
} else {
   print "Keine Duplikate gefunden!";
}

Weiß nicht, könnte schneller sein als dauernd zu vergleichen. Je nach Datengröße in den Spalten müsste man evtl noch einen Hashalgorythmus in Betracht ziehen.
Vielleicht lässt sich das aber auch schnell mit "cut" "wc -l" lösen.

[gms]

Entspricht am Ende die Anzahl an Schlüsseln im Hash der Anzahl an records, gab es keine Duplikate

Hash ist gut, jedoch würde ich schon beim Einfügen der Schlüssel in den Hash abfragen, ob der aktuelle Wert schon im Hash vorhanden ist. Im günstigsten Fall, kann dadurch das Einsortieren in den Hash von 4.500.000 Werte auf 2 Werte reduziert werden.

Gruß
gms

edit: eventuell würde ich auch ein 64 bit Perl in Erwägung ziehen
Bei 4.500.000 Zeilen und 600 Spalten, wird es schwer diese Datenmenge im Speicher zu behalten

[roli]

Hash ist gut, jedoch würde ich schon beim Einfügen der Schlüssel in den Hash abfragen, ob der aktuelle Wert schon im Hash vorhanden ist. Im günstigsten Fall, kann dadurch das Einsortieren in den Hash von 4.500.000 Werte auf 2 Werte reduziert werden.

Die Anzahl der Werte ist 4.500.000 (Records) * 600 (Spalten), also noch'n Eckchen mehr

[HELLinG3R]

Ob der aktuelle Wert schon im hash vorhanden ist, spielt keine rolle, denn wenn er nicht vorhanden ist, wird er hinzugefügt, ansonsten einfach überschrieben. Da der Spalteninhalt als Key des hashs benutzt wird, sind Duplikate ausgeschlossen. Das sollte relativ schnell gehen.

Die Geschichte mit dem Speicher lässt sich logisch eingrenzen, sobald irgendein Wert 2 erreicht, kann man die aktuelle Spalte abbrechen:

Code: Alles auswählen

Int spalten;

for (i=1, i<=spalten, i++){
    Hash h;    //leeren Hash initialisieren

    foreach (datensatz) {
        if (key_exists(datensatz[i], h)) {
            print "Spalte " + i + " ungeeignet!";
            break;   //weiter bei nächster spalte
        } else {
            h[datensatz[i]] = 1;
        }
    }
    print "Spalte " + i + " ist geeignet!"; //geeignet, da letzter Datensatz geprüft und keine Duplikate
}

Trotzdem ist es sicherlich sinnvoller, das fachlich zu prüfen - denn selbst "kein duplikat" in der spalte bedeutet nicht, dass die Daten darin auch als Primärschlüssel benutzt werden können, wen noch daten dazu kommen oder verändert werden.

[gms]

wenn man einen Index über mehrere Spalten überprüfen möchte, genügt es nicht einzelne Spalten auf doppelte Werte zu überprüfen
z.B wäre bei diesen Daten ein Primary Key über Vorname und Nachname noch möglich, obwohl in jeder Spalte doppelte Einträge vorhanden sind:

Code: Alles auswählen

Vorname; Nachname
Max;Mustermann
Max;Schlauberger
Elfriede;Schlauberger

Am einfachsten vergleicht man dann mittels Delimiter zusammengehängte Werte. Man tragt also "Max;Mustermann" in ein Hash ein, danach schaut man ob "Max;Schlauberger" im Hash vorhanden ist, wenn ja, kann man abbrechen, wenn nicht weitermachen, usw


Gruß
gms

[123456]

bei 4,5 Mio Datensätzen könnte man doch zusätzlich noch ne if Abfrage in den Code einbauen, die prüft, ob das aktuelle Feld leer ist. Wenn ja, kanns kein Primärschlüssel sein und es kann ein break; aus der Spalte erfolgen...

[gms]

Habe gerade auf cpan geguckt, welches Perl-Modul hilfreich sein könnte und dort das Modul "Math::Combinatorics" entdeckt.

Die äußeren Schleifen lassen sich damit sehr leicht bewerkstelligen:

Code: Alles auswählen

for ( my $keylen = 1; $keylen < $colcount; $keylen++) {
  my $c = Math::Combinatorics->new(count => $keylen, data => [1..$colcount]);
  while(my @keycols = $c->next_combination){
    print "test key @keycols ...\n";
    if ( isKeyUnique(@keycols) ) {
      print "primary key found: @keycols\n";
      exit(0);
    }
  }
}

Die Funktion "isKeyUnique" läßt sich auch sehr leicht implementieren:

Code: Alles auswählen

sub isKeyUnique(@) {
  my @keycols = @_;

  my %keyvalues = ();
  for ( my $rowidx=0; $rowidx < $rowcount; $rowidx++) {
    my $keyvalue = "";
    foreach my $keycol ( @keycols ) {
      $keyvalue .= $data[$rowidx][$keycol-1];
      $keyvalue .= ";";
    }
    if ( defined $keyvalues{$keyvalue} ) {
       # hier können wir abbrechen, die Anzahl der verschiedenen
       # Schlüsselwerte benötigen wir eigentlich nicht
       return 0;
    }
    $keyvalues{$keyvalue} = 0;
  }
  return 1;
}

Damit sollte das Grundgerüst eigentlich stehen. Das Einlesen in das @data Array und das Setzen von $rowcount und $colcount, sollte keine große Übung mehr sein. Das benötigte Modul besteht aus reinem Perlcode und kann daher auch ohne Compiler sehr leicht nachinstalliert werden.
Das Speicherproblem und das Problem mit der riesigen Anzahl an Kombinationen, besteht natürlich noch weiterhin. Daher würde ich das Script auch nur über eine KLEINE Teilmenge drüber laufen lassen. ( Eventuell solltest du dann das "exit 0" auskommentieren ( und $keylen limitieren ), damit du mehrere mögliche Primary Key-Kandidaten aus dieser Teilmenge bekommst )

Gruß
gms

[roli]

Hi,

erstmal DANKE an alle, ich denke ich habe jetzt eine Basis auf der ich gut aufbauen kann.
Wenn aber jemand noch weitere Tips hat, nur zu!