Senftenberg, ein ungewöhnliches Konzept

Vom einfachen Programm zum fertigen Debian-Paket, Fragen rund um Programmiersprachen, Scripting und Lizenzierung.
Antworten
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