Senftenberg, ein ungewöhnliches Konzept

Vom einfachen Programm zum fertigen Debian-Paket, Fragen rund um Programmiersprachen, Scripting und Lizenzierung.
Antworten
Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 15.11.2018 22:24:20

Ich habe in den letzten Wochen etwas Ungewöhnliches gebaut, Senftenberg.
Ist es eine Datenbank? Ist es ein Dateisystem? Ich weiß es selber nicht.
Gibt es schon etwas ähnliches?

Senftenberg macht so etwas wie Index mit Hashtable, aber es gibt dazu gar keine Tabellen, die gejoint werden. Es funktioniert mit beliebigen Datenstücken.
Möglicherweise ist das für Datenkraken sehr nützlich, aber weil es öffentlich ist, herrscht Waffengleichheit.

Bitte schaut euch das mal an, und sagt mir, was ihr davon haltet!
Harry, hol schon mal das Rasiermesser!

cronoik
Beiträge: 2049
Registriert: 18.03.2012 21:13:42
Lizenz eigener Beiträge: GNU Free Documentation License

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von cronoik » 16.11.2018 02:47:36

Dein anderer Thread hat mich schon ganz gespannt gemacht auf das was du da gebaut hast und es ist schoen, dass das Geheimnis nun gelueftet wird. Den Code habe ich mir noch nicht angesehen, aber das PDF konnte ich schon lesen. Fuer mich klingt es, ungeachtet der konkreten technischen Implementation, auf den ersten Moment so als ob du mehrere Graphen erzeugst und in diesen die Daten speicherst. Die Kanten dienen dabei nicht nur der Verknuepfung, sondern enthalten auch selbst Daten. Falls du dem zustimmst, dann nennt sich das extended property graph model und wurde an der Uni Leipzig entwickelt [1]. Deine technische Implementation unterscheidet sich natuerlich vom Leipziger Gradoop.

[1] https://dbs.uni-leipzig.de/file/EPGM.pdf
Hilf mit unser Wiki zu verbessern!

Benutzeravatar
bluestar
Beiträge: 2334
Registriert: 26.10.2004 11:16:34
Wohnort: Rhein-Main-Gebiet

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von bluestar » 16.11.2018 10:29:02

cronoik hat geschrieben: ↑ zum Beitrag ↑
16.11.2018 02:47:36
https://dbs.uni-leipzig.de/file/EPGM.pdf
Du warst schneller, aber ja ich teile deine Meinung -> Das müsste genau der Alg sein.

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 16.11.2018 19:11:35

cronoik hat geschrieben: ↑ zum Beitrag ↑
16.11.2018 02:47:36
Dein anderer Thread hat mich schon ganz gespannt gemacht auf das was du da gebaut hast und es ist schoen, dass das Geheimnis nun gelueftet wird.
Das Geheimnis nicht zu lüften, wäre Undank. Ich stehe, so wie andere auch, auf den Schultern von Riesen, und diesen Riesen gebührt die Veröffentlichung.
cronoik hat geschrieben: ↑ zum Beitrag ↑
16.11.2018 02:47:36
Fuer mich klingt es, ungeachtet der konkreten technischen Implementation, auf den ersten Moment so als ob du mehrere Graphen erzeugst und in diesen die Daten speicherst.
Ich baue einen Graf, der aus Bäumen besteht, deren Wurzeln (Nein, das ist falsch. Bei einem Baum ist der Bug des einen Pfeils das Heck eines anderen Pfeils. Bei mir ist der gesamte eine Pfeil das Heck des anderen Pfeils.) bei SHA-256 Wörter aus 43 Base64-Zeichen, und bei SHA-1 Wörter aus 27 Base64-Zeichen sind.
Wenn so ein Wort der Hash von etwas ist, dann steht diese Wurzel für dieses Etwas. Und wenn nicht, oder man nicht weiß, ob, dann ist es halt so.
cronoik hat geschrieben: ↑ zum Beitrag ↑
16.11.2018 02:47:36
Die Kanten dienen dabei nicht nur der Verknuepfung, sondern enthalten auch selbst Daten.
Da muss ich zwischen Graf0 und Graf1 unterscheiden. Graf0 ist der Graf, über den ich Information speichere, und Graf1 ist der Graf in der Information.
Ein Pfeil in Graf0, nämlich das an A hängende B, ist in Graf1 ein Punkt, sein Name ist Hash(AB). Gespeichert wird Hash(AB)ABZ, wobei Z ein Zusatz ist.
Manche Punkte in Graf1 enthalten Information über Pfeile in Graf0 (nämlich das Z von eben). Andere Punkte in Graf1 sind Kinder von Punkten in Graf1 (Wieder falsch. Sind Pfeile in Graf1, deren Heck ein Pfeil in Graf0 ist, oder deren Heck ein Pfeil in Graf1 ist, dessen Heck ...) und enthalten dann weitere Information, die letztendlich sich auf den Pfeil in Graf0 bezieht, der die Wurzel des Baumes ist, an dem dieses Kind hängt.

Es fällt mir sehr schwer, das verständlich in deutscher Sprache zu formulieren.
cronoik hat geschrieben: ↑ zum Beitrag ↑
16.11.2018 02:47:36
Falls du dem zustimmst, dann nennt sich das extended property graph model und wurde an der Uni Leipzig entwickelt [1].
Sehr interessant.
Vllt habe ich so etwas wie das Property Graph Model (gained wide acceptance and is used in many graph database systems) neu erfunden, das mit Extended Property Graph Model erweitert wurde.

Ich bin gerade dabei, mich durch das Ding aus Leipzig hindurchzuknuspern. Leider ist das noch für mich recht verwirrend.
Ich frage mich, wie das konkret bei EPGM gespeichert wird. Von Hadoop habe ich schon mal etwas gehört, aber der Rest ist mir völlig neu.

Seid ihr beiden cronoik und bluestar im Bereich EPGM bewandert, und kann ich mich mit euch über Einzelheiten dazu unterhalten?
Ich hänge gerade bei Seite 3 und habe schon bemerkt, dass in der Grafik oben auf Seite 3 im grünen Kasten 0 vmtl vertexCount : 2 heißen muss.
Zuletzt geändert von Lohengrin am 17.11.2018 22:19:39, insgesamt 2-mal geändert.
Harry, hol schon mal das Rasiermesser!

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 17.11.2018 05:23:43

Ich habe mich gerade durch das Ding aus Leipzig hindurchgeknuspert.
Mich stört es, dass da zwischen Vertex, Edge und Graph unterschieden wird, die dann auch noch ihre eigenen Indexe haben. Außerdem verstehe ich nicht, warum zwischen Label und Property unterschieden wird.

EPGM würde ich in Senftenberg wie folgt modellieren.
Sei (x) der Hash von x.

Es gibt einen Punkt, an dem die Vertexe hängen. Sein Name ist (Vertex).
Das Vertex mit Index i, also v_i, ist das an (Vertex) hängende (i). Am an (Vertex) hängenden (i) hängen die Property-Keys von v_i, ein Property-Key heißt (Label). Am an (Vertex) hängenden (i) hängenden Property-Key hängen die dazugehörigen Property-Values.
Wenn es zu einem Property-Key genau einen kurzen Eintrag gibt, zB eine Zahl, kann man die auch als Zusatz am am (Vertex) hängendem (i) hängendem Property-Key angeben. Gibt es mehrere kurze Einträge, kann man als Property-Values Salze dranhängen, und zu jedem Anhang mit Salz einen Zusatz.

Es gibt einen Punkt, an dem die Edge hängen. Sein Name ist (Edge).
Das Edge mit Index k, also e_k, ist das an (Edge) hängende (k). Am an (Edge) hängenden (k) hängen die Property-Keys von e_k, ein Property-Key heißt (Heck) und einer heißt (Bug). Wenn E_k=<v_i,v_j> dann gibt es ein am (Edge) hängenden (k) hängenden (Heck) hängendes ((Vertex)(i)) und ein am (Edge) hängenden (k) hängenden (Bug) hängendes ((Vertex)(j)).

Es gibt einen Punkt, an dem die Graphe hängen. Sein Name ist (Graph).
Das Graph mit Index m, also G_m, ist das an (Graph) hängende (m). Am an (Graph) hängenden (m) hängen die Property-Keys von G_m, ein Property-Key heißt (Inhalt). Am an (Graph) hängenden (m) hängenden (Inhalt) hängen die ((Vertex)(i)) und die ((Edge)(k)).

Es gibt einen Punkt, an dem die Collection hängen. Sein Name ist (Collection).
... das gleiche Spiel.

Die Indexe kommen sich nicht ins Gehege, weil zB ((Vertex)(i)) == ((Edge)(k)) eine Kollision beim Hash wäre.

Ich habe gerade Vertex, Edge, Graph und Collection künstlich nachgebaut, weil das im EPGM so ist. Nötig ist das nicht.
Alles ist Anhang. Und Anhänge können Anhänge haben. Mehr ist nicht nötig.

Ich stehe doch jetzt irgendwie auf dem Schlauch. Das kann doch alles nicht wahr sein. Wo ist mein Denkfehler?
Die bauen doch nicht in Leipzig so einen Apparat, wenn es nicht nötig wäre.
Harry, hol schon mal das Rasiermesser!

eggy
Beiträge: 3331
Registriert: 10.05.2008 11:23:50

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von eggy » 17.11.2018 08:02:40

Ich hatte beim Lesen Probleme Deiner Beschreibung zu folgen.

In der Literatur ist es üblich den Graph formal zu benennen:
G = (V, E, .. )
V:= Vertices (Knoten; "Punkte")
E:= Edges (Kanten; "Pfeile" im gerichteten Graph)
... alles was Du noch brauchst.
Und dann wäre es hilfreich anfangs mal zu sagen, ist das ein gerichteter Graph, oder ein ungerichteter?

Du benutzt sowohl Kante als auch Pfeil, ist das bei dir das selbe?

Und was soll das mit dem Salz? Woher stammt es? Das wird aus dem Text nicht deutlich.

Zur Hashfunktion, Du schreibst, dass es egal sei, welche das sei (3.9).
"Nimm die Größe der Datei, bilde alle Dateien mit gerader Anzahl von Bytes auf A, alle anderen auf B ab." wäre auch eine Hashfunktion. Später (3.1) verlangst Du indirekt, dass sie (annähernd) kollisionsfrei sein müsse.

Ähnliches für Anhang (3.2): wenn ich (A,C) habe folgt daraus AC, klar soweit. Aber wie geht Dein System damit um, wenn ich aus (AB,C) ABC erzeuge und aus (A,BC) ebenfalls ABC? Das wird aus dem Text nicht klar. Insbesondere da Du von "praktisch eindeutigen Namen" sprichst.

Korrigiere mich bitte, falls ich da einem Irrtum verfallen bin, aber ich hab es so verstanden, dass ich beliebige Dinge verknüpfen kann. Demnach sollte ich auch in der Lage sein, einen Kreis zu bauen. Nehmen wir das Dateisystembeispiel: ich sollte ohne Probleme einen längeren Dateipfad von / nach /a/b/c/d/.../aa/ab/.../aaa/aab/.../zzz bauen können. Oder wenn ich irgendwo das letzte Verzeichnis wieder nach oben zu "/" verlinke, habe ich einen schönen Kreis. Jetzt schreibst Du aber in 6.1.0, dass die Anzahl der #-Teil auf 64 begrenzt sei. Demnach sollte ich keinen Kreis und auch kein Dateisystem mit einer Pfadtiefe von 65 und mehr beschreiben können. Oder war das ganz anders gemeint und bezieht sich auf die Anzahl der Dateien im Verzeichnis? Auch dann erscheint es mir nicht praktikabel.

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 17.11.2018 13:54:49

eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Ich hatte beim Lesen Probleme Deiner Beschreibung zu folgen.
Das verstehe ich sehr gut.
Es ist mir sehr schwer gefallen, das überhaupt in deutscher Sprache zu formulieren, und sehr viel gefällt mir nicht. Es ist immer die Gratwanderung zwischen zuviel und zuwenig Präzision.
Das Nachvollziehen muss für andere fürchterlich sein.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
In der Literatur ist es üblich den Graph formal zu benennen:
G = (V, E, .. )
V:= Vertices (Knoten; "Punkte")
E:= Edges (Kanten; "Pfeile" im gerichteten Graph)
... alles was Du noch brauchst.
Und dann wäre es hilfreich anfangs mal zu sagen, ist das ein gerichteter Graph, oder ein ungerichteter?
Es ist ein gerichteter Graf. Ich habe versucht, nie Kante, immer Pfeil zu schreiben.
Das mit der Angabe der Punktmenge ist sehr interessant. Ich nehme irgendwelche Elemente (Begriff von mir), was bei SHA-256 irgendwelche 43 Base64-Zeichen sind. Wenn man es formal definieren will, ist es bei SHA-256 isomorph zu 64^43.

Die Pfeile heißen bei mir Anhang, sind selber Punkte. Ein Pfeil mit Heck A und Bug B ist das an A hängende B. Es ist (AB), also der Hash vom hintereindandergeschriebenen A und B, also ein Element. Jeder Pfeil ist bei mir auch ein Punkt.
Das hoffte ich in Punkt 3.2 verständlich formuliert zu haben.

Gibt es für so ein Konstrukt schon einen mathematischen Begriff?
Analog: Punkte N (natürliche Zahlen). Pfeile Teilmenge von NxN. Und dann mit einer Abzählung N -> NxN die Pfeile in die Punkte einbetten. 8O
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Du benutzt sowohl Kante als auch Pfeil, ist das bei dir das selbe?
Ich habe, als ich mich auf EPGM bezog, Edge geschrieben, weil das der Begriff ist, den die Leipziger verwendet haben.
Auf deutsch hätte ich Pfeil und nicht Kante gesagt.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Und was soll das mit dem Salz? Woher stammt es? Das wird aus dem Text nicht deutlich.
Das stammt aus /dev/urandom
Wenn ich einen Sicherungspunkt mache, kann es sein, dass in der Info Elemente entstehen, die, bis auf das Salz, den gleichen Inhalt haben, wie etwas, das es schon gibt. Wenn ich dann zum Sicherungspunkt zurückgehe, und die neugemachten lösche, habe ich ein Problem. Ich müsste so etwas wie einen Hardlinkcounter mitführen.
Beim EPGM ist mir mal wieder aufgefallen, wie nützlich das Salz ist. Wenn ich eine neue Person baue, dann braucht die einen eindeutigen Index, einen, den es noch nie gab. Da nehme ich Salz.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Zur Hashfunktion, Du schreibst, dass es egal sei, welche das sei (3.9).
"Nimm die Größe der Datei, bilde alle Dateien mit gerader Anzahl von Bytes auf A, alle anderen auf B ab." wäre auch eine Hashfunktion. Später (3.1) verlangst Du indirekt, dass sie (annähernd) kollisionsfrei sein müsse.
Die muss praktisch kollisionsfrei sein. Daran hängt alles. Sonst geht mir das System von Infoelementen kaputt und vieles mehr.
Das war wieder die Gratwanderung zwischen zuwenig und zuviel Präzision.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Ähnliches für Anhang (3.2): wenn ich (A,C) habe folgt daraus AC, klar soweit.
Im pdf unterstrichen und hier eingeklammert bedeutet "Hash von". AC sind 2*L Base64-Zeichen. (AC) sind L.
Auf Blatt Papier habe ich Hash mit Violinschlüssel davor und spiegelverkehrtem Violinschlüssel dahinter geschrieben. Ich brauche irgendwelche Klammern, die noch nicht vergeben sind. Runde Klammern sind blöd, weil mehrdeutig, aber mir fällt hier im Forum nichts Besseres ein.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Aber wie geht Dein System damit um, wenn ich aus (AB,C) ABC erzeuge und aus (A,BC) ebenfalls ABC?
((AB)C), (A(BC)) und (ABC) ist jeweils ein Element. Und wenn zwei davon gleich sind, habe ich eine Kollision beim Hash.
Das ist nicht assoziativ.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Korrigiere mich bitte, falls ich da einem Irrtum verfallen bin, aber ich hab es so verstanden, dass ich beliebige Dinge verknüpfen kann. Demnach sollte ich auch in der Lage sein, einen Kreis zu bauen.
Der Graf, über den Information gespeichert wird, kann Kreise haben. Aber die beteiligten Pfeile sind paarweise verschieden.
In einer Kette von A ist das an B hängende C, D ist das an A hängende E, F ist ..., ..., G ist ..., H ist das an G hängende I gibt es keinen Kreis, denn das wäre eine Kollsion beim Hash.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Nehmen wir das Dateisystembeispiel: ich sollte ohne Probleme einen längeren Dateipfad von / nach /a/b/c/d/.../aa/ab/.../aaa/aab/.../zzz bauen können.
Ich habe geschrieben, dass es für hundert Millionen Infoelemente praktisch sei, diese in Verzeichnissen mit vier Ebenen zu speichern.
Weil Hash bunt ist, wäre dann in jedem untersten Verzeichnis so umme 6 Dateien, und das ganze Ding wäre etwa ein halbes Tebibyte groß.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Jetzt schreibst Du aber in 6.1.0, dass die Anzahl der #-Teil auf 64 begrenzt sei.
Wenn es 20 an A hängende B_i gibt, dann ist es schon recht wahrscheinlich, dass es zwei gibt, wo B_i und B_j mit demselben Base64-Zeichen b_0 beginnen. Dann hat das Verzeichnis (A)A#...#... weniger als 20 #-Teile, und einer davon ist #b_0. Das größte, was da vorkommt, ist gut 20 lange und etwa 40 kurze.
eggy hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 08:02:40
Oder war das ganz anders gemeint und bezieht sich auf die Anzahl der Dateien im Verzeichnis? Auch dann erscheint es mir nicht praktikabel.
Es bezieht sich auf die Anzahl der #-Teile im Verzeichnis, wobei Verzeichnis ein Zeilen-Sorte ist, die in Infoelementen vorkommt.
Das Dateisystem, wo die Infoelemente gespeichert werden, und die Zeilen in den Infoelementen sind zwei verschiedene Sachen.
Harry, hol schon mal das Rasiermesser!

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 18.11.2018 20:28:27

Kennt sich hier jemand mit dem Property Graph Model aus?

Ich habe den Eindruck, dass das ein Konzept ist, wo man an Pfeile (Edge) Eigenschaften (Property) und Zettel (Label) hängen kann, und wo man an einen Punkt (Vertex) A einen Henkel hängt, nämlich einen Pfeil von A nach A, an den man auch wieder Eigenschaften und Zettel hängen kann. (Ist das so korrekt?)
Das Extended Property Graph Model hat das Property Graph Model so erweitert, dass man auch an Grafen (Logical Graph) Eigenschaften und Zettel hängen kann.

Wie sind im PGM die Punkte und Pfeile, Eigenschaften und Zettel, und wie sind im EPGM die Punkte, Pfeile, Grafen, Eigenschaften und Zettel konkret gespeichert?
Ich vermute, dass das wieder eine gewöhnliche Datenbank ist.

Senftenberg ist so etwas wie eine Datenbank, das auf PGM und EPGM zugeschnitten zu sein scheint.
Ich habe an etwas noch Allgemeineres als PGM und EPGM gedacht, und dazu etwas passendes Datenbankartiges gebaut. Hätte ich vorher schon etwas von PGM oder EPGM gehört, dann wäre wohl einiges anders gelaufen. Aber es ist jetzt so wie es ist.

Bei Senftenberg wird irgend ein Hashcode A an irgendeinen Hashcode B angehängt, und der Anhang ist wieder ein Hashcode, nämlich (AB), der Hashcode vom hintereinandergeschriebenen A und B.
Der Anhang ist, weil er ein Hashcode ist, bunt. Er ist kurz und schnell findbar, nämlch gemäß Hashtable. Zum Anhang (AB) wird A, B und optional ein kurzer Zusatz gespeichert.
Wenn ein Anhang (AB) gespeichert wird, wird auch zum A das B gespeichert. Da die B bunt sind, geht das kurz und schnell findbar, nämlich wieder gemäß Hashtable. Das geschieht in den Verzeichnissen.
Die gesamte Information, die Senftenberg speichert, ist in Infoelemente gestückelt, die meistens unter 4 und selten unter 8 KiB groß sind. Diese Infoelemente haben wieder Hashcodes als Namen und sind kurz und schnell findbar, nämlich wieder gemäß Hashtable.

In Senftenberg bilden die Anhänge selber keinen Baum, denn in einem Baum ist ein Weg die Verkettung von Pfeilen, wobei der Bug des einen Pfeils das Heck des anderen Pfeils ist.
Bei Senftenberg gibt es den Anhang ((AB)C), was das an (AB) hängende C benennt, und weil (AB) das an A hängende B ist, ist ((AB)C) das am an A hängenden B hängende C. Das ist kein Weg in einem Graf. Wenn man das als Pfeile beschreiben will, ist das ein Pfeil, dessen Heck ein Pfeil ist.
Wenn man das als Graf darstellt, ist bei SHA-256 die Punktemenge {A,...,Z,a,...,z,0,...,9,+,/}^43, und ein Anhang ist selber wieder ein Punkt, der aber einen Pfeil benennt. Die Gesamtheit der Anhänge benennt Pfeile, die aber anders als Wege zusammen gehören.
Ich weiß nicht, wie man aus Anhängen sinnvoll Bäume konstruieren kann, denn ((AB)C) und (A(BC)) sind verschieden, keines von beiden stellt die zwei Anhänge (AB) und (BC) oder den Anhang ((AB)(BC)) dar. Und (ABC) ist noch nicht einmal ein Anhang. Das ginge höchstens mit rotem Pfeil von A nach (AB) und blauem Pfeil von B nach (AB), womit ich dann einen Property-Baum hätte. Oder ich nehme davon nur die roten Pfeile (das hatte ich im Kopf, als ich es zuerst als Baum bezeichnet hatte).

Mglw stehe ich immer noch auf dem Schlauch, denn ich kann nicht erkennen, wo ich einen Denkfehler gemacht habe.
Das Ding aus Leipzig muss mit Senftenberg ausprobiert werden. Leider bin ich ein miserabler Programmierer, habe kaum Erfahrung.
Harry, hol schon mal das Rasiermesser!

cronoik
Beiträge: 2049
Registriert: 18.03.2012 21:13:42
Lizenz eigener Beiträge: GNU Free Documentation License

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von cronoik » 22.11.2018 15:21:46

Lohengrin hat geschrieben: ↑ zum Beitrag ↑
16.11.2018 19:11:35
...Seid ihr beiden cronoik und bluestar im Bereich EPGM bewandert, und kann ich mich mit euch über Einzelheiten dazu unterhalten?
Ich hänge gerade bei Seite 3 und habe schon bemerkt, dass in der Grafik oben auf Seite 3 im grünen Kasten 0 vmtl vertexCount : 2 heißen muss.
So weit wuerde ich nicht gehen, aber ich habe schon einmal mit der Implementation, Gradoop, gearbeitet und werde dir im Rahmen meiner Moeglichkeiten antworten. Ja, vertexcount muesste 2 sein.
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
18.11.2018 20:28:27
Ich habe den Eindruck, dass das ein Konzept ist, wo man an Pfeile (Edge) Eigenschaften (Property) und Zettel (Label) hängen kann, und wo man an einen Punkt (Vertex) A einen Henkel hängt, nämlich einen Pfeil von A nach A, an den man auch wieder Eigenschaften und Zettel hängen kann. (Ist das so korrekt?)
Ja.
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
18.11.2018 20:28:27
Wie sind im PGM die Punkte und Pfeile, Eigenschaften und Zettel, und wie sind im EPGM die Punkte, Pfeile, Grafen, Eigenschaften und Zettel konkret gespeichert?
Ich vermute, dass das wieder eine gewöhnliche Datenbank ist.
Dazu gibt es keine konkrete Aussage. Das ist ein Konzept wie ein B-Baum und kann implementiert werden wie man moechte. Bei der Implementation Gradoop, handelt es sich um eine Erweiterung von Apache Flink [1] und das zielt in erster Linie auf die Verarbeitung von Streams (auch wenn Batch jetzt etwas mehr in den Fokus kam).
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
18.11.2018 20:28:27
In Senftenberg bilden die Anhänge selber keinen Baum, denn in einem Baum ist ein Weg die Verkettung von Pfeilen, wobei der Bug des einen Pfeils das Heck des anderen Pfeils ist.
Bei Senftenberg gibt es den Anhang ((AB)C), was das an (AB) hängende C benennt, und weil (AB) das an A hängende B ist, ist ((AB)C) das am an A hängenden B hängende C. Das ist kein Weg in einem Graf. Wenn man das als Pfeile beschreiben will, ist das ein Pfeil, dessen Heck ein Pfeil ist.
Wenn man das als Graf darstellt, ist bei SHA-256 die Punktemenge {A,...,Z,a,...,z,0,...,9,+,/}^43, und ein Anhang ist selber wieder ein Punkt, der aber einen Pfeil benennt. Die Gesamtheit der Anhänge benennt Pfeile, die aber anders als Wege zusammen gehören.
Ich weiß nicht, wie man aus Anhängen sinnvoll Bäume konstruieren kann, denn ((AB)C) und (A(BC)) sind verschieden, keines von beiden stellt die zwei Anhänge (AB) und (BC) oder den Anhang ((AB)(BC)) dar. Und (ABC) ist noch nicht einmal ein Anhang. Das ginge höchstens mit rotem Pfeil von A nach (AB) und blauem Pfeil von B nach (AB), womit ich dann einen Property-Baum hätte. Oder ich nehme davon nur die roten Pfeile (das hatte ich im Kopf, als ich es zuerst als Baum bezeichnet hatte).
So etwas kannst du gern mal in dein Dokument aufnehmen (gern auch mit ein paar passenden Bildern). Zum Codelesen bin ich leider noch nicht gekommen.
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
18.11.2018 20:28:27
Das Ding aus Leipzig muss mit Senftenberg ausprobiert werden. Leider bin ich ein miserabler Programmierer, habe kaum Erfahrung.
Was mochtest du denn genau machen.

[1] https://flink.apache.org/
Hilf mit unser Wiki zu verbessern!

reox
Beiträge: 2459
Registriert: 06.06.2006 22:09:47
Lizenz eigener Beiträge: MIT Lizenz

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von reox » 22.11.2018 16:00:59

Lohengrin hat geschrieben: ↑ zum Beitrag ↑
17.11.2018 13:54:49
Es ist mir sehr schwer gefallen, das überhaupt in deutscher Sprache zu formulieren, und sehr viel gefällt mir nicht. Es ist immer die Gratwanderung zwischen zuviel und zuwenig Präzision.
[...]
Ich habe versucht, nie Kante, immer Pfeil zu schreiben.
Das ist zum Beispiel eher hinderlich beim lesen. Ich tu mir da schwer, wenn ich jedes mal die Begriffe "übersetzen" muss, da ich es einfach gewöhnt bin, dass es Graphen, Kanten und Knoten gibt. Auch Heck und Bug ist eher nicht gebräuchlich, eher Kopf und Fuß (siehe https://de.wikipedia.org/wiki/Gerichtet ... ndbegriffe).
Ich bin auch nicht wirklich ein Freund davon, einfach Englische Begriffe zu verwenden (obwohl es manchmal gar nicht anders möglich ist), aber ich finde man sollte dann schon die etablierten Deutschen Begriffe verwenden.

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 23.11.2018 06:28:56

reox hat geschrieben: ↑ zum Beitrag ↑
22.11.2018 16:00:59
Ich tu mir da schwer, wenn ich jedes mal die Begriffe "übersetzen" muss, da ich es einfach gewöhnt bin, dass es Graphen, Kanten und Knoten gibt.
Ich habe inzwischen den Eindruck, dass es ein ein Fehler war, überhaupt etwas von Graf zu schreiben.
Das Ding, was ich da habe, ist so ähnlich wie Graf, aber im wichtigsten Punkt anders.
reox hat geschrieben: ↑ zum Beitrag ↑
22.11.2018 16:00:59
Auch Heck und Bug ist eher nicht gebräuchlich, eher Kopf und Fuß (siehe https://de.wikipedia.org/wiki/Gerichtet ... ndbegriffe).
Dass Kopf und Fuß gebräuchlich ist, wusste ich nicht. Ich dachte da an ein gerichtetes Objekt, was ein Vorne und ein Hinten hat, und da habe ich an Schiffe gedacht. Bei Schlangen wäre Kopf und Schwanz passend.
Aber Kopf und Fuß? Das erinnert mich eher an einen Text mit Kopfzeile und Fußzeile, und dann wäre die Pfeilspitze der Fuß. Und bei Kühen sind die Füße (mehrere!) unten und der Kopf ist vorne ... Faultiere ... Schnecken ...

Danke für deine Kritik!
Ich habe beim Formulieren große Probleme und brauche dabei Hilfe.
Harry, hol schon mal das Rasiermesser!

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 23.11.2018 07:09:26

cronoik hat geschrieben: ↑ zum Beitrag ↑
22.11.2018 15:21:46
Das ist ein Konzept wie ein B-Baum und kann implementiert werden wie man moechte.
Ahja! B-Baum. Den Begriff hatte ich nicht auf Lager.
Das, was ich da gemacht habe, hat sehr viel von B-Baum.
Ich habe von ziemlich vielen verschiedenen Konzepten etwas benutzt. Das Wichtigste ist mMn die praktisch eindeutigen Namen durch Hash.
cronoik hat geschrieben: ↑ zum Beitrag ↑
22.11.2018 15:21:46
Bei der Implementation Gradoop, handelt es sich um eine Erweiterung von Apache Flink [1]
Apache Flink stand ja auch in dem Werk aus Leipzig. Leider habe ich davon noch nie etwas gehört.
cronoik hat geschrieben: ↑ zum Beitrag ↑
22.11.2018 15:21:46
So etwas kannst du gern mal in dein Dokument aufnehmen (gern auch mit ein paar passenden Bildern).
Ich habe selber noch das Problem, das Ganze sauber zu formulieren.
Graf scheint mir inzwischen das falsche Konzept zu sein. Dass die Mengen, mit denen ich hantiere, nur quasi definiert sind, ist eine Kröte, die ein Mathematiker nur schwer schluckt.
Und Bilder? Passende Bilder zu malen fällt mir noch schwerer als passende Texte zu formulieren.
cronoik hat geschrieben: ↑ zum Beitrag ↑
22.11.2018 15:21:46
Zum Codelesen bin ich leider noch nicht gekommen.
Ich befürchte, das ist fast unzumutbar, so unübersichtlich wie ich das programmiert habe. Das geht mit Sicherheit viel eleganter.
Ich werde das Ding irgendwann mal in C programmieren. So ein Ding in Bash ist doch verrückt. Hoffentlich habe ich auch weiterhin die Zeit dafür.
cronoik hat geschrieben: ↑ zum Beitrag ↑
22.11.2018 15:21:46
Was mochtest du denn genau machen.
Eigentlich war ich dabei, etwas zu bauen, das lokal HTML-Seiten zusammenstellt, die dann Blogs, Foren und dergleichen sind, wie man sie aus dem Web kennt. Die einzelnen Schnipsel sollen von verschiedenen Quellen geholt werden können, sind eindeutig durch ihren Hash identifiziert, und sind unterschrieben. Welcher Schnipsel wohin gehört, ist wieder durch Hash benannt. Die Schnipsel müssen effizient gesucht und gefunden werden. Das Caching des Web soll wieder benutzt werden können. Natürlich soll man damit auch selber Antworten erstellen und unterschreiben können, die man dann irgendwo online stellen kann.
Ich will eine Struktur haben, wo der Blogbetreiber gar nicht mehr verhindern kann, dass Kommentare erscheinen, die er nicht haben will. Dann kann er auch nicht dazu gezwungen werden, diese "zu löschen".

Bei dieser Aktion hat mir dann das Konzept gefehlt, die Datenschnipsel organisiert zu speichern. Und daraus ist dann Senftenberg geworden.

Sämtliches, das ich bisher kenne, basiert auf willkürlich vergebenen Identitäten. Das führt zwangsläufig zu Namensstreit und Unterordnung unter eine Herrschaft, auf die sich alle einigen müssen. Das fängt schon bei den IP-Nummern an, geht über DNS und Zertifikate und ist jetzt bei Twitter-Accounts.
Ich will Hashcodes als Identitäten haben. Die fallen vom Himmel, und die sind bunt, also genau richtig für B-Bäume und ähnliches.
Die Leute sollen den Hashcodes Namen geben, wie sie es gerne wollen. Das kann jeder über ein Web-Of-Trust oder dergleichen für sich selber regeln. Dann kann Schneider Böck auch nicht mehr verhindern, dass andere ihn Meckmeckmeck nennen.
Harry, hol schon mal das Rasiermesser!

reox
Beiträge: 2459
Registriert: 06.06.2006 22:09:47
Lizenz eigener Beiträge: MIT Lizenz

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von reox » 23.11.2018 07:53:38

Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 06:28:56
Ich habe beim Formulieren große Probleme und brauche dabei Hilfe.
Wenn du Probleme beim Formulieren hast, würde ich mir fachverwandte Texte durchlesen und schauen wie das dort gemacht wird. Ich habe das Problem auch immer wieder und kann mir aber gewisse Formulierungen aus Fachartikeln abschauen.
Daher würde ich mir mal die Wikipedia Seiten zum Thema Graphen, Listen, Bäume etc durchlesen. Die Begriffe sind dort (meistens) so gewählt, dass sie auch in der Fachliteratur wiederzufinden sind, bzw oft ja sogar aus Fachbüchern abgeschr... äh zitiert.
Was auch immer hilft, ist den Text vorher von jemand anderem Probelesen zu lassen. Idealerweise von jemanden der sich damit gut auskennt (Mathematiker zB) oder auch von "Laien" - die kommen oft sogar noch schneller drauf wo Texte kompliziert und unverständlich geschrieben sind.

Wegen Kopf/Fuß, Heck/Bug, ...: Grundsätzlich versteht man ja was gemeint ist, wenn du Kopf/Schwanz oder Heck/Bug verwendest. Das Problem entsteht, wenn jemand den Text ließt, der von Schiffen keine Ahnung hat und sich denkt "wo zum heck kommt der Käfer her?". Ich finds auch interessant, denn im Englischen heißen die Dinger ja head und tail. dH Fuß ist eigentlich die falsche Übersetzung... Vermutlich aus solchen gründen, werden dann sogar in Deutscher Fachliteratur die Englischen Begriffe verwendet.

eggy
Beiträge: 3331
Registriert: 10.05.2008 11:23:50

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von eggy » 23.11.2018 08:05:09

Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 06:28:56
Das Ding, was ich da habe, ist so ähnlich wie Graf, aber im wichtigsten Punkt anders.
Dann erklär doch erstmal diesen einen Punkt. Losgelöst von allem anderen.

Graph ist schon die richtige Formulierung. Nicht hauen, aber ich habe ein wenig den Eindruck, Du versuchst Dich um die Fachterminologie/Formalien zu drücken ;) ... Ist ok, aber macht es halt super schwer, Deinen Gedankengängen zu folgen. Und wird sicherlich auch einige Leute davon abhalten, sich eingehender mit Deinen Ideen zu beschäftigen.

Ein Graph an sich ist ja nur die "grundlegende" Struktur: Dinge die Verbindungen haben. (trifft bei Dir zu)
formal: G={V,E} ; wobei G der Graph ist, V die Menge der Dinge ("Vertex", Plural "Vertices", Knoten) und E die Menge der Verbindungen ("Edge", Plural "Edges", dt: Kante).
Dann fängt man an seinen Graphen zu beschreiben:
G ist gerichtet oder G ist ungerichtet. "ungerichtet" ("undirected") bedeutet, dass es, wenn es eine Kante zwischen den "Dingen" A und B gibt, dies automatisch bedeutet, dass diese Kante auch in der Rückrichtung gilt. Anderenfalls ist der Graph "gerichtet" ("directed").
Jetzt überlege mal, ob eine dieser Eingenschaften auf Dein Gebilde zutrifft. (ja, ziemlich sicher; evtl hast Du "Teilgraphen" bei denen das eine gilt, und Teile bei denen das andere besser passt).
Diese Teile kannst Du auch wunderbar "formal" beschreiben, G' ist eine Teilmenge von G für die blabla zutrifft.
Blabla wiederum sind dann die entsprechenden Eigenschaften, die geht man dann in Ruhe der Reihe nach durch. Dann nimmst Du irgendeine Definition der Grapheigenschaften, z.B. "kreisfrei" ("Du kommst von A nach B und von B nach C aber nicht von C nach A"), und schaust ob das auf Dein Gebilde zutrifft, ob es nur für Teile passt oder garnicht. Dann nimmst die nächste Eigenschaft und überprüfst auch diese und so weiter. Einfach schrittweise vortasten. Das dauert, aber am Ende hast Du eine saubere Beschreibung, der jeder, der die Fachterminologie kennt, problemlos folgen kann.
Ich denke, vieles von dem oben geschriebenen ist Dir bereits bekannt, Du bist es nur nicht gewohnt (oder weigerst Dich ;)) die übliche Terminologie zu nutzen. Ich kann verstehen, wenn Leute sagen, sie wollen in Ihrer Muttersprache kommunizieren, ja das macht es auf den ersten Blick einfacher. Leider nur auf den ersten Blick, denn man ist, wie reox es nannte, später ständig am Übersetzen zwischen den verschiedenen Begriffen. Will man effizient mit vielen Leuten sprechen, muss man sich auf eine gemeinsame Sprache einigen, die alle verstehen. Ist hier nunmal "Graphensprech". Nimm die komischen Wörter einfach mit in deinen Wortschatz auf, ist auch nichts anderes als Tür oder Fenster.

Eine ganz nette Liste der englischen Begriffe findest Du hier: https://en.wikipedia.org/wiki/Glossary_ ... #Subgraphs
der englische Wikipedia Artikel zu Graphen ist was die Eigenschaften angeht auch ganz übersichtlich https://en.wikipedia.org/wiki/Graph_(di ... thematics), in den meisten Erstsemestervorlesungen zur theoretischen Informatik werden Graphen grundlegend abgehandelt, die einen schreibens verständlicher auf, die andern nuja, ohne lange gesucht zu haben für den Einstieg z.B. http://www.thi.informatik.uni-frankfurt ... Folien.pdf , such Dir einen Foliensatz mit dem Du gut klarkommst, und versuch mal Deinen Text zu "formalisieren". Du wirst merken, dass es Stellen gibt, wo es Dir schwerer fällt, die Worte zu finden, das sind dann wahrscheinlich auch die Stellen, über die Du nochmal grübeln solltest, weil evtl doch noch Widersprüche/Schwammigkeiten enthalten sind.

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 23.11.2018 08:35:00

eggy hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 08:05:09
Graph ist schon die richtige Formulierung. Nicht hauen, aber ich habe ein wenig den Eindruck, Du versuchst Dich um die Fachterminologie/Formalien zu drücken ;) ...
Ist schon ok. Danke für deine Kritik.
eggy hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 08:05:09
Ein Graph an sich ist ja nur die "grundlegende" Struktur: Dinge die Verbindungen haben. (trifft bei Dir zu)
formal: G={V,E} ; wobei G der Graph ist, V die Menge der Dinge ("Vertex", Plural "Vertices", Knoten) und E die Menge der Verbindungen ("Edge", Plural "Edges", dt: Kante).
Da ist es schon soweit. Bei mir ist E eine Teilmenge von V. Die Unterscheidung von V und E ist künstlich, führt in die Irre.
eggy hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 08:05:09
Ich denke, vieles von dem oben geschriebenen ist Dir bereits bekannt, Du bist es nur nicht gewohnt (oder weigerst Dich ;)) die übliche Terminologie zu nutzen.
Es hat lange genug gedauert, mich gedanklich vom Graf zu lösen. Diese Trennung zwischen V und E war das, wo ich vor Bäumen den Wald nicht gesehen habe.
Der Knackpunkt ist die Unterscheidung zwischen Name und Benanntem, zwischen der Information über ein Objekt und dem Objekt. Und dass die Information selber wieder Objekt ist.
Ob man dann Knoten, Kanten oder Grafen Information anhängt, oder Information Information anhängt, ist dann die gleiche Kiste.

In meinem pdf kommen deshalb die Begriffe Knoten und Kante, auch nicht Punkt und Pfeil, vor. Ich nenne das dort Element und Anhang, wobei Anhänge Elemente sind. Anhänge haben etwas von Pfeil, aber sie sind vor allem Punkt.
eggy hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 08:05:09
in den meisten Erstsemestervorlesungen zur theoretischen Informatik werden Graphen grundlegend abgehandelt,
Ich hatte an der Uni nur wenige Veranstaltungen von Informatikern, zB den Kurs C und C++. Wie die Veranstaltung mit den Grafen hieß, weiß ich leider nicht mehr. Ich weiß nur noch, was da vorkam, nämlich aus einem Graf A einen Graf B basteln, wo die Punkte in B Wege in A sind. Und interessant wurde es, wenn man das zweimal macht, und Graf A in Graf C einbettet.
Harry, hol schon mal das Rasiermesser!

reox
Beiträge: 2459
Registriert: 06.06.2006 22:09:47
Lizenz eigener Beiträge: MIT Lizenz

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von reox » 23.11.2018 09:38:11

Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 08:35:00
Da ist es schon soweit. Bei mir ist E eine Teilmenge von V. Die Unterscheidung von V und E ist künstlich, führt in die Irre.
Das kann aber eigentlich nicht sein. Kanten und Knoten sind durchaus unterschiedliche Dinge und die Unterscheidung sinnvoll. Ich denke was du meinst ist, dass du Daten sowohl auf den Kanten als auch auf den Knoten haben kannst. Soweit ich das weiß würde man formell deshalb aber trotzdem Kanten und Knoten unterscheiden und jedem die Eigenschaft eines Datums geben.

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 23.11.2018 10:18:05

reox hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 09:38:11
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 08:35:00
Da ist es schon soweit. Bei mir ist E eine Teilmenge von V. Die Unterscheidung von V und E ist künstlich, führt in die Irre.
Das kann aber eigentlich nicht sein. Kanten und Knoten sind durchaus unterschiedliche Dinge und die Unterscheidung sinnvoll.
Bei mir nicht. Beides sind Hashcodes.
Ein Anhang ist selber ein Hashcode und benennt den Zusammenhang zweier Hashcodes, so wie ein Hashcode als Fingerabdrucke eine Datei benennt.
Wenn ich zuerst zwischen Knoten und Kante unterscheide, muss ich das Anhängen von Information zwei mal machen, nämlich einmal für Knoten und einmal für Kanten. Und dann kann man das erweitern, indem man das noch einmal für Grafen und für Sammlungen von Grafen macht.

Was ein Hashcode benennt, gehört nicht ins Modell. Das ist Anwendung.
Ich kann ein Element zu einem Knoten erklären, indem ich ihm die Eigenschaft Knotensein anhänge.
Ob ein Element Anhang ist oder sonstwas, sieht man dem Element nicht an. Wenn es Senftenberg als Anhang gespeichert hat, dann ist es ein Anhang. Ob das Element überhaupt für irgendwas Sinnvolles steht, sieht man dem Element auch nicht an. Das ergibt sich erst aus der Information, die Senftenberg gespeichert hat.

Ich benutze die Kollisionsfreiheit vom Hash. Es ist unmöglich, dass zwei verschiedene Objekte gleich heißen. Wenn sie gleich heißen, sind sie gleich. Daher brauche ich keine Datenbank, die mir mit primärem Schlüssel die Eindeutigkeit erzeugt.
reox hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 09:38:11
Ich denke was du meinst ist, dass du Daten sowohl auf den Kanten als auch auf den Knoten haben kannst. Soweit ich das weiß würde man formell deshalb aber trotzdem Kanten und Knoten unterscheiden und jedem die Eigenschaft eines Datums geben.
Ja, das macht man so. Und das macht die Sache unnötig kompliziert.

Es ist schon vorteilhaft, wenn man Knoten und Kanten beschreibt, diese zu trennen, damit man, wenn man Knoten sucht, nicht die Kanten vor der Flinte hat. Aber das geht viel besser, indem man das so macht, wie man das mit anderen Eigenschaften, die man als Suchkriterium hat, auch macht.
Wenn ich Knoten mit Personen habe, und öfters Männer suche, dann mache ich einen Knoten (Mann), und hänge die Knoten, die Personen mit Eigenschaft Mann sind, dort an. Das stört die angehängten Knoten nicht. Es gibt dann ein paar Anhänge, die, wenn man bei (Mann) sucht, gefunden werden, und auf diese Personen verweisen. Mit anderen Worten, ich baue einen Index.
Harry, hol schon mal das Rasiermesser!

reox
Beiträge: 2459
Registriert: 06.06.2006 22:09:47
Lizenz eigener Beiträge: MIT Lizenz

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von reox » 23.11.2018 10:27:05

Ok ich sehe worauf du da hinaus willst. Allerdings macht es meiner Meinung nach wenig Sinn wenn Kanten und Knoten formell als gleiche Objekte behandelt werden. Es muss schon klar sein, was eine Beziehung ist und was das Subjekt/Objekt bzw die Objekte.
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 10:18:05
Ein Anhang ist selber ein Hashcode und benennt den Zusammenhang zweier Hashcodes, so wie ein Hashcode als Fingerabdrucke eine Datei benennt.
Wenn ich zuerst zwischen Knoten und Kante unterscheide, muss ich das Anhängen von Information zwei mal machen, nämlich einmal für Knoten und einmal für Kanten. Und dann kann man das erweitern, indem man das noch einmal für Grafen und für Sammlungen von Grafen macht.
Ich vermute du meinst damit, es gibt zwei hashcodes A, B element V und einen hashcode C element E, wobei C die Verbindung A->B speichert.
Das tolle an der formalen Beschreibung ist, dass sie mit der tatsächlichen Implementation ja nur insofern was zu tun haben muss, als dass sie abbildbar ist.
Wieso du das Anhängen zwei mal machen müsstest sehe ich jetzt nicht unbedingt. Wenn aus C eindeutig hervorgeht, dass A->B, musst du ja gar nichts doppelt anhängen. Trotzdem ist es formal aber definiert.

eggy
Beiträge: 3331
Registriert: 10.05.2008 11:23:50

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von eggy » 23.11.2018 10:33:36

Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 10:18:05
Ich benutze die Kollisionsfreiheit vom Hash. Es ist unmöglich, dass zwei verschiedene Objekte gleich heißen.
Ich befürchte, da überschätzt Du die Fähigkeit der allgemeinen Hashfunktionen: "seeeeeeeeeeehr unwahrscheinlich" aber nicht "unmöglich". Willst Du Kollisionsfreiheit erreichen, bräuchtest Du eine 1:1 Zuordnung für unendlich viele Objekte. Und damit wären Deine durch die Hashfunktion erzeugten Objekte auch unendlich lang, das ist eher unpraktisch wenn man damit arbeiten will ;)
Auch wenn für eine bekannte Hashfunktion gilt: theoretisch kannst Du damit jedem Sandkorn im Universum einen eigenen Hashwert zuweisen, aber es ist leider immer noch so, dass Dir niemand garantieren kann, dass in der Praxis nicht trotzdem eine Kollision bei den ersten zwei Sandkörnern auftritt.

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 23.11.2018 10:39:08

eggy hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 10:33:36
Ich befürchte, da überschätzt Du die Fähigkeit der allgemeinen Hashfunktionen: "seeeeeeeeeeehr unwahrscheinlich" aber nicht "unmöglich".
Korrekt. Es ist nur praktisch kollisionsfrei. Und das ist die Kröte, die ein Mathematiker nur sehr widerwillig schluckt. Aber mir reicht es, wenn es praktisch funktioniert.
Harry, hol schon mal das Rasiermesser!

Benutzeravatar
Lohengrin
Beiträge: 3227
Registriert: 29.08.2004 00:01:05
Wohnort: Montsalvat

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von Lohengrin » 23.11.2018 13:25:49

reox hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 10:27:05
Ok ich sehe worauf du da hinaus willst. Allerdings macht es meiner Meinung nach wenig Sinn wenn Kanten und Knoten formell als gleiche Objekte behandelt werden. Es muss schon klar sein, was eine Beziehung ist und was das Subjekt/Objekt bzw die Objekte.
Wozu der Unterschied?
Kanten sind Objekte, die Knoten benennen und weitere Eigenschaften haben. Wieso wird so etwas gesondert berücksichtigt? Objekte die drei Knoten benennen, haben auch keine Sonderstellung.
Bei mir sind sowohl Knoten als auch Kanten Elemente. Denen kann man alles Mögliche anhängen, insbesondere auch einen Bezug zu einem anderen Objekt.
Wenn man will, kann man einem Teil der Elemente die Eigenschaft Knotensein anhängen, und von anderen Elementen verlangen, dass ihnen genau zwei Bezüge zu jeweils einem Element, das Knoten ist, anhängt, und ihnen die Eigenschaft Kantesein anhängen.
Nur wozu diese Einschränkung? Damit man sie überwinden muss, wenn man auf die Idee kommt, Elemente zu bauen, an denen mehrere Knoten und mehrere Kanten hängen, damit man auch Grafen Eigenschaften anhängen kann, also EPGM machen kann?

Der Unterschied zwischen Knoten und Kanten ist Anwendung. Das gehört nicht hartverdrahtet ins Konzept.

Wenn man das unbedingt als Graf beschreiben will, habe ich eine Abstraktionsebene mehr. Ich nehme Graf0 mit Knoten und Kanten (und meinetwegen logischen Grafen und Sammlungen), die Eigenschaften (Key-Value-Paare) und Label (auch nur eine Eigenschaft, wo Value irrelevant ist) haben. Daraus mache ich Graf1, wo jedes Objekt aus Graf0, egal ob Knoten, Kante, oder Eigenschaft ein Knoten ist, und Kanten, die zB einen Knoten aus Graf0 mit seinem Label verbinden.
Ein Knoten aus Graf0 sollte angegeben haben, welche Kanten aus Graf0 an ihm andocken. Das sind Kanten in Graf1. Der Fuß (meinetwegen Fuß) ist der Knoten in Graf0 und der Kopf (meinetwegen Kopf) ist die Kante in Graf0. Ob ein Knoten in Graf0 eine Eigenschaft hat, oder ob an ihm eine Kante andockt, ist das Gleiche, nämlich eine Kante in Graf1.
Da die Kanten in Graf1 auch Knoten in Graf1 sind, können die wieder Fuß oder Kopf einer Kante sein.
Senftenberg speichert zu einem Knoten in Graf1, der auch Kante in Graf1 ist, was sein Fuß und was sein Kopf ist (Anhang). Und Senftenberg speichert zu einem Knoten in Graf1, welche Kanten in Graf1 von ihm abgehen (Verzeichnis).
Was ein Knoten in Graf1, der nicht Kante in Graf1 ist, zu bedeuten hat, ist Anwendung, gehört nicht zu Senftenberg. Das ist etwas für den, der Senftenberg benutzt. Der wird das berücksichtigen, wenn er sich von einem Knoten in Graf0 über eine Kante in Graf0 zu einem Knoten in Graf0 hangelt. Das ist in Senftenberg eine Hangelei über mehrere Knoten in Graf1, zB Alice -> Alice.Füße -> "Alice kennt Bob" -> "Alice-kennt-Bob".Kopf -> Bob. Für Senftenberg sind die Knoten in Graf1 nur Hashcodes. Was die zu bedeuten haben, muss der Benutzer wissen. Senftenberg interessiert sich weder für Alice noch für In-Graf0-Kante-Sein.

Mag ja sein, dass man Senftenberg für einen monströsen Fall über Hadoop organisieren kann. Aber eine Millarde Anhänge mit allem Drum und Dran sind nur ein paar hundert Gigabyte.
reox hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 10:27:05
Ich vermute du meinst damit, es gibt zwei hashcodes A, B element V und einen hashcode C element E, wobei C die Verbindung A->B speichert.
Ja. Aber E ist auch noch Teilmenge von V. Der Unterschied ist nur, dass Senftenberg C als Anhang gespeichert hat, konkret ist Hash(AB)AB gespeichert. Man kann diese Zeile erfragen. Zu A ist vermutlich nichts gepeichert. Aber zu Hash(A) ist etwas gespeichert, nämlich Hash(A)A#...#B... oder so ähnlich (Verzeichnis). Auch das kann man erfragen.

Ich sehe leider keinen Nutzen darin, das über Graf1 zu beschreiben. Es führt nur dazu, dass man Graf1 mit Graf0 verwechselt. Und es erweckt den Eindruck, dass die Kanten in Graf1 keine Knoten in Graf1 seien.
Die Verzeichnisse sind übrigens auch noch Hashcodes, also auch Knoten in Graf1. Es spricht nichts dagegen, Anhänge zwischen Verzeichnissen zu bauen. Wenn der Benutzer meint, dass das für irgendwas gut sei, soll er es doch tun.
reox hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 10:27:05
Wieso du das Anhängen zwei mal machen müsstest sehe ich jetzt nicht unbedingt. Wenn aus C eindeutig hervorgeht, dass A->B, musst du ja gar nichts doppelt anhängen. Trotzdem ist es formal aber definiert.
Ich meinte, dass man, wenn man einmal Knoten mit Eigenschaften versieht und dann Kanten auch noch, die beiden aber getrennt verwaltet, das zweimal machen muss. PGM macht da einen Trick. Die hängen an einen Knoten einen Henkel, also eine Kante mit diesem Knoten als Fuß und als Kopf, und hängen die Eigenschaft an den Henkel. Aber der Trick geht nicht mehr, wenn man auch noch Eigenschaften an logische Grafen hängen will (EPGM).
Harry, hol schon mal das Rasiermesser!

reox
Beiträge: 2459
Registriert: 06.06.2006 22:09:47
Lizenz eigener Beiträge: MIT Lizenz

Re: Senftenberg, ein ungewöhnliches Konzept

Beitrag von reox » 23.11.2018 13:45:06

Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 13:25:49
Wozu der Unterschied?
Kanten sind Objekte, die Knoten benennen und weitere Eigenschaften haben. Wieso wird so etwas gesondert berücksichtigt? Objekte die drei Knoten benennen, haben auch keine Sonderstellung.
Genau dort: Eine Kante in einem Graphen verbindet genau zwei Knoten. Nicht mehr, nicht weniger.
Wenn du ein System hast, in dem Tripel von Knoten verbunden werden, dann musst du bei der Formalisierung eben ein neues Element einführen, das schlussendlich wieder Knoten und Kanten enthält (ok, ich muss dazu sagen, dass Theoretische Informatik und Logik auch wieder ne Zeit her ist und ich jetzt nicht der Pro in Formelle Methoden bin...)
zB kannst du dann sagen dass T ein 3-Tuple ist, welches drei Knoten enthält, zB T(A, B, C). oder du kannst auch sagen, dass X ein n-Tupel ist mit X(A_1, A_2, ..., A_n).
Jetzt kannst du einen Schritt weiter gehen und zB ausdrücken, dass du solche Tupel auch in einem Graphen darstellen kannst. Vorher hast du ja keine Kanten gehabt, bzw gebraucht.
Angenommen ich nehme mal den 3-Tupel Fall, dann kann ich sagen, dass der Graph G={V, E} mit V={A, B, C} und E={AB, AC, BC, BA, CB, CA} das Ding beschreibt. Man kann sich auch noch überlegen ob die Knoten mit sich selber in Beziehnung stehen sollen oder nicht. Nimmt man jetzt ein zweites 3-Tupel mit C, D, E, so kann man den Graphen erweitern, dass V={A, B, C, D, E} und E={AB, AC, BC, BA, CB, CA, CD, CE, DE, DC, EC, ED}.
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 13:25:49
Der Unterschied zwischen Knoten und Kanten ist Anwendung. Das gehört nicht hartverdrahtet ins Konzept.
Also ich würde eher sagen, je nach dem für welchen Formalismus du dich entscheidest, sind deine Objekte eben Kanten und Knoten oder Tupel oder meinetwegen Turingmaschinen.
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 13:25:49
Wenn man das unbedingt als Graf beschreiben will, habe ich eine Abstraktionsebene mehr.
Richtig, und darum geht es ja. Wenn man es schafft sein Problem als Graph zu definieren, kann man auf einmal viele Algorithmen verwenden die auf Graphen funktionieren - Also wenn man es braucht.
In dem Fall den ich oben Konstruiert habe, kann man zB Algorithmen verwenden um zu testen ob A und E eine Verbindung haben. oder man kann sich anschauen ob Kanten doppelt sind oder ob das Ding Kreisfrei ist. Dafür gibt es wunderbare Lösungen, welche für Graphen funktionieren.
Wenn man das nicht braucht, ...
Lohengrin hat geschrieben: ↑ zum Beitrag ↑
23.11.2018 13:25:49
Ich sehe leider keinen Nutzen darin, das über Graf1 zu beschreiben.
... sind Graphen vielleicht ja eh der falsche Formalismus, ja.

Antworten