Relationenalgebra < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) reagiert/warte auf Reaktion  | | Datum: | 15:48 Fr 07.10.2005 | | Autor: | HOST |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Hallo zusammen,
ich habe folgendes Problem:
Ich habe drei binäre Relationen [mm] R_{1}, R_{2} [/mm] := (b,a) [mm] \subset [/mm] BxA und [mm] R_{3} [/mm] := (a1,a2) [mm] \subset [/mm] AxA..
Wie bekomme ich jetzt alle a2 raus, für die gilt das alle Paare (b,a), die in [mm] R_{1} [/mm] stehen und a1 = a ist, auch in [mm] R_{2} [/mm] stehen
Ich habe folgendes probiert:
[mm] \bigwedge\limits_{a_i \in A} \bigvee\limits_{a_k \in A} \; [(b,a_i) \in R_{1} \wedge(a_i, a_k) \in R_3]
[/mm]
: [mm] \Rightarrow (b_i, a_k) \in R_{sucht} [/mm]
[mm] \mbox{mit }\bigwedge\limits_{b_i \in B}(b_i,a_k) \in R_2 [/mm]
Ich bekomme jedoch die Gleichmächtigkeit nicht hin.
Beispiel:
[mm] R_{1}={(b1,a1),(b2,a1),(b1,a2)}
[/mm]
[mm] R_{2}={(b1,a1),(b2,a1)}
[/mm]
[mm] R_{3}={(a1,a2)}
[/mm]
Ich brauche (b1,a2).
Falls mir hier jemand helfen kann, wäre das toll.
Viele Dank und viele Grüße
Stephan
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 23:29 Fr 07.10.2005 | | Autor: | DaMenge |
Hallo Stephan,
> Wie bekomme ich jetzt alle a2 raus, für die gilt das alle
> Paare (b,a), die in [mm]R_{1}[/mm] stehen und a1 = a ist, auch in
> [mm]R_{2}[/mm] stehen
Wie meinst du das [mm] a_2 [/mm] heraus bekommen?
Meinst du die Mengenschreibweise oder meinst du, wie man es mit einem PC für gegebene Relationen ausrechnen lassen könnte?
Also die Mengenschreibweise wäre sowas wie:
[mm] $\{ a_2 | (a_1,a_2)\in R_3 \wedge \exists b \in B : (b,a_1) \in (R_1 \cap R_2) \}$
[/mm]
und das ausrechnen würde ähnlich gehen - nur eben von hinten nach vorne berechnet.
allerdings verstehe ich dein Beispiel nicht:
> Beispiel:
> [mm]R_{1}={(b1,a1),(b2,a1),(b1,a2)}[/mm]
> [mm]R_{2}={(b1,a1),(b2,a1)}[/mm]
> [mm]R_{3}={(a1,a2)}[/mm]
>
> Ich brauche (b1,a2).
wieso brauchst du [mm] b_1 [/mm] dabei ? und weshalb nicht [mm] b_2 [/mm] ?
(Schließlich kommt das Paar [mm] $(b_2,a_1)$ [/mm] auch in R1 und R2 vor)
sollte ich den Sinn zu dieser späten Stunde völlig fehl-interpretiert haben, tut es mir leid, aber dann könntest du es ja nochmal anders beschreiben, was genau du suchst.
EDIT: wg. Fälligkeit auf "reagiert" gesetzt.
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Frage) beantwortet  | | Datum: | 14:43 Mo 10.10.2005 | | Autor: | HOST |
Hallo DaMenge,
zu Beginn erst einmal vielen Dank für die Antwort.
Ziel meiner Frage ist die Berechnung für gegebene Relationen mit dem PC. (Wie Du richtig vermutet hast.)
Mein Beispiel ist folgendermassen zu verstehen:
Durch Relation [mm] R_{1} [/mm] soll definiert werden, welche Elemente der Menge B in Relation zu Elementen der Menge A stehen sollen. Soweit klar. In Relation [mm] R_{2} [/mm] soll definiert werden welche Elemente der Menge B tatsächlich zu Elementen der Relation A stehen. [mm] R_2 [/mm] ist dabei eine Teilmenge von [mm] R_1. [/mm]
Im Beispiel gilt dies für die beiden ersten Paare der Relationen [mm] R_{1} [/mm] und [mm] R_{2}. (b_1,a_1) [/mm] und [mm] (b_2,a_1).
[/mm]
Da nun in den beiden Relationen beide Paare bezogen auf [mm] a_1 [/mm] vorkommen, also vollständig spezifiziert sind, möchte ich aus der Relation [mm] R_{3} [/mm] das Paar [mm] (a_1,a_2) [/mm] bestimmen, wobei [mm] a_2 [/mm] in Relation [mm] R_1 [/mm] durch das Paar [mm] (b_1,a_2) [/mm] in Relation zu [mm] b_1 [/mm] gestellt wird.
Würde in Relation [mm] R_1 [/mm] beispielsweise noch das Paar [mm] (b_3, a_1) [/mm] stehen und in Relation [mm] R_2 [/mm] nicht, würde die leere Menge als Ergebnis der Berechnung herauskommen sollen.
Das Mißverständnis meiner Frage möchte ich somit auf die fehlende Ausführlichkeit meines Beispiels schieben.
Vielen Dank und hoffentlich bis bald.
HOST
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 19:47 Mo 10.10.2005 | | Autor: | DaMenge |
Hallo Stephan,
ich muss gleich vorweg wieder eine Frage stellen:
Geht es hierbei im entferntesten um Datenbanken (also SQL, Datalog &Co ?) oder sind dir deine Relationen sonst irgendwie besonders gegeben (durch physikalische Gesetze oder oder...) oder geht es hier um wirklich große [mm] (>10^6 [/mm] ) Relationen ?!?
Dann wäre nämlich (jeweils) sofort ein anderer Ansatz sinnvoller...
Aber nun gut - und du willst tatsächlich wissen, wie man das AUSRECHNET - du willst nicht irgendwie sowas wie einen geschlossenen Ausdruck in irgendeiner Sprache ?
Wie sind dir die Mengen A und B gegeben ? Sind sie fix oder sind sie implizit über die Relationen gegeben (d.h alle zweiten Komponenten von [mm] R_1 [/mm] und [mm] R_2 [/mm] und die Komponenten von [mm] R_3 [/mm] bilden A und der Rest B) ?
Ich gehe mal von letzter Variante aus.
Ich verstehe auch noch nicht ganz, welche genauen Paare du jetzt aus [mm] R_3 [/mm] haben willst : willst du ALLE Paare, deren erste Komponente vollständig mit den Elementen aus B in [mm] R_2 [/mm] vorkommen oder nur das erst beste ?
Wie auch immer wird wohl die Hauptaufgabe sein zu finden, welche Elemente aus A vollständig mit allen Elementen von B in [mm] R_2 [/mm] vorkommen.
(dass sie zugleich in [mm] R_1 [/mm] vorkommen müssen ist ja irrelevant, denn [mm] R_2 [/mm] ist eine Teilmenge von [mm] R_1 [/mm] )
Ich würde dieses Problem so lösen :
1) Bestimme ganz A
2) "Elemeniere" alle Paare aus [mm] R_1, [/mm] die auch in [mm] R_2 [/mm] vorkommen
3) Die Elemente aus A, die noch im Rest von [mm] R_1 [/mm] (in der zweiten Komponente) stehen, sind NICHT vollständig, also "lösche" man all diese aus der Menge A
4) übrig bleibt die gesuchte Teilmenge von A, die vollständig mit allen b aus B in [mm] R_2 [/mm] in Relation steht.
[Danach müsste man zu [mm] R_3 [/mm] gehen und die Paare raussuchen, die man haben will - aber da weiß ich nicht recht, welche du haben willst]
Ist das so ungefähr, was du gesucht hast?
viele Grüße
DaMenge
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 12:29 Di 11.10.2005 | | Autor: | HOST |
Hallo DaMenge,
danke wiederum für die Antwort.
Der Sachverhalt läßt sich etwa so beschreiben.
Das Ergebnis meiner (und zur Zeit auch Deiner) Bemühungen ist
ein Programm, welches in Java geschrieben werden soll. Mit Hilfe dieses Programmes werden die Mengen (A und B mit A [mm] \cap [/mm] B = 0) und [mm] R_1, R_2 [/mm] und [mm] R_3 [/mm] spezifizert. Die Größenordnung aller Elemente sollte bei maximal [mm] 10^4 [/mm] liegen.
Um die Programmierung theoretisch sauber zu halten, versuche ich die Dinge entsprechend sauber zu formulieren, also die Vorgehensweise mit Hilfe von Operationen der Mengenlehre zu beschreiben. Also brauche ich einen geschlossenen Ausdruck, der die Vorgehensweise beschreibt. Deshalb auch mein ursprünglicher Versuch einen solchen Ausdruck zu finden. Deine erste Formulierung ging also bereits in die richtige Richtung.
Ich brauche also, um auf Deine Detailfrage zurück zu kommen, alle Paare (b,a) aus [mm] R_1, [/mm] die die beschriebenen Bedingungen erfüllen. Den diese wiederum kann ich benutzen, um [mm] R_2 [/mm] weiter zu spezifizieren, bis [mm] R_1 [/mm] und [mm] R_2 [/mm] gleich sind. Von daher ist es mir wichtig, dass sich für ein a in den Relationen [mm] R_1 [/mm] und [mm] R_2 [/mm] genau die gleichen Paare befinden, um mit Hilfe von [mm] R_3 [/mm] ein neues a zu bestimmen.
Ich hoffe das Du mir da weiterhin zur Seite stehen kannst.
Vielen Dank schon mal.
Gruß Stephan
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:07 Mi 12.10.2005 | | Autor: | DaMenge |
Hallo Stephan,
sorry - ich hatte gestern keine Zeit fuer das I-Net...
so - ich moechte uns beiden ein wenig helfen indem ich das jetzt mal mathematisiere und du musst mr dann sagen, ob ich das alles soweit richtig verstanden habe:
Erstmal die Grundmengen A und B :
Ist es richtig, dass diese implizit gegeben sind durch die Relationen?
Also - sei [mm] $(R_i)_j$ [/mm] die Menge alle j-ten Komponenten der i-ten Relation:
(Dies ist eine Projektion - also es kommen keine Elemente doppelt vor)
[mm] $A:=(R_1)_2 \cup (R_2)_2 \cup (R_3)_1 \cup (R_3)_2$
[/mm]
[mm] $B:=(R_1)_1 \cup (R_2)_1$
[/mm]
und jetzt musst du mir nochmals folgenden Satz von dir bestaetigen:
"Durch Relation $ [mm] R_{1} [/mm] $ soll definiert werden, welche Elemente der Menge B in Relation zu Elementen der Menge A stehen sollen. Soweit klar. In Relation $ [mm] R_{2} [/mm] $ soll definiert werden welche Elemente der Menge B tatsächlich zu Elementen der Relation A stehen. $ [mm] R_2 [/mm] $ ist dabei eine Teilmenge von $ [mm] R_1. [/mm] $ "
Also [mm] R_2 [/mm] ist wirklich eine Teilmenge von [mm] R_1 [/mm] , ja?
Also : [mm] $R_1 \cap R_2 [/mm] = [mm] R_2$ [/mm] , ja?
Dann ist die gesuchte Menge ist dann :
"möchte ich aus der Relation $ [mm] R_{3} [/mm] $ das Paar $ [mm] (a_1,a_2) [/mm] $ bestimmen, wobei.."
also :
[mm] $M:=\{ (a_1,a_2)\in R_3 | \forall b\in B : (b,a_1)\in R_2 \}$
[/mm]
(insbesondere : ALLE entspr. Paare aus [mm] R_3 [/mm] )
die Aufgabe unterteilt sich dann also in zwei Schritte :
I) finde die [mm] a_1 [/mm] , die mit allen b in [mm] R_2 [/mm] vorkommen
II) finde dann alle entspr. Paare in [mm] R_3
[/mm]
Unter der Vorraussetzung, dass diese Relationen auch wirklich Relationen sind, d.h. keine Paare doppelt vorkommen koennen, kann man den ersten Schritt so angehen :
1.1) Bestimme A und B wie oben in der Mengenschreibweise beschrieben.
1.2) Erzeuge die gesamt-Relation S=BxA - darin sind fuer jedes a mit allen b aus B die Paare enthalten.
1.3) loesche aus S alle Paare, die in [mm] R_2 [/mm] stehen (also [mm] $S\backslash R_2$), [/mm] wenn es also ein [mm] a_1 [/mm] gibt, dass mit allen b aus B in [mm] R_2 [/mm] steht, dann wird dieses [mm] a_1 [/mm] aus S geloescht , daraus folgt:
1.4) alles was noch in [mm] $(S)_2$ [/mm] steht, kommt nicht vollstaendig in [mm] R_2 [/mm] vor, also bestimme [mm] $X:=A\backslash (S)_2$ [/mm] - dies ist deine gesuchte Menge von Schritt I
und bei Schritt II kann man einfach ueber alle Paare gehen, also
[mm] $M:=\{ (a_1,a_2)\in R_3 | a_1 \in X \}$
[/mm]
Ist es soweit das, was du wolltest oder habe ich zwischenzeitlich etwas falsch verstanden ?
viele Gruesse
DaMenge
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 13:50 Fr 14.10.2005 | | Autor: | HOST |
Hallo DaMenge,
kein Problem mit der Antwortzeit, die werde ich nächste Woche bequem überbieten. Bis dahin werde ich Deine Antwort erst mal verdauen.
Viele Grüße
HOST
|
|
|
|
