Übung zur Materialisierung

Die blauen Knoten sind materialisiert.

1. Durchgang

Angenommen (A1, A2) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	50	600	0
(A1)	1000	600	400
(A2)	50	600	0
(A1, A2)	1000	600	400

Nutzen (Gesamt) = 400 + 400 = 800

Angenommen (A2, A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	50	500	0
(A2)	50	500	0
(A3)	1000	500	500
(A2, A3)	1000	500	500

Nutzen (Gesamt) = 500 + 500 = 1000

Angenommen (A1, A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	50	700	0
(A1)	1000	700	300
(A3)	1000	700	300
(A1, A3)	1000	700	300

Nutzen (Gesamt) = 300 + 300 + 300 = 900

Angenommen (A1) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	50	20	30
(A1)	1000	20	980

Nutzen (Gesamt) = 980 + 30 = 1010

Angenommen (A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	50	70	0
(A3)	1000	70	930

Nutzen (Gesamt) = 930 + 0 = 930

• Knote (A1) wird materialisiert.
• s = 20 → Verbraucht
• S = 1000 - 20 = 980 → Übrig

---

Durchgang 2

Angenommen (A2, A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	500	0
(A2)	50	500	0
(A3)	1000	500	500
(A2, A3)	1000	500	500

Nutzen (Gesamt) = 500 + 500 = 1000

Angenommen (A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	70	0
(A3)	1000	70	930

Nutzen (Gesamt) = 930 + 0 = 930

Angenommen (A1, A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	700	0
(A1)	20	700	0
(A3)	1000	700	300
(A1, A3)	1000	700	300

Nutzen (Gesamt) = 300 + 300 = 600

Angenommen (A1, A2) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	600	0
(A1)	20	600	0
(A2)	50	600	0
(A1, A2)	1000	600	400

Nutzen (Gesamt) = 400 = 400

• Knote (A3) wird materialisiert.
• s = 70 → Verbraucht
• S = 980 - 70 = 910 → Übrig

---

Durchgang 3

Angenommen (A1, A2) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	600	0
(A1)	20	600	0
(A2)	50	600	0
(A1, A2)	1000	600	400

• Nutzen (Gesamt) = 400 = 400

Angenommen (A1, A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	700	0
(A1)	20	700	0
(A3)	70	700	0
(A1, A3)	1000	700	300

• Nutzen (Gesamt) = 300 = 300

Angenommen (A2, A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	500	0
(A2)	50	500	0
(A3)	70	500	0
(A2, A3)	1000	500	500

• Nutzen (Gesamt) = 500 = 500

• Knote (A2, A3) wird materialisiert.

• s = 500 → Verbraucht

• S = 910 - 500 = 410 → Übrig

Durchgang 4 nicht machen, Begründung unten

Materalisierung gehen über den verbleibenden Speicherplatz hinaus

Ergebnis

Alle mögliche Materialisierung

M = {(A1),(A3),(A2, A3)

---

NICHT MACHEN

4. Durchgang

Angenommen (A1, A2) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	600	0
(A1)	20	600	0
(A2)	50	600	0
(A1, A2)	1000	600	400

Nutzen (Gesamt) = 400 = 400

Angenommen (A1, A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	700	0
(A1)	20	700	0
(A3)	70	700	0
(A1, A3)	1000	700	300

Nutzen (Gesamt) = 300 = 300

• Knote (A1, A2) wird materialisiert.
• s = 600 → Verbraucht
• S = 910 - 500 = 410 → Übrig

Beispiel aus der Vorlesung

Angenommen (A1, A3) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	6000	120	5880
(A1)	6000	120	5880
(A3)	6000	120	5880
(A1, A3)	6000	120	5880

Nutzen (Gesamt) = 5880 * 4 =

Angenommen (A1, A2) wird materialisiert:

• Was bedeutet das für alle noch nicht materialisierten Knoten:

Knoten	Aktuelle Kosten	Potenzielle Kosten	Nutzen
()	20	600	0
(A1)	20	600	0
(A2)	50	600	0
(A1, A2)	1000	600	400

Nutzen (Gesamt) = 400 = 400