Komplexe, zubuchbare Leistungen abstrahieren

[Namenloser]

[OT]

Zitat von nahpets:

Hallo Robotiker,

Zitat von Robotiker:

Zitat von nahpets:

Hallo Valle,
So, und jetzt kommt der Teil, für den ihr mich alle für vollkommen bekloppt halten dürft

Eigentlich nicht, es erinnert mich nur etwas an den Nachbau einer Graphdatenbank mit relationalen Mitteln. Auch weil du weiter oben eine Darstellung des Problems als Matrix erwähnst, das wäre dann quasi die Adjazenzmatrixdarstellung der Graphdatenbank.

Doch, ich bin bekloppt (und fühl mich wohl dabei ). Das Wort Adjazenzmatrixdarstellung habe ich ja noch nie gehört. Die Suchmaschine meiner Wahl liefert mir dazu einige Ergebnisse, überwiegend von Seiten, deren Webadressen durchaus wissenschaftlich klingen. Was soll's. Angeklickt, gelesen, nix verstanden. (Ja, schon gut, sollte mir das mal etwas entspannter an einem oder zweidreivier schönen Abenden reinziehen.)

Eine Adjazenzmatrix ist eigentlich was total einfaches. Sagen wir du hast einen Graphen mit den Knoten A,B,C und D. Zwischen zwei Knoten kann es höchstens eine Kante (Verbindung) geben.

Ein möglicher (ungerichteter) Graph wäre z.B. folgender:

Code:

A --- B
 \    |
  \   |
   \  |
    \ |
C --- D

Das kannst du aber auch so darstellen:

Code:

    A B C D
  +--------
A | 0 1 0 1
B | 1 0 0 1
C | 0 0 0 1
D | 1 1 1 0

Eine 1 in der Tabelle bedeutet einfach, es gibt eine Kante zwischen den Knoten, und eine 0 bedeutet, es gibt keine Kante.

Wenn die Kanten gewichtet sind, dann sind zusätzlich zu 0en und 1en halt noch weiterere Werte möglich. Die Zahl gibt dann an, „wie stark“ die Knoten verbunden sind.

[/OT]

[nahpets]

[OT]
Hallo NamenLozer,

das ist mir jetzt noch zu hoch.

Fahren wir mal Eisenbahn.

In Deinem Beispiel seien A, B, C, D irgendwelche Orte mit Bahnhof, ich kann damit also feststellen, von welchem Ort ich zu welchem Ort fahren kann. Also von A komme ich nach B und nach D.

Wenn wir jetzt hergehen und für A, B, C, D weitere Matrizen aufstellen, z. B. für A, E, F, G:

Code:

    A E F G
  +--------
A | 0 0 0 1
E | 0 0 1 0
F | 0 1 0 1
G | 1 0 1 0

Desgleichen noch für B, C, D und weitere Orte, so kann ich mich hier quasi von Matrix zu Matrix hangeln, um letztlich einen Weg von z. B. D nach G zu finden, der hier also über A führt, wo ich aber umsteigen muss.

Wenn ich jetzt die beiden Matrizen zusammenfasse (heißt das so?) käme dann das dabei raus?

Code:

    A B C D E F G
  +--------------
A | 0 1 0 1 0 0 0
B | 1 0 0 1 0 0 0
C | 0 0 0 1 0 0 0
D | 1 1 1 0 0 0 1
E | 0 0 0 0 0 0 0
F | 0 0 0 0 0 0 0
G | 0 0 0 1 0 0 0

Also schaue ich in A stehend wohin ich kann. Das sind B und D. Nun schaue ich für B nach, wohin ich kann, das sind A und D. das passt mir nicht. Jetzt schaue ich für D nach, wohin ich kann, das sind A, B, C und G. Und schon habe ich meine Route

(Da meldet sich im Hintergrund eine Stimme, die mich dran erinnert: Da war mal was mit Matrizenmultiplikation! - gehört das hierhin?)

Ok, ist eigentlich nix anderes, als das, was Valle hier benötigt, um die Bedingungen für Leistungen und die entsprechenden Abhängigkeiten von Buchungszeitraum ... feststellen zu können.

Eigentlich ganz einfach kompliziert oder lieber kompliziert einfach?
Oder die simple Programmiererregel: Zerlege ein Problem solange in kleinere Schritte, bist Du es umsetzen kannst.

Und das scheint mir hier beim Ferienhausbuchungsprojekt das Wesentliche zu sein, danach ist das dann "nur noch" Fleißarbeit.

@Robotiker

Zitat von Robotiker:

Oh, 'tschuldigung, ich wollte nicht mit Fachbegriffen um mich werfen. Ich dachte es wäre unter Programmieren allgemein bekannt, dass man einen Graphen nicht nur mit Kreisen und Pfeilen (Knoten und Kanten) darstellen kann, sondern auch als Tabelle mit einer Zeile und Spalte pro Knoten. Das ist die Adjazenzmatrix.

Da brauchst Du Dich nicht zu entschuldigen, es gibt im großen Netz genug Möglichkeiten zu suchen und (fast) alles an Antworten zu finden. Hat mich jetzt ja auch nur 'ne Minute gekostet. Mit Fachbegriffen stand ich schon immer auf Kriegsfuß, eigentlich habe ich von der Theorie keine Ahnung, baue aber trotzdem (verblüffenderweise) Lösungen zu Problemen, bei denen andere sagen, das geht doch garnicht. Allerdings nur im kaufmännischen Bereich, technische Erfahrungen fehlen mir vollkommen.

Das was mit neo4j gemacht werden kann ist also u. a. die optische Darstellung der Datenbankinhalte a la UML. (?) Das Bild möchte ich für das hier diskutierte Problem gerne mal sehen, um sehen zu können, ob meine Vorstellungen mit der Realität in Einklang zu bringen sind [/OT]

[Robotiker]

Zitat von nahpets:

Das was mit neo4j gemacht werden kann ist also u. a. die optische Darstellung der Datenbankinhalte a la UML.

Nein, das ist kein Grafiktool. Das ist eine Datenbank, aber ohne Tabellen, sondern mit Knoten und Kanten, an denen Eigenschaften hängen.

Man könnte mit den Kanten Beziehungen, wie "ist Zubuchoption von", "enthält", "schliesst aus", "muss kleiner sein als", usw. darstellen. Man muss das nicht in Tabellen modellieren.

Im Prinzip läuft das auf eine ähnliche Lösung hinaus, wie in dem Beitrag von Furtbichler oben, aber mit einer anderen Art von NoSQL-Datenbank und eventuell unter dem Verzicht auf explizit geschriebenen Plugins, die könnte man z.B. mit Graph Rewriting aus der Datenbank ableiten, z.B. so
http://en.wikipedia.org/wiki/GrGen

[nahpets]

@Robotiker

Zitat von Robotiker:

Zitat von nahpets:

Das was mit neo4j gemacht werden kann ist also u. a. die optische Darstellung der Datenbankinhalte a la UML.

Nein, das ist kein Grafiktool. Das ist eine Datenbank, aber ohne Tabellen, sondern mit Knoten und Kanten, an denen Eigenschaften hängen.

So hatte ich das auch nicht aufgefasst, sondern nur eher beim Ergebnis der Darstellung. Gut, da habe ich (noch) keine Ahnung. Muss ich mir mal intensiv anschauen.

Zitat von Robotiker:

Man könnte mit den Kanten Beziehungen, wie "ist Zubuchoption von", "enthält", "schliesst aus", "muss kleiner sein als", usw. darstellen. Man muss das nicht in Tabellen modellieren.

Im Prinzip läuft das auf eine ähnliche Lösung hinaus, wie in dem Beitrag von Furtbichler oben, aber mit einer anderen Art von NoSQL-Datenbank und eventuell unter dem Verzicht auf explizit geschriebenen Plugins, die könnte man z.B. mit Graph Rewriting aus der Datenbank ableiten, z.B. so
http://en.wikipedia.org/wiki/GrGen

Also eigentlich ein vollkommen anderer Weg, um das hier diskutierte Problem lösen zu können.

Bisheriges Fazit aus diesem Thread: Es gibt viele Wege nach Rom und Valle bekommt jetzt das Problem zu entscheiden, welcher Weg der für ihn der Beste ist.

[Robotiker]

Zitat von nahpets:

Bisheriges Fazit aus diesem Thread: Es gibt viele Wege nach Rom und Valle bekommt jetzt das Problem zu entscheiden, welcher Weg der für ihn der Beste ist.

Das wird bei einem solchen Thema zwangsläufig der Fall sein. Und wir haben sicher noch nicht alle Möglichkeiten ausgelotet.

Manchmal ist es aber so, wie oben bei der Graph- und Matrixdarstellung, dass man es mit zwei Seiten einer Medaille zu tun hat. Dann kann es hilfreich sein, auch mal auf die andere Seite zu schauen, sei es auch nur um das Problem besser zu verstehen.

Wenn man z.B. sehr viele n:m Beziehungen einführt (wie "enthält", "schliesst aus" usw.) und die auch noch rekursiv durchsuchen muss, dann sollte man schon mal an eine Speicherung als Graph denken, da kriegt man das dann quasi mit Automatikgetriebe.

[Namenloser]

[OT]

Zitat von nahpets:

Wenn wir jetzt hergehen und für A, B, C, D weitere Matrizen aufstellen, z. B. für A, E, F, G:

Code:

    A E F G
  +--------
A | 0 0 0 1
E | 0 0 1 0
F | 0 1 0 1
G | 1 0 1 0

Desgleichen noch für B, C, D und weitere Orte, so kann ich mich hier quasi von Matrix zu Matrix hangeln, um letztlich einen Weg von z. B. D nach G zu finden, der hier also über A führt, wo ich aber umsteigen muss.

Wenn ich jetzt die beiden Matrizen zusammenfasse (heißt das so?) käme dann das dabei raus?

Code:

    A B C D E F G
  +--------------
A | 0 1 0 1 0 0 0
B | 1 0 0 1 0 0 0
C | 0 0 0 1 0 0 0
D | 1 1 1 0 0 0 1
E | 0 0 0 0 0 0 0
F | 0 0 0 0 0 0 0
G | 0 0 0 1 0 0 0

Also schaue ich in A stehend wohin ich kann. Das sind B und D. Nun schaue ich für B nach, wohin ich kann, das sind A und D. das passt mir nicht. Jetzt schaue ich für D nach, wohin ich kann, das sind A, B, C und G. Und schon habe ich meine Route

(Da meldet sich im Hintergrund eine Stimme, die mich dran erinnert: Da war mal was mit Matrizenmultiplikation! - gehört das hierhin?)[/OT]

Ja, wenn du die Adjazenzmatrix mit sich selbst multiplizierst, dann bekommst du für jeden Knoten die Knoten, die du mit genau 2 Schritten erreichst. Wenn du dann noch mal die Matrix dranmultiplizierst kriegst du die Knoten, die du mit 3 Schritten erreichst usw...

Allerdings macht deine zusammengefasste Matrix irgendwie keinen Sinn. Da steht jetzt z.B. dass du von D nach G gehen kannst, dabei gibt es gar keine Verbindung zwischen D und G. Auf der anderen Seite müsstest du von A nach G kommen, aber da steht bei dir eine 0. Und alle anderen Verbindungen von deiner AEFG-Matrix fehlen irgendwie auch...

Ich kenn es außerdem eigentlich auch nur so, dass es eine Adjazenzmatrix gibt, in der alle Knoten-Kombinationen drin sind, und nicht mehrere Ajazenzmatrizen für Teilgraphen, die erst noch kombiniert werden müssen.

Aber ich verweise jetzt einfach mal auf diese Vorlesungsfolien (oder hier das etwas ausführlichere Skript, ab Seite 101 geht’s los), damit wir nicht noch weiter ins Off-Topic abdriften.

[/OT]

[nahpets]

@NamenLozer
[OT]
Deine Antwort zeigt mir, dass ich da wohl so einiges (ziemlich alles) nicht verstanden habe, aber dafür gibt es neuen Lesestoff, um das zu ändern Und damit genug OT.
[/OT]

[generic]

was nahpets meint lässt sich auch einfacher Ausdrücken.
Bitmap-Index

[nahpets]

Zitat von generic:

was nahpets meint lässt sich auch einfacher Ausdrücken.
Bitmap-Index

Da bin ich mir nicht sicher, da hier ja deutlich mehr als nur ja/nein abgebildet werden muss. Zumindest scheinen hier ja auch Bereiche möglich zu sein, die man nicht zwingend in eine klare ja/nein-Aufzählung auflösen kann. Auch bestehen vermutlich Abhängigkeiten von Bedingungen untereinander.

Eine Bitmap-Index ist eine spezielle Speicherstruktur, die halt für Spalten geeignet ist, die nur wenige unterschiedliche Werte (Aufzählungstyp) aufweisen. Aber den Aufzählungstyp kann ich hier nicht bei allen Bedingungen erkennen.

Aber um dies entscheiden zu können, müsste man sich mal alle Leistungen und die zugehörigen Bedingungen im Detail anschauen, für eine Teilmenge mag aber ein Bitmap-Index eine brauchbare Lösung sein.

Eventuell fehlt mir aber auch nur das Abstraktionsvermögen, um hier die Nutzungsmöglichkeit für einen Bitmap-Index erkennen zu können.

[Valle]

Hi,

nein, ich bin nicht verschwunden.

Erstmal nochmal vielen Dank für eure Antworten! Die Adjazenzmatrix hab' ich jetzt sicher verstanden. Aber wie ihr ja schon festgestellt habt, hilft diese hier nicht weiter.

Ich habe die letzte Woche genutzt um weiter unsere Anforderunngen zu evaluieren und verschiedene Problemlösungen auszutesten. Letztendlich haben wir jetzt ein (bisher gut) laufenden System mit SQL-Plugins. Ähnlich wie du, nahpets, es vorgeschlagen hast. Jedes Haus ist mit mehreren Leistungen verknüpft. Jede dieser Verknüpfungen ist mit mehreren Plugins verknüpft, für Dinge wie Preis oder Maximale Menge. Außerdem lässt sich zu jeder Plugin-Verknüpfung ein beliebiger Parameter bilden, damit nicht für jeden festen Preis ein neues Plugin erstellt werden muss.

Die Plugins habe ich tatsächlich als SQL-Funktionen geschrieben. Schön mich endlich damit mal auseinandergesetzt zu haben. Im gleichen Zug habe ich übrigens auch meine erste Stored Procedure geschrieben, um bisher vorhandene Daten ansatzweise in unser neues System einzupflegen, damit unsere Mitarbeiter nicht wirklich jede Leistung einzeln bearbeiten müssen. Die SQL-Funktionen erlauben tatsächlich eine enorme Flexibilität und haben die bisherigen Probleme auf eine schöne Art gelöst, wie ich finde. Danke dafür! Falls du mal da bist, geb ich dir ein Bier aus.

Jetzt kann man nur hoffen, dass sich in Zukunft nicht noch größere Probleme ergeben werden. Ich bin allerdings zuversichtlich, dass wir so eine gute Grundlage haben.

Liebe Grüße,
Valentin