(min,max)-Notation, Beziehungsinstanzen

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

(min,max)-Notation, Beziehungsinstanzen
Hallo,

bei folgender Aufgabe habe ich so meine Verständnisprobleme:

Gegeben sei folgender Ausschnitt aus einem E/R-Diagramm (siehe Anhang)

Wie viele Beziehungsinstanzen vom Typ C können in einer vollständig repräsentativen Extension
höchstens existieren, wenn die Vereinigungsmenge aller Entitäten der Typen A und B insgesamt
n (wobei n aus den natürlichen Zahlen ist) Elemente enthält?

Ich hatte mir überlegt, dass das Ergebnis n/2 sein könnte???

Habe irgendwie nichts konkretes in der Literatur noch in den VL-Folien gefunden.

Vielen Dank schon mal im Voraus für eure Unterstützung.

CdX

Attachment:
ER.jpg: https://fsi.cs.fau.de/unb-attachments/post_144604/ER.jpg


n/2 sinds nicht, ein Gegenbeispiel ist schnell gefunden… z.B. mit A={a1}, B={b1,b2} gibts die Beziehungen (a1,b1), (a1,b2). Also ist n=3, aber es gibt 2 Beziehungen.
Tatsaechlich ist die Antwort floor(2n/3). Jedes A kann 2 mal an einer Beziehung teilnehmen, jedes B aber nur 1 mal, womit eine Verteilung von 2 Bs pro A die maximale Anzahl von Beziehungsinstanzen ergibt.


[quote=xenexi]Jedes A kann 2 mal an einer Beziehung teilnehmen, jedes B aber nur 1 mal, womit eine Verteilung von 2 Bs pro A die maximale Anzahl von Beziehungsinstanzen ergibt.
[/quote]
Wie kannst du von hier auf floor(2n/3) schließen? Die genauen Anzahlen, wie viele As und Bs es gibt, sind doch gar nicht gegeben.


[quote=Marcel[Inf]]

[quote=xenexi]Jedes A kann 2 mal an einer Beziehung teilnehmen, jedes B aber nur 1 mal, womit eine Verteilung von 2 Bs pro A die maximale Anzahl von Beziehungsinstanzen ergibt.
[/quote]
Wie kannst du von hier auf floor(2n/3) schließen? Die genauen Anzahlen, wie viele As und Bs es gibt, sind doch gar nicht gegeben.
[/quote]

Man soll die maximale Anzahl der Beziehungsinstanzen für alle Anzahlen von A und B ermitteln. Deswegen ist die genaue Anzahl von A und B egal, sie soll nur die Nebenbedingung |A|+|B|=n erfüllen.


[quote=ic97usop]Man soll die maximale Anzahl der Beziehungsinstanzen für alle Anzahlen von A und B ermitteln. Deswegen ist die genaue Anzahl von A und B egal, sie soll nur die Nebenbedingung |A|+|B|=n erfüllen.
[/quote]
Danke, damit wird dieser Teil schon mal klar:

Trotzdem verstehe ich leider nicht, wie man auf floor(2/3 * n) kommt. Ist das wie folgt? Wäre nett, wenn das jemand bestätigen könnte :slight_smile:

Beste Verteilung wäre 2Bs pro A. Anders ausgedrückt, in der Gesamtmenge (alle Entities von A und B vereinigt) wäre die beste Verteilung: 1/3 As und 2/3 Bs, jeweils als relative Häufigkeit von der Gesamtmenge.

=> Da jedes A zweimal teilnehmen kann, gibt es 2*(1/3)*n = (2/3) * n Tupel in der Endrelation im besten Fall.
Und wie kommt man auf floor()? Heißt es, dass (2/3) * n nicht immer aufgeht und man deswegen abrundet, weil der nächste halbe Datensatz physisch nicht existieren könnte?

Allerdings: Die Endrelation soll doch vollständig repräsentativ sein! Das würde doch heißen, dass alle Bs genau an einer Beziehung teilnehmen, es As gibt, die nur an einer (!) Beziehung teilnehmen, und schließlich auch As, die an zwei Beziehungen teilnehmen. Für unseren besten Fall oben gingen wir immer von zwei Beziehungen aus. Aber dann wäre doch die Relation nicht vollständig repräsentativ, denn würde man das ER-Diagramm rückkonstruieren, käme man auf (2,2) als MinMax-Notation bei A.

Also kann floor(2/3 * n) nicht stimmen?!


Wir benötigen hier eine Fallunterscheidung. Sei dafür x eine natürliche Zahl oder 0.

  1. Fall: n = 3x. Dann lässt sich die Menge in x As und 2x Bs zerlegen. Die Anzahl der Beziehungen ist dann 2x.
  2. Fall: n = 3x + 1. Dann können wir die Menge in x As und 2x Bs zerlegen. Das letzte Element kann man nicht für eine Beziehung verwenden, also ist die Anzahl der Beziehungen gerade 2x. Ist übrigens n > 1, so können wir für die vollständige Repräsentation ein A nur mit einem B verbinden, damit das letzte Element auch eine Beziehung eingeht - das ändert aber an der maximalen Zahl eingegangener Beziehungen nichts.
  3. Fall: n = 3x + 2. Auch hier lässt sich die Menge in x As und 2x Bs zerlegen. Die letzten 2 Elemente kann man aber als 1 A und 1 B verwenden, die wiederum eine Beziehung eingehen. Damit ist die Anzahl der Beziehungen 2x+1.

Nun ermitteln wir floor(2n/3). Dazu:

  1. Fall: floor(2/3n) = floor(2/33x) = floor(2x) = 2x.
  2. Fall: floor(2/3n) = floor(2/3(3x+1)) = floor(2x+2/3) = 2x.
  3. Fall: floor(2/3n) = floor(2/3(3x+2)) = floor(2x+4/3) = 2x+1.

Das ist aber genau die Anzahl der eingegangenen Beziehungen.

1 Like

Vielen Dank für die ausführliche Antwort!

Nehmen wir deinen ersten Fall, sei n = 6 = 3 * 2, x = 2:

A = {a1, a2}, B = {b1, b2, b3, b4}.

Beziehungstabelle:

Entity A | Entity B a1 b1 a1 b2 a2 b3 a2 b4
Wenn ich dir alleine diese Beziehungstabelle geben würde und sie als “vollständig repräsentativ” bezeichnen würde, könntest du nur folgende Schlüsse ziehen:

  1. Jedes A geht minimal 2 und maximal 2, also genau 2 Beziehungen ein.
  2. Jedes B geht genau 1 Beziehung ein.

=> In MinMax-Notation lauten das: (2,2) auf der A-Seite, (1,1) auf der B-Seite. In der Angabe war es jedoch (1,2) auf der A-Seite.

PS: Ich habe deinen Edit von 20:06 Uhr gelesen.


Verstehe, dann ist aber der Fall 1 der einzige Fall, bei dem man eine Veränderung benötigt. In diesem Fall wäre die Anzahl der Beziehungen 2x-1 und man könnte die Anzahl der Beziehungen allgemein durch z. B. floor(2/3*n-1/6) ausrechnen lassen. Die Konstante 1/6 ist dabei auch durch jede beliebige Konstante c in (0, 1/3] ersetzbar.