Datenbankauswahl

[Philipp Kraus]

Hallo,

ich ben�tige aktuell f�r eine Projektplanung ein paar Anregungen. Ich
arbeite aktuell an einer
Simulation mit Hilfe von stochastischen Algorithmen auf einem Clustersystem.
Im Moment erarbeite ich das System f�r die Verwaltung der Daten. Jeder
Job, der durch den
Cluster berechnet werden soll, wird als eintrag in der Datenbank
gespeichert. Die Simulation
holt dann den Datensatz, berechnet diesen und schreibt die Ergebnisse
wieder zur�ck in die
Datenbank.

Als Anforderungen m�chte ich auf jeden Fall eine Verschl�sselte
Verbindung (SSL) zur Datenbank
haben und entsprechende C++ Bibliotheken zur Anbindung m�ssen zur
Verf�gung stehen.
Das Problem an sich, das ich aktuell habe, dass ich mit Graphen /
Distanzstrukturen und mehrdimensionalen
Hypercubes arbeiten muss und diese gerne nativ in der Datenbank ablegen
w�rde. Z.B. habe
ich ein Stra�ennetz, das in der Datenbank gespeichert werden muss,
wobei aber zus�tzlich weitere
Informationen zu dem Netz bzw. zu der Simulation geh�ren (Metainfos).
Ich kann hier keine reinen GPS basierte Darstellung verwenden, weil ich
aufgrund von Adjazenzmatrizen
bzw. Listen entsprechende Algorithmen anwende.
Bez�glich der Cubes kann ich diese nicht in ein relationelles Schema
umwandeln (Sternschema), weil die Cubs
pro Simulation variieren k�nnen (Olap Struktur)

Meine �berlegung war evtl etwas Hybrides zu verwenden ein ein
relationelles System f�r die Metadaten
und eine entsprechende Datenbank f�r die Cubes & Graphenstrukturen.
Sch�n w�re ein unter GPL (o.�.)
bestehendes System.
H�tte jemand ein paar sinnvolle Tips?

Danke

Phil

[Florian Weimer]

* Philipp Kraus:

> ich ben�tige aktuell f�r eine Projektplanung ein paar

> Anregungen. Ich Meine �berlegung war evtl etwas Hybrides zu

> verwenden ein ein relationelles System f�r die Metadaten und eine
> entsprechende Datenbank f�r die Cubes & Graphenstrukturen.

Es gibt PostGIS. Ob es die Algorithmen bereitstellt, die ben�tigst,
m��test Du selbst pr�fen.

[Marc Santhoff]

Am Wed, 12 Dec 2012 18:02:28 +0100
schrieb Philipp Kraus <philip...@flashpixx.de>:

> Hätte jemand ein paar sinnvolle Tips?

HDF5 und Verwandte.

Marc

[Philipp Kraus]

On 2012-12-12 21:06:36 +0100, Florian Weimer said:

> PostGIS

Ich denke ein Teil davon passt auf jeden Fall, aber ich sehe da aktuell
nicht die M�glichkeit von n-dimensionalen ggf sparse Hypercubes.
Bzw. von "nicht geographischen" Daten, wie es z.B. bei Hash-Value
Strukturen ben�tigt wird, daf�r w�re ja dann wohl so etwas wie
Cassandra sinnvoller

Phil

[Philipp Kraus]

On 2012-12-12 21:26:51 +0100, Marc Santhoff said:

> Am Wed, 12 Dec 2012 18:02:28 +0100
> schrieb Philipp Kraus <philip...@flashpixx.de>:
>

>> H�tte jemand ein paar sinnvolle Tips?
>
> HDF5 und Verwandte.

HDF5 habe ich schon im Einsatz, ist aber keine Datenbank, gerade wenn
es um shared Zugriffe auf die Datens�tze geht
Ich kann die HDF Daten als Blob in der Datenbank lagern, aber in diesem
Fall gehen auch keine shared Zugriffe

Phil

[Norbert_Paul]

Philipp Kraus wrote:
> Hallo,

> Das Problem an sich, das ich aktuell habe, dass ich mit Graphen /
> Distanzstrukturen und mehrdimensionalen
> Hypercubes arbeiten muss und diese gerne nativ in der Datenbank ablegen

> würde. Z.B. habe
> ich ein Straßennetz, das in der Datenbank gespeichert werden muss, wobei
> aber zusätzlich weitere
> Informationen zu dem Netz bzw. zu der Simulation gehören (Metainfos).

> Ich kann hier keine reinen GPS basierte Darstellung verwenden, weil ich
> aufgrund von Adjazenzmatrizen
> bzw. Listen entsprechende Algorithmen anwende.

> Bezüglich der Cubes kann ich diese nicht in ein relationelles Schema

> umwandeln (Sternschema), weil die Cubs

> pro Simulation variieren können (Olap Struktur)

Schön! Das sieht sehr nach Topologie aus!
Topologische Daten in relationalen DB ist meine Spezialität. Könntest Du
etwas genauer bezüglich der Hypercubes (== Hypercubs?) etc. sein?

* Meinst du Adjazenmatrizen (Kante-JKante, Knoten-Knoten) oder Inzidenzmatrizen
(Hyperhypervolumen-Hypervolumen, ... , Fläche-Kante, Kante-Knoten)?

* Was ist "Dimension"?

* In welchem Zusammenhang stehen die Graphen mit den Hypercubes?

* Was meinst Dum mit GPS (Global Positioninmg System?)?

* Warum genau kann ein Cube nicht relational dargestellt werden?

* Was ist ein "Sternschema"? (In der Topologie ist "Stern" oft ein
Synonym für eine minimale Umgebung)

Vielleicht kann ich Dir helfen. Meine Arbeiten sind zwar bisher sehr
theoretisch, eine Implementierung steht noch aus, aber ich freue mich
auf jede praktische Anwendung die sich findet.

Für dimensionsunabhängige Topologie kannst Du jedes relationale DBMS
benutzen, das die transitive Hülle einer Relation berechnen kann.
In PostgreSQL geht das z.B. mit WITH RECURSIVE Queries.
Ohne transitive Hülle ist deine (topologische) Dimension prinzipiell
nach oben beschränkt.

Norbert

[Norbert_Paul]

Philipp Kraus wrote:
> Hallo,

> Das Problem an sich, das ich aktuell habe, dass ich mit Graphen /
> Distanzstrukturen und mehrdimensionalen
> Hypercubes arbeiten muss und diese gerne nativ in der Datenbank ablegen
> w�rde. Z.B. habe
> ich ein Stra�ennetz, das in der Datenbank gespeichert werden muss, wobei
> aber zus�tzlich weitere
> Informationen zu dem Netz bzw. zu der Simulation geh�ren (Metainfos).
> Ich kann hier keine reinen GPS basierte Darstellung verwenden, weil ich
> aufgrund von Adjazenzmatrizen
> bzw. Listen entsprechende Algorithmen anwende.
> Bez�glich der Cubes kann ich diese nicht in ein relationelles Schema
> umwandeln (Sternschema), weil die Cubs
> pro Simulation variieren k�nnen (Olap Struktur)

Sch�n! Das sieht sehr nach Topologie aus!
Topologische Daten in relationalen DB ist meine Spezialit�t. K�nntest Du
etwas genauer bez�glich der Hypercubes (== Hypercubs?) etc. sein?

* Meinst du Adjazenmatrizen (Kante-JKante, Knoten-Knoten) oder Inzidenzmatrizen

(Hyperhypervolumen-Hypervolumen, ... , Fl�che-Kante, Kante-Knoten)?

* Was ist "Dimension"?

* In welchem Zusammenhang stehen die Graphen mit den Hypercubes?

* Was meinst Du mit GPS (Global Positioninmg System?)?

* Warum genau kann ein Cube nicht relational dargestellt werden?

* Was ist ein "Sternschema"? (In der Topologie ist "Stern" oft ein

Synonym f�r eine minimale Umgebung)

Vielleicht kann ich Dir helfen. Meine Arbeiten sind zwar bisher sehr
theoretisch, eine Implementierung steht noch aus, aber ich freue mich
auf jede praktische Anwendung die sich findet.

F�r dimensionsunabh�ngige Topologie kannst Du jedes relationale DBMS
benutzen, das die transitive H�lle einer Relation berechnen kann.

In PostgreSQL geht das z.B. mit WITH RECURSIVE Queries.

Ohne transitive H�lle ist deine (topologische) Dimension prinzipiell
nach oben beschr�nkt.

Norbert

[Philipp Kraus]

On 2012-12-13 12:12:15 +0100, Norbert_Paul said:

> Philipp Kraus wrote:
>> Hallo,
>> Das Problem an sich, das ich aktuell habe, dass ich mit Graphen /
>> Distanzstrukturen und mehrdimensionalen
>> Hypercubes arbeiten muss und diese gerne nativ in der Datenbank ablegen
>> w�rde. Z.B. habe
>> ich ein Stra�ennetz, das in der Datenbank gespeichert werden muss, wobei
>> aber zus�tzlich weitere
>> Informationen zu dem Netz bzw. zu der Simulation geh�ren (Metainfos).
>> Ich kann hier keine reinen GPS basierte Darstellung verwenden, weil ich
>> aufgrund von Adjazenzmatrizen
>> bzw. Listen entsprechende Algorithmen anwende.
>> Bez�glich der Cubes kann ich diese nicht in ein relationelles Schema
>> umwandeln (Sternschema), weil die Cubs
>> pro Simulation variieren k�nnen (Olap Struktur)

Hallo,

> Sch�n! Das sieht sehr nach Topologie aus!
> Topologische Daten in relationalen DB ist meine Spezialit�t. K�nntest Du
> etwas genauer bez�glich der Hypercubes (== Hypercubs?) etc. sein?

Es sind topologische Strukturen, die ich abbilden will

> * Meinst du Adjazenmatrizen (Kante-JKante, Knoten-Knoten) oder Inzidenzmatrizen
> (Hyperhypervolumen-Hypervolumen, ... , Fl�che-Kante, Kante-Knoten)?

Ich bezeichne Adjazenzstrukturen (Listen & Matrizen) f�r die
Repr�sentation von Graphen
im Rechner. Ich arbeite �berwiegend mit den Adjazenzmatrizen, weil auf
diese numerische
Algos anwenden kann

> * Was ist "Dimension"?

Ich hab in den meistenf�llen einen (Pseudo)-Vektorraum gegeben der als
R^n bzw C^n definiert
werden kann, wobei n dann die Dimension ist.

> * In welchem Zusammenhang stehen die Graphen mit den Hypercubes?

Sorry, das war etwas missverst�ndlich: Sie stehen in keinen
Zusammenhang ich brauche sp�ter evtl
f�r das Datenbank die M�glichkeiten sowohl Graphen als Adjazenzmatrizen
zu repr�sentieren und
ich brauche eine M�glichkeit (Pseudo)-Vektorraume �ber R bzw C
beliebiger Dimensionalit�t

> * Was meinst Du mit GPS (Global Positioninmg System?)?

Ja genau.

> * Warum genau kann ein Cube nicht relational dargestellt werden?

Mir ist aktuell keine M�glichkeit bekannt wie ich "effizient" einen
n-dimensionalen
Vektorraum in eine relationelle Darstellung �berf�hren kann, wobei das n dann
frei durch die Anwendung definierbar ist.

Ich kann zwar die Dimensionalit�t als Spalten definieren und die Zeilen
einer Tabelle
als dann einzelne Vektoren, nur die Spaltenanzahl l�sst sich nicht
dynamisch anpassen.

> * Was ist ein "Sternschema"? (In der Topologie ist "Stern" oft ein
> Synonym f�r eine minimale Umgebung)

Sorry, mein Fehler ich h�tte hier etwas pr�zisier formulieren m�ssen.
Der Begriff
Sternschema habe ich aus dem Bereich Datawarehouse genommen siehe:
http://de.wikipedia.org/wiki/Datawarehouse
http://de.wikipedia.org/wiki/Sternschema

> Vielleicht kann ich Dir helfen. Meine Arbeiten sind zwar bisher sehr
> theoretisch, eine Implementierung steht noch aus, aber ich freue mich
> auf jede praktische Anwendung die sich findet.

Das h�rt sich nett an, ich komme auch eher aus der theoretischen Arbeit,
brauche aber auch eine praktische Umsetzung.

> F�r dimensionsunabh�ngige Topologie kannst Du jedes relationale DBMS
> benutzen, das die transitive H�lle einer Relation berechnen kann.
> In PostgreSQL geht das z.B. mit WITH RECURSIVE Queries.
> Ohne transitive H�lle ist deine (topologische) Dimension prinzipiell
> nach oben beschr�nkt.

Das habe ich gesehen, habe ich mich aber noch nicht im Detail f�r die
Anwendung eingelesen.

Es geht unter anderem in meiner Anwendung um zellul�re Automaten (
http://de.wikipedia.org/wiki/Zellul�rer_Automat )
wobei ich eben eine "sinnvolle" Darstellung den kompletten Zustandsraum
ben�tige. Da ich in der Datenbank
unterschiedliche Automaten habe, soll die Dimensionalit�t flexibel sein.
Als zweites Problem kommen eben GPS Daten hinzu, wobei ich im Grunde
nicht die wirklichen Positionen brauche,
sondern im Grunde nur die Distanz zwischen zwei Punkten, was dann
letztendlich eine Matrix ergibt.

Ich "f�ttere" meine Automaten mit den Distanzdaten und m�chte die
Zust�nde der Automaten in der Datenbank speichern
Es geht um Simulationen, wobei eben die konkrete Struktur der Daten
durch die Simulation vorgegeben wird.

Vielen Dank und ich freue mich auf eine Antwort

Phil

[Norbert_Paul]

Philipp Kraus wrote:
> Es sind topologische Strukturen, die ich abbilden will

> Ich bezeichne Adjazenzstrukturen (Listen & Matrizen) für die
> Repräsentation von Graphen
> im Rechner. Ich arbeite überwiegend mit den Adjazenzmatrizen, weil auf

> diese numerische
> Algos anwenden kann

Ist das Beispiel, etwa für den Graphen,
({A,B,C,D}, {(A,B), (A,C), (B,D)}
so richtig?

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

Kann man da nicht Platz sparen, indem man nur die Einsen
speichert und die Algorithmen entsprechend modofiziert?
(Siehe weiter unten)

Wie ist die Topologie definiert. Ist das eine "Topologie"
im mathematischen Sinne?
http://de.wikipedia.org/wiki/Topologischer_Raum#Definition

Ist das die einzige Topologie? Ich hatte vermutet deine Hypercubes sind
topologisch.

>> * Was ist "Dimension"?
>

> Ich hab in den meistenfällen einen (Pseudo)-Vektorraum gegeben der als

> R^n bzw C^n definiert
> werden kann, wobei n dann die Dimension ist.

Das ist Vektorraumdimension. Da die "Dimension" dynamisch ist, sind deine
Vektorräume eigentlich R[X] und C[X], jeweils der (unendlich-dimensionale)
Vektorraum der reelen und komplexen Polynome. Übrigens ein echter Vektorraum und
nicht "Pseudo-".

Da die Anzahl der Spalten einer Tabelle in einer Datenbank stets fest ist
(bzw. fest sein sollte), musst du deine Vektoren auf immer mehrere Tupel verteilen:
Das einfachste Schema ist
Vector(vid, cid +-> value) // für R^{*} -- die "Wörter" aus reelen Zahlen ;-)
oder
Vector(vid, cid +-> realpart, imgpart) // für C^{*}
Das "+->" trennt Primärschlüssel vom Rest.

Ich betrachte nur noch R^{*}. C^{*} geht sinngemäß.

Du kannst damit ganz gut lineare Algebra mit SQL machen:
Die Vektoren v1 = (2, 5, 7, 8), v2 = (1, 0, 0, 0, 0, 7) sind dann in der
Tabelle (bei nullbasiertem Koordinatenindex):

vid cid value
1 0 2
1 1 5
1 2 7
1 3 8
2 0 1
2 5 7

Beachte, dass man Nullen einfach weglassen kann.
Zum effizienten Rechnen (effizienten Zugrif auf einzelne Vektoren)
müsstest Du noch einen (nicht unique) Index für das Attribut vid anlegen.

Dann geht:

Auswahl eines Vektors vi:

SELECT cid, value FROM Vector WHERE vid=i;


Summe: v1 + v2

SELECT cid, SUM(value) as value
FROM Vector
WHERE vid IN (1,2)
GROUP BY cid
HAVING SUM(value)!= 0.

Der Having-Teil ist optional und entfernt (überflüssige) Nullen.


Skalarprodukt v1*v2:

SELECT SUM(V1.value * V2.value) as value
FROM Vector V1, Vector V2
WHERE V1.vid = 1 AND V2.vid = 2 AND V1.cid = V2.cid

etcetc.

Du kannst auch dünn besetzte Matrizen als Relation darstellen:

Matrix(mid, row, col +-> value)

Bedenke: Eine Matrix ist ebenfalls ein Vektor. Die Koordinaten-id ist
halt nicht mehr nur eine Zahl cid sondern ein Zahlenpaar (row,col).

Damit kann man die Adjazenzmatrix so speichern:

mid row col value
1 A B 1
1 A C 1
1 B D 1

und ebenfalls die Nullen weglassen.
A, B, C können auch Zahlen (Zeilen-Spalten-Nummern) sein.
Dann kannst Du sogar mit SQL eine Vektor-Matrix-Multiplikation und Matrizenmultiplikation
machen (MIT JOIN und GROUP BY). Hier dürfte aber wieder ein Index jeweils für
(mid) -- die Matrix-id, (mid,row) und (mid,col) angebracht sein.

Ein gutes DBMS sollte diese lineare Algebra effizient durchführen können.
Vergiss nicht die Indexe. Die "Koordinatentupel" dürften auf der Festplatte
in aufeinanderfolgenden Seiten gespeichert sein und somit beim Abarbeiten der
Anfragen "en block" in den Speicher geladen werden. Das heißt, dieses
"Ein-Tupel-pro-Kooridnate" Schema dürfte recht effizient abgearbeitet werden.

Alternativ könntest Du deine Vektoren "clustern":

Vector(vid, cid +-> val0, val1, ... , valb) // für R^{*}

cid ist dann "Clusterid": bei Clustergröße 2, also b=1 sehen
v1 und v2 dann so aus:

vid cid val0 val1
1 0 2 5
1 1 7 8
2 0 1 0
2 2 0 7

Die Anfragen werden dann aber erheblich umständlicher. Ob das
schneller geht solltest Du testen. Ich vermute, der Gewinn dürfte
in keinem günstigen Verhältnis zur schlechteren Wartbarkeit des
Programms stehen. Beachte, dass die Koordinatenzahl immer Vielfache
von der Clustergröße sind. Damit brauchst Du eine zweite Tabelle, in der
die Vektordimension (Länge des Koordinatentupels) abgespeichert ist.
Umständlich!

>> * Warum genau kann ein Cube nicht relational dargestellt werden?
>

> Mir ist aktuell keine Möglichkeit bekannt wie ich "effizient" einen
> n-dimensionalen
> Vektorraum in eine relationelle Darstellung überführen kann, wobei das n

> dann
> frei durch die Anwendung definierbar ist.
>

> Ich kann zwar die Dimensionalität als Spalten definieren und die Zeilen
> einer Tabelle
> als dann einzelne Vektoren, nur die Spaltenanzahl lässt sich nicht
> dynamisch anpassen.

Ich habe gerade einen Vorschlag gemacht. Ich vermute, er ist effizient
genug. Jedenfalls ist er sehr klar und dies erleichtert die Wartbarkeit
deiner Software.

>> * Was ist ein "Sternschema"? (In der Topologie ist "Stern" oft ein

>> Synonym für eine minimale Umgebung)
>
> Sorry, mein Fehler ich hätte hier etwas präzisier formulieren müssen.

> Der Begriff
> Sternschema habe ich aus dem Bereich Datawarehouse genommen siehe:
> http://de.wikipedia.org/wiki/Datawarehouse
> http://de.wikipedia.org/wiki/Sternschema

OK. Das ist dann nicht der Stern der Topologen.


>> Für dimensionsunabhängige Topologie kannst Du jedes relationale DBMS
>> benutzen, das die transitive Hülle einer Relation berechnen kann.

>> In PostgreSQL geht das z.B. mit WITH RECURSIVE Queries.

>> Ohne transitive Hülle ist deine (topologische) Dimension prinzipiell
>> nach oben beschränkt.
>
> Das habe ich gesehen, habe ich mich aber noch nicht im Detail für die
> Anwendung eingelesen.
>
> Es geht unter anderem in meiner Anwendung um zelluläre Automaten (
> http://de.wikipedia.org/wiki/Zellulärer_Automat )

> wobei ich eben eine "sinnvolle" Darstellung den kompletten Zustandsraum

> benötige. Da ich in der Datenbank
> unterschiedliche Automaten habe, soll die Dimensionalität flexibel sein.

> Als zweites Problem kommen eben GPS Daten hinzu, wobei ich im Grunde
> nicht die wirklichen Positionen brauche,
> sondern im Grunde nur die Distanz zwischen zwei Punkten, was dann
> letztendlich eine Matrix ergibt.
>

> Ich "füttere" meine Automaten mit den Distanzdaten und möchte die
> Zustände der Automaten in der Datenbank speichern

> Es geht um Simulationen, wobei eben die konkrete Struktur der Daten
> durch die Simulation vorgegeben wird.

Das ist alles sehr vage. Zelluläre Automaten sind nicht mein Thema.
Dazu kann ich leider nichts sagen.

> Vielen Dank und ich freue mich auf eine Antwort

Hoffe ich konnte helfen. War leider keine Topologie -- nur LA.


> Phil

Norbert

[Philipp Kraus]

On 2012-12-14 11:21:40 +0100, Norbert_Paul said:

> Philipp Kraus wrote:
>> Es sind topologische Strukturen, die ich abbilden will
>> Ich bezeichne Adjazenzstrukturen (Listen & Matrizen) für die
>> Repräsentation von Graphen
>> im Rechner. Ich arbeite überwiegend mit den Adjazenzmatrizen, weil auf
>> diese numerische
>> Algos anwenden kann
>
> Ist das Beispiel, etwa für den Graphen,
> ({A,B,C,D}, {(A,B), (A,C), (B,D)}
> so richtig?
>
> |A B C D
> --+---------
> A | 0 1 1 0
> B | 0 0 0 1
> C | 0 0 0 0
> D | 0 0 0 0
>
> Kann man da nicht Platz sparen, indem man nur die Einsen
> speichert und die Algorithmen entsprechend modofiziert?
> (Siehe weiter unten)

Ja, natürlich, als sparse Struktur, aber das Problem ist, wie bekommt man wenn
so etwas in eine relationelle Datenbank hinein, wobei eben die Zeilen-
/ Spaltenanzahl
nicht in der Datenbank definiert wird, sondern durch die Anwendung

>
> Wie ist die Topologie definiert. Ist das eine "Topologie"
> im mathematischen Sinne?
> http://de.wikipedia.org/wiki/Topologischer_Raum#Definition
>
> Ist das die einzige Topologie? Ich hatte vermutet deine Hypercubes sind
> topologisch.

Ja genau

>
>
>>> * Was ist "Dimension"?
>>
>> Ich hab in den meistenfällen einen (Pseudo)-Vektorraum gegeben der als
>> R^n bzw C^n definiert
>> werden kann, wobei n dann die Dimension ist.
>
> Das ist Vektorraumdimension. Da die "Dimension" dynamisch ist, sind deine
> Vektorräume eigentlich R[X] und C[X], jeweils der (unendlich-dimensionale)
> Vektorraum der reelen und komplexen Polynome. Übrigens ein echter
> Vektorraum und
> nicht "Pseudo-".
>
> Da die Anzahl der Spalten einer Tabelle in einer Datenbank stets fest ist
> (bzw. fest sein sollte), musst du deine Vektoren auf immer mehrere
> Tupel verteilen:
> Das einfachste Schema ist
> Vector(vid, cid +-> value) // für R^{*} -- die "Wörter" aus reelen
> Zahlen ;-)
> oder
> Vector(vid, cid +-> realpart, imgpart) // für C^{*}
> Das "+->" trennt Primärschlüssel vom Rest.
>
> Ich betrachte nur noch R^{*}. C^{*} geht sinngemäß.

Das klingt sehr gut *g* das muss ich mir noch mal etwas durch den Kopf
gehen lassen,
aber das hilft definitiv schon viel weiter. Das müsste doch meines Wissens dann
auch mit nicht-euklidischen Strukturen funktionieren also z.B.
hyperbolisch, oder?
Denn letztendlich wäre ja dann nur der Vektor ein Typel mit 2 Elementen
bei einem
hyperbolischen Raum.

Das ist klar, wenn ich aber jetzt die Matrix um eine 3te Dimension erweitere
(also Würfel), würde würde man dann arbeiten (x,y,z) wäre ja dann das Tripel
um den Wert zu identifizieren. Wenn ich nun sage ich möchte eine "beliebige"
Dimension haben, also (x1,x2,....xn), dann habe ich doch wieder das Problem
wie ich das real in der Datenbank ablegen, ich kann ja nicht "beliebig"
viele Spalten
erzeugen. Für ein konstantes n, bräuchte ich dann n+1 Spalten, n für
die Adressierung
und einen für den konkreten Wert. In einem n-dimensionalen Würfel, eben
eine Tabelle
mit n+1 Spalten.

>
> Damit kann man die Adjazenzmatrix so speichern:
>
> mid row col value
> 1 A B 1
> 1 A C 1
> 1 B D 1
>
> und ebenfalls die Nullen weglassen.
> A, B, C können auch Zahlen (Zeilen-Spalten-Nummern) sein.
> Dann kannst Du sogar mit SQL eine Vektor-Matrix-Multiplikation und
> Matrizenmultiplikation
> machen (MIT JOIN und GROUP BY). Hier dürfte aber wieder ein Index jeweils für
> (mid) -- die Matrix-id, (mid,row) und (mid,col) angebracht sein.
>
> Ein gutes DBMS sollte diese lineare Algebra effizient durchführen können.
> Vergiss nicht die Indexe. Die "Koordinatentupel" dürften auf der Festplatte
> in aufeinanderfolgenden Seiten gespeichert sein und somit beim Abarbeiten der
> Anfragen "en block" in den Speicher geladen werden. Das heißt, dieses
> "Ein-Tupel-pro-Kooridnate" Schema dürfte recht effizient abgearbeitet werden.

Bei Matrizen ist das klar, das mit dem Index werde ich mir überlegen.
Aber das hilft schon mal
sehr viel weiter.

>
> Alternativ könntest Du deine Vektoren "clustern":
>
> Vector(vid, cid +-> val0, val1, ... , valb) // für R^{*}
>
> cid ist dann "Clusterid": bei Clustergröße 2, also b=1 sehen
> v1 und v2 dann so aus:
>
> vid cid val0 val1
> 1 0 2 5
> 1 1 7 8
> 2 0 1 0
> 2 2 0 7
>
> Die Anfragen werden dann aber erheblich umständlicher. Ob das
> schneller geht solltest Du testen. Ich vermute, der Gewinn dürfte
> in keinem günstigen Verhältnis zur schlechteren Wartbarkeit des
> Programms stehen. Beachte, dass die Koordinatenzahl immer Vielfache
> von der Clustergröße sind. Damit brauchst Du eine zweite Tabelle, in der
> die Vektordimension (Länge des Koordinatentupels) abgespeichert ist.
> Umständlich!

Das ist auch klar, mir geht es als Ziel darum, auch eine gute Lesbarkeit
bzw Wartbarkeit zu haben, d.h. ich denke das Clustern werden ich nicht
machen.


Ich habe leider doch etwas Bedenken, da ich ja nach diesen Schemata relativ
schmale Tabellen mit sehr vielen Elementen erzeuge, weil z.B. bei einem R^100
ein einzelner Vektor auf 100 einzelne Zeilen verteilt wird:
[ (vectorid, 1, value), ....., (vectorid, 100, value) ]
Wie würde ich das SQL technisch dann umsetzen, wenn ich z.B. alle Vektoren
mit der ID 1 bis 50 holen will, so dass ich dann aus dem SQL Result
eine spalten- oder
zeilenorientierte Matrix mit den Daten erhalte. Ich speichere eine
Menge von Vektoren
als Matrix, wobei ich fast immer Zeilenvektoren dann verwende.

Vielleicht kannst Du noch meine Bedenken etwas zerstreuen

>> Vielen Dank und ich freue mich auf eine Antwort
>
> Hoffe ich konnte helfen. War leider keine Topologie -- nur LA.

Auf jeden Fall, jedenfalls war ein perfekter Ansatz, den ich so weiter
verfolgen kann.

Phil

[Norbert_Paul]

Philipp Kraus wrote:
>> Wie ist die Topologie definiert. Ist das eine "Topologie"
>> im mathematischen Sinne?
>> http://de.wikipedia.org/wiki/Topologischer_Raum#Definition
>>
>> Ist das die einzige Topologie? Ich hatte vermutet deine Hypercubes sind
>> topologisch.
>
> Ja genau

???

>> Bedenke: Eine Matrix ist ebenfalls ein Vektor. Die Koordinaten-id ist
>> halt nicht mehr nur eine Zahl cid sondern ein Zahlenpaar (row,col).
>
> Das ist klar, wenn ich aber jetzt die Matrix um eine 3te Dimension
> erweitere
> (also Würfel), würde würde man dann arbeiten (x,y,z) wäre ja dann das
> Tripel
> um den Wert zu identifizieren. Wenn ich nun sage ich möchte eine
> "beliebige"
> Dimension haben, also (x1,x2,....xn), dann habe ich doch wieder das Problem
> wie ich das real in der Datenbank ablegen, ich kann ja nicht "beliebig"
> viele Spalten
> erzeugen. Für ein konstantes n, bräuchte ich dann n+1 Spalten, n für die
> Adressierung
> und einen für den konkreten Wert. In einem n-dimensionalen Würfel, eben
> eine Tabelle
> mit n+1 Spalten.

Das ist dann keine Matrix sondern ein Tensor. Ich denk 'mal darüber nach.

> Ich habe leider doch etwas Bedenken, da ich ja nach diesen Schemata relativ
> schmale Tabellen mit sehr vielen Elementen erzeuge, weil z.B. bei einem
> R^100
> ein einzelner Vektor auf 100 einzelne Zeilen verteilt wird:
> [ (vectorid, 1, value), ....., (vectorid, 100, value) ]
> Wie würde ich das SQL technisch dann umsetzen, wenn ich z.B. alle Vektoren
> mit der ID 1 bis 50 holen will, so dass ich dann aus dem SQL Result eine
> spalten- oder
> zeilenorientierte Matrix mit den Daten erhalte. Ich speichere eine Menge
> von Vektoren
> als Matrix, wobei ich fast immer Zeilenvektoren dann verwende.
>
> Vielleicht kannst Du noch meine Bedenken etwas zerstreuen>

Das kann ich.
Das ist gar nicht Aufgabe von SQL. Der Sinn einer Anfragesprache ist ja gerade,
dass Du dich nicht um solche Fragen kümmern musst und dich auf die Semantik der
Daten konzentrieren kannst. Sinn einer Datenbank ist es, große Datenmengen zu
speichern.

Das wird wohl als (je nach verwendeter Programmiersprache)
struct coordinate {int vid; int cid; float value}; // C
(defstruct cordinate (vid :type integer) (cid :type integer) (value 0d0 :type double-float)) ; Lisp
... # other...
sortiert nach vid, cid gespeichert werden. Vielleicht gibt es sogar DBMS, die
struct coordinate {int cid; float value};
(defstruct cordinate (cid :type integer) (value 0d0 :type double-float))
sortiert nach cid speichern und die Anfangsadresse des ersten Tupels der vid
in einem separaten Index speichern. Kompakter geht wohl kaum. Die zusätzlichen
cid kann man sicher verkraften.

Norbert

[Philipp Kraus]

Ich nutze für die Matrix / Vektor / Cube / Tupeldarstellung

http://www.boost.org/doc/libs/1_52_0/libs/numeric/ublas/doc/index.htm
http://www.boost.org/doc/libs/1_52_0/libs/multi_array/doc/index.html
http://www.boost.org/doc/libs/1_52_0/libs/tuple/doc/tuple_users_guide.html

Dass ich natürlich nicht darum herum komme, die Daten aus der Datenbank
abzufragen und in
eine entsprechende Datenstruktur zu kopieren ist klar, aber es wäre
eben sinnvoll, wenn man die
Daten aus der Datenbank schon passend als "Block" z.B. via Cursor
erhalten kann, denn
dann kann ich z.B. via memcpy einfach den Datenblock des Records in
meine Matrix
kopieren, was deutlich performanter ist, als jeden Wert einzeln zu übertragen
Sprich kann ich via SQL z.B. alle Vektoren als Zeilenvektoren erhalten
und dieses direkt
als "Matrixstruktur" in einem Resultset bekommen, dann muss ich
technisch nur einmal
den Speicherblock kopieren.

z.B.
matrix mymatrix( result->rows, result->columns )
for( result->first; result->end; result->next)
memcpy( &mymatrix(result->id, 0), &result.data,
sizeof(double)*result->columns )

oder wenn möglich direkt
memcpy( &mymatrix.data, &result.data,
sizeof(double)*result->columns*result->rows )

Ich denke es ist somit auch nicht unerhelblich, wie die Daten dann auf
Anwendungsseite
dargestellt werden.

Danke

phil

[Norbert_Paul]

Philipp Kraus wrote:
> Dass ich natürlich nicht darum herum komme, die Daten aus der Datenbank
> abzufragen und in
> eine entsprechende Datenstruktur zu kopieren ist klar, aber es wäre eben
> sinnvoll, wenn man die
> Daten aus der Datenbank schon passend als "Block" z.B. via Cursor
> erhalten kann, denn
> dann kann ich z.B. via memcpy einfach den Datenblock des Records in
> meine Matrix
> kopieren, was deutlich performanter ist, als jeden Wert einzeln zu
> übertragen

Premature optimization is the root of all evil!

> Sprich kann ich via SQL z.B. alle Vektoren als Zeilenvektoren erhalten
> und dieses direkt
> als "Matrixstruktur" in einem Resultset bekommen, dann muss ich
> technisch nur einmal
> den Speicherblock kopieren.

Noch einmal: Die effiziente Organisation der Speicherseiten ist
Sache des DBMS. Darum musst Du dich nicht mehr kümmern. Wenn doch,
wechsle lieber das DBMS.

> z.B.
> matrix mymatrix( result->rows, result->columns )
> for( result->first; result->end; result->next)
> memcpy( &mymatrix(result->id, 0), &result.data,
> sizeof(double)*result->columns )
>
> oder wenn möglich direkt
> memcpy( &mymatrix.data, &result.data,
> sizeof(double)*result->columns*result->rows )

Das sieht sehr gefährlich aus! Überprüfen dann besser, ob durch die API
abgesichert (und dokumentiert!) ist, dass Du einfach so Speicherblöcke
aus Anfrageergebnissen in eigene Strukturen kopieren und verwenden kannst?

> Ich denke es ist somit auch nicht unerhelblich, wie die Daten dann auf
> Anwendungsseite dargestellt werden.

Auf der sicheren Seite (und vermutlich auch schneller fertig) bist Du, wenn
Du eine klare Trennung zwischen der Datenbank-Seite und deiner eigenen
Anwendung machst und die Daten über eine klar definierte Schnittstelle zwischen
beiden Seiten überträgst. Erst wenn das Programm läuft, solltest Du dich um
die Flaschenhälse kümmern. Die sind nämlich oft ganz woanders als man denkt.


Ich habe übrigens eine Idee für die Tensoren:

Relatonenschema:

Tensor(id,dimId -> length)
TensorData(tid,cellId -> value)
ForeignKey(TensorData.tid -> Tensor.id)

Beispiel-Pseudocode:
Tensor t1 = new Tensor(10,7,15);
t1[i,j,k] = 3.14;

Datenbank:
Tensor: id dimid length
1 0 10
1 1 7
1 2 16
...

Tensordata: tid cellid value
1 10*7*i + 10*j + k 3.14
...

Ist allerdings etwas umständlich dafür sehr dynamisch.

Ich würde aber gerne den Thread abschließen und werde wohl keine Posts mehr
beantworten.


Ciao--Viel Erfolg.

Norbert

[Norbert_Paul]

... oder nimm einfach SQL-array.
Ich bevorzuge halt NF1-Schemata.

[Philipp Kraus]

On 2012-12-16 16:41:11 +0100, Norbert_Paul said:

> ... oder nimm einfach SQL-array.
> Ich bevorzuge halt NF1-Schemata.

ielen dank für die Antwort

Phil