Repräsentation betrieblicher Informationssysteme durch

Kombination von Entity-Relationship- und Petrinetz-Technik

Diplomarbeit

vorgelegt dem Fachbereich Wirtschaftswissenschaften der

Universität Essen

von:

cand. rer. pol. Urs Lässer

Wintersemester 2002/03, 13. Studiensemester

Voraussichtlicher Studienabschluss: Wintersemester 2002/03

---

I

Inhaltsverzeichnis

Abbildungsverzeichnis IV

Tabellenverzeichnis V

Definitionsverzeichnis VI

Abkürzungsverzeichnis VII

Symbolverzeichnis IX

1

Modellierung betrieblicher Informationssysteme als Problem des

Informationsmanagements 1

1.1

Ziele und Aufgaben 1

1.2

Gliederung und Ziel der Arbeit 4

2

Petrinetze als Modellierungstechnik für betriebliche

Informationssysteme 7

2.1

Modellierung betrieblicher Informationssysteme 7

2.2

Das Modellierungspotenzial von Petrinetzen 10

2.2.1

Allgemeine Potenziale von Petrinetzen 10

2.2.2

Spezielle Potenziale ausgewählter Petrinetz-Typen 11

2.2.2.1 K/I-Netze 12

2.2.2.2 B/E-Netze 14

2.2.2.3 S/T-Netze 16

2.2.2.4 Pr/T-Netze 17

2.3

Modellierungsdefekte von Petrinetzen 19

2.3.1

Komplex strukturierte Datenobjekte 19

2.3.2

Unabhängig voneinander ausführbare Arbeitsschritte 20

2.3.3 Undefinierte

Werte 22

2.4

Ansätze zur Heilung der Modellierungsdefekte 22

3

Ansätze zur Heilung der Modellierungsdefekte von Petrinetzen mit

Hilfe der Entity-Relationship-Technik 24

---

II

3.1

Das Modellierungspotenzial der Entity-Relationship-Technik 24

3.1.1 Semiformale

Datenmodelle 25

3.1.2 Formale

Datenmodelle 27

3.1.3 Resümee 29

3.2

Komplexe Datenobjekte in E-R-Modellen 29

3.2.1

Normalisierung komplexer Datenobjekte 29

3.2.2

Genestete Relationen zur Modellierung komplexer Datenobjekte

33

3.2.2.1 Das Modellierungspotenzial genesteter Relationen 33

3.2.2.2 Genestete Relationen als Erweiterung des Entity-Relationship-

Modells 34

3.2.2.3 Genestete Relationen als Sichten auf das Entity-Relationship-

Modell 36

3.3

Manipulation von Daten in genesteten Relationen 41

3.3.1

Begründung des Manipulationsbedarfs 41

3.3.2

Defekte bei der Manipulation von Daten in genesteten

Relationen 43

3.3.3

Ansätze zur Heilung der Manipulationsdefekte 43

3.3.3.1 Inklusionsordnung 44

3.3.3.2 Objektordnung 46

3.3.3.3 Ordnungsdefinition

und

Ordnungsgleichung 49

3.3.3.4 GPNF-Instanzen 52

3.3.3.5 Negativ einer Instanz 54

3.3.4

Filtertabellen zur semiformalen Beschreibung der erweiterten

Ausdrucksmittel 56

3.3.4.1 Das Modellierungspotenzial von Filtertabellen 56

3.3.4.2 Operationen auf genesteten Relationen mit Filtertabellen 58

3.3.4.2.1 Selektion von Daten 58

3.3.4.2.2 Einfügen und Löschen von Daten 59

3.4 Resümee 61

4

Integration von Ausdrucksmitteln der E-R- in die Petrinetz-Technik

63

4.1 NF²-Relationen/Transitionen-Netze 63

---

III

4.2 Netzkomponenten 65

4.2.1

Stellen und genestete Relationen 65

4.2.2

Kanten und Filtertabellen 66

4.2.3

Transitionen und Schaltregeln 67

5

Evaluation 70

5.1 Beurteilungskriterien 70

5.2

Bewertung der Modellierungstechnik 71

5.2.1 Modellierungsfähigkeit 71

5.2.2 Integration 73

5.2.3 Flexibilität 74

5.3 Kritische

Würdigung 76

Literaturverzeichnis 78

Anhang 86

Petrinetz-Definitionen 86

Fallstudie 92

Eidesstattliche Versicherung 105

---

IV

Abbildungsverzeichnis

Abbildung 1: Crew-Anforderung als Formular 6

Abbildung 2: Die drei Konzepte eines Systems 8

Abbildung 3: Modellierung betrieblicher Informationssysteme 9

Abbildung 4: Geschäftsvorfall "Flugvorbereitung" als K/I-Netz 12

Abbildung 5: Flugvorbereitung als B/E-Netz 15

Abbildung 6: Flugvorbereitung als S/T-Netz 16

Abbildung 7: Flugzeugzuweisung als Pr/T-Netz (Teil 1) 18

Abbildung 8: Flugzeugzuweisung als Pr/T-Netz (Teil 2) 18

Abbildung 9: Sperren eines Datenobjektes 21

Abbildung 10: E-R-Modell ohne Attribute 25

Abbildung 11: E-R-Modell mit Attributen 26

Abbildung 12: Ausschnitt aus einem E-R-Modell 38

Abbildung 13: Beispiel für ein NR/T-Netz 63

---

V

Tabellenverzeichnis

Tabelle 1: Aufbau der Arbeit 5

Tabelle 2: Flugzeug mit flachen

n

-Tupeln dargestellt 19

Tabelle 3: Aufteilung von Daten über mehrere Tabellen 20

Tabelle 4: Nullwerte in einem flachen

n

-Tupel 22

Tabelle 5: Daten in Non First Normalform 30

Tabelle 6: Daten in erster Normalform 31

Tabelle 7: Daten in dritter Normalform 32

Tabelle 8: Komplexes Datenobjekt als geschachtelte Tabelle 33

Tabelle 9: Genestete Relation in Tabellenform 35

Tabelle 10: Hergeleitetes Datenobjekt in Tabellenform (1) 40

Tabelle 11: Hergeleitetes Datenobjekt in Tabellenform (2) 40

Tabelle 12: Mehrere Flugzeuge gleicher Bauart 41

Tabelle 13: Tupel eines komplexen Datenobjekts (Beispiel 1) 42

Tabelle 14: Mitarbeiter mit veränderlichen Qualifikationen 42

Tabelle 15: Tupel als komplexes Datenobjekt (Beispiel 2) 42

Tabelle 16: Zwei Instanzen des Datenmodells "Flugzeug" 45

Tabelle 17: Vereinigung und Schnittmenge mit der Inklusionsordnung 45

Tabelle 18: Zwei Instanzen des Datenmodells "Mitarbeiter" 47

Tabelle 19: Vereinigung und Schnittmenge mit der Objektordnung 48

Tabelle 20: Nicht antisymmetrische Instanzen 48

Tabelle 21: Instanzen der Relation ,,Aufgabe" 49

Tabelle 22: Verschmelzen von Instanzen mit Ordnungen 51

Tabelle 23: Negativ einer Instanz 1 55

Tabelle 24: Datenbestand für die Abfrage von Daten 58

Tabelle 25: Ergebnis einer Selektion 59

Tabelle 26: Hinzufügen von Tupeln (1) 60

Tabelle 27: Hinzufügen von Tupeln (2) 60

Tabelle 28: Hinzufügen von Tupeln (3) 61

Tabelle 29: Startmarkierung eines NR/T-Netzes 66

Tabelle 30: Bewertung der Modellierungsfähigkeit 73

Tabelle 31: Bewertung der Integration 74

Tabelle 32: Bewertung der Flexibilität 75

Tabelle 33: Gesamtbewertung der Modellierungstechnik 76

---

VI

Definitionsverzeichnis

Definition 1: Netz 14

Definition 2: Datenmodell 27

Definition 3: Entity-Typ 28

Definition 4: Beziehungs-Typ 28

Definition 5: Instanz (einzelwertige Attribute) 31

Definition 6: Instanz (mengenwertige Attribute) 35

Definition 7: Inklusionsordnung 44

Definition 8: Objektordnung 46

Definition 9: PNF-Instanzen 48

Definition 10: Ordnungsdefinition und Ordnungsgleichung 50

Definition 11: Generalized Partitioned Normal Form (GPNF-) Instanzen 52

Definition 12: Negativ einer Instanz 55

Definition 13: Bewerteter Top-Level-Term, Instanziierung eines Terms 56

Definition 14: NR/T-Netz 64

Definition 15: Aktivierte Transition 68

Definition 16: Schalten einer Transition 68

---

VII

Abkürzungsverzeichnis

1NF erste

Normalform

3NF dritte

Normalform

AG Aktiengesellschaft

B/E Bedingungs/Ereignis

BIS betriebliche(s)

Informationssystem(e)

bspw. beispielsweise

BV

Besloten Vennootschap (niederländisch: GmbH)

BWL Betriebswirtschaftslehre

bzw. beziehungsweise

CIM

Computer Integrated Manufacturing

COSA

Eigenname für Softwareprodukt der Software-Ley GmbH

d.h. das

heißt

E-R Entity-Relationship

EDV elektronische

Datenverarbeitung

EPK ereignisgesteuerte

Prozesskette

evtl. eventuell

f. folgende

GmbH

Gesellschaft mit beschränkter Haftung

Hrsg. Herausgeber

i.d.R.

in der Regel

INCOME

Eigenname für Softwareprodukt der Promatis AG

Jg. Jahrgang

K/I Kanal/Instanzen

NFNF

Non First Normalform

Nr. Nummer

NR/T Nested

Relation/Transition

o.g. oben

genannte

Pr/T Prädikate/Transitionen

PROTOS

Eigenname für Softwareprodukt der Pallas Athena BV

R/3 Release

3

S. Seite(n)

S/T Stellen/Transitionen

SAP

Systeme Anwendungen Programme

---

VIII

s.o. siehe

oben

sog. sogenannte

s.u. siehe

unten

u.a. unter

anderem

u.ä. und

ähnliche(s)

usw.

und so weiter

vgl. vergleiche

WfMS Workflow-Managementsystem

z.B. zum

Beispiel

z.T. zum

Teil

---

IX

Symbolverzeichnis

a

Einzelwertiges Attribut

A

Mengenwertiges Attribut

AI

Funktion, die jeder Kante aus

F

eine Filtertabelle

BT

zuweist

Wert eines Attributs

attr

Funktion, die Attribute mit einem Entity- oder Beziehungs-Typ

verknüpft

B

Gleichheitsattribute von

A

BEN

Bedingungs/Ereignis-Netz

BT

Menge von Filtertabellen (auch: bewertete Top-Level-Terme)

C

Teilmengenattribute von

A

Pr-Belegung

d

Domäne

dom

Funktion, die eine Domäne i mit einem Attribut verknüpft

D

Datenmodell

Menge von Domänen

f

Kante aus der Menge der Kanten

F

GPNF

Funktion, welche die Menge der Instanzen, die den

Bedingungen der Generalized Partitioned Normal Form

genügen, abbildet

E

Entity-Typ

FU

Menge der auf

D

definierten Funktionen

Menge gültiger Instanzen

i

Index-Zähler

id

Funktion, die Schlüsselattribute mit einem Entity-Typ

verknüpft

I

feste Interpretation von

P

Wert einer Instanz

j

Index-Zähler

k

Kapazität einer Stelle

kb

Teilmenge von

KB

KB

Menge von Kantebeschriftungen

LF

Menge von logischen Ausdrücken

---

X

M

Startmarkierung eines Netzes

N

Netz

Teilmenge von Namen aus

U

p

prädikatenlogischer Ausdruck

P

n

-Stelliges Prädikat

P

Menge der prädikatenlogischen Ausdrücke zu einer Struktur

PNF

Funktion welche die Menge der Instanzen, die den

Bedingungen der Partitioned Normal Form genügen, abbildet

PR

Menge der auf

D

definierten Prädikate

PT

Prädikate/Transitionen-Netz

Signatur eines Nr/T-Netzes

Struktur eines prädikatenlogischen Ausdrucks

R

Beziehungs-Typ, Relations-Typ

Instanz

s

Stelle

S

Menge von Stellen

ST

Stellen/Transitionen-Netz

t

Transition

t

Vorbereich

t

Nachbereich

T

Menge von Transitionen

TI

Funktion welche einen prädikatenlogischen Ausdruck als

Inschrift einer Flussrelation in einem Pr/T-Netz zuweist

TV

Wahrheitswert

Tupel

Top-Level-Datenmodell

U

Universum, Universe of Discourse, Menge der Attribute

Ueinfach

Menge der in

U

enthaltenen einzelwertigen Attribute

var

Variable

w

Kantengewichtung in einem S/T-Netz

W

Funktion welche jeder Kante im Netz eine Gewichtung zuweist

x

Variable

X

Menge von Variablen

---

XI

gültige Instanziierung

y

Variable

Logisch-mathematische Symbole

kleiner oder gleich

D

Objektordnung

größer oder gleich

Ordnungsdefinition

ist Element von

ist nicht Element von

ist Teilmenge von

D

Inklusionsordnung

logisches Und

logisches Oder

Negation

Abbildung einer Funktion

daraus folgt

genau dann, wenn

Vereinigungsmenge

Schnittmenge

für Alle

es gibt (mindestens) ein

unendlich

leere Menge

\ ohne

IN

Menge der natürlichen Zahlen ohne Null

IN0

Menge der natürlichen Zahlen mit Null

---

1

1 Modellierung betrieblicher Informationssysteme als

Problem des Informationsmanagements

1.1 Ziele und Aufgaben

,,Alles Leben ist Problemlösen. Alle Organismen sind Erfinder und Techniker,

gute oder weniger gute, erfolgreich oder weniger erfolgreich im Lösen von

technischen Problemen."1

Betriebswirtschaftliche Probleme2 entstehen aus unternehmerischen Zielen

sowie den daraus resultierenden Aufgabenstellungen. Sie werden auf der Basis

von

Informationen

3 gelöst. Informationen dienen der

Problembeschreibung

,

der Formulierung einer

Frage

und der

Problemlösung

: Die Problembeschrei-

bung wird durch gegebene Informationen, eine Frage durch gesuchte Informa-

tionen repräsentiert. Eine Frage zu beantworten bedeutet, eine Problemlösung

vorzuschlagen4. Die Möglichkeiten der Problemlösung hängen von den

vorhandenen Informationen zur Problembeschreibung und den realisierbaren

Lösungsalternativen ab. Deshalb müssen Informationen über das Problem und

seine Lösungsmöglichkeiten beschafft werden5.

Betriebliche Informationssysteme (im folgenden auch kurz: BIS) bestehen aus

Menschen und Maschinen, die durch den Austausch und die Verarbeitung von

Informationen innerhalb eines organisatorischen Rahmens miteinander

kom-

munizieren

6. Diese Kommunikation kann von Mensch zu Mensch, Mensch zu

Maschine, Maschine zu Mensch und Maschine zu Maschine erfolgen. Der

1 Popper (2002), S. 257.

2 Probleme werden verstanden als Abweichungen eines Ist- Zustands vom Soll-Zustand.

3 Informationen werden verstanden als das, was vielfältige pragmatische Komponenten auf-

weist, Wissen (d.h. die für wahr erachteten Sätze) voraussetzt, Neuigkeitsgrad besitzt, zeit-

punktbezogen ist und beliebige mit menschlichem Handeln verbundene Träger besitzt. In-

formationen weisen enge Beziehungen zum Wissen auf, weil sie einerseits Wissen voraus-

setzen und andererseits zu einer Veränderung des Wissenstandes führen können. Daten

werden nicht als ,,inhaltsfrei" verstanden, da auch Rohdaten Informationen darstellen kön-

nen. Sie werden statt dessen als spezifische Informationen betrachtet, die Aussagen über die

Realität vor dem Hintergrund einer bestimmten Vorstrukturierung treffen. Daten setzen

damit eine Strukturierung der Welt voraus, zu der es Daten geben kann, vgl. Schütte

(1998), S. 1-5, Fußnote 5.

4 Vgl. Schmidt (1999), S. 1.

5 Vgl. Schmidt (1999), S. 11.

6 Vgl. Antweiler (1995), S. 12 f.

---

2

Schwerpunkt dieser Arbeit richtet sich auf

technikgestützte

BIS. Diese weisen

mindestens eine technische ­i.d.R. computergestützte­ Komponente auf.

Ziel

des Einsatzes von BIS ist es, die Wirtschaftlichkeit der betrieblichen Sys-

teme, aber auch der Informationssysteme selbst zu gewährleisten. Dieses Ziel

setzt sich aus der Reduzierung der Kosten und der Erhöhung des Nutzens für

die BIS, vor allem aber aus den Nutzensteigerungen in indirekten Bereichen

zusammen7. Nutzensteigerungen in indirekten Bereichen können z.B. durch die

Beschleunigung zentraler Geschäftsprozesse erreicht werden8.

Weitere relevante operationale Teilziele der BIS sind Flexibilitätssteigerun-

gen, Reduzierung der Durchlaufzeiten bei den Informationsprozessen, eine

möglichst große Aufgabenbezogenheit, Qualitätssteigerungen der Informa-

tionen und der Informationsprozesse, die Beherrschung der Systemkomplexität

bei gleichzeitig hohem Integrationsgrad sowie die sich daraus ergebenden, auf

den Markt gerichteten Ziele indirekter Bereiche9.

Unternehmen stehen daher vor der

Aufgabe

, den Einsatz der Ressource Infor-

mation10 und die damit verbundenen Geschäftsprozesse zu planen, zu steuern

und zu kontrollieren. Aufgrund dieser Aufgaben empfiehlt es sich, den Infor-

mationsbedarf und die Geschäftsprozesse eines Unternehmens zu

modellieren

.

Dabei wird die Hypothese vertreten, dass die Komplexität der aus den o.g.

Aufgaben resultierenden Probleme mit Hilfe von Modellen besser handhabbar

ist. Zweck dieser Modelle ist es, BIS zu

repräsentieren

, d.h. sprachlich zu re-

konstruieren und zu implementieren11. Auf Basis dieser

Informationssystem-

Modelle

können Geschäftsprozesse und der damit verbundene Informationsbe-

darf eines Unternehmens geplant, analysiert, modifiziert, dokumentiert und in

das BIS implementiert werden. Es wird die Hypothese vertreten, dass damit

7 Vgl. Antweiler (1995), S. 42.

8 Vgl. Österle (1996), S. 1. Danach ist ein Geschäftsprozess dann besser, wenn er mit

niedrigeren Kosten und/oder in höherer Qualität als zuvor abgewickelt werden kann.

9 Vgl. Antweiler (1995), S. 43.

10 Während Information als Gestaltungsobjekt früher oftmals nur in Form dispositiver

Tätigkeiten Berücksichtigung fand, wird sie heute zum einen als Produkt und zum anderen

als Produktionsfaktor explizit wahrgenommen, vgl. Antweiler (1995), S. 4 f. sowie S. 4,

Fußnoten 13 und 14.

11

Die Repräsentation umfasst die Beziehung eines Begriffs zu dessen semanti-

scher/pragmatischer Bedeutung als Objekt in der Realität oder Fiktion.

---

3

eine Senkung der Prozesskosten und/oder eine qualitative Verbesserung der

Prozesse erreicht wird.

Die in der Betriebswirtschaftslehre häufig verwendete

natürliche

Sprache be-

sitzt jedoch bestimmte Eigenschaften, die für die Modellierung von BIS

nachteilig sind12. Dies betrifft ihre fehlende Eindeutigkeit und mögliche Wider-

sprüche. Verbale Beschreibungen sind deshalb für die Modellierung von BIS

nur bedingt geeignet. Die für Entscheidungs- und Planungsprobleme in der

Betriebswirtschaftslehre verwendete

mathematische

Sprache ist zwar exakter

und verifizierbar, aber für den Adressaten in der Unternehmenspraxis häufig

nicht oder nur schwer verständlich13. Formale Sprachen allgemein können je-

doch helfen, Begriffe und Zusammenhänge zu klären oder zu präzisieren14.

Mitunter kann eine formale Beschreibungssprache zur Realisierbarkeit innova-

tiver strategischer Ansätze beitragen, da entsprechend formal beschreibbare

Konzepte in ein EDV-System implementierbar sind15.

Um diesen unterschiedlichen Anforderungen an Beschreibungssprachen ge-

recht zu werden, könnten für die Modellierung von BIS eine oder mehrere Mo-

dellierungssprachen verwendet werden, die stufenweise Transformationen von

einer verbalen zu einer formalen Beschreibung ermöglichen. So könnten natür-

lich sprachliche Beschreibungen als Grundlage für die Modellierung von BIS

verwendet und durch eine stufenweise Formalisierung die o.g. Probleme ver-

12 Für eine weitergehende untersuchende Darstellung verschiedener Spracharten siehe Ditt-

mann (2002).

13 Die schwere Verständlichkeit formal-mathematischer Beschreibungen für Adressaten in der

Unternehmenspraxis stellt insb. einen Nachteil in bezug auf die Kommunikation zwischen

Informatikern/Mathematikern und Informatik-/Mathematik-Laien dar. Abweichend Scheer

(1998), S. 1 f. SCHEER nimmt an, dass ,,die in der Betriebswirtschaftslehre verwendete ma-

thematische Sprache" nicht für alle betriebswirtschaftlichen Problembeschreibungen an-

wendbar ist. Jedoch erläutert SCHEER nicht, was genau unter ,,der" mathematischen Sprache

zu verstehen ist und für welche betriebswirtschaftlichen Problembeschreibungen eine sol-

che Sprache anwendbar wäre. Für mögliche Anwendungen siehe z.B. Zelewski et al.

(2001), insb. S. 196-200.

14 Eine Folge begrifflicher Defizite können methodische Defizite sein, unter denen u.a. die

Wirtschaftsinformatik leidet, vgl. Lehner (1996), S. 68-72.

15 Beispiele der Vergangenheit haben gezeigt, dass innovative strategische Ansätze zur

Gestaltung von Unternehmen scheitern, wenn sie sich nicht durch geeignete Informations-

und Kommunikationstechnologien realisieren lassen. Dies gilt bspw. für die Ideen zu Ma-

nagement-Informationssystemen in den 70er genauso wie für den CIM-Gedanken in den

80er Jahren, vgl. Scheer (1996), S. 255.

---

4

baler Beschreibungen reduziert werden. Die Konzeption einer solchen Model-

lierungssprache ist das Thema dieser Arbeit.

1.2 Gliederung und Ziel der Arbeit

In dieser Arbeit wird ein Konzept zur Repräsentation betrieblicher Informa-

tionssysteme durch

Kombination

von Entity-Relationship- (E-R-) und Petri-

netz-Technik16 erstellt. Ausgehend von Petrinetzen als Modellierungstechnik

für BIS werden in

Kapitel 2

die Potenziale und die Defekte dieser Technik

aufgezeigt. In

Kapitel 3

werden die Potenziale der E-R-Technik beschrieben.

Dabei wird aufgezeigt, wie die Potenziale der E-R-Technik die zuvor beschrie-

benen Defekte der Petrinetz-Technik heilen können.

Die verfügbaren Publikationen17, die sich mit einer solchen Kombination

befassen, sind für Informatik-Laien i.d.R. nicht oder nur schwer verständlich.

Das ist u.a. darin begründet, dass unterschiedliche Ansätze auf verschiedenen

Abstraktionsebenen mit unterschiedlichen, teilweise schwer nachvollziehbaren

Beispielen überwiegend formal-mathematisch beschrieben werden.

Daher werden in den

Kapiteln 3 und 4

Elemente unterschiedlicher Ansätze

zusammengefügt

und anhand eines

einheitlichen

, praxisrelevanten Beispiels

erklärt. Dieses Beispiel wird verbal, und anschließend mit Hilfe der Modellie-

rungstechniken sowohl semiformal als auch formal beschrieben. Die semifor-

male Beschreibung wird dabei in Form einer grafischen Beschreibung als

Schnittstelle zwischen verbaler und formaler Beschreibung verwendet18.

In

Kapitel 4

werden die erarbeiteten Ausdrucksmittel der E-R-Technik mit

den erarbeiteten Ausdrucksmitteln der Petrinetz-Technik kombiniert.

16 Techniken werden als Teilmenge wissenschaftlicher Methoden verstanden.

17 Wie z.B. Bancilhon/Khoshafian (1989); Jaeschke (1996); Jaeschke et al. (1993); Jaeschke

et al. (1994); Lamersdorf/Schmidt (1983); Oberweis (1996a); Oberweis (1996b); Oberweis

et al. (1997a); Oberweis et al. (1997b); Oberweis/Sander (1996); Roth et al. (1988); Sander

(1992); Sander (1993); Schek/Scholl (1983); Schek/Scholl (1986); Stucky et al. (1993);

Thalheim (2000).

18 Die formale Beschreibung wird dabei als Basis für eine Implementierung in ein EDV-Sys-

tem betrachtet. Sie ist jedoch unabhängig von einer maschinenorientierten Programmier-

sprache, vgl. Oberweis (1996a), S. 173-178.

---

5

Kapitel 1: Gliederung und Ziel der Arbeit

Kapitel 2: Petrinetze als Modellierungstechnik für BIS

Petrinetze

Kapitel 2.1:

Kapitel 2.2:

Kapitel 2.3:

BIS

Potenziale

Defekte

Kapitel 3: Ansätze zur Heilung der Defekte mit Hilfe der E-R-Technik

Kapitel 3.1:

Kapitel 3.2:

Kapitel 3.3:

Potenziale der E-R-Technik

Komplexe Datenobjekte

Manipulation von Daten

Kapitel 3.4: Resümee

Kapitel 4: Integration der E-R-Technik in die Petrinetz-Technik

Kapitel 5: Evaluation

Tabelle 1: Aufbau der Arbeit

In

Kapitel 5

wird abschließend evaluiert, welchen Beitrag dieser Ansatz für die

Repräsentation von BIS leistet. Dabei wird angenommen, dass aus einem posi-

tiven Beitrag zur Repräsentation von BIS ein positiver Beitrag für das Infor-

mationsmanagement folgt.

Zur Veranschaulichung der Modellierungstechniken wird das Problem des sog.

,,Crew-Scheduling" verwendet19. Es handelt sich dabei um ein Problem, das im

Rahmen des operativen Managements von Fluggesellschaften auftritt.

19 Ziel des Crew-Scheduling ist es, die Kosten von Flugzeug-Crews durch Optimierung der

Einsatzpläne zu minimieren. Dieses Problem wird in der Fachliteratur mit Hilfe unter-

schiedlicher Ansätze behandelt. Murray (1961) präsentierte bereits 1961 einen Lösungsan-

satz; Levine (1996) diskutierte die Entwicklung eines genetischen Algorithmus als Lö-

sungsansatz; Chu et al. (1997) behandelten das Problem als ganzzahliges Teilmengen-

problem; Beasley/Cao (1998) versuchten das Crew Scheduling-Problem mit einem auf dy-

namischer Programmierung basierenden Algorithmus zu lösen; Lagerholm et al. (2000)

präsentierten einen auf neuronalen Netzwerken basierenden Lösungsansatz; Ozde-

mir/Mohan (2001) entwickelten einen genetischen Algorithmus als Lösungsansatz;

Yan/Chang (2002) sowie Yan/Tu (2002) favorisieren ein Netzwerk-Modell, das sie anhand

von Flugdaten einer taiwanesischen Fluggesellschaft insb. für das Scheduling der

Cockpit

-

Crew testeten.

---

6

Crew-Anforderung

Flug#: 455

Start: Düsseldorf

Ziel:

Rom

Flugdurchführung

Datum:

17.12.2002

Flugzeugzuordnung

Flugzeug: 12

Typ: Airbus-320

Crew

Aufgaben Flugpersonal

Nr. Name

Pilot

Copilot

Ähnlich: Jaeschke (1996), S. 182.

Abbildung 1: Crew-Anforderung als Formular

Anhand dieses, in Abbildung 1 angedeuteten Beispiels wird schrittweise erläu-

tert, wie durch die kombinierte Modellierung mit E-R- und Petrinetz-Technik

ein BIS repräsentiert werden kann. Abbildung 1 zeigt ein Formular, mit dem

eine Cockpit-Crew für einen Flug von Düsseldorf nach Rom angefordert wird.

Der Flug wird mit einem Airbus-320 durchgeführt, für den als Crew-Mitglieder

ein Pilot und ein Copilot benötigt werden. Von den mathematischen Modellen

zur Lösung des Crew-Scheduling-Problems wird abstrahiert und auf die in

Fußnote 19 aufgeführte Literatur verwiesen. Das hier verwendete Beispiel

fokussiert die Repräsentation eines BIS, mit dem sichergestellt werden soll,

dass die zur Lösung des Crew-Scheduling-Problems benötigten Informationen

bereit gestellt werden.

---

7

2 Petrinetze als Modellierungstechnik für betriebliche

Informationssysteme

2.1 Modellierung betrieblicher Informationssysteme

Die theoretische Grundlage zur Strukturierung von Problemen bildet in dieser

Arbeit die

Systemtheorie

20. Für das Verständnis von Systemen sind das

struktu-

rale

, das

funktionale

und das

hierarchische

Systemkonzept zu unterscheiden21

(vgl. Abbildung 2). Dabei fokussiert das Strukturkonzept die Elemente und de-

ren Beziehungen untereinander, es soll zeitlich unabhängig gültige Aussagen

über das System wiedergeben. Das funktionale Konzept22, teilweise auch als

Systemverhalten bezeichnet, betrachtet, wie sich etwas verhält. Zum funktio-

nalen Konzept gehört auch das logische Verknüpfungsmuster der im System

ablaufenden Prozesse sowie die Beziehungen zur Umwelt. Die tatsächlichen

zeitlichen Prozessverläufe werden als das dynamische Verhalten des Systems

bezeichnet. Unter dem hierarchischen Aspekt wird der Umstand verstanden,

dass die Elemente eines Systems sowohl Sub-Systeme repräsentieren und

zugleich Teil eines Super-Systems sein können. Von Sub-Systemen abzugren-

zen sind Teil-Systeme, bei denen Elemente und Beziehungen einer System-

ebene nach einem Kriterium zusammengefasst werden. Ein Element kann so-

mit zu mehreren Teil-Systemen gehören, jedoch nur zu einem Super-System.

Die Hierarchisierung von Systemen ist insbesondere von Bedeutung, um Kom-

plexität, wie sie realen Systemen eigen ist, zu beherrschen23.

20 Für eine detailliertere Einführung in die allgemeine Systemtheorie siehe z.B. Krieger

(1998). Die Systemtheorie wird in dieser Arbeit als

Konzeptualisierungsmuster

betrachtet,

übereinstimmend Zelewski et al. (2001), S. 212.

21 Vgl. Schütte (1998), S. 37-40.

22 Das funktionale Konzept der Systemtheorie ist abzugrenzen von der funktionalen Organisa-

tion eines Unternehmens (,,Taylorismus"), die sich von der prozessorientierten Organisa-

tion dadurch unterscheidet, dass bei der funktionalen Organisation primär die Strukturen

der Aufbauorganisation und Funktionshierarchien, bei der prozessorientierten Organisation

dagegen primär die Prozessstrukturen betrachtet werden.

23 Vgl. Krieger (1998), S. 14-17.

---

8

Ähnlich: Ropohl (1978), S.15.

Abbildung 2: Die drei Konzepte eines Systems

Ein

Modell

wird verstanden als ,,das Ergebnis einer

Konstruktion eines Model-

lierers

, der für

Modellnutzer

eine Repräsentation eines Originals zu einer

Zeit

als relevant mit Hilfe einer

Sprache

deklariert [...]. Ein Modell setzt sich somit

aus der Konstruktion des Modellierers, dem Modellnutzer, einem Original, der

Zeit und einer Sprache zusammen"24. Ein Informationssystem-Modell stellt

eine spezifische Modellart dar, die Informationen in einem betrieblichen Sys-

tem fokussiert25. In Anlehnung an die zuvor zitierte allgemeine Definition ei-

nes Modells kann ein Informationssystem-Modell, das betriebliche Informa-

tionssysteme fokussiert, wie folgt als spezielles Modell definiert werden: ,,Ein

Informationsmodell ist das Ergebnis einer Konstruktion eines

Modellierers

, der

für

Anwendungssystem- und Organisationsgestalter Informationen

über zu

modellierende Elemente eines Systems zu einer Zeit als relevant mit Hilfe ei-

ner Sprache deklariert"26.

24 Schütte (1998), S. 59. Vgl. auch Schütte (1997), S. 1. Dieser Arbeit liegt damit insb. die

Annahme zugrunde, dass es keine reale Problemsituation gibt, die

ohne

das

erkennende
Subjekt

das Ergebnis des Modellbildungsprozesses determiniert. Damit wird das Verständ-

nis von Modellen als

Abbilder

der Realität explizit

abgelehnt

und Modelle statt dessen als

Konstruktionen des Modellierers

aufgefasst. Davon abweichend z.B. Sinz (1996), S. 125 f.

25 Vgl. Schütte (1998), S. 63.

26 Schütte (1998), S. 63. SCHÜTTE verwendet die Bezeichnung ,,Informationsmodell". In

dieser Arbeit wird der Begriff ,,Informationssystem-Modell" synonym verwendet, da es

sich um Informationsmodelle handelt, deren theoretische Grundlage die Systemtheorie ist.

---

9

Unternehmensziele

und -Aufgaben

Prozessstruktur

Notw endigkeit des

Informations-

managements

Organisa-

tions-

struktur

Datenstruktur

Aufgabe: Model-

lierung betrieblicher

Informationssysteme

Ähnlich: Jaeschke (1996), S. 3.

Abbildung 3: Modellierung betrieblicher Informationssysteme

Abbildung 3 verdeutlicht, wie bereits Anfangs erläutert, dass sich aus unterneh-

merischen Zielen und Aufgaben die Notwendigkeit des Managements der Res-

source Information ergibt. Daraus ergibt sich als Aufgabe des Informations-

managements die Modellierung von BIS.

Auf dieser Basis sollte vor dem Prozess der Modellierung der notwendige

Detaillierungsgrad eines Modells bestimmt werden, damit eine ökonomisch

sinnvolle Relation zwischen den Kosten der Erstellung und dem späteren Nut-

zen des Modells erzielt wird27.

Weiter verdeutlicht Abbildung 3, dass BIS in

Prozess-

,

Daten-

und

Organisationsstruktur

28 unterteilt werden können. Die Prozessstruktur bezieht

sich insofern auf die funktionale Komponente des Systems, als dass sie anzeigt,

wie sich das System verhält. Sie wird als ,,strukturale Beschreibung des Ver-

haltensaspektes eines Systems"29 interpretiert. Die Daten- und Organisations-

struktur30 wird dagegen als statische und strukturale Komponente eines BIS

interpretiert31.

27 Vgl. Jaeschke (1996), S. 4.

28 Jaeschke (1996), insb. S. 3, unterscheidet zwischen Ablaufschema, Informationsschema

und Organisationsschema. In der hier verwendeten Terminologie ist dies mit Prozess-, Da-

ten- und Organisationsstruktur gleichzusetzen, vgl. auch Abbildung 3. Ähnlich Scheer

(1998), S. S. 32-38; SCHEER trennt jedoch Funktions- und Steuerungssicht, die in dieser

Arbeit als ,,Prozessstruktur" zusammengefasst sind.

29 Schütte (1998), S. 99.

30 Die Organisationsstruktur bezieht sich auf die Struktur der Aufbauorganisation.

31 Vgl. Schütte (1998), S. 99.

---

10

Der Fokus dieser Arbeit ist ein Konzept zur

kombinierten Modellierung von

Prozess- und Datenstrukturen

. Dabei fokussiert die Petrinetz-Technik die Pro-

zess- und die E-R-Technik die Datenstrukturen. Von der expliziten Behandlung

der Organisationsstruktur, genauer: der Struktur der

Aufbau

organisation, wird

damit abgesehen. Diese ist jedoch implizit in der Prozessstruktur enthalten, da

einzelne Funktionen bestimmten Organisationseinheiten zuzuordnen sind. Die

Prozessstruktur fokussiert damit die

Ablauf

organisation eines Unternehmens.

Eine Zuordnung bestimmter Organisationseinheiten zu einzelnen Funktionen

der Prozesse kann so bspw. durch eine zusätzliche informale Beschriftung der

Funktionssymbole, oder formal über die Integration in Datenobjekte erfolgen32.

2.2 Das Modellierungspotenzial von Petrinetzen

2.2.1 Allgemeine Potenziale von Petrinetzen

Die Grundlage für Petrinetze33 wurde von PETRI 1962 im Rahmen einer

Dissertation mit dem zweideutigen Titel34 ,,Kommunikation mit Automaten"35

gelegt. Eine in dieser Dissertation beschriebene Theorie wurde in den darauf

folgenden Jahren unter der Bezeichnung ,,Petrinetze" weltweit bekannt36.

Petrinetze können als grafischer Formalismus zur Beschreibung von

Prozess-

strukturen

verwendet werden. Sie ermöglichen die Beschreibung sequenzieller,

sich gegenseitig ausschließender sowie nebenläufiger Aktivitäten37, die nicht

determiniert sein müssen. Mit Petrinetzen können Zustände eines Geschäfts-

prozesses explizit modelliert werden, und es sind Analysetechniken zum Vali-

dieren und Verifizieren der konstruierten Modelle verfügbar38. Petrinetze besit-

zen ein ,,solides" theoretisches Fundament und es ist möglich, ,,Petri-Netz-

artige Darstellungen mit speziellen, anwendungsnahen graphischen

32 Vgl. Oberweis (1996a), S. 178-186.

33 Für eine informale Einführung in Petrinetze siehe Reisig (1985), für eine formale Einfüh-

rung siehe Reisig (1991); für eine anwendungsorientierte Einführung siehe Baumgarten

(1990). Für die Dissertation von PETRI siehe Petri (1962). Diese Dissertation ist z.B. in der

Universitäts-Bibliothek Bonn archiviert und kann dort eingesehen werden.

34 Der Titel kann als Kommunikation von Menschen mit Automaten oder als Kommunikation

zwischen Menschen mit Hilfe von Automaten verstanden werden.

35 Vgl. Petri (1962).

36 Vgl. Rozenberg (1991).

37 Vgl. Oberweis (1996a), S. 98.

38 Vgl. Aalst (1996), insb. S. 188 f.

---

11

Symbolen"39 zu verwenden, wodurch eine semantisch gehaltvolle Darstellung

erreicht werden kann.

Auf Petrinetzen basierende Modellierungsansätze haben sich als ,,tragfähig für

die Modellierung, die Analyse und die Durchführung realer Geschäftsprozesse

herausgestellt"40. Der erfolgreiche Einsatz von Petrinetzen für die Model-

lierung von Prozessstrukturen im akademischen Bereich41 ermutigte Unterneh-

men, auf der Petrinetz-Technik basierende kommerzielle Modellierungssoft-

ware anzubieten42. Die verfügbare Modellierungssoftware unterstützt z.T. auch

die automatisierte Implementierung der Prozessmodelle in EDV-Systeme,

bspw. in Workflow-Management-Systeme (WfMS)43.

Petrinetze unterstützen die Komplexitätsreduzierung u.a. durch die Möglichkeit

der Vergröberung und Verfeinerung der Netzelemente44. Ein Petrinetz wird

verfeinert, indem ein Netzelement durch ein weiteres Netz ersetzt wird. Umge-

kehrt wird ein Petrinetz vergröbert, indem ein bestehendes Netz zu einem

Netzelement zusammengefasst wird.

2.2.2 Spezielle Potenziale ausgewählter Petrinetz-Typen

Für die Modellierung mit Petrinetzen werden von der Theorie verschiedene

Petrinetz-Typen angeboten, die sich durch ihre unterschiedlichen Netzkompo-

nenten klassifizieren lassen. Dazu gehören45 Petrinetze mit Kanälen und Instan-

39 Oberweis (1996a), S. 176.

40 Gruhn/Kampmann (1996), S. 383.

41 Für einen Überblick über den Einsatz von Petrinetzen für die Modellierung von

Prozessstrukturen im akademischen Bereich siehe Janssens et al. (2000), insb. S. 3 f. Für

ein detailliertes Stärken/Schwächen-Profil für Petrinetze siehe Zelewski (1996), insb. S.

373.

42 Für einen ausführlichen Überblick über auf Petrinetzen basierende Software für die Model-

lierung von Prozessstrukturen siehe Salimifard/Wright (2001), S. 669-673. Als Beispiele

können das niederländische Unternehmen Pallas Athena BV mit der Software ,,Protos",

vgl. Protos (o.D.), das deutsche Unternehmen Promatis AG mit der Software ,,INCOME

Processdesigner", vgl. Income (o.D.), und das deutsche Unternehmen Software-Ley GmbH

mit der Software ,,COSA", vgl. Cosa (o.D.), genannt werden. In einer weiten Definition

können auch ereignisgesteuerte Prozessketten als vereinfachte Form eines Petrinetzes ver-

standen werden, vgl. Schütte (1998), S. 99; Langner et al. (1997), S. 480-485. Für Details

zu ereignisgesteuerten Prozessketten siehe Scheer (1998), S. 20.

43 Vgl. bspw. Income (o.D.).

44 Vgl. Reisig (1985), S. 67-75.

45 Weiter werden u.a. zeitbehaftete, gefärbte, stochastische und synthetische Petrinetze

angeboten. Diese Erweiterungen lassen sich jedoch z.T. mit den hier beschriebenen Netzty-

pen konstruieren, vgl. Richter (1993), S. 73 f.

---

12

zen (K/I-Netze)46, Bedingungen und Ereignissen (B/E-Netze)47, Stellen und

Transitionen (S/T-Netze)48 sowie Prädikaten und Transitionen (Pr/T-Netze)49.

Im folgenden wird die Anwendung dieser vier Netz-Typen anhand des Bei-

spiels der Fluggesellschaft für die semiformale und formale Beschreibung von

BIS erläutert. Dabei wird aufgezeigt, dass Unterschiede hinsichtlich der Eig-

nung dieser Netztypen für eine kombinierte Modellierung von Prozess- und

Datenstrukturen bestehen.

2.2.2.1 K/I-Netze

Abbildung 4 (s.u.) zeigt ein K/I-Netz, mit dem der Geschäftsvorfall

,,Flugvorbereitung" vereinfacht modelliert wurde. Mit dem in dieser Abbildung

dargestellten Netz wird

semiformal

beschrieben, dass Informationen über das

verfügbare Flugpersonal und die vorhandenen Crewanforderungen für eine

Crewzusammenstellung benötigt werden. Informationen über Crewanforderun-

gen ergeben sich aus einer Flugzeugzuweisung, für die wiederum Informatio-

nen über durchzuführende Flüge und verfügbare Flugzeuge benötigt werden.

Nach der Crewzusammenstellung findet eine Vollständigkeitsprüfung statt, mit

der überprüft wird, ob für alle Aufgaben (Pilot, Copilot, usw.) entsprechendes

Personal zugeordnet wurde. Das Ergebnis des hier beschriebenen Geschäfts-

vorfalls ist ein Einsatzplan.

Verfügbares

Flugpersonal

Crewzusammenstel ung

s1

t2

Flugdurchführung

s2

Flugzeugzuweisung

Volständigkeitsprüfung

t1

s4

t3

s5

Crew anforderung

Einsatzplan

s3

Verfügbare

Flugzeuge

Ähnlich: Jaeschke (1996), S. 183

Abbildung 4: Geschäftsvorfall "Flugvorbereitung" als K/I-Netz

46 Vgl. Baumgarten (1990), S. 49-76; Reisig (1985), S. 63-65.

47 Vgl. Baumgarten (1990), S. 111-116; Reisig (1985), S. 11-25; Reisig (1991), S. 19-33.

48 Vgl. Baumgarten (1990), S. 77-110; Reisig (1985), S. 27-35; Reisig (1991), S. 70-85.

49 Vgl. Baumgarten (1990), S. 193-222; Reisig (1985), S. 37-61; Reisig (1991), S. 132-145.

---

13

An dieser Stelle wird ein Vorteil der semiformalen Beschreibung in Abbildung

4 gegenüber der verbalen Beschreibung deutlich: Bereits dieser stark verein-

fachte Zusammenhang kann nur verhältnismäßig schlecht verständlich verbal

beschrieben werden. Eine weitere Stärke der Petrinetze ist die

Formalisierbar-

keit

dieser semiformalen Beschreibung. Dadurch ist es möglich, eine verbale

Beschreibung in eine leichter kommunizierbare semiformale Beschreibung zu

überführen, diese semiformale Beschreibung wiederum in eine formale Be-

schreibung zu überführen und umgekehrt. Es wird nun erläutert, wie aus der

semiformalen Beschreibung in Abbildung 4 eine solche formale Beschreibung

hergeleitet werden kann.

In einem Netz mit Kanälen und Instanzen50 stellt jeder Kanal (Kreis) eine

pas-

sive

Systemkomponente dar, die lagern, speichern, Zustände annehmen und

Objekte sichtbar machen kann. Jede Instanz (Rechteck) stellt eine

aktive

Sys-

temkomponente dar, die für die Erzeugung, den Transport und die Verände-

rung von Objekten verantwortlich ist. Ein Pfeil zeigt einen logischen Zusam-

menhang, räumliche Nähe, Zugriffsrechte oder unmittelbare Kopplung an. Mit

einem Pfeil wird keine ,,reale" Systemkomponente repräsentiert, sondern im-

mer eine abstrakte, gedankliche Beziehung (Relation). Zeigt ein Pfeil von einer

Instanz auf einen Kanal, gehört die Instanz zum Vorbereich des Kanals. Zeigt

umgekehrt ein Pfeil von einem Kanal auf eine Instanz, gehört die Instanz zum

Nachbereich des Kanals. Ein K/I-Netz wird i.d.R. mit natürlichsprachlichen

Anschriften versehen, präzise Schaltregeln existieren dagegen nicht.

Für die folgende formale Definition wurde zur Vereinfachung ­zusätzlich zur

natürlich sprachlichen Beschriftung­ jeder Kanal mit

si

,

i

= 1,...,

m

, jede Instanz

mit

tj

,

j

= 1,...,

n

beschriftet (vgl. Abbildung 4).

Das Beispiel aus Abbildung 4 zeigt ein Netz

N

= (

S

,

T

,

F

) mit

S

= {

s1

,

s2

,

s3

,

s4

,

s5

},

T

= {

t1

,

t2

,

t3

} und

F

= {(

s1

,

t2

), (

s2

,

t1

), (

s3

,

t1

), (

t1

,

s4

), (

t2

,

s4

), (

s4

,

t2

), (

s4

,

t3

), (

t3

, s5)}. Die Elemente aus

S

werden allgemein

Stellen

und die Elemente

aus

T

werden allgemein

Transitionen

genannt.

F

ist die

Flussrelation

51 von

N

.

50 Vgl. Reisig (1985), S. 63-65.

51 (

S T

) und (

T S

) bezeichnen jeweils das kartesische Produkt aus

S

und

T

bzw.

T

und

S

.

---

14

In K/I-Netzen stellen die

S

-Elemente

Kanäle

, die

T

-Elemente

Instanzen

dar.

Diese Mengen müssen bestimmten Bedingungen genügen, damit sie ein Netz

im Sinne eines K/I-Netzes beschreiben. Alle in den folgenden Kapiteln erläu-

terten Netze können als Erweiterungen dieses Petrinetz-Typs aufgefasst wer-

den. Sie müssen daher auch den nun folgenden Bedingungen genügen52.

Definition 1: Netz

Ein Tripel

N

= (

S

,

T

,

F

) heißt

Netz

, falls gilt:

(i)

S

,

T

sind endliche Mengen

(ii)

S

T

=

(iii)

S

T

(iv)

F

(

S T

) (

T S

)

Es lässt sich festhalten, dass mit der Petrinetz-Technik Prozessstrukturen durch

Kreise, Rechtecke und Pfeile

semiformal

beschrieben werden können. Weiter

können Prozessstrukturen durch Mengen, die bestimmten Bedingungen genü-

gen,

formal

beschrieben werden.

2.2.2.2 B/E-Netze

Abbildung 5 (s.u.) zeigt ein B/E-Netz. Es wurde ein Ausschnitt des Netzes aus

Abbildung 4 gewählt, um die Größe des Modells auf ein Mindestmaß zu

reduzieren und das Problem der kombinierten Modellierung von Prozess- und

Datenstrukturen zu fokussieren.

In einem B/E-Netz stellen die Kreise Bedingungen dar, die erfüllt (wahr) sein

müssen, damit das nachfolgende Ereignis eintreten kann. Eine erfüllte Bedin-

gung wird durch eine Marke (schwarzer Punkt im Kreis, auch als ,,Token" be-

zeichnet) repräsentiert. In dem hier konstruierten Systemzustand sind die Be-

dingungen ,,Flugdurchführung" (

s2

) und ,,Verfügbare Flugzeuge" (

s3

)

wahr

53.

52 Für weitere, allgemein bekannte Petrinetz-Definitionen siehe Anhang: Petrinetz-Definitio-

nen (S. 86-91). Diese Definitionen wurden Reisig (1985), Reisig (1986), Baumgarten

(1990) und Oberweis (1996a) entnommen und an die hier verwendete Notation angepasst.

53 Präziser wäre hier an den Stellen des Netzes die Verwendung der Beschriftungen

,,Informationen über Flugdurchführung vorhanden", ,,Informationen über verfügbare Flug-

---

15

Daher kann das Ereignis ,,Flugzeugzuweisung" (

t1

) eintreten. Nach dem Ein-

treten des Ereignisses ,,Flugzeugzuweisung" werden die Stellen

s2

und

s3 nicht
wahr

, und die Stelle

s4

wird

wahr

. Solange mindestens eine Bedingung im

Vorbereich nicht wahr ist, kann das nachfolgende Ereignis nicht eintreten. Ein

B/E-Netz wird formal wie ein K/I-Netz definiert, jedoch um sog.

Startmar-

kierungen

und

Schaltbedingungen

erweitert (vgl. Anhang: Petrinetz-Definitio-

nen).

Flugdurchführung (s2)

Flugzeugzuweisung (t1)

Crew anforderung (s4)

Verfügbare

Flugzeuge (s3)

Abbildung 5: Flugvorbereitung als B/E-Netz

Im Gegensatz zu K/I-Netzen können mit B/E-Netzen Bedingungen, z.B. für die

Ausführung eines Arbeitsschritts, repräsentiert werden. Eine erfüllte Bedin-

gung kann alternativ auch als das Vorhandensein eines Objekts interpretiert

werden. Mit dieser Interpretation lässt sich aber in jeder Stelle lediglich

ein

Objekt repräsentieren. Auch wird von der Struktur des zu repräsentierenden

Objekts abstrahiert, das Objekt kann nur ,,sein" oder ,,nicht sein". Für die Mo-

dellierung von BIS sind B/E-Netze daher nur auf einem hohen Abstraktions-

niveau anwendbar. Mitunter werden B/E-Netze schnell groß und unübersicht-

lich, z.B. müsste bereits bei der Möglichkeit, dass drei Flugzeuge gleichzeitig

verfügbar sind, jeweils eine Bedingung für jedes Flugzeug modelliert werden.

Für B/E-Netze lässt sich daher festhalten, dass zusätzlich

Bedingungen

und das

Vorhandensein von Objekten

repräsentiert werden können bzw. kann. Das ist

jedoch im Kontext von BIS nur auf einem hohen Abstraktionsniveau mit gro-

ßen, unübersichtlichen Netzen und daher

sehr schlecht

möglich.

zeuge vorhanden" und ,,Crewanforderung vorhanden". Zur besseren Vergleichbarkeit wur-

den aber die Beschriftungen aus Abbildung 4 beibehalten.

---

16

2.2.2.3 S/T-Netze

In Stellen/Transitionen- (S/T-) Netzen (vgl. Abbildung 6) werden die Kreise

als Objektbehälter interpretiert. Eine Kapazitätsbeschränkung (

k

) legt für jede

Stelle eine maximale (möglicherweise unendliche) Anzahl von Objekten fest,

die in der Stelle zu einem Zeitpunkt vorkommen darf. Die Objekte werden als

,,anonyme" Marken repräsentiert, die keine Eigenschaften (Werte) besitzen.

Transitionen können schalten, d.h. sie sind aktiviert, wenn in jeder Stelle im

Vorbereich genügend Marken entsprechend einer für jede Kante angegebenen

Kantengewichtung

w

vorhanden sind und wenn in jeder Stelle im Nachbereich

eine ausreichende Kapazität für zusätzliche Marken entsprechend der jeweili-

gen Kantenbeschriftung

w

ist. Wenn eine aktivierte Transition schaltet, wird

die an den Eingangskanten angegebene Anzahl von Marken aus den jeweiligen

Stellen im Vorbereich entfernt und die an den Ausgangskanten angegebene

Anzahl von Marken in die jeweiligen Stellen im Nachbereich eingefügt. For-

mal werden S/T-Netze gegenüber B/E-Netzen um Kapazitäten der Stellen und

Kantenbeschriftungen erweitert. Die Schaltregel muss entsprechend angepasst

werden (siehe Anhang: Petrinetz-Defintionen).

Flugdurchführung (s2)

w=1 Flugzeugzuweisung (t1)

k=100

w=1

w=1

Crew anforderung (s4)

k=20

k=1

Verfügbare

Flugzeuge (s3)

Abbildung 6: Flugvorbereitung als S/T-Netz

Im Vergleich zu B/E-Netzen kann in S/T-Netzen den Stellen eine Anzahl vor-

handener Objekte zugeordnet werden. Zusätzlich können für die Stellen Kapa-

zitätsbeschränkungen und durch Kantengewichtungen der Verbrauch an Ob-

jekten pro Arbeitsschritt angegeben werden. Von Objektstrukturen wird in S/T-

Netzen jedoch ebenfalls abstrahiert. Für die Modellierung von BIS impliziert

diese Beschränkung, dass von den Eigenschaften eines Objekts abstrahiert

werden muss.

---

17

Damit lässt sich festhalten, dass S/T-Netze

Kapazitäten

und den

Verbrauch

von Objekten repräsentieren können. Das stellt eine Verbesserung gegenüber

B/E-Netzen dar. Da jedoch weiterhin von Objektstrukturen abstrahiert werden

muss, lassen sich Objekte nur

schlecht

modellieren.

2.2.2.4 Pr/T-Netze

Abbildung 7 und Abbildung 8 (s.u.) zeigen ein Pr/T-Netz mit einer Startmar-

kierung bzw. einer Folgemarkierung. Pr/T-Netze ermöglichen die Integration

objektbezogener Aspekte. Jeder Stelle des Netzes wird, vereinfacht ausge-

drückt, eine ,,Tabelle" (genauer: eine Menge an Prädikaten mit veränderlichen

Ausprägungen) zugeordnet, die diese objektbezogenen Aspekte in Form von

Attributen (z.B. Flug#, Start, Ziel, ...) repräsentiert. Der Aufbau einer solchen

Tabelle wird im folgenden als

Datenstruktur

bezeichnet, die damit bezweckten

Repräsentationen von Objekten werden

Datenobjekte

genannt.

Den Transitionen werden Schaltbedingungen und Schaltwirkungen in Form

prädikatenlogischer Ausdrücke zugeordnet. Die Schaltbedingung muss erfüllt

sein, damit eine Transition schalten und die Schaltwirkung eintreten kann. Die

Kanten werden mit Mengen von Variablentupeln beschriftet, deren Stelligkeit

gleich der Stelligkeit der dazugehörigen (adjazenten) Prädikaten-Menge der

Stelle ist. Das Ergebnis dieser Schaltwirkung wird an die nachfolgende ,,Ta-

belle" der Stelle ,,weitergereicht", die Startmarkierung wird in eine Folgemar-

kierung transformiert.

Als Schaltbedingung könnte z.B. definiert werden, dass ein Flugzeug min-

destens über so viele Sitze verfügen muss, wie Plätze für den durchzuführen-

den Flug benötigt werden. Als Schaltwirkung könnte z.B. bei einer Flugbu-

chung (hier nicht dargestellt) definiert werden, dass die Anzahl der verfügbaren

Plätze für einen bestimmten Flug um die Anzahl

x

reduziert wird (für die for-

malen Definitionen der Pr/T-Netze siehe Anhang: Petrinetz-Definitionen).

---

18

Abbildung 7: Flugzeugzuweisung als Pr/T-Netz (Teil 1)

Abbildung 8 (s.u.) stellt das Schalten der Transition Flugzeugzuweisung (

t1

) in

bezug auf die Startmarkierung von Abbildung 7 dar. Für den Flug# 455 wird

ein Flugzeug mit mindestens 150 Plätzen benötigt. Das Flugzeug# 12 erfüllt

mit 155 Sitzen diese Bedingung. Da das Flugzeug# 12 einen Piloten und einen

Copiloten (,,Aufgaben") benötigt, wurde der Stelle Crewanforderung (

s2

) für

jede zu erfüllende Aufgabe jeweils ein

n

-Tupel (d.h. insgesamt

zwei n

-Tupel)

zugeordnet.

Abbildung 8: Flugzeugzuweisung als Pr/T-Netz (Teil 2)

---

19

Pr/T-Netze heben einen Teil der Restriktionen von B/E- und S/T-Netzen hin-

sichtlich der Repräsentation von Objekten durch die Möglichkeit der Verwen-

dung von Datenobjekten auf. Sie sind damit ­scheinbar­ gut geeignet zur Be-

schreibung von Prozess-

und

den zugehörigen Datenstrukturen. Wie im folgen-

den noch zu zeigen ist, bestehen jedoch auch bei Pr/T-Netzen Restriktionen,

durch die eine Repräsentation von BIS erschwert wird.

2.3 Modellierungsdefekte von Petrinetzen

2.3.1 Komplex strukturierte Datenobjekte

Wie in Kapitel 2.2.2.4 bereits angedeutet wurde, sind Pr/T-Netze hinsichtlich

der Datenobjekte auf ,,flache" Tabellen (d.h. unstrukturierte

n

-Tupel) be-

schränkt54. Komplex strukturierte Datenobjekte (im folgenden auch kurz: kom-

plexe Datenobjekte), wie z.B. das Formular aus Abbildung 1 (S. 6), lassen sich

dagegen nicht unmittelbar mit Pr/T-Netzen modellieren.

Die Beschränkung auf unstrukturierte

n

-Tupel führt dazu, dass zusammenge-

hörige Aspekte

eines

komplexen Datenobjekts in

mehreren

Zeilen einer Ta-

belle ­oder alternativ über mehrere Tabellen verteilt­ beschrieben werden

müssen. Um z.B. den in Abbildung 1 dargestellten Flug durchführen zu kön-

nen, wird genau

ein

Flugzeug benötigt. Für dieses eine Flugzeug ist jedoch eine

Cockpit-Crew erforderlich, die aus

mehreren

Personen besteht, nämlich aus

Pilot und Copilot. Da unstrukturierte

n

-Tupel nur

einzelwertige

Ausprägungen

der Attribute enthalten dürfen55, besteht ein Zwang, das Formular aus

Abbildung 1 relativ umständlich zu modellieren. Bereits der triviale

Zusammenhang ,,Flugzeug-Crew" würde das in Tabelle 2 dargestellte künstli-

che Konstrukt erzwingen.

Flugzeug

Flugzeug# Typ

Sitze Aufgabe

12 Airbus-320

155

Pilot

12 Airbus-320

155

Copilot

Tabelle 2: Flugzeug mit flachen n-Tupeln dargestellt

54 Vgl. Oberweis (1996a), S. 105-109.

55 Ein Attribut darf nur die Ausprägung ,,Pilot" oder ,,Copilot" annehmen, nicht jedoch die

Ausprägung ,,Pilot, Copilot".

---

20

Künstlich ist an Tabelle 2, dass die Ausprägungen der Attribute Flugzeug#,

Typ und Sitze doppelt angegeben werden müssen, damit beide Aufgaben er-

fasst werden können. Die Verwendung von mehreren Attributen (z.B. ,,Auf-

gabe1", ,,Aufgabe2" usw.) ist unbefriedigend, weil so für jede potenzielle Auf-

gabe ein einzelnes Attribut verwendet werden müsste, wodurch das Modell

unübersichtlich würde. Alternativ könnten diese

redundanten

Daten durch eine

Aufteilung über zwei Tabellen weitgehend vermieden werden (vgl. Tabelle

3)56. Dann müsste die Beschreibung der verfügbaren Flugzeuge aber zugleich

auf zwei Stellen im Netz verteilt werden, was ebenfalls eine künstliche und

unübersichtliche Beschreibung wäre. Mitunter könnte dadurch in komplexen

Modellen der Fall eintreten, dass durch einen Fehler des Modellierers zwar das

Löschen des Flugzeugs modelliert, das Löschen der zugehörigen Aufgaben

jedoch vergessen wird. In einem solchen Fall spricht man von

Inkonsistenzen

hinsichtlich des Modells und damit später auch der Datenbestände57.

Flugzeug

Aufgabe

Flugzeug# Typ Sitze

Flugzeug# Bezeichnung

12 Airbus-320

155

12 Pilot

12 Copilot

Tabelle 3: Aufteilung von Daten über mehrere Tabellen

Es lässt sich festhalten, dass Pr/T-Netze für die Modellierung von komplexen

Datenobjekten lediglich

mittelmäßig

geeignet sind. Das ist darin begründet,

dass komplexe Strukturen, wie sie Datenobjekten i.d.R. eigen sind, zu kompli-

zierten und künstlichen Netzkonstruktionen führen, da der Zugriff einer Tran-

sition auf alle zu einem Datenobjekt gehörigen Tupel nur umständlich model-

liert werden kann.

2.3.2 Unabhängig voneinander ausführbare Arbeitsschritte

Das Problem der Modellierung von

Nebenläufigkeit

58, d.h. unabhängig

voneinander ausführbarer Arbeitsschritte, folgt aus dem Problem, dass kom-

plexe Datenobjekte in Pr/T-Netzen nur umständlich modelliert werden können.

56 Das entspräche dem Vorgehen bei der Normalisierung, wie sie CODD vorschlägt, vgl. Codd

(1970), S. 381 f.

57 Mit einer Modellierungssoftware könnten solche Inkonsistenzen zwar automatisch erkannt

und damit verhindert werden, das Problem künstlicher und unübersichtlicher Modelle wäre

damit jedoch nicht gelöst.

58 Vgl. Oberweis (1996a), S. 107 f.

---

21

So könnte dasselbe Formular ­falls in digitalisierter Form vorliegend­ gleich-

zeitig für mehrere Arbeitsschritte und unterschiedliche Mitarbeiter im Zustand

,,in Bearbeitung" sein. Wenn aber ausgeschlossen werden soll, dass ein Sach-

bearbeiter gleichzeitig mehrere Arbeitsschritte ausführt, d.h. mehrere Formu-

lare gleichzeitig am Bildschirm geöffnet hat, dann ist die Einführung einer

,,künstlichen" Prädikat-Stelle ,,Formular-gesperrt" nötig.

Ähnlich: Oberweis (1996a), S. 108.

Abbildung 9: Sperren eines Datenobjektes

Angenommen, es soll beschrieben werden, dass dasselbe Datenobjekt ,,Flug-

zeug" an unterschiedlichen Arbeitsplätzen unabhängig voneinander bearbeitet

wird. So ist es bspw. denkbar, dass an bestimmten Arbeitsplätzen den Flugzeu-

gen Crews zugewiesen werden und an anderen Arbeitsplätzen für dieselben

Flugzeuge Eintragungen für erforderliche Inspektionen vorgenommen werden.

Wenn aber ausgeschlossen werden soll, dass ein Sachbearbeiter in einem

EDV-System z.B. gleichzeitig für mehrere Flugzeuge Crew-Zuweisungen vor-

nimmt, dann ist die Einführung der oben erwähnten künstlichen Prädikat-Stelle

,,Formular-gesperrt" notwendig. Da in Pr/T-Netzen keine komplexen Daten-

objekte zugelassen sind, kann ein Formular mit dem Status ,,Formular-ge-

sperrt" in anderen Arbeitsschritten nicht mehr bearbeitet werden.

Es lässt sich das Fazit ziehen, dass Restriktionen hinsichtlich der Nebenläufig-

keit von Schaltvorgängen auf unterschiedlichen Komponenten desselben kom-

plexen Datenobjekts nur sehr umständlich modellierbar sind. Daher kann fest-

gehalten werden, dass Pr/T-Netze für die Modellierung von Nebenläufigkeit

lediglich

mittelmäßig

geeignet sind.

---

22

2.3.3 Undefinierte Werte

Das Problem der undefinierten Werte59 betrifft in dem hier verwendeten Bei-

spiel das Einfügen von Fluganforderungen, für die noch nicht bekannt ist, wie

viele Sitzplätze benötigt werden. In einem solchen Fall müssten vordefinierte

Nullwerte

eingeführt werden, die angeben, dass für den betreffenden Flug noch

nicht feststeht, wie viele Sitzplätze benötigt werden. Um eine konsistente Be-

handlung von Nullwerten sicherzustellen, müssten zusätzliche Integritätsbe-

dingungen eingeführt werden, die eine konsistente Behandlung solcher Null-

werte sicherstellen.

Flug# Start Ziel Datum

Plätze

455 Düsseldorf Rom

24.07.2002 0

354 Rom

Düsseldorf 27.07.2002 N.B.

Tabelle 4: Nullwerte in einem flachen n-Tupel

Würde bspw. der Fall eintreten, dass die Anzahl der benötigten Plätze für einen

einzutragenden Flug noch nicht bekannt ist, so ließe sich dies nicht durch die

Zahl

,,0" darstellen. Zeile 1 in Tabelle 4 könnte nämlich interpretiert werden

derart, dass für den Flug# 455

keine

Plätze benötigt werden. Daher müsste für

ein betroffenes Pr/T-Netz vereinbart werden, dass bspw. der Wert ,,N.B." da-

hingehend zu interpretieren ist, dass

nicht bekannt

ist, wie viele Plätze benötigt

für den Flug benötigt werden.

Es lässt sich festhalten, dass in Pr/T-Netzen eine umständliche Einführung von

Nullwerten notwendig ist, um leere Mengen repräsentieren zu können. Wün-

schenswert ist dagegen, leere Mengen explizit repräsentieren zu können.

2.4 Ansätze zur Heilung der Modellierungsdefekte

(1) Abstraktion von Datenstrukturen

Durch die Verwendung von B/E- und S/T-Netzen kann generell von Daten-

strukturen abstrahiert werden60, d.h. Objekte werden als Marken ohne weitere

Eigenschaften (Attribute) modelliert. Auch kann das Systemverhalten dann

nicht explizit in Abhängigkeit von bestimmten Objekteigenschaften beschrie-

ben werden, sondern nur in Abhängigkeit von dem Vorhandensein eines Ob-

59 Vgl. Oberweis (1996a), S. 108 f.

60 Vgl. Oberweis (1996a), S. 110.

---

23

jektes. Alternativ könnte zwar jede Objekteigenschaft in B/E-Netzen durch

eine Bedingung und in S/T-Netzen durch eine Marke repräsentiert werden. Das

bedeutet jedoch eine Aufblähung des Netzes und ist bei im Umfang über Trivi-

albeispiele hinausgehenden Anwendungen kaum praktikabel.

(2) Verwendung eines einfachen Datenmodells

Aufgrund der fehlenden Schnittstelle zwischen komplexen Datenobjekten und

Pr/T-Netzen kann zur Datenmodellierung ein (Meta-)Datenmodell eingesetzt

werden, das keine komplexen Datenobjekte zulässt61. Damit wird jedoch nur

das Schnittstellenproblem zwischen Pr/T-Netzen und Datenstrukturen gelöst,

nicht jedoch die Probleme der Beschreibung komplexer Datenobjekte, der Ne-

benläufigkeit und der undefinierten Werte.

(3) Zulassen komplexer Datenobjekte

Die zuvor genannten Ansätze heilen die Modellierungsdefekte von Petrinetzen

durch eine

Reduzierung

des Modellierungspotenzials, lösen aber nicht die zu-

vor beschriebenen Defekte der Pr/T-Netze. Um diese Defekte zu heilen,

ohne

das Modellierungspotenzial zu reduzieren, müssten komplexe Datenobjekte

und die Möglichkeit zur Manipulation dieser (d.h. hinzufügen, ändern und lö-

schen) in Petrinetze integriert werden, idealerweise mit der Möglichkeit der

Heilung des Nebenläufigkeit-Defekts und der Repräsentation undefinierter

Werte von Attributen. Aus diesen Anforderungen folgt jedoch, dass man dafür

in einem ersten Schritt die Restriktion Datenobjekte müssten als flache

n

-Tupel

konstruiert sein fallen lassen muss. Denn wie bereits z.T. erläutert wurde, re-

sultieren die Probleme aus dem Zwang zur Modellierung der Datenobjekte als

flache

n

-Tupel.

61 Vgl. Oberweis (1996a), S. 109 f.

---

24

3 Ansätze zur Heilung der Modellierungsdefekte von

Petrinetzen mit Hilfe der Entity-Relationship-

Technik

Im diesem Kapitel wird eine zusätzliche Modellierungstechnik für die Model-

lierung von Datenstrukturen eingeführt. Dabei wird von dem für die Datenmo-

dellierung verbreiteten Entity-Relationship- (E-R-) Ansatz ausgegangen, da

dieser unabhängig von EDV-technischen Implementierungsaspekten, intuitiv

verständlich62 und formalisierbar63 ist. Dieser E-R-Ansatz wird anschließend

derart erweitert und formal definiert, dass daraus abgeleitete komplexe Daten-

objekte mit Petrinetzen kombiniert werden können. Durch eine solche Kombi-

nation sollen dann sowohl Prozess- als auch Datenstrukturen eines BIS Model-

liert werden können.

3.1 Das Modellierungspotenzial der Entity-Relationship-

Technik

Der Entity-Relationship-

Ansatz

wurde 1976 von CHEN als konzeptuelles Da-

tenmodell vorgestellt64. Die Entity-Relationship-

Technik

(E-R-Technik) be-

zieht sich auf dieses konzeptuelle Datenmodell, das im folgenden um die für

die hier behandelte Problematik relevanten Aspekte erweitert wird.

CHEN definiert ,,Entity" als ein ,,Ding", das deutlich (,,distinctly") identifi-

ziert werden kann und nimmt an, dass zwischen Entities Beziehungen (Rela-

tionen) existieren65. Auf der Grundlage dieses Ansatzes wurden verschiedene

Varianten und Erweiterungen entwickelt66, die in der betrieblichen Praxis z.T.

Verbreitung gefunden haben67.

62 Vgl. Chen (1977), S. 9 f.

63 Vgl. Thalheim (2000), S. 29-54.

64 Für die Originalarbeit von CHEN siehe Chen (1976) und Chen (1977). Für eine Einführung

in die E-R-Modellierung siehe z.B. Rauh/Stickel (1997), S. 37-110, und Thalheim (2000),

S. 29-54. Für erweiterte E-R-Techniken siehe Thalheim (2000), S. 55-424. Im Rahmen die-

ser Arbeit werden nur für die Thematik relevante Aspekte erläutert.

65 Vgl. Chen (1977), S. 17.

66 Vgl. Rauh/Stickel (1997), S. 87-101.

67 Vgl. Jaeschke (1996), S. 196 f.

---

25

3.1.1 Semiformale Datenmodelle

Die E-R-Technik bietet die Möglichkeit, Datenmodelle unabhängig von

Aspekten der technischen Implementierung in ein EDV-System zu kon-

struieren. Statt technischer Implementierungsaspekte wird die Repräsentation

der ,,realen Welt" fokussiert, was als

konzeptuelle Datenmodellierung

bezeich-

net wird68. Die Ergebnisse der konzeptuellen Datenmodellierung zeigen die

Datenobjekte

des Systems und die

Beziehungen

zwischen ihnen.

Unter einem Datenmodell versteht man allgemein ein Grundmuster zur Glie-

derung und Manipulation von Daten. Da die E-R-Technik ursprünglich nicht

als Basis für die Implementierung in Datenbanksysteme verwendet wurde,

sondern vielmehr als Beschreibungssprache für die vorgelagerte Modellierung

von Datenstrukturen, wurden die notwendigen Operationen zur Manipulation

der Daten in der Originalarbeit von CHEN nur bruchstückhaft definiert69. Im

folgenden wird jedoch gezeigt, dass man die E-R-Technik durchaus formal

definieren und um Operationen zur Manipulation der Daten ergänzen kann.

Damit steht dann eine Technik zur Verfügung, mit der Datenstrukturen sowohl

mit einer

semiformalen

als auch mit einer

formalen

Sprache beschrieben wer-

den können. Auf dieser Basis wird anschließend analysiert, wie die E-R-Tech-

nik mit der Petrinetz-Technik kombiniert werden kann und welche Erweiterun-

gen dafür gegebenenfalls notwendig sind.

Flugz eug-

Mitarbeiter

qualifiziert

1 Aufgabe

benötigt

n n 1

für (R

(R3)

Typ (E

(E

1)

4)

1)

(E2)

ist

vom Typ

1

(R2)

1

Flugz eug

benutzt

Flug (E5)

für (R

(E

4)

1 1

3)

Abbildung 10: E-R-Modell ohne Attribute

68 Vgl. Chen (1977), S. 9 f.

69 Vgl. Rauh/Stickel (1997), S. 16 f. Diese ,,bruchstückhaften Definitionen" finden sich bei

Chen (1976) auf S. 11-20. Auf S. 20-25 wird ansatzweise eine implementierungsnahe Da-

tenbank-Abfragesprache vorgeschlagen, und auf S. 25-34 analysiert CHEN, wie implemen-

tierungsnahe Datenmodelle aus dem E-R-Modell hergeleitet werden können.

---

26

Abbildung 10 zeigt ein E-R-Modell für das stark vereinfachte Beispiel der

Flugdurchführung. Rechtecke stellen Entity-Typen, Rauten Relationship-Ty-

pen (im folgenden auch als ,,Beziehungs-Typen" bezeichnet) dar. Entity-Typen

müssen

, Beziehungs-Typen

können

Attribute70 besitzen. Entity-Typen werden

durch ihre Attribute, Beziehungs-Typen durch die ihnen zugeordneten Entity-

Typen und den Attributen der Beziehung (Relation) beschrieben. Weiter wer-

den bei der E-R-Modellierung sog. ,,Kardinalitäten" verwendet, die an die

Kanten zwischen Entity-Typ und Beziehungs-Typ geschrieben werden71. Eine

Kardinalität gibt an, wie viele Entities (d.h. Ausprägungen) eines Entity-Typs

zu einer Beziehung gehören. In Abbildung 10 gehört z.B. genau ein Entity vom

Typ ,,Mitarbeiter" (

E1

) und

n

(d.h. ein oder mehrere) Entities vom Typ ,,Auf-

gabe" (

E2

) zur Beziehung ,,qualifiziert für" (

R1

).

Aufgabe

Flugz eug-

Mitarbeiter

1

qualifiziert

n

n

benötigt

1

für (R

(E

(R3)

Typ (E

(E

1)

2)

4)

1)

MA#

Name

Bezeichnung

Typname

(a1)

(a2)

(a3)

(a4)

Abbildung 11: E-R-Modell mit Attributen

Abbildung 11 zeigt einen um

Attribute

erweiterten Ausschnitt aus dem E-R-

Modell der Abbildung 10. Die Attribute werden als Ellipsen dargestellt. Attri-

bute, mit denen ein Entity eindeutig identifiziert werden kann, werden unter-

strichen dargestellt und als ,,Schlüssel" bezeichnet.

In Abbildung 11 ist folgender Zusammenhang

semiformal

dargestellt: ,,Ein

Mitarbeiter, charakterisiert durch Ma# und Name, ist qualifiziert für

n

Aufga-

ben (charakterisiert durch die Bezeichnung der Aufgabe). Es werden

n

Aufga-

ben für einen Flugzeug-Typ benötigt".

70 Diese Attribute sind in Abbildung 10 zur Vereinfachung nicht grafisch dargestellt. Das

Weglassen der Attribute in der grafischen Darstellung ist ein übliches Vorgehen zur Kom-

plexitätsreduzierung in den frühen Phasen der Datenmodellierung.

71 Auf erweiterte Kardinalitäten mit sog. (min,max)-Notation wird in dieser Arbeit zur

Vereinfachung verzichtet. Die hier konstruierten Beispiele können jedoch um diese Nota-

tion erweitert werden. Zu (min,max)-Kardinalitäten siehe z.B. Jaeschke et al. (1994), S. 29

f.; Rauh/Stickel (1997), S. 26; Schütte (1998), S. 95; Thalheim (2000), S. 165-199.

---

27

Die Komplexitätsreduzierung wird u.a. durch die Abstraktionsprinzipien

Gene-

ralisierung

und

Aggregation

unterstützt72. Bei der Generalisierung wird von

Entity-Typen abstrahiert, indem zu zwei oder mehreren untergeordneten Da-

tenobjekten (Sub-Typen) ein übergeordnetes Datenobjekt gesucht wird (Super-

Typ). Durch eine Aggregation wird aus bestehenden Entity-Typen ein neues

Datenobjekt erzeugt.

Davon zu unterscheiden ist die strukturelle Beschreibung eines Datenmodells

durch Hierarchisierung von Systemen, indem Cluster gebildet werden73. In

Clustern werden Entity- und Relationship-Typen zusammengefasst, damit eine

abstraktere Betrachtung auf Cluster- und nicht auf Entity-Typ-Ebene möglich

wird. Die Datencluster selbst können wiederum hierarchisch geordnet sein.

3.1.2 Formale Datenmodelle

In dem in Abbildung 10 und Abbildung 11 dargestellten Beispiel wurden die

natürlichsprachlichen Bezeichnungen (Mitarbeiter, Aufgabe, Flugzeug-Typ,

...) der Entity- und Beziehungs-Typen sowie der Attribute zusätzlich um for-

male Bezeichnungen (

E1

,

R1

,

a1

, ...) ergänzt, um formale Definitionen im fol-

genden kompakter und allgemeiner konstruieren zu können. Statt z.B. ,,Entity

vom Typ Mitarbeiter" wird damit im Rahmen der formalen Definition alterna-

tiv die Bezeichnung ,,

E1

" verwendet. In konkreten Beispielen werden dagegen

primär die natürlichsprachlichen Bezeichnungen verwendet, um die Verständ-

lichkeit zu erhöhen. Anhand des E-R-Modells in Abbildung 11 wird nun ge-

zeigt, wie dieses semiformale Datenmodell formalisiert werden kann. Dafür

werden die Begriffe ,,Datenmodell", ,,Entity-Typ" und ,,Beziehungs-Typ" for-

mal definiert.

Definition 2: Datenmodell

Formal ist ein Datenmodell

D

= (

U

, ,

dom

) definiert durch74

die endliche Menge aller Attribute

U

,

die Menge der Domänen = (

d1

,

d2

, ...,

dn

)

72 Vgl. Schütte (1998), S. 96-99.

73 Vgl. Schütte (1998), S. 99.

74 Vgl. Thalheim (2000), S. 34 f.

---

28

und einer Funktion

dom

:

U

welche die Domäne mit jedem Attribut

verknüpft.

In dem Beispiel aus Abbildung 11 ist

U

= {Ma#, Name, Bezeichnung, Typ-

name},

dom

(Ma#) =

Int

,

dom

(Name) =

dom

(Bezeichnung) =

dom

(Typname) =

Char

. Dabei bezeichnet

Char

die Menge aller Buchstaben, Ziffern und Sonder-

zeichen, z.B. ist {1, 2, a, b, -, +}

Char

.

Int

bezeichnet die Menge der natür-

lichen Zahlen. Eine solche Domäne kann auch spezifischer definiert werden,

z.B. könnte auch

dom

(Typname) = {Airbus-320, Airbus-330, Boing-747} sein.

Definition 3: Entity-Typ

Ein Entity vom Typ

E

ist75

ein Paar (

attr

(

E

),

id

(

E

))

wobei

E

der Name der Entity-Menge ist,

attr

(

E

)

U

eine Menge von Attributen von

U

und

id

(

E

)

attr

(

E

) eine Teilmenge von Attributen ist, die ,,

Schlüssel

" ge-

nannt wird.

Durch seinen Schlüssel lässt sich ein Entity eindeutig identifizieren. In dem

Beispiel aus Abbildung 11 ist das Attribut MA# (Mitarbeiternummer) des En-

tity-Typs Mitarbeiter alleiniger Schlüssel. Ein Schlüssel kann auch aus mehre-

ren Attributen bestehen. Ist der Schlüssel

id

(

E

) eines Entity-Typs leer, wird der

Entity-Typ ,,

Weak Entity

" genannt. Die Existenz eines solchen Entity-Typs ist

dann abhängig von der Existenz anderer Entity-Typen. Ein Entity vom Typ

,,Flug" (in dem Beispiel nicht dargestellt) könnte z.B. abhängig von der Exis-

tenz eines Entities vom Typ ,,Flugzeug" sein.

Definition 4: Beziehungs-Typ

Eine Beziehung vom Typ

R

ist76

ein Paar (

ent

(

R

),

attr

(

R

)) wobei

R

der Name des Beziehungs-Typs (alternativ: Relationen-Typs),

75 Vgl. Thalheim (2000), S. 34.

76 Vgl. Thalheim (2000), S. 34.

---

29

ent

(

R

)

E

eine Sequenz von Entity-Typen und

attr

(

R

)

U

eine Teilmenge von Attributen von

U

ist.

Mit Hilfe dieser Definitionen kann man das Beispiel aus Abbildung 11 formal

mit Gleichungen wie folgt beschrieben werden:

E1

:= (

a1

,

a2

),

E2

:= (

a3

),

E4

:= (

a4

),

R1

:= (

E1

,

E2

) ,

R3

:= (

E2

,

E4

).

Die o.g. Kardinalitäten sind in diesen Gleichungen zur Vereinfachung nicht

enthalten. Sie könnten aber in den Relationen oder separat als Restriktionen

definiert werden.

3.1.3 Resümee

Es wurde gezeigt, dass eine verbal beschriebene Datenstruktur eines Informa-

tionssystems mit Hilfe der E-R-Technik in eine semiformale Sprache überführt

werden kann. Weiter lässt sich diese semiformale Sprache anschließend in eine

formale Sprache überführen. Gleiches gilt auch für die Petrinetz-Technik, was

bereits in Kapitel 2.2 gezeigt wurde. Hinsichtlich der Kombination dieser bei-

den Techniken treten jedoch Probleme auf, da durch E-R-Modelle repräsen-

tierte komplexe Datenobjekte mit ihren möglicherweise vielfältigen Beziehun-

gen untereinander ­wie in Kapitel 2.3 erläutert­ nicht ohne weiteres in Pr/T-

Netzen verwendet werden können.

Es lässt sich damit festhalten, dass die E-R-Technik gut für die Repräsentation

der Datenstruktur geeignet ist. Eine Kombination der E-R- in die Petrinetz-

Technik ist jedoch mit Problemen behaftet. Die E-R-Technik als nicht mit

Petrinetzen kombinierte Modellierungstechnik ist daher für die Repräsentation

betrieblicher Informations

systeme

lediglich

mittelmäßig

geeignet.

3.2 Komplexe Datenobjekte in E-R-Modellen

3.2.1 Normalisierung komplexer Datenobjekte

Um das E-R-Modell aus Abbildung 11 in ein Pr/T-Netz integrieren zu können,

müsste eine

Normalisierung

, basierend auf dem

relationalen Datenmodell

von

CODD77, durchgeführt werden. Eine aus der Normalisierung resultierende

Nor-

77 Vgl. Codd (1970), insb. S. 381 f.

---

30

malform

ist eine allgemeine und formale Beschreibung eines zweckmäßigen

Tabellenaufbaus78. Die Normalisierungstheorie befasst sich mit dem Problem,

wie Tabellen strukturiert sein müssen, so dass die Daten möglichst problemlos

modifiziert werden können. Probleme bei der Modifikation von Daten werden

besonders durch Redundanz der Daten verursacht. Dafür hat die Normali-

sierungstheorie verschiedene durchnummerierte Normalformen entwickelt,

wobei eine höhere Normalform strengere Anforderungen an eine Tabelle stellt

als eine niedrigere.

Eine nach der Normalisierungstheorie ,,akzeptable" Tabelle erfüllt i.d.R. min-

destens die dritte Normalform (3NF), die höchste Normalform ist die Fünfte79.

Zur Behandlung des Problems der Repräsentation von BIS wird an dieser

Stelle kurz die gemäß der Normalisierungstheorie als inakzeptabel zu bezeich-

nende nullte Normalform (Non First Normalform, NFNF), die als ungünstig

bezeichnete80 erste Normalform (1NF) und die als akzeptabel bezeichnete 3NF

vorgestellt.

Eine Tabelle befindet sich in der NFNF, wenn der Wertebereich der Attribute

nicht atomar ist. Das ist dann der Fall, wenn in der Zelle einer Tabelle einem

Attribut zwei oder mehr Werte zugeordnet sind. Tabelle 5 stellt eine mögliche

Instanziierung

der Datenstruktur des E-R-Modells aus Abbildung 11 in der

NFNF dar. Dass sich diese Tabelle in der NFNF befindet, ist darin begründet,

dass der Ausprägung des Attributs ,,Typname" zwei Werte (Airbus-320 und

Boing-747) zugeordnet sind.

Mitarbeiter-Aufgaben-Flugzeugtyp (ENFNF)

Ma# (a1) Name

(a2) Aufgabe

(a3) Typname (a4)

1024 (

1.1

) Smit h (

2.1

) Pilot (

3.1

)

Airbus-320

Boing-747 (

4.1

)

Tabelle 5: Daten in Non First Normalform

Eine solche Mehrwertigkeit muss aus der Sicht der Normalisierungstheorie als

nicht akzeptabel bezeichnet werden, weil formal nur die Zelle

4.1

als Ganzes

beschrieben werden kann, nicht jedoch die Ausprägung ,,Airbus-320" als ein-

78 Vgl. Rauh/Stickel (1997), S. 127-143.

79 Vgl. Rauh/Stickel (1997), S.127.

80 Vgl. Rauh/Stickel (1997), S. 134 f.

---

31

zelner Wert. Das wäre z.B. dann problematisch, wenn eine Bedingung model-

liert werden soll, die besagt, dass nur ein Pilot mit Qualifikation für den Flug-

zeug-Typ Airbus-320 ein entsprechendes Flugzeug fliegen darf.

Dieses Problem löst die 1NF, die fordert, dass der Wertebereich der Attribute

atomar

81 ist. Es dürfen also keine weiteren Mengen von Werten (und keine

weiteren Relationen) in der Ausprägung eines Attributs, d.h. in der Zelle einer

Tabelle, vorkommen. Überführt man das E-R-Modell aus Abbildung 11 in die

erste Normalform, lässt sich das Ergebnis in Tabellenform wie in Tabelle 6

darstellen. Zusätzlich sind in Tabelle 6 wieder Ausprägungen der Attribute

aufgelistet.

Mitarbeiter-Aufgaben-Flugzeugtyp (E1NF)

Ma# (a1) Name

(a2) Aufgabe

(a3) Typname

(a4)

1024 (

1.1

) Smit h (

2.1

) Pilot

(

3.1

) Airbus-320

(

4.1

)

1024 (

1.2

) Smit h (

2.2

) Pilot

(

3.2

) Boing-747

(

4.2

)

2048 (

1.3

) Müller (

2.3

) Copilot (

3.3

) Airbus-320

(

4.3

)

2048 (

1.4

) Müller (

2.4

) Navigator (

3.4

) Boing-747 (

4.4

)

Tabelle 6: Daten in erster Normalform

Die Ausprägung eines Attributs wird auch als

Instanz

bezeichnet. Bestehen

Instanzen nur aus einzelwertigen Attributen, befinden sie sich in der 1NF (s.o.).

Der Begriff ,,Instanz" kann für einzelwertige Attribute formal definiert werden.

Definition 5: Instanz (einzelwertige Attribute)

Es sei82

D

ein Datenmodell und

U

die Menge aller in

D

auftretenden Na-

men. Die Menge aller möglichen Instanzen einzelwertiger Attribute

a

von

D

wird definiert durch

a

U

und

dom

(

a

).

a

: ist eine Instanz vom Typ

a

mit der einzelwertigen (synonym: atomaren und synonym: elementaren) Aus-

prägung .

81 Synonym zu ,,

atomar

" werden in dieser Arbeit die Begriffe ,,

elementar

" und ,,

einzelwertig

"

verwendet.

82 Vgl. ähnlich Oberweis (1996a), S. 113 f.

---

32

In dem Beispiel aus Abbildung 11 ist das Datenmodell

D

= {

E1

:= (

a1

,

a2

),

E2

:= (

a3

),

E4

:= (

a4

),

R1

:= (

E1

,

E2

) ,

R3

:= (

E3

,

E4

)}. In dem Beispiel aus Tabelle 6

besteht das Datenmodell nur noch aus einem einzigen Entity

E1NF

, d.h.

D

=

E1NF

:= (

a1

,

a2

,

a3

,

a4

).

Tabelle 6 erfüllt die Forderung der ersten Normalform, da die Wertebereiche

der Attribute ,,Ma#", ,,Name", ,,Aufgabe" und ,,Typname" atomar sind. Dafür

wird jedoch von einem Teil der Datenstruktur abstrahiert, d.h. Informationen

über die Struktur der Daten gehen verloren. Auch wird es nun erforderlich,

jeden Mitarbeiter mehrmals aufzuführen, sofern er mehrere Qualifikationen

besitzt. Diese Redundanz bereitet Probleme, wenn das Modifizieren von Daten

modelliert werden soll83, weshalb die 1NF aus der Sicht der

Normalisierungstheorie als ,,ungünstig" bezeichnet werden kann.

Dieses Problem wird durch die 3NF gelöst. Die 3NF fordert, eine wie oben

dargestellte Tabelle in mehrere Tabellen aufzuteilen derart, dass keine funktio-

nalen Abhängigkeiten zwischen nicht dem Schlüssel angehörigen Attributen

einer Tabelle bestehen. Dadurch wird die bemängelte Redundanz auf die

Schlüsselattribute reduziert. In Tabelle 7 wird die funktionale Abhängigkeit

Mitarbeiter

Flugzeug-Typ (vgl. Tabelle 6) über zwei Tabellen ,,verteilt"84.

Mitarbeiter

Flugzeug-Typ

Ma# Name

Ma# Aufgabe Typname

1024 Smith

1024 Pilot Airbus-320

2048 Müller

1024 Pilot Boing-747

2048 Copilot Airbus-320

2048 Navigator Boing-747

Tabelle 7: Daten in dritter Normalform

Bezogen auf das Problem der kombinierten Prozess- und Datenmodellierung

ergibt sich aus dieser vermeintlichen Lösung aber wieder das Problem, dass

jeder Stelle eines Pr/T-Netzes nur eine ,,Tabelle", d.h. eine Menge unstruktu-

rierter

n

-Tupel, zugeordnet werden kann85. Möchte man aber ein komplexes

Datenobjekt in

einer

Stelle beschreiben, ist das nach der Normalierungstheorie

83 Das Löschen eines Mitarbeiters würde das Löschen mehrerer Zeilen der Tabelle erfordern.

84 Ein weiteres Aufteilen der Attribute ,,Aufgabe" und ,,Typname" erscheint dagegen nicht

sinnvoll, da beide Attribute gemeinsam den Schlüssel darstellen.

85 Dieses Problem besteht u.a. bei dem Ansatz zur Kombination von E-R- und Petrinetz-Tech-

nik von Heuser et al. (1993), insb. S. 276. HEUSER ET AL. nehmen in ihrem Ansatz implizit

die Restriktionen der Normalisierungstheorie an.

---

33

nur durch die Verwendung der 1NF möglich, womit aber wiederum Datenre-

dundanz hingenommen werden muss. Dieses Dilemma führt wieder zu den in

Kapitel 2.3 beschriebenen Problemen.

Damit kann es als zutreffend bezeichnet werden, dass die Normalisierungs-

theorie für die Strukturierung von Datentabellen (z.B. für die Implementierung

in relationale Datenbanken) hilfreich ist. Die Probleme kombinierter Prozess-

und Datenmodellierung lassen sich damit jedoch

nicht

lösen.

3.2.2

Genestete Relationen zur Modellierung komplexer

Datenobjekte

3.2.2.1 Das Modellierungspotenzial genesteter Relationen

Eine Modellierung von Datenstrukturen auf Grundlage der Normalisierungs-

theorie führt offensichtlich nicht zur Lösung des Problems der kombinierten

Modellierung von Prozess- und Datenstrukturen. Vielmehr erscheint es not-

wendig, nach geeigneten Methoden zu suchen, mit denen der zu betrachtende

Realweltausschnitt adäquat, d.h. wirklichkeitsnah und mit möglichst wenig

Informationsverlust, beschrieben werden kann. Ein wichtiges Merkmal ist da-

bei die Unterstützung

komplexer Datenobjekte

86.

Mitarbeiter

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Typname

1024 Smith

Pilot

Airbus-320

Boing-747

2048 Müller

Copilot Airbus-320

Navigator Boing-747

Tabelle 8: Komplexes Datenobjekt als geschachtelte Tabelle

In Tabelle 8 ist der gleiche Zusammenhang wie in Tabelle 6 dargestellt. Jedoch

erfüllt Tabelle 8

nicht

die Bedingung der 1NF. Dem ersten Tupel (d.h. der

ersten Zeile der ,,oberen" Tabelle) sind durch eine Schachtelung bspw.

zwei

Werte des Attributs ,,Typname" zugeordnet, was der von der Normali-

sierungstheorie als nicht akzeptabel bezeichneten NFNF entspricht. So können

86 Vgl. Bancilhon/Khoshafian (1989), S. 326 f.; Lamersdorf/Schmidt (1983), S. 150 f.; Sander

(1992), S. 93; Sander (1993), S. 1 f.; Schek/Scholl (1983), S. 114 f.; Schek/Scholl (1986),

S. 137.

---

34

aber diejenigen Strukturen in

einer

(geschachtelten) Tabelle dargestellt werden,

die am Anfang der Arbeit in Abbildung 1 (S. 6) als ,,Formular" vorgestellt wur-

den. Das in Tabelle 8 dargestellte Modell ist die tabellarische Darstellung ge-

nesteter Relationen87, die man auch als geschachtelte Tabellen88 interpretieren

kann.

Mit Hilfe dieser genesteten Relationen können komplexe Datenobjekte wirk-

lichkeitsnäher und mit weniger Informationsverlust beschrieben werden. Frag-

lich bleibt an dieser Stelle jedoch, wie genestete Relationen formal definiert

werden können und wie diese mit der Petrinetz-Technik zu kombinieren sind.

Ohne formale Notation bleibt auch unklar, wie dieses Konzept in einem EDV-

System realisiert werden kann und ob die Beschreibung von Datenmanipula-

tionen möglich ist. Wäre dies nicht der Fall, dürfte eine solche Modellierungs-

technik nur einen geringen Anwendungsnutzen besitzen. Eine auf genesteten

Relationen basierende Modellierungstechnik ohne Möglichkeit der formalen

Beschreibung wäre nicht mehr als eine ,,kreative Ästhetisierung", die von In-

formatik-Spezialisten letztlich wieder gemäß der Normalisierungstheorie in

eine entsprechende Normalform überführt werden müsste.

3.2.2.2 Genestete Relationen als Erweiterung des Entity-Relationship-

Modells

Die in Kapitel 3.1 beschriebene formale Definition des E-R-Modells wird nun

in einem ersten Schritt hinsichtlich der

Attribute

um genestete Relationen er-

weitert. Damit wird die Normalisierungstheorie für die kombinierte Prozess-

und Datenmodellierung abgelehnt.

Betrachtet man das Beispiel aus Abbildung 11, so wurde angenommen, dass

jedes Attribut

a1

, ...,

a4

nur jeweils genau einen atomaren Wert enthalten darf.

Doch bereits CHEN ließ in seiner ersten Veröffentlichung über den E-R-Ansatz

sog.

mengenwertige

Attribute zu, ging jedoch nicht weiter auf deren formale

87 Vgl. Lamersdorf/Schmidt (1983), S. 158; Sander (1992), S. 94 und S. 97; Sander (1993), S.

22 und S. 44; Schek/Scholl (1983), S. 117; Schek/Scholl (1986), S. 140; Oberweis (1996a),

S. 113.

88 Der Begriff ,,genestet" stammt vom englischen Begriff ,,to nest" ab, was als ,,schachteln"

übersetzt werden kann.

---

35

Definition ein89. Ein Beispiel für ein mengenwertiges Attribut ist der Flugzeug-

Typ (

a4

), da ein Mitarbeiter für mehrere Flugzeuge qualifiziert sein kann.

Bezeichne

a4

das Attribut ,,Flugzeug-Typ". Jetzt wird angenommen, dass

a4

mehrere Werte eines weiteren Attributs ,,Typname"

a4.1

zugeordnet werden

können. Das wird formal beschrieben als

a4

:= (

a4.1

).

Durch Einsetzen in

E

:= (

a1

,

a2

,

a3

,

a4

) erhält man

E

:= (

a1

,

a2

,

a3

,

a4

:= (

a4.1

)).

Diese Gleichung beschreibt eine genestete Relation und lässt sich wie in

Tabelle 9 darstellen90. Zum besseren Verständnis für die nachfolgende Defini-

tion wurden bereits die Symbole für atomare ( ) und zusammengesetzte ( )

Werte einer Instanz hinzugefügt.

E

a1

a2

a3

a4

a4.1

1.1

2.1

3.1

{

4.1

,...,

}

1

4.1n

= 1.1

Tabelle 9: Genestete Relation in Tabellenform

Um in der formalen Schreibweise zwischen mengenwertigen und einzelwer-

tigen Attributen unterschieden zu können, werden einzelwertige Attribute

weiter mit ,,

a

" , zusammengesetzte jedoch mit ,,

A

" bezeichnet. In der folgenden

Definition wird der Begriff ,,Instanz" für

mengenwertige

Attribute definiert91.

Definition 6: Instanz (mengenwertige Attribute)

Es sei

D

ein Datenmodell und

U

die Menge aller in

D

auftretenden Namen.

(i)

Die Menge aller möglichen Instanzen mengenwertiger (auch:

zusammengesetzer) Attribute

A

von

D

ist

A

:= (

A1

,...,

An

) und

n

IN.

A

: {( 11,..., 1n),...,( m1,..., mn)} ist eine Instanz vom Typ

A

, falls

m

89 Vgl. Chen (1976), S. 13-20.

90 Alternativ ist z.B. eine Darstellung als Baumstruktur denkbar. In dieser Arbeit wird aber die

Darstellung in Tabellenform gewählt, da diese eine größere Nähe zu ,,Formularen" besitzt

und damit intuitiv verständlicher ist.

91 Vgl. ähnlich Sander (1992), S. 96; Sander (1993), S. 50; Oberweis (1996a), S. 114. Für eine

formale Beschreibung mengenwertiger Attribute als genestete Attribute siehe auch

Thalheim (2000), S. 64-73.

---

36

IN0 und falls für alle

i

{1,...,

m

} und

j

{1,...,

n

} gilt: ij ist eine

Instanz vom Typ

Aj

. Für eine Instanz :

x

wird der Name und

x

der Wert einer Instanz genannt.

(ii) Es

bezeichne

Ins

(

D

) die Menge aller möglichen Instanzen von

D

.

(iii) Ein Element ( i1,..., in) des Wertes einer Instanz

A

:

{( 11,..., 1n),...,( m1,..., mn)} wird auch

Tupel

vom Typ

A

genannt.

Dabei bezeichnet .

Ak

die dem Attribut

Ak

zugeordnete Instanz, d.h.

für = ( i1,..., in) sei .

Ak

= ik. Weiter wird vereinbart, dass für In-

stanzen der griechische Buchstabe wie folgt benutzt wird: Die

Schreibweise

wird verwendet, um auszudrücken, dass ein

Element des Wertes

der Instanz ist.

(iv) Ein (zusammengesetztes) Attribut, dass in keiner ,,rechten Seite"

der Gleichung eines Datenmodells auftritt, heißt

Top-Level-Attribut

.

Es lässt sich damit festhalten, dass mengenwertige Attribute mit Hilfe ge-

nesteter Relationen formal definiert werden können. Ein mengenwertiges

Attribut besteht wiederum aus mengenwertigen und/oder einzelwertigen Attri-

buten. Es nicht zwingend notwendig, dass einzelwertige Attribute Ausprägun-

gen annehmen. Die Beschreibung undefinierter Werte wird dadurch möglich:

Die Anzahl der Ausprägungen einzelwertiger Attribute, die einem mengen-

wertigen Attribut zugeordnet werden, darf gleich Null sein.

Weiter besteht die begründete Hoffnung, dass sich eine solche formale Defi-

nition auch aus größeren E-R-Modellen für komplexe Datenobjekte herleiten

lässt. Ein zusätzliches Problem bei E-R-Modellen ist jedoch, dass ein einzel-

nes, für eine bestimmte Aufgabe benötigtes komplexes Datenobjekt auch aus

mehreren Entities

und den dazugehörigen Relationen bestehen könnte. Daher

wird die Formalisierung genesteter Relationen im folgenden Kapitel auf

mehrere Entities und zugehörige Relationen erweitert.

3.2.2.3 Genestete Relationen als Sichten auf das Entity-Relationship-

Modell

In Kapitel 3.2.2.2 wurde das E-R-Modell um genestete Relationen erweitert.

Diese Erweiterung bezog sich auf mengenwertige Attribute

eines

Entities.

Komplexe Datenobjekte können sich aber auch aus mehreren Entities zusam-

---

37

mensetzen. So besteht die Datenstruktur für die Crewzusammenstellung in dem

in Abbildung 10 konstruierten E-R-Modell aus den Entity- und Beziehungs-

Typen ,,Mitarbeiter", ,,qualifiziert für", ,,Aufgabe", ,,benötigt" und ,,Flugzeug-

Typ". Es reicht damit nicht aus, das E-R-Modell um mengenwertige Attribute

in

einem Entity-Typ

zu erweitern. Vielmehr wird eine Technik benötigt, die es

erlaubt, aus

mehreren Entity-Typen

eines Datenmodells ein komplexes Daten-

objekt mit genesteten Relationen herzuleiten.

In dem hier vorgestellten Ansatz wird vorgeschlagen, zuerst eine

globale Sicht

auf die Datenstruktur eines BIS mit Hilfe der E-R-Technik semiformal zu mo-

dellieren.

Lokale Sichten

werden als Ausschnitte, d.h. Teilmengen, aus diesem

E-R-Modell aufgefasst, die für ein komplexes Datenobjekt relevante Daten

beschreiben92. Aus diesen lokalen Sichten eines E-R-Modells werden genestete

Relationen hergeleitet. Diese werden einerseits in formaler Notation, anderer-

seits als (geschachtelte) Tabellen dargestellt93.

Bezugnehmend auf das hier verwendete Beispiel sind für den Aspekt der

durchzuführenden Flüge (,,Flugdurchführung") und den Aspekt der dafür zur

Verfügung stehenden Flugzeuge (,,verfügbare Flugzeuge") unterschiedliche

Ausschnitte des E-R-Modells relevant. Diese unterschiedlichen Ausschnitte

beschreiben jeweils ein komplexes Datenobjekt, das auch als genestete Rela-

tionen beschrieben werden kann. Die einzelnen Phasen der Ableitung geneste-

ter Relationen aus dem globalen E-R-Modell können folgendermaßen geglie-

dert werden94:

92 Eine Trennung von globaler und lokaler Sicht wird ebenso von JAESCHKE vorgeschlagen,

vgl. Jaeschke (1996), S. 196 f. Bei der Herleitung von genesteten Relationen geht

JAESCHKE jedoch anders vor, vgl. Fußnote 93.

93 Eine weitere Möglichkeit ist, die relevante Teilmenge eines E-R-Modells in ein

Semantisch

Hierarchisches Datenmodell

(SHM) zu konvertieren, da semantische Datenmodelle ,,aus-

drucksstarke Strukturierungskonzepte [bieten, der Autor], um die strukturellen Aspekte der

Diskurswelt (verhältnismäßig) anwendungsnah zu beschreiben", Oberweis (1996a), S. 47;

übereinstimmend Jaeschke (1996), S. 197-209. Bei der Verwendung eines SHM müsste

aber eine zusätzliche Modellierungstechnik eingeführt werden, was u.a. den Aufwand für

das Erlernen der Modellierungssprache erhöht.

94 Die Punkte 1-3 sind ähnlich wie die von Jaeschke (1996), S. 199, vorgeschlagenen Regeln.

Punkt 4 ersetzt jedoch die Regeln ,,Definiere eine Entity-Relationship-View, die der Struk-

tur des komplexen Objekttyps entspricht [...]" und ,,Leite das SHM- bzw. EER-Schema des

komplexen Objekttyps aus der Struktur der View ab".

---

38

1. Bevor mit der Ableitung der genesteten Relationen begonnen wird, lege

zunächst unabhängig vom globalen E-R-Modell fest, welche Objekte

der Realität mit dem komplexen Datenobjekt repräsentiert werden sol-

len.

2. Bestimme den Kern-Entity-Typ des komplexen Datenobjekts. Der

Kern-Entity-Typ des komplexen Datenobjekts ist der Entity-Typ, des-

sen Schlüssel auch Schlüssel des komplexen Datenobjekts ist. Dieser

Schlüssel muss das zu repräsentierende Objekt der Realität eindeutig

identifizieren.

3. Bestimme den Ausschnitt des E-R-Modells, der die Daten beschreibt,

die dem komplexen Datenobjekt zugrunde liegen.

4. Konstruiere die genestete(n) Relation(en) mit der im folgenden

beispielhaft beschriebenen Heuristik.

Um eine Flugzeugzuweisung durchführen zu können, müssen zum einen die

verfügbaren Flugzeuge und zum anderen die durchzuführenden Flüge model-

liert werden (vgl. Abbildung 7). Im folgenden wird ein komplexes Datenobjekt

mit genesteten Relationen für die verfügbaren Flugzeuge aus dem E-R-Modell

in Abbildung 10 konstruiert.

Der sog. ,,Kern-Entity-Typ" ist in diesem Fall der Entity-Typ ,,Flugzeug"

(

E3

). Weitere relevante Daten sind die benötigten Aufgaben für das Flugzeug

und der Flugzeug-Typ. Die Entity-Typen ,,Mitarbeiter" und ,,Flug" sind dage-

gen für das Datenobjekt ,,Verfügbare Flugzeuge" nicht relevant. In Abbildung

12 ist der zuvor beschriebene Ausschnitt aus dem E-R-Modell mit Punkten

unterlegt. Weiter wurden die für diesen Ausschnitt relevanten Attribute (

a3

,

a4

,

a5

,

a6

) hinzugefügt.

Flugz eug-

Mitarbeiter

qualifiziert

1 Aufgabe

benötigt

n n 1

für (R

(R3)

Typ (E

(E

1)

4)

1)

(E2)

Bezeichnung

1

ist vom

(a3)

Typname

Typ (R2)

(a4)

Flugzeug#

1

(a5)

Flugz eug

benutzt

Flug (E5)

für (R

Sitze

(E

4)

1 1

3)

(a6)

Abbildung 12: Ausschnitt aus einem E-R-Modell

---

39

Ausgehend vom Kern-Entity-Typ, also ,,Flugzeug" (

E3

), ist der Ausschnitt des

E-R-Modells nun formal zu definieren. Dafür wird insb. auf Definition 6 (In-

stanz zusammengesetzer Attribute) zurückgegriffen. Diese Definition bezog

sich auf zusammengesetzte Attribute eines Entity-Typs und wird nun auf

mehrere Entity- und Beziehungs-Typen angewendet.

Die formale Notation des Ausschnitts aus Abbildung 12 lautet wie folgt:

E3

:= (

a5

,

a6

),

E2

:= (

a3

),

E4

:= (

a4

),

R2

:= (

E3

,

E4

) ,

R3

:= (

E2

,

E4

).

Hebt man die Annahme auf, dass, wie in Kapitel 3.2.2.2 dargestellt, lediglich

Attribute eines Entity-Typs zusammengesetzt sein dürfen, so können auch

diese einzelnen Definitionsgleichungen zusammengefasst werden.

Dafür wird folgendermaßen vorgegangen: Der Kern-Entity-Typ ist

E3

. Ausge-

hend vom Kern-Entity-Typ wird nach Beziehungs-Gleichungen gesucht, die

diesen Kern-Entity-Typ enthalten. Das trifft auf die Beziehung

R2

zu.

R2

ist zu

entnehmen, dass eine Beziehung zwischen

E3

und

E4

besteht. Deshalb wird

E4

in

E3

eingesetzt. Es gibt keine weiteren Relationen, die

E3

enthalten. Deshalb

wird mit den in

E3

eingesetzten Entity-Typen fortgefahren, d.h. in diesem Bei-

spiel mit

E4

.

E4

ist in der Relation

R3

enthalten.

R3

ist zu entnehmen, dass eine

Beziehung zwischen

E4

und

E2

besteht. Daher wird

E2

in

E4

eingesetzt. Es gibt

keine weiteren Relationen; daher wird der Vorgang beendet.

Das Ergebnis ist die folgende Gleichung:

E3

:= (

a5

,

a6

,

E4

:= (

a4

,

E2

:= (

a3

)))

Um eine solche Gleichung nicht unnötig zu vergrößern, können alle Relationen

herausgekürzt werden, die eine 1:1-Kardinalität besitzen. Das ist darin begrün-

det, dass bei 1:1-Kardinalitäten keine mengenwertigen Attribute auftreten kön-

nen. In dem verwendeten Beispiel trifft das auf

R2

:= (

E3

,

E4

) zu. Das bedeutet,

E4

kann aus der Gleichung ,,herausgekürzt" werden, was zu folgender Glei-

chung führt:

E3

:= (

a5

,

a6

,

a4

,

E2

:= (

a3

))

Abschließend wird die Gleichung noch in eine Mengenotation überführt, um

anzuzeigen, dass diese im folgenden mengentheoretisch zu interpretieren ist95:

95 Das entspricht der Repräsentation komplexer Objekte mit Hilfe von genesteten Relationen

bei Oberweis (1996a), S. 112 f.; Oberweis/Sander (1996), S. 385-3387; Sander (1992), S.

---

40

E3

:=

{

(

a5

,

a6

,

a4

,

E2

:=

{

(

a3

)

}

)

}

In Tabellenform lässt sich dieser Zusammenhang folgendermaßen darstellen:

E3

a5

a6

a4

E2

a3

Tabelle 10: Hergeleitetes Datenobjekt in Tabellenform (1)

Ersetzt man die formale Notation durch die natürlichsprachlichen Bezeichnun-

gen, ergibt sich folgende Tabelle:

Flugzeug

Flugzeug# Sitze Typname

Aufgabe

Bezeichnung

Tabelle 11: Hergeleitetes Datenobjekt in Tabellenform (2)

Unter Verwendung der in Definition 6 verwendeten Notation entspricht das der

folgenden Struktur:

D1

= (

A1

:=

{

(

a1

,

a2

,

a3

,

A2

:=

{

(

a4

)

}

)

}

).

Ein Tupel (

A

1,...,

A

k), das alle

Top-Level-Attribute

der aus einem E-R-Modell

hergeleiteten lokalen Datenobjekte enthält, definiert das

Top-Level-Datenmo-

dell D

. Die Top-Level-Attribute aus (

A

1,...,

A

k) identifizieren die lokalen Da-

tenmodelle (

D

1,...,

D

k).

An dieser Stelle wird festgehalten, dass komplexe Datenobjekte mit Hilfe ge-

nesteter Relationen aus E-R-Modellen hergeleitet werden können, selbst dann,

wenn sich ein komplexes Datenobjekt aus

mehreren

Entity-Typen und Be-

ziehungs-Typen zusammensetzt. Ein solches komplexes Datenobjekt müsste

sich formal in

eine

Stelle eines Petrinetzes integrieren lassen, da es mit

einer

Gleichung beschrieben werden kann. Fraglich bleibt aber, ob sich die

Manipu-

lation

dieser komplexen Datenobjekte formal beschreiben lässt. Dieser Frage

wird im folgenden Kapitel nachgegangen.

94-96; Sander (1993), S. 48 f. Davon abweichend Thalheim (2000), S. 64-73, der mengen-

wertige Attribute eines Entities fokussiert und abweichend Bancilhon/Khoshafian (1989),

S. 327-329, die auch ,,Tupel von Tupeln" und ,,Mengen von Mengen" als ,,komplexe Ob-

jekte" zulassen. Die Notation entspricht der von Bancilhon/Koshafian (1989), S. 327-329,

die von SANDER übernommen wurde, vgl. Sander (1992), S. 94, und ebenso von OBERWEIS

verwendet wird, vgl. Oberweis (1996a), S. 113.

---

41

3.3 Manipulation von Daten in genesteten Relationen

3.3.1 Begründung des Manipulationsbedarfs

Nach dem hier zugrundegelegten Verständnis von BIS reicht es nicht aus, sta-

tische Datenobjekte zu modellieren. Vielmehr ist es zusätzlich notwendig, Ver-

änderungen der Datenbestände beim Eintreten bestimmter Ereignisse zu be-

schreiben. Das könnte durch die Beschreibung von Manipulationen auf ge-

nesteten Relationen realisiert werden. Zwei prinzipiell unterschiedliche Be-

darfe hinsichtlich der Manipulation genesteter Relationen werden im folgenden

wieder an dem Beispiel der Fluggesellschaft erläutert96.

Beispiel 1:

In diesem in Tabelle 12 dargestellten Beispiel wird angenommen, dass die

Fluggesellschaft zwei Flugzeuge vom Typ Airbus-320 besitzt und ein weiteres

Flugzeug, ebenfalls vom Typ Airbus-320, erwirbt. Um diese Veränderung mit

einem Informationssystem-Modell der Fluggesellschaft zu repräsentieren,

müsste das

Hinzufügen

des neuen Flugzeugs beschrieben werden. In diesem

Fall ist wesentlich, dass die Ausprägungen der Attribute eines Flugzeugs i.d.R.

nicht veränderlich sind, d.h. der Airbus-320 mit Flugzeug# 12 besitzt in diesem

Beispiel immer 155 Sitze und benötigt als Crew immer einen Piloten und einen

Copiloten.

Flugzeug

Flugzeug# Typname

Sitze

Aufgabe

Bezeichnung

12 Airbus-320

155

Pilot

Copilot

24 Airbus-320

155

Pilot

Copilot

Tabelle 12: Mehrere Flugzeuge gleicher Bauart

Sollen in diesem Beispiel Daten über den dritten Airbus-320 hinzugefügt wer-

den, entspricht das dem in Tabelle 13 dargestellten Tupel.

96 Vgl. hierzu auch Sander (1993), S. 44-47. SANDER wählte jedoch andere, unterschiedliche

Beispiele (Zugverbindungen und Autoausstattungen).

---

42

48 Airbus-320

155

Pilot

Copilot

Tabelle 13: Tupel eines komplexen Datenobjekts (Beispiel 1)

Es ist zu erkennen, dass das gesamte Tupel als weitere Zeile in die Tabelle 12

eingefügt werden muss.

Beispiel 2:

In diesem in Tabelle 14 dargestellten Beispiel werden zwei Mitarbeiter mit

unterschiedlichen Qualifikationen (Attribut: ,,Aufgabe") repräsentiert. Eine

wesentliche Eigenschaft ist, dass sich in diesem Beispiel die Qualifikationen

der Mitarbeiter im Zeitablauf erweitern können, d.h. Mitarbeiter Müller könnte

bspw. die Qualifikation ,,Pilot" für einen Airbus-320 erwerben.

Mitarbeiter

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Typname

1024 Smith

Pilot

Airbus-320

Boing-747

2048 Müller

Copilot Airbus-320

Navigator Boing-747

... ...

Tabelle 14: Mitarbeiter mit veränderlichen Qualifikationen

In diesem Fall müsste das in Tabelle 15 dargestellte Tupel hinzugefügt werden.

2048 Müller

Pilot Airbus-320

Tabelle 15: Tupel als komplexes Datenobjekt (Beispiel 2)

Jedoch sollen diese Daten mit den bereits vorhandenen ,,verschmolzen" werden

und nicht, wie im ersten Beispiel, ein weiteres Tupel (d.h. in diesem Beispiel

ein weiterer Mitarbeiter in der Tabelle) ,,angehangen" werden.

Der grundlegende Unterschied zwischen beiden Beispielen besteht darin, dass

im zweiten Beispiel ein ,,Sub-Tupel" zu der bereits vorhandenen Information

hinzugefügt werden soll, während im ersten Beispiel das neue Tupel als ,,auto-

nom" angesehen werden kann, da es als Ganzes einzufügen ist. Ein ähnlicher

---

43

Unterschied tritt beim Löschen von Tupeln auf97. Daher muss die erste Überle-

gung für die formale Beschreibung von Datenmanipulationen in genesteten

Relationen sein, wie Tupel

und Sub-Tupel

in genesteten Relationen eingefügt

und entfernt werden können98.

3.3.2 Defekte bei der Manipulation von Daten in genesteten

Relationen

Aus den in Kapitel 3.3.1 eingeführten Beispielen geht hervor, dass nicht nur

vollständige Tupel wie in Beispiel 1, sondern auch ,,Sub-Tupel" wie in Beispiel

2 eingefügt und gelöscht werden müssen. Das ist aber nicht ohne weiteres

möglich, da auf Basis der Normalisierungstheorie keine Sub-Tupel auftreten

können und auch keine Ausdrucksmittel für deren Beschreibung vorhanden

sind (vgl. Kapitel 3.2.1). Auch die Ausdrucksmittel der Pr/T-Netze bieten keine

Möglichkeit, Zugriffe auf Sub-Tupel zu beschreiben, da hier ebenfalls nur fla-

che

n

-Tupel zulässig sind (vgl. auch Anhang: Petrinetz-Defintionen).

Möchte man sich das erhöhte Modellierungspotenzial genesteter Relationen in

bezug auf Datenstrukturen von BIS nicht durch ein niedrigeres Modellierungs-

potenzial in bezug auf die Verhaltensaspekte ,,erkaufen", ist es jedoch notwen-

dig, entsprechende Ausdrucksmittel zur Verfügung zu stellen.

3.3.3 Ansätze zur Heilung der Manipulationsdefekte

Im folgenden werden sog.

Ordnungen

auf genesteten Relationen eingeführt

und anhand des Beispiels der Fluggesellschaft erläutert. Mit Hilfe dieser Ord-

nungen wird die Möglichkeit geschaffen, die Operationen auf genesteten Rela-

tionen formal zu beschreiben, die auch auf flachen

n

-Tupeln beschreibbar sind.

Gleichzeitig kann jedoch weiterhin eine intuitiv verständliche Darstellung der

Datenobjekte (z.B. als geschachtelte Tabelle) aus den formalen Beschreibun-

gen hergeleitet werden. Dieser Ansatz ist theoretisch fundiert und in ein EDV-

System implementierbar. Die Implementierbarkeit eines solchen Ansatzes

97 Beim Löschen eines Tupels müsste entweder ein Sub-Tupel oder ein ganzes Tupel gelöscht

werden, vgl. Sander (1993), S. 46.

98 Vgl. Sander (1993), S. 44.

---

44

wurde z.B. von LAMERSDORF/SCHMIDT und SCHECK/SCHOLL bereits 1983 im

Rahmen eines auf genesteten Relationen basierenden Ansatz aufgezeigt99.

3.3.3.1 Inklusionsordnung

Die sog.

Inklusionsordnung

wird als Grundlage für die Beschreibung von Ma-

nipulationen auf

ganzen

Tupeln verwendet. Die folgende formale Notation

wird wie gewohnt anhand des Beispiels der Fluggesellschaft erläutert, um auf-

zuzeigen, wie dessen Anwendung auf die zuvor definierten genesteten Relatio-

nen (vgl. Kapitel 3.3.1) wirkt.

Definition 7: Inklusionsordnung

Es bezeichne ein Datenmodell, das durch eine Gleichung

D

:=

(

a

1,...,

a

k,

A

1,...,

A

j) definiert wird (

k

,

j

IN0,

k

+

j

IN). Ferner seien 1 und 2

Instanzen von Typ

D

und bezeichne einen Tupel.

Die Inklusionsordnung ist (im Sinne der Mengenlehre) eine Teilmengenbezie-

hung zwischen Instanzen100:

1

2 :

1 :

2 oder gleichwertig

1

2 :

1 :

′

2:

Attribute

ai

und

Ai

: .

ai

= ′.

ai

und .

Ai

= ′.

Ai

Zwei Instanzen stehen also hinsichtlich der Inklusionsordnung in Relation zu-

einander, wenn jedes Tupel der linken Instanz auch in der rechten Instanz ent-

halten ist. Diese Inklusionsordnung wird mit ,, D" bezeichnet.

99 Lamersdorf/Schmidt (1983), insb. S. 162-164, beschrieben die implementierungsnahe

Modellierung ,,komplexer Objekte". Schek/Scholl (1983), S. 114, hielten es für einen ent-

scheidenden Nachteil, ,,daß sich 1NF-Relationen und die zugehörige Algebra nicht beson-

ders gut eignen zur Beschreibung der Datenstrukturen und Operationen, die auf der Ebene

der Datensätze und Zugriffspfade üblicherweise auftreten", schlugen einen ähnlichen An-

satz wie den hier behandelten als sogar bessere Alternative für die Implementierung in Da-

tenbanken vor und realisierten einen entsprechenden Prototyp.

100 Die Definition ist Sander (1993), S. 52, entnommen. Die Notation wurde jedoch angepasst,

insb. um Widersprüche in bezug auf die zuvor getroffenen Definitionen zu vermeiden.

---

45

Flugzeug

(

A1

)

Flugzeug

Flug-

Typname

Sitze

Aufgabe

Flug-

Typname Sitze Aufgabe

zeug#

(

a2

)

(

a3

)

(

A2

)

zeug#

Bezeichnung

(

a1

)

Bezeichnung

48 Airbus-320

155

Pilot

(

a4

)

Copilot

12 Airbus-320

155

Pilot

1

Instanz 2

Copilot

24 Airbus-320

155

Pilot

2

Copilot

Instanz 1

Tabelle 16: Zwei Instanzen des Datenmodells "Flugzeug"

In Tabelle 16 sind zwei Instanzen 1 und 2 dargestellt, hier gilt die

Inklusionsordnung 2 D 1. In der Instanz 1 sind zum besseren Verständnis die

äquivalenten formalen Notationen der Felder eingetragen. Eine Vereinigung

der beiden Instanzen 1 D 2 bewirkt, dass das Flugzeug# 48 an das Flugzeug#

12 und 24 ,,angehangen" wird, da bei keinem Tupel Gleichheit für alle Attri-

bute vorliegt: Die Ausprägungen des Attributs Flugzeug# im Tupel der Instanz

1 erfüllen nicht die Bedingung, dass sie gleich der Ausprägung des Attributs

Flugzeug# im Tupel der Instanz 2 sind. Die Schnittmenge der beiden Instanzen

1

D 2 ist die leere Menge, da kein Tupel in 1 im Sinne der Inklusionsordnung

gleich dem Tupel in 2 ist. Das Ergebnis von Vereinigung und Schnittmenge

der beiden Instanzen ist in Tabelle 17 dargestellt.

Flugzeug

Flugzeug

Flugzeug# Typname Sitze Aufgabe

Flugzeug# Typname Sitze Aufgabe

Bezeichnung

Bezeichnung

12 Airbus-320

155

Pilot

Copilot

1

D 2

24 Airbus-320

155

Pilot

Copilot

48 Airbus-320

155

Pilot

Copilot

1

D 2

Tabelle 17: Vereinigung und Schnittmenge mit der Inklusionsordnung

Es lässt sich festhalten, dass mit Hilfe der hier definierten Inklusionsordnung

ganze

Tupel in genestete Relationen eingefügt und gelöscht werden können.

Jedoch bietet die Inklusionsordnung nicht die Möglichkeit, Operationen nur auf

Sub-Tupeln durchzuführen. Eine solche Möglichkeit wird aber in dem hier

---

46

gewählten Beispiel der Fluggesellschaft benötigt, um einem Mitarbeiter eine

zusätzlich erworbene Qualifikation zuzuordnen (s.o.)101.

3.3.3.2 Objektordnung

Da mit der Inklusionsordnung keine Manipulationen von Sub-Tupeln beschrie-

ben werden können, wie es in Beispiel 2 aus Kapitel 3.3.1 notwendig wäre,

wird an dieser Stelle die sog.

Objektordnung

102 definiert. Die Objektordnung

soll als Grundlage für die Beschreibung von Manipulationen auf

Sub-Tupeln

verwendet werden.

Definition 8: Objektordnung

Es bezeichne ein Datenmodell, das durch eine Gleichung

D

:=

(

a

1,...,

a

k,

A

1,...,

A

j) definiert wird (

k

,

j

IN0,

k

+

j

IN). Ferner seien 1 und 2

Instanzen von Typ

D

und bezeichne einen Tupel. Die Objektordnung wird

rekursiv definiert:

1

2 :

1:

′

2 :

einfachen Attribute

a

: .

a

= ′.

a

zusammengesetzten Attribute

A

: .

A

′.

A

Für die Werte zusammengesetzter Attribute

A

wird also hinsichtlich der Ob-

jektordnung keine Gleichheit gefordert, sondern ebenfalls (rekursiv) die Ob-

jektordnung. Diese Objektordnung wird mit ,, D" bezeichnet. Der Unterschied

zu der Inklusionsordung ,, D" besteht darin, dass bei der Objektordnung ,, D"

ein Tupel möglicherweise nur als Sub-Tupel in einem anderen Tupel enthalten

sein braucht, damit die o.a. Definition wahr ist.

101 Alternativ müsste erst das gesamte Tupel gelöscht werden und anschließend ein ganzes

Tupel neu eingefügt werden, was hinsichtlich der Modellierung von Prozessstrukturen in

Petrinetzen zu unübersichtlichen Modellen führen würde.

102

Die Objektordnung geht zurück auf die ,,Sub-Object"-Beziehung von

Bancilhon/Khoshafian (1989), S. 327-334.

---

47

Mitarbeiter

Mitarbeiter

Ma# Name Aufgabe

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Bezeichnung Flugzeug-Typ

Typname

Typname

1024 Smith Pilot

Airbus-320

2048 Müller

Pilot Airbus-320

Boing-747

Instanz

2048 Müller Copilot Airbus-320

2

Navigator Boing-747

Instanz 1

Tabelle 18: Zwei Instanzen des Datenmodells "Mitarbeiter"

In Tabelle 18 sind zwei Instanzen des Datenmodells ,,Mitarbeiter" dargestellt,

wobei die einzelwertigen Attribute ,,Ma#" und ,,Name" in einem Tupel iden-

tisch sind.

Eine Vereinigung der beiden Instanzen 1 D 2 bewirkt, dass das Tupel der

Instanz 1 mit dem Tupel der Instanz 2 verschmolzen wird, da lediglich für die

einzelwertigen Attribute ,,Ma#", ,,Name" und ,,Typname" Gleichheit gefordert

ist. Für die zusammengesetzten Attribute ,,Aufgabe" und ,,Flugzeug-Typ" wird

dagegen nur gefordert, dass deren Ausprägungen einer Instanz in der anderen

enthalten sind. Die Schnittmenge der beiden Instanzen 1 D 2 bewirkt im Ver-

gleich zur Inklusionsordnung ein Löschen der Aufgaben des Mitarbeiters

Müller. Der Mitarbeiter selbst wird aufgrund der Anwendung der Objektord-

nung nicht gelöscht, da zwar das Aufgabe-Tupel aus 1 nicht in 2 enthalten ist,

jedoch eine Gleichheit der Attribute ,,Ma#" und ,,Name" vorliegt. Der Mitar-

beiter Smith wird dagegen vollständig gelöscht, da er hinsichtlich zusammen-

gesetzter Attribute nicht in Instanz 2 enthalten ist und auch keine Gleichheit in

bezug auf einzelwertige Attribute vorliegt.

Das Ergebnis ist in Tabelle 19 dargestellt. In dem als 1 D 2 deklarierten Be-

reich ist auch die Verwendung

leerer Mengen

erkennbar. Die einzelwertigen

Attribute ,,Bezeichnung" und ,,Typname" müssen nicht zwingend Ausprägun-

gen annehmen, da diese von einem übergeordneten zusammengesetzten Attri-

but funktional abhängig sind (siehe auch S. 36).

---

48

Mitarbeiter

Mitarbeiter

Ma# Name Aufgabe

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Bezeichnung Flugzeug-Typ

Typname

Typname

1024 Smith Pilot

Airbus-320

2048 Müller

Boing-747

2048 Müller Copilot Airbus-320

1

D 2

Navigator Boing-747

Pilot Airbus-320

1

D 2

Tabelle 19: Vereinigung und Schnittmenge mit der Objektordnung

Die Objektordnung ist jedoch

nicht antisymmetrisch

103, bspw. gilt für die in

Tabelle 20 dargestellten Instanzen sowohl 1 D 2 als auch 2 D 1. Die Anti-

symmetrie der Objektordnung muss durch die Einführung sogenannter

PNF-

Instanzen

(Instanzen in Partitioned Normal Form) sichergestellt werden104.

PNF-Instanzen stellen eine Restriktion in bezug auf die erlaubten Instanzen

dar, wodurch nur noch Instanzen zugelassen werden, die antisymmetrisch sind.

Mitarbeiter

Mitarbeiter

Ma# Name Aufgabe

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Bezeichnung

Flugzeug-Typ

Typname

Typname

2048 Müller Copilot

Airbus-320

2048 Müller

Copilot Airbus-320

Navigator Boing-747

2048 Müller Copilot Airbus-320

Navigator Boing-747

Instanz 2

Instanz 1

Tabelle 20: Nicht antisymmetrische Instanzen

Definition 9: PNF-Instanzen

(1) Eine Instanz vom Typ

D

mit

D

:= (

a

1,...,

a

k,

A

1,...,

A

j) ist in der Parti-

tioned Normal Form (PNF), wenn die folgenden zwei Bedingungen

gelten:

a.

erfüllt die funktionale Abhängigkeit {

a

1,...,

a

k}

{

A

1,...,

A

j},

d.h. es gibt keine zwei verschiedenen Tupel in , die jeweils auf

den einzelwertigen Attributen

a

1,...,

a

k übereinstimmen.

103 Vgl. Bancilhon/Khoshafian (1989), S. 331.

104 Vgl. Roth et al. (1988), S. 397-399. Die dort beschriebene ,,Partitioned Normal Form"

wurde von SANDER übernommen, um die Antisymmetrie der von BANCILHON/KHOSHAFIAN

beschriebenen Objektordnung in bezug auf genestete Relationen sicherzustellen, vgl.

Sander (1992), S. 98; Sander (1993), S. 53.

---

49

b. In jedem Tupel aus sind die Werte der zusammengesetzten

Attribute

A

i wiederum in Partitioned Normal Form.

(2) Instanzen in Partitioned Normal Form heißen auch kurz

PNF-Instanzen

.

Die Menge aller PNF-Instanzen vom Typ

D

wird mit

PNF

(

D

) angege-

ben.

Die Relation ,, D" stellt auf der Menge der PNF-Instanzen eine

partielle Ord-

nung

dar105.

Es lässt sich damit festhalten, dass ein Zugriff auf Sub-Tupel komplexer Da-

tenobjekte prinzipiell

möglich

ist. Jedoch fehlt ein Formalismus, der eine diffe-

renziertere Beschreibung von Zugriffen auf Datenobjekte ermöglicht, wie im

folgenden zu zeigen ist. An dieser Stelle kann man eher von einem ,,Rohbau"

für das Ziel der Modellierung komplexer Datenobjekte mit genesteten Relatio-

nen sprechen.

3.3.3.3 Ordnungsdefinition und Ordnungsgleichung

Es ist denkbar, dass verschiedene zusammengesetzte Attribute einer Instanz

unterschiedlich behandelt werden müssen. Dies wird anhand eines Beispiels

verdeutlicht. Tabelle 21 zeigt zwei Instanzen einer komplexen Datenstruktur,

in denen verschiedene Kombinationen von Aufgaben beschrieben sind.

Aufgabe

Aufgabe

Bezeichnungen Flugzeug-Typ

Bezeichnungen Flugzeug-Typ

Bezeichnung Typname

Bezeichnung Typname

Pilot

Airbus-320

Pilot

Boing-747

Pilot

Airbus-320

Copilot

Boing-747

Instanz 2

Pilot

Airbus-320

Copilot

Pilot

Airbus-320

Copilot

Navigator

Instanz 1

Tabelle 21: Instanzen der Relation ,,Aufgabe"

Angenommen, es soll der Bezeichnungskombination {Pilot, Copilot} in 1 der

Typname ,,Boing-747" hinzugefügt werden. In diesem Fall müsste bei der

105 Der Beweis findet sich in Sander (1993), S. 171 f.

---

50

Operation ( 1 D 2) auf den Pfad ,,Aufgabe-Bezeichnungen" die Inklusions-

ordnung angewendet werden, auf den Pfad ,,Aufgaben-Flugzeug-Typ" dagegen

die Objektordnung.

Zu diesem Zweck werden Ordnungsdefinitionen und Ordnungsgleichungen

eingeführt106. Diese ermöglichen es, auf unterschiedliche zusammengesetzte

Attribute eines Datenmodells entweder die Inklusions-

oder

die Objektordnung

anzuwenden.

Definition 10: Ordnungsdefinition und Ordnungsgleichung

Es bezeichne ein Datenmodell, das durch eine Gleichung

D

:=

(

a

1,...,

a

k,

A

1,...,

A

j) definiert wird (

k

,

j

IN0,

k

+

j

IN), wobei mit

a

i einzelwer-

tige Attribute und mit

A

i mengenwertige Attribute bezeichnet werden.

Eine

Ordnungsdefinition O

in bezug auf ist eine endliche Menge von

Ord-

nungsgleichungen

, wobei eine Ordnungsgleichung für ein Modell

D

von der

Form

D

:= (=a ,..., = ,

,...,

) ist. Gleiches gilt für die Menge

Ins

(

D

), d.h.

1

ak

A1

Aj

die Menge aller möglichen Instanzen des Datenmodells

D

.

Dabei ist jedes Symbol A entweder ein Gleichheitsprädikat = oder ein

i

Ai

Symbol A . Im ersten Fall wird das entsprechende Attribut

A

i

i ein Gleichheits-

attribut, im zweiten Fall ein Teilmengenattribut genannt.

Die Menge

O

muss den folgenden Bedingungen genügen:

(a) Für jede Gleichung

D

gilt: Es gibt eine Ordnungsgleichung der Form

D

:= (...) in

O

, und für jedes Teilmengenattribut

A

i in

D

gibt es in

O

eben-

falls genau eine Ordnungsgleichung .

(b) Weitere Ordnungsgleichungen gibt es in

O

nicht.

106 Vgl. Sander (1992), S. 111 f.; Sander (1993), S. 55-59.

---

51

Weiter sei

D

:= (=a ,...,= ,

,...,

) eine Ordnungsgleichung für ein Modell

1

ak

A1

Aj

D

. Dadurch besteht in folgender Weise eine Relation

D

zwischen den Instan-

zen 1, 2:

1

D 2 :

1:

′

2 :

einfachen Attribute

a

: .

a

= ′.

a

zusammengesetzten Attribute

A

: .

A

A ′.

A

i

Jedes Symbol =A soll als ein Gleichheitsprädikat auf der Menge

dom

(

A

i

i) inter-

pretiert werden. Falls A von der Form = ist, so soll auch dieses Symbol als

i

Ai

ein Gleichheitsprädikat interpretiert werden, anderenfalls ­d.h. falls A von

i

der Form A ist­ gibt es wegen (a) eine weitere Ordnungsgleichung, welche

i

die Bedeutung des Symbols festlegt.

Die eingeführte Ordnung ist eine Verallgemeinerung der zuvor definierten In-

klusions- (Definition 7) und Objektordnung (Definition 8). Die Ordnungsglei-

chungen für das am Anfang erwähnte Beispiel aus Tabelle 21 können damit

folgendermaßen definiert werden:

Aufgabe

:=( =Bezeichnungen,

Flugzeugtyp),

Flugzeug-Typ

:=( =Typname)

Das Einfügen der Instanz 2 in die Instanz 1 in bezug auf die Relation ,,Auf-

gabe" wird formal als 1 Aufgabe Aufgabe:{ 2} beschrieben, d.h. beim Vereini-

gen der beiden der genesteten Relation ,,Aufgabe" entsprechenden Instanzen

wird die Ordnung

Aufgabe

verwendet. Das Resultat ist in Tabelle 22 dargestellt.

Aufgabe

Bezeichnungen

Flugzeug-Typ

Bezeichnung Typname

Pilot

Airbus-320

Pilot

Airbus-320

Boing-747

Pilot

Airbus-320

Copilot

Boing-747

Pilot

Airbus-320

Copilot

Navigator

Tabelle 22: Verschmelzen von Instanzen mit Ordnungen

---

52

Für das zusammengesetzte Attribut ,,Aufgabe" gilt die Objektordnung. Für

,,Bezeichnungen" gilt die Inklusionsordnung, ein Tupel muss genau die Menge

an Werten {Pilot, Copilot} enthalten. Für das Attribut ,,Flugzeug-Typ" gilt

dagegen wieder die Objektordnung, wodurch der Wert {Boing-747} in die

Instanz aufgenommen wird, weil der entsprechende Wert von ,,Typname" nicht

bereits in der Instanz enthalten ist.

3.3.3.4 GPNF-Instanzen

Bei der Ordnungsdefinition ist lediglich eine Relation festgelegt worden, es

handelt sich jedoch nicht um eine partielle Ordnung, d.h. um eine reflexive,

transitive und antisymmetrische Relation. Um bei dieser Verallgemeinerung

der Inklusions- und Objektordnung sicherzustellen, dass es sich um eine par-

tielle Ordnung handelt, werden Generalised Partitioned Normal Form (GPNF-)

Instanzen defniert107.

Definition 11: Generalized Partitioned Normal Form (GPNF-) Instanzen

Es bezeichne ein Datenmodell, das durch eine Modellgleichung

D

:=

(

a

1,...,

a

k,

A

1,...,

A

j) definiert wird und

D

:= (=a ,...,= ,

,...,

) die zugehö-

1

ak

A1

Aj

rige Ordnungsgleichung der entsprechenden Ordnungsdefinition

O

. Ferner

bezeichne

A

i ,...,

A

die Gleichheitsattribute der Menge {

A

1

ip

1,...,

A

j}, während

A

i ,...,

A

Teilmengenattribute seien.

p+1

ij

(1) Eine Instanz vom Typ

D

ist in der Generalized Partitioned Normal

Form, falls die folgenden zwei Bedingungen gelten:

a.

genügt der funktionalen Abhängigkeit {

a

1,...,

a

k,

A

i ,...,

A

}

1

ip

{

A

i ,...,

A

}, d.h. es gibt keine zwei verschiedenen Tupel in ,

p+1

ij

die jeweils auf den atomaren Attributen

a

1,...,

a

k und auf den

Gleichheitsattributen

A

i ,...,

A

übereinstimmen.

1

ip

b. In jedem Tupel der Instanz sind Werte aller Teilmengenattri-

bute

A

i ,...,

A

wiederum in Generalized Partitioned Normal-

p+1

ij

form.

107 Vgl. Sander (1992), S. 111-113; Sander (1993), S. 59-61.

---

53

(2) Instanzen in Generalized Partitioned Normal Form werden auch kurz

GPNF-Instanzen genannt. Die Menge aller GPNF-Instanzen vom Typ

D

wird kurz mit

GPNF

(

D

) bezeichnet.

Um Gleichheits- und Teilmengenattribute bereits im Modell unterscheiden zu

können, werden die folgenden Gleichungen in der Form

D

:= (

a

1,...,

a

k,

B

1,...,

B

j,

C

1,...,

C

p) geschrieben, wobei

a

i die atomaren,

B

i die Gleichheits- und

C

i Teilmengenattribute darstellen.

Satz:

Sei

ein Datenmodell, das durch eine Modellgleichung

D

:=

(

a

1,...,

a

k,

B

1,...,

B

j,

C

1,...,

C

p) definiert wird (

k

,

j

IN0,

k

+

j

IN) und

D

:=

(=a ,...,= ,

,...,

) die zugehörige Ordnungsgleichung der entsprechenden

1

ak

A1

Aj

Ordnungsdefinition

O

. Dann gilt:

(1) (

GPNF

(

D

),

D

) ist eine partiell geordnete Menge, welche die

Schrankeneigenschaft erfüllt, d.h.

GPNF

(

D

) ist eine Menge zulässiger

Instanzen in bezug auf

D

. Somit wird ein Verband

LD

:=

(

GPNF

(

D

),

D

,

D

) induziert, der vollständig ist und ein Nullelement 0

D

und ein Einselement 1

D

besitzt108.

(2) Es gilt für Operationen

D

und

D

:

1, 2

GPNF

(

D

):

1

D 2

1

1:

2

2:

i {1,...,k}: .

ai

= 1.

ai

= 2.

ai

und

i {1,...,j}: .

Bi

= 1.

Bi

= 2.

Bi

und

i {1,...,p}: .

Ci

= 1.

Ci Ci

2.

Ci

.

1

D 2

1

1:

2

2:

i {1,...,k}: .

ai

= 1.

ai

= 2.

ai

und

i {1,...,j}: .

Bi

= 1

.Bi

= 2.

Bi

und

i {1,...,p}: .

Bi

= 1.

Ci Ci

2.

Ci

.

108 Für Details über Verbände partiell geordneter Mengen bei GPNF-Instanzen siehe Sander

(1992), S. 121-128, sowie Sander (1993), S. 66-74. Für verbandstheoretische Grundlagen

siehe z.B. Sander (1993), S. 165-170, oder Verbandstheorie (o.D.).

---

54

Es stellt sich heraus, dass die in den Kapiteln 3.3.3.1 und 3.3.3.2 betrachteten

partiellen Ordnungen ­die Inklusions- und die Objektordnung­

Spezialfälle

darstellen: Zu einem Datenmodell

D

mit

D

:= (

a

1,...,

a

k,

A

1,...,

A

j) kann die Inklu-

sionsordnung durch eine Ordnungsgleichung der Form

D

:=(=a ,...,= ,=

,...,= ) und die Objektordnung durch

1

ak A1

Aj

D

:=(=a ,...,= ,

,...,

) ­mit entsprechenden Gleichungen für

A

1

ak A1

Aj

1

,...,

Aj

­ spezi-

fiziert werden.

3.3.3.5 Negativ einer Instanz

Mit Hilfe der Inklusions- und Objektordnung wurde das Einfügen von Tupeln

definiert. Durch diese Operationen wurde das

Hinzufügen

von Daten durch die

Bildung einer Vereinigungsmenge in Datenmodellen möglich, die nicht den

Anforderungen der ersten oder einer höheren Normalform genügen. Durch

Ordnungsdefinition und -gleichung wurde die kombinierte Verwendung von

Inklusions- und Objektordnung möglich.

Das Löschen von Daten lässt sich mit den bislang erarbeiteten Methoden je-

doch noch nicht formal beschreiben. Um das zu ermöglichen, wird nachfolgend

ein sog. ,,Negativ einer GPNF-Instanz "

Neg

( ) eingeführt109, mit der das Lö-

schen eines Tupels in als

Neg

(

D

:{ }) beschrieben werden kann.

Als Beispiel wird das Datenmodell Aufgabe := (Bezeichnung, Flugzeug-Typ :=

(Typname)) gewählt. Als Wertebereich wird aus Gründen der Komplexitätsre-

duktion

dom

(Bezeichnung) =

dom

(Typname) = {1,2} gewählt, d.h. es gibt le-

diglich zwei Aufgabenbezeichnungen und zwei Flugzeugtyp-Bezeichnungen.

Die zugehörige Ordnungsdefinition lautet

Aufgabe

:= (=

Bezeichnung

,

Flugzeug-Typ

:=

(=

Typname

)). Die Instanz 1 in Tabelle 23 repräsentiert die Aufgabe ,,1" für das

Flugzeug vom Typ ,,1". Das Negativ dieser Instanz

Neg

( 1) repräsentiert die

Menge aller möglichen Tupel in bezug auf eine (andere) Instanz, jedoch ohne

1. Die Semantik des Löschens ist, dass bei Verwendung der Objektordnung

nur enthaltene Tupel gelöscht werden. Wird bei keinem Attribut die Objekt-

109 Vgl. Sander (1992), S. 120; Sander (1993), S. 65 f.

---

55

ordnung, d.h. nur die Inklusionsordnung, verwendet, so wird das gesamte Tu-

pel gelöscht.

Aufgabe

Aufgabe

Bezeichnung Flugzeug-Typ

Bezeichnung Flugzeug-Typ

Typname

Typname

1

1

1

2

2

1

1

2

Neg

( 1)

Tabelle 23: Negativ einer Instanz 1

Definition 12: Negativ einer Instanz

Es sei

D

ein Modell mit

D

:= (

a

1,...,

a

k,

B

1,...,

B

j,

C

1,...,

C

p) und eine GPNF-In-

stanz vom Typ

D

mit einer Ordnungsgleichung

O

. 1

D,O

bezeichne die größte

GPNF-Instanz über

D

. Dann ist das Negativ einer Instanz , kurz

NegD,O

( ),

rekursiv definiert durch:

Falls

D

kein Teilmengenattribut

C

i enthält (d.h.

p

= 0)

NegD,O

( ) := D:{ |

1

D,O

und

}

Anderenfalls (d.h.

p

IN)

NegD,O

( ) := D:{ | erfüllt die folgende Bedingung (*)}.

(*) Für alle Attribute

a

i und

B

i gilt .

a

i

dom

(

a

i) und .

B

i

Ins

(

B

i),

und falls es ein Tupel ′ gibt, welches auf allen Attributen

a

i und

B

i mit

übereinstimmt, das also .

a

i = ′.

a

i und .

B

i = ′.

B

i erfüllt ist, dann

gilt für alle Teilmengenattribute

C

i: .

C

i =

NegCi,O

( ′,

C

i), anderenfalls

gilt für die Attribute

C

i: .

C

i = 1

Ci,O

.

Damit lässt sich festhalten, dass ein formaler Rahmen zur Beschreibung von

Manipulationen auf genesteten Relationen erarbeitet wurde. Es fehlt jedoch

noch eine geeignete Technik zur Beschreibung dieser Operationen in semifor-

malen Modellen.

---

56

3.3.4 Filtertabellen zur semiformalen Beschreibung der erweiterten

Ausdrucksmittel

3.3.4.1 Das Modellierungspotenzial von Filtertabellen

In Kapitel 3.3.3 wurde eine Technik für die Modellierung von Datenstrukturen

vorgestellt. Die praktische Handhabung einer solchen Technik erfordert jedoch

ein hohes Maß an Abstraktionsvermögen und an formalen Vorkenntnissen.

Einem Informatik-Laien ist aber nicht zuzumuten, Sichten auf ein Datenmodell

direkt in Form von Regeln und partiellen Ordnungen zu spezifizieren. Deshalb

wird für die Beschreibung der Manipulation von Daten mit semiformalen Mo-

dellen eine grafikbasierte Sprache eingeführt.

Als grafikbasierte Sprache wird die Verwendung von sog.

Filtertabellen

110

vorgeschlagen. Diese können verwendet werden, um Einfüge- und Löschope-

rationen hinsichtlich einer Datenbasis zu spezifizieren. Für die Verwendung

von Filtertabellen sind jedoch keine Kenntnisse hinsichtlich der beschriebenen

Regeln und partiellen Ordnungen notwendig.

Filtertabellen bestehen aus zwei grafischen Symbolen. Das Symbol

be-

zeichnet Operationen in bezug auf die

Objektordnung

, im folgenden auch als

offener

Term bezeichnet. Dagegen bezeichnet das Symbol

Operationen in

bezug auf die

Inklusionsordnung

, im folgenden auch als

geschlossener

Term

bezeichnet. Werte eines offenen Terms brauchen daher in einem im Tupel des

Datenbestands lediglich

enthalten

sein. Werte eines geschlossenen Terms müs-

sen dagegen genau dem Tupel des Datenbestands entsprechen, also

gleich

sein.

Definition 13: Bewerteter Top-Level-Term, Instanziierung eines Terms

Es sei ein Datenmodell,

U

die Menge aller in auftretenden Namen und

var

eine unendliche Menge von Variablen. Dann wird die Menge aller Terme

definiert durch111:

110 Vgl. Sander (1993), S. 146 f.; Oberweis (1996), S. 129-138. Das Konzept der Filtertabellen

ähnelt mitunter dem der Abfragesprache für Datenbanken ,,Query-By-Example", vgl. Zloof

(1975), S. 2-22, die sich jedoch nur auf einzelwertige Attribute bezieht. Eine Erweiterung

von Query-By-Example" um genestete Attribute findet sich u.a. bei Thalheim (2002), S.

245-250.

111 Vgl. Oberweis (1996a), S. 131-133; Oberweis/Sander (1996), S. 396-398.

---

57

(i)

A

U

und

X

var

ist

A

:

X

ein Term vom Typ

A

. Man sagt:

X

repräsentiert Werte vom Typ

A

.

(ii)

Für ein einfaches Attribut

a

U

und

dom

(

a

) ist

a

: ein Term

vom Typ

a

.

(iii)

Für ein zusammengesetztes Attribut

A

U

mit A := (

A

1,...,

A

n) ist

{( 11,..., 1n), ..., ( m1,..., mn)}eine

Term vom Typ A

, falls

m

IN0 für

alle

i

{1,...,

m

} und für alle

j

{1,...,

n

} gilt: ij ist ein Term vom

Typ

A

j.

(iv)

Ein Paar ( ,

O

) wird als

bewerteter Top-Level-Term

bezeichnet, wo-

bei einen Top-Level-Term des Top-Level-Attributs

A

bezeichnet

und

O

eine Ordnungsdefinition des Top-Level-Attributs

A

ist. Da-

mit ist ein Paar ( ,

O

) zugleich der bewertete Top-Level-Term eines

lokalen Datenmodells (vgl. Kapitel 3.2.2.3).

(v) Die

Abbildung

( ) (verkürzte Schreibweise: ) der Menge aller

in vorkommenden Variablen in die Menge der Werte der ent-

sprechenden Attribute ist die

Instanziierung

des Terms. Wenn der

Term keine Variablen enthält, ist die einzig mögliche Instanziierung

die leere Instanziierung (der Term wird auf sich selbst abgebildet).

(vi)

Wenn der Term vom Typ

A

ist und

GPNF

(

A

,

O

) die Menge der

GPNF

-Instanzen in bezug auf die Ordnungsdefinition

O

ist, dann

heißt die Instanziierung

gültig

, wenn

GPNF

(

A

,

O

) ist.

Jeder Term =

A

: {( 11,..., 1n), ..., ( m1,..., mn)}wird in eine Tabelle der Form ij

=

termij

umgewandelt:

term11, ... , term1n

term21, ... , term2n

...

termm1, ... , termmn

Jeder Term

termij

kann seinerseits wiederum eine Filtertabelle sein, wenn sein

Wert eine Menge von Tupeln repräsentiert. Ist der Term von der Form

A

:

X

,

d.h. mit einer Variablen versehen, oder von der Form

A

: , d.h. mit einem Wert

versehen, dann wird für den Term jeweils

X

bzw. ,, " eingesetzt. Ist der Term

---

58

also mit einem Wert versehen, wird dieser in Anführungszeichen gesetzt, um

das eindeutig anzuzeigen112.

3.3.4.2 Operationen auf genesteten Relationen mit Filtertabellen

3.3.4.2.1 Selektion von Daten

Gegeben sei der Datenbestand in Tabelle 24, zu verstehen als Instanz des kom-

plexen Datenobjekts ,,Mitarbeiter"113.

Mitarbeiter

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Typname

1024 Smith

Pilot

Airbus-320

Boing-747

Copilot Airbus-320

2048 Müller

Copilot Airbus-320

Navigator Boing-747

Tabelle 24: Datenbestand für die Abfrage von Daten

Sollen aus der Instanz die Flugzeug-Typen der existierenden Mitarbeiter selek-

tiert werden, welche die Lizenz (d.h. die Bezeichnung) ,,Pilot" besitzen, so

kann das mit folgender Filtertabelle beschrieben werden:

Für die Attribute ,,Ma#" und ,,Name" wurden die zu instanziierenden Variablen

Ma und Na eingetragen. Für das Attribut ,,Bezeichnung" wird der Wert ,,Pilot"

angegeben, für das zusammengesetzte Attribut ,,Flugzeug-Typ" wird die zu

instanziierende Variable Ft eingetragen. Der gesamte Ausdruck wird in einem

offenen Term (

) eingeschlossen, d.h. für das komplexe Datenobjekt ,,Mitar-

beiter" gilt die Objektordnung. ,,Ma#" und ,,Name" sind einzelwertige Attri-

bute, für diese gilt die Inklusionsordnung. Das Tupel (,,Pilot", Ft) wird wie-

derum in einen offenen Term eingeschlossen, d.h. für ,,Aufgabe" gilt die Ob-

jektordnung. ,,Bezeichnung" ist ein einzelwertiges Attribut. Für dieses gilt die

Inklusionsordnung und es muss gleich dem Wert ,,Pilot" sein. Es werden also

die Tupel selektiert, die den Wert ,,Pilot"

enthalten

, da für das zusammenge-

112 Abweichend Oberweis/Sander (1996), S.395-398. In der dort verwendeten Notation werden

Werte nicht in Anführungszeichen gesetzt und Variablen durch Großschreibung gekenn-

zeichnet.

113 Praktisch ist z.B. denkbar, dass ein solcher Datenbestand in einer Tabellenkalkulation oder

in einem entsprechenden Datenbanksystem in digitaler Form vorliegt.

---

59

setzte Attribut ,,Aufgabe" die Objektordnung gilt. Die Variable ,,Ft" wird mit

einem Oberstrich dargestellt. Das bedeutet, für die gesamte nachfolgende

Struktur des zusammengesetzten Attributs ,,Flugzeug-Typ" (in diesem Fall

gehört lediglich ,,Typname" zu dieser Struktur) ist die Objektordnung anzu-

wenden. Damit wird beschrieben, dass nur die Flugzeug-Typen eines Mitar-

beiters selektiert werden, für die dieser eine Piloten-Lizenz besitzt. Das Ergeb-

nis dieser Anfrage sieht folgendermaßen aus:

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Typname

1024 Smith

Pilot

Airbus-320

Boing-747

Tabelle 25: Ergebnis einer Selektion

Dem Mitarbeiter Smith ist die Bezeichnung ,,Pilot" zugeordnet, und nur dieser

wird selektiert. Weiter werden alle dieser Bezeichnung des Mitarbeiters Smith

zugeordneten Flugzeug-Typ-Ausprägungen selektiert, die von der Bezeichnung

,,Pilot" funktional abhängig sind (in diesem einfach Beispiel nur Ausprägungen

des Attributs ,,Typname").

3.3.4.2.2 Einfügen und Löschen von Daten

Für das Einfügen von Daten wird die oben beschriebene Technik zur Selektion

von Daten verwendet. Als Basis dient wieder der in Tabelle 24 dargestellte

Datenbestand. Es soll nun beschrieben werden, dass dem Mitarbeiter ,,Smith"

die Aufgabe ,,Copilot" für den ,,Airbus-320" hinzugefügt wird. Dies wird mit

folgender Filtertabelle beschrieben:

.

In diesem Fall werden nur offene Terme verwendet, da dieses Tupel dem be-

reits bestehenden hinzugefügt werden soll. Das Ergebnis sieht folgendermaßen

aus:

---

60

Mitarbeiter

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Typname

1024 Smith

Pilot

Airbus-320

Boing-747

Copilot

Airbus-320

Boing-747

2048 Müller

Copilot Airbus-320

Navigator Boing-747

Tabelle 26: Hinzufügen von Tupeln (1)

Würde man bei der Filtertabelle für alle mengenwertigen Attribute geschlos-

sene Terme verwenden, so würde ein weiteres Tupel an den bestehenden Da-

tenbestand angehangen werden:

.

Ergebnis:

Mitarbeiter

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Typname

1024 Smith

Pilot

Airbus-320

Boing-747

Copilot Airbus-320

2048 Müller

Copilot Airbus-320

Navigator Boing-747

1024 Smith

Copilot Boing-747

Tabelle 27: Hinzufügen von Tupeln (2)

Würde man nur hinsichtlich des mengenwertigen Attributs ,,Flugzeug-Typ"

einen geschlossenen Term verwenden, so würde dem Mitarbeiter Smith ein

weiteres Aufgabe-Tupel hinzugefügt werden:

.

---

61

Ergebnis:

Mitarbeiter

Ma# Name

Aufgabe

Bezeichnung Flugzeug-Typ

Typname

1024 Smith

Pilot

Airbus-320

Boing-747

Copilot Airbus-320

Copilot Boing-747

2048 Müller

Copilot Airbus-320

Navigator Boing-747

Tabelle 28: Hinzufügen von Tupeln (3)

Das Löschen von Daten geschieht analog zur Technik des Einfügens. Ob ein

mit einer Filtertabelle beschriebenes Tupel eingefügt oder gelöscht werden soll,

ergibt sich später aus dem Kontext des Petrinetzes.

Möchte man bspw. aus Tabelle 26 das Tupel (,,1024", ,,Smith", ,,Copilot",

,,Boing-747") entfernen, so lässt sich das analog mit der beim Einfügen ver-

wendeten Filtertabelle beschreiben. Auch die in Tabelle 27 und Tabelle 28

eingefügten Tupel lassen sich durch analoge Anwendung der entsprechenden

Filtertabellen bei entsprechender Interpretation entfernen. Dafür muss die

Schnittmenge aus dem Negativ der Instanz der in der Filtertabelle beschriebe-

nen Tupel und dem Datenbestand gebildet werden. Werden beim Löschen nur

geschlossene Terme verwendet, so wird das

gesamte

Tupel gelöscht. Ist dage-

gen mindestens ein Term ein Offener, so werden nur die

enthaltenen

Sub-Tu-

pel gelöscht.

3.4 Resümee

In Kapitel 3 wurde eine Technik zur Repräsentation von Datenstrukturen in

BIS beschrieben. Im Kontext dieser Arbeit löst diese Technik das Problem der

Beschreibung komplex strukturierter Datenobjekte. Es wurde einerseits eine

präzise formale Sprache erläutert, andererseits eine besser verständliche semi-

formale Sprache dafür vorgeschlagen. Diese Technik ist für die formale und

semiformale Beschreibung von Datenstrukturen eines BIS sehr gut geeignet.

Für die formale Beschreibung von Datenmanipulationen eignet sich diese

Technik sehr gut, da mit ihr präzise definiert wird, wie ein Datenobjekt struk-

turiert sein muss und wie Manipulationen in bezug auf die Datenbestände zu

erfolgen haben. Für die semiformale Beschreibung sind dagegen lediglich zwei

---

62

zusätzliche Symbole notwendig, was die Kompliziertheit der Beschreibung auf

ein Mindestmaß reduziert. Die Metapher ,,offener" und ,,geschlossener" Terme,

die man auch als ,,Behälter" bezeichnen könnte, erleichtert ein intuitives Ver-

ständnis des dahinter verborgenen Formalismus.

Um dem Anspruch der kombinierten Repräsentation von Prozess- und Daten-

strukturen zu genügen, muss jedoch noch aufgezeigt werden, wie E-R- und

Petrinetz-Technik mit Hilfe der in dieser Arbeit behandelten genesteten Rela-

tionen kombiniert werden können. Das geschieht im folgenden Kapitel.

Das Problem einer Integration der

Organisationsstruktur

wird dagegen nicht

gelöst. Insb. fehlt eine klare formale Beschreibung der Organisationsstruktur

und ein Konzept für dessen Integration in ein Gesamtmodell zur Repräsenta-

tion von BIS. Durch eine Kombination von E-R- und Petrinetz-Technik kann

diese Integration nur über Umwege erfolgen, was eine eher schlechte Lösung

darstellt.

---

63

4 Integration von Ausdrucksmitteln der E-R- in die

Petrinetz-Technik

4.1 NF²-Relationen/Transitionen-Netze

Um den Anspruch der

Kombination

von E-R- und Petrinetz-Technik zu erfül-

len, werden die aus einem E-R-Modell herzuleitenden genesteten Relationen

jetzt in einem auf Pr/T-Netzen basierenden Petrinetz-Typ114 integriert. Dieser

Petrinetz-Typ wird als NF²-Relationen/Transitionen-Netz (im folgenden kurz:

NR/T-Netz) bezeichnet115. Dieses NR/T-Netz wird im formal definiert und

anhand des Beispiels aus Abbildung 13 werden dessen einzelne Komponenten

näher erläutert.

Abbildung 13: Beispiel für ein NR/T-Netz

Mit den folgenden Definitionen und Erläuterungen dieser Netzkomponenten

wird verdeutlicht, dass es sich bei NR/T-Netzen um eine ,,echte" Kombination

von Prozess- und Datenmodellierung handelt. ,,Echt" bedeutet dabei, dass die

Kombination von Prozess- und Datenmodellierung formalsprachlich präzise

beschrieben wird und nicht lediglich grafische Elemente im Rahmen eines se-

miformalen Modells kombiniert verwendet werden. Durch diese formalsprach-

liche Definition wird wiederum deutlich, dass mit dieser Technik konstruierte

semiformale Modelle nicht nur grafisch dargestellt werden können. Vielmehr

könnte eine entsprechende Modellierungssoftware einerseits zur Simulation

114 Dieser Petrinetz-Typ geht auf OBERWEIS zurück, vgl. Oberweis (1996a), S. 125-172;

Oberweis (1996b), S. 33-43. Diesen erarbeitete OBERWEIS überwiegend mit Hilfe der Ar-

beiten von SANDER, vgl. Oberweis (1996a), S. 112-125; Oberweis/Sander (1996), S. 399-

406; Sander (1993), S. 43-163. Jedoch erläutert OBERWEIS nicht, wie dieser Petrinetz-Typ

mit der E-R-Technik kombiniert werden kann, vgl Oberweis (1996a), S. 105-107 und S.

157. Auch JAESCHKE erläutert nicht im Detail eine solche kombinierte Verwendung, son-

dern fokussiert das sog. ,,E-R-Clustering", vgl. Jaeschke (1996), S. 179-224.

115 NF² steht für Non First Normalform (NFNF).

---

64

eines BIS verwendet werden, aber auch zur (anschließenden)

automatisierten

Implementierung

, bspw. in ein WfMS wie Lotus Workflow116. Denkbar sind

ebenso Anwendungen in den Bereichen der Produktionsplanung und -steu-

erung, dem unternehmensübergreifenden Management von Liefernetzwerken

und der Einführung und dem Betrieb von betriebswirtschaftlicher Standdard-

software, wie z.B. SAP R/3.

Definition 14: NR/T-Netz

Ein NR/T-Netz117 ist ein 5-Tupel

NRT

= (

NN

,

P

,

AI

,

TI

,

M0

) mit

(1)

NN

= ( ,

N

) ist ein sog. NR-Netz (NF²-Relationen-Netz), = (

U

,

D

, ,

dom

),

N

= (

S

,

T

,

F

) wobei

U

eine Menge von atomaren und zusammengesetzten Attribu-

ten,

Ueinfach

die Menge der atomaren Attribute in

U

,

D

ein Datenmodell,

= { 1, 2, ...} eine Menge von Domänen,

dom

:

Ueinfach

eine Funktion und

N =

(

S

,

T

,

F

) ein Netz ist mit

S

= {

A1

, ...,

An

}, der Menge der

Top-Level-Attribute aus

D

ist.

(2)

P

ist eine Menge von Prädikatsymbolen, um Gleichheit, Enthaltensein

usw. zwischen Instanzen auszudrücken. Jedes Element

p

P

hat eine

feste Interpretation

I

(

p

), die eine Relation entsprechender Stelligkeit

über Instanzen und Tupel ist.

(3) Sei

BT

(

A

) die Menge aller bewerteten Top-Level-Terme (d.h.

Filtertabellen). Dann ist

AI

eine Funktion, die jeder Kante

f

F

eine

Filtertabelle aus

BT

(

A

) zuweist, wobei

A

das zu der adjazenten Stelle

gehörige lokale Datenobjekt, bezeichnet durch dessen Top-Level-Attri-

but, ist.

(4)

TI

:

T

LF

ist eine Funktion, die jeder Transition einen logischen Aus-

druck aus

LF

zuweist, wobei

LF

wie folgt definiert ist:

116 Lotus Workflow ist eine Workflow-Management-Software des Unternehmens IBM, vgl.

Lotus (o.D.).

117 Vgl. Oberweis (1996a), S. 125-129 und S. 139 f., sowie Oberweis/Sander (1996), S. 399 f.

und S. 402.

---

65

TRUE

LF

Wenn

p

P

ein

n

-stelliges Prädikat ist und

var1

,...,

varn

Variab-

len oder konstante Werte sind, dann ist

p

(

var1

,...,

varn

)

LF

Wenn

p1

LF

und

p2

LF

, dann sind auch

p1

p2

,

p1

p2

,

p1

LF

(5) Eine Markierung

M

ist eine Abbildung, die jeder Stelle

Ai

S

eine In-

stanz118 vom Typ

Aj

zuweist.

M0

ist die sogenannte Startmarkierung.

4.2 Netzkomponenten

4.2.1 Stellen und genestete Relationen

Gemäß der o.a. Definition und dem hier gewählten Ansatz zur Herleitung

komplexer Datenobjekte sind die Stellen eines NR/T-Netzes

S

gleich der

Menge der Top-Level-Attribute, die jeweils ein lokales Datenmodell bezeich-

nen. Bezogen auf das Beispiel aus Abbildung 13 sind dies die Attribute ,,Flug-

durchführung", ,,Verfügbare-Flugzeuge" und ,,Crew-Anforderung". Damit

kann die Menge der Stellen definiert werden als

S

= {Flugdurchführung, Ver-

fügbare-Flugzeuge, Crew-Anforderung}.

Die Startmarkierung

M0

weist jeder Stelle

Ai

S

eine

Instanz

mit der Daten-

struktur vom Typ

Aj

zu, die sich aus dem Datenmodell

D

ergibt119, bspw. für s

= Verfügbare-Flugzeuge die Datenstruktur

Verfügbare-Flugzeuge := {(Flugzeug-Nr, Sitze, Typname, Auf-

gabe := {(Bezeichnung)})}

mit folgender Startmarkierung (d.h. Instanz):

118 Anders Oberweis (1996a), S. 140: Statt ,,Instanz" wird dort der Begriff ,,Relation" verwen-

det. Eine Markierung entspricht aber einer Instanz, übereinstimmend Oberweis/Sander

(1996), S. 402. In der hier verwendeten Terminologie ist eine Markierung eine Instanz vom

Typ

A

, wobei

A

als Top-Level-Attribut eines Relationen-Typs (d.h. einer ,,geschachtelten

Tabelle") ist.

119 Vgl. Kapitel 3.2.2.

---

66

Verfügbare-Flugzeuge

Flugzeug-Nr Typname Sitze

Aufgabe

Bezeichnung

12 Airbus-320

155

Pilot

Copilot

24 Airbus-320

155

Pilot

Copilot

Tabelle 29: Startmarkierung eines NR/T-Netzes

Jeder Stelle des Netzes wird also die Instanz einer genesteten Relation zuge-

wiesen. Die Struktur der genesteten Relation ergibt sich aus der Struktur eines

E-R-Modell-Ausschnitts. Sie repräsentiert Objekte der Realität in Form von

komplexen Datenobjekten, hier veranschaulicht in Form einer geschachtelten

Tabelle. Die in Kapitel 2.3 beschriebenen Probleme der Pr/T-Netze hinsichtlich

der Stellen eines Netzes existieren durch diese Technik damit nicht mehr: Die

Beschränkung auf flache

n

-Tupel ist aufgehoben und die Repräsentation leerer

Mengen120 ist ebenfalls explizit möglich.

4.2.2 Kanten und Filtertabellen

Jeder Kante (d.h. Flussrelation)

f

eines NR/T-Netzes wird jeweils eine Filterta-

belle zugeordnet. Mit einer Filtertabelle wird die Selektion der in einer Stelle

,,enthaltenen" Daten beschrieben, die den Selektionskriterien der Filtertabelle

entsprechen. Ob die selektierten Daten gelöscht oder hinzugefügt werden, er-

gibt sich aus dem Kontext des Netzes: Eine Filtertabelle im Vorbereich

t

einer

Transition ,,entnimmt" die entsprechenden Daten ,,aus" der adjazenten Stelle,

eine Filtertabelle im Nachbereich

t

einer Transition fügt die Daten der adja-

zenten Stelle hinzu.

Eine Filtertabelle besteht formal aus einem bewerteten Top-Level-Term aus

BT

, eine Funktion

AI

weist einer Kante eine Filtertabelle aus

BT

zu. Für das

Beispiel aus Abbildung 13 wird die Filtertabelle der Flussrelation (Verfügbare-

Flugzeuge, Flugzeugzuweisung) folgendermaßen definiert:

BT

(Verfügbare-Flugzeuge, Flugzeugzuweisung) :=

(({(Flugzeug-Nr: Fl, Sitze: Si, Typname: Ty, Aufgabe:

Au)}), ( Verfügbare-Flugzeuge := (=Flugzeug-Nr, =Sitze, =Aufgabe)))

120 Vgl. hierzu auch S. 36.

---

67

Durch diese Filtertabelle werden alle Tupel der adjazenten Stelle ,,Verfügbare-

Flugzeuge" entnommen. Dagegen würde eine Filtertabelle der Art

BT

(Verfügbare-Flugzeuge, Flugzeugzuweisung) :=

(({(Flugzeug-Nr: Fl, Sitze: Si, Typname: ,,Airbus-320",

Aufgabe: Au)}), ( Verfügbare-Flugzeuge := (=Flugzeug-Nr, =Sitze,

=Aufgabe)))

nur Tupel mit Typname ,,Airbus-320" entnehmen.

Eine Filtertabelle im Vorbereich einer Transition, die nur aus geschlossenen

Termen besteht, entnimmt die gesamten mit ihr beschriebenen Tupel. Besteht

eine Filtertabelle im Vorbereich jedoch aus mindestens einem offenen Term, so

werden nur die enthaltenen Sub-Tupel entnommen (d.h. gelöscht).

Eine Filtertabelle im Nachbereich einer Transition, die nur aus geschlossenen

Termen besteht, fügt die mit ihr beschriebenen Tupel als Ganzes hinzu. Eine

Filtertabelle im Nachbereich einer Transition, die aus mindestens einem of-

fenen Term besteht, verschmelzt den mit ihr beschriebenen Sub-Tupel mit ei-

nem bestehenden Tupel in dem Fall, dass Gleichheit hinsichtlich der Instan-

ziierungen der einzelwertigen Attribute und der mengenwertigen Attribute mit

geschlossenen Termen besteht. Dies wird im nächsten Kapitel mit den Schalt-

regeln einer Transition definiert.

4.2.3 Transitionen und Schaltregeln

Einer Transition

t

T

eines NR/T-Netzes wird eine logische Funktion durch

die Funktion

FI

(

t

) zugeordnet. Mit einer solchen logischen Funktion lassen

sich die Bedingungen definieren, unter denen eine Transition schalten kann.

Mit diesen logischen Funktionen sind aber auch über Trivialbeispiele

hinausgehende Regeln modellierbar, bspw. auch komplexe Crew-Scheduling-

Algorithmen. In dem hier verwendeten Beispiel kann eine einfache Regel

sinnvoll der Transition ,,Flugzeug-Zuweisung" zugeordnet werden: Die Anzahl

der Sitze (in einem Flugzeug) muss mindestens so groß sein wie die Anzahl der

Plätze (die ein angeforderter Flug, bspw. ein Charterflug, benötigt). Gemäß

Definition 14 (4) kann das als

TI

(Flugzeugzuweisung) = (Si Pl) formal

beschrieben werden.

---

68

Eine Transition ist aktiviert und schaltet, wenn die Bedingung

TI

erfüllt werden

kann. Das Schalten einer Transition wird definiert derart, dass instanziierte

Terme der Filtertabelle aus den Stellen im Vorbereich gelöscht und in die

Stellen im Nachbereich eingefügt werden.

Definition 15: Aktivierte Transition

Sei eine gültige Instanziierung aller Terme in der Umgebung von

t

, und

M

eine gültige Markierung. Die Transition

t

ist (

M

, )-

aktiviert

, wenn gilt121:

(1)

A

t

:

A

,

O M

(

A

), wobei

AI

(

A

,

t

) = ( ,

O

).

(2)

A

t

:

A

,

O Neg A,O

(

M

(

A

)), wobei

AI

(

A

,

t

) = ( ,

O

).

(3)

TV

(

TI

(

t

) ) = TRUE.

Die erste Bedingung verlangt, dass der

instanziierte Term

einer Eingangs-

Kante vollständig in der Instanz

M

(

A

) der adjazenten Stelle

A

enthalten sein

muss. Die zweite Bedingung fordert, dass der instanziierte Term einer Aus-

gangs-Kante nicht ­auch nicht teilweise­ in der Instanz

M

(

A

) der adjazenten

Stelle

A

enthalten sein darf. Zusätzlich muss nach der dritten Bedingung gelten,

dass der Wahrheitswert der Transitionsbeschriftung für die Variablenbelegung

TRUE ergeben muss. Wenn eine Transition

t

(

M

, )-aktiviert ist, kann sie für

die Markierung

M

und die Variablen-Instanziierung schalten.

Definition 16: Schalten einer Transition

Sei eine Transition (

M

, )-aktiviert. Wenn

t

schaltet, wird die Markierung

M

in

einem Schritt zur neuen Markierung

M

′, die sich wie folgt ergibt122:

(1)

A

S

\ (

t

t

) :

M

′(

A

) =

M

(

A

).

(2)

A

t

\ (

t

t

) :

M

′(

A

) =

M

(

A

)

A

,

O NegA,O

( ),

wobei

AI

(

A

,

t

) = ( ,

O

).

(3)

A

t

\ (

t

t

) :

M

′(

A

)

A

,

O

, wobei

AI

(

t

,

A

) = ( ,

O

).

121 Vgl. Oberweis (1996a), S. 148 f.

122 Vgl. Oberweis (1996a), S. 149 f.

---

69

(4)

A

(

t

t

) :

M′

(

A

) =

M

(

A

)

A

,

O NegA,O

( )

A

,

O

′ ,

wobei

AI

(

t

,

A

) = ( ′,

O

′) und

AI

(

A

,

t

) = ( ,

O

).

Nach (1) bleiben Markierungen, die nicht in der Umgebung von

t

liegen, durch

das Schalten von

t

unverändert. Nach (2) werden aus den Eingangsstellen, die

nicht gleichzeitig Ausgangsstellen von

t

sind, die durch die instanziierten Fil-

tertabellen an den entsprechenden Kanten spezifizierten Tupel entfernt; in die

Ausgangsstellen, die nicht gleichzeitig Eingangsstellen von

t

sind, werden die

durch die instanziierten Filtertabellen an den entsprechenden Kanten spezifi-

zierten Tupel gemäß (3) eingefügt; in die Stellen, die sowohl im Vor- als auch

im Nachbereich von

t

liegen, werden die durch die instanziierten Filtertabellen

an

t

′s Ausgangskanten bestimmten Tupel eingefügt, und außerdem werden die

durch die instanziierten Filtertabellen an

t

′s Eingangskanten bestimmten Tupel

aus diesen Stellen gelöscht. Die Reihenfolge des Einfügens und Löschens ist

wegen der Unabhängigkeit der instanziierten Terme beliebig (4). Zu beachten

ist hier, dass Einfügen und Löschen des gleichen (Sub-)Tupels durch einen

einzelnen Schaltvorgang von

t

nicht möglich ist, da

t

nicht aktiviert ist, falls ein

einzufügendes (Sub-)Tupel bereits in der betreffenden Stelle (in bezug auf die

entsprechende Ordnung) enthalten ist.

---

70

5 Evaluation

5.1 Beurteilungskriterien

In diesem Kapitel wird ein Kriterienkatalog zur abschließenden Beurteilung

der auf NF/R-Netzen basierenden Technik zur Repräsentation betrieblicher

Informationssysteme durch Kombination von E-R- und Petrinetz-Technik auf-

gestellt. Dieser Kriterienkatalog wird in die Kriterien

Modellierungsfähigkeit

,

Integration

und

Flexibilität

unterteilt. Die Kriterien werden auf einer Ordi-

nalskala gemessen, da keine begründete Hoffnung besteht, dass die Messung

auf einer Kardinalskala realisierbar ist123. Hinsichtlich der Aggregation der

Messergebnisse wird darauf hingewiesen, dass die Bildung eines Mittelwerts

bei der Verwendung einer Ordinalskala eigentlich einen Skalenbruch darstellt

und damit nicht zulässig ist. Aufgrund fehlender Alternativen (z.B. die Mög-

lichkeit der Messung auf einer Kardinalskala) wird dieser Mangel jedoch hin-

genommen. Aussagen über die Vollständigkeit der Modellierungssprache hin-

sichtlich der Realitätsbeschreibung können aufgrund der Sprachrelativität von

Realitätsbeschreibungen nicht gemacht werden124, da dieser Arbeit das

Verständnis von Modellen als Resultate aktiver Konstruktionsleistungen

zugrunde liegt.

Die

Modellierungsfähigkeit

betrifft ausgewählte Elemente der behandelten

Modellierungs-Technik. Jedes Element wird unterteilt in dessen Model-

lierungsfähigkeit für semiformale und formale Modelle. Die auf Basis dieser

Arbeit ausgewählten Elemente sind Datenstruktur, Datenmanipulation, Pro-

zessstruktur, Ablauflogik, Nebenläufigkeit und Organisationsstruktur. Zusätz-

lich werden die Elemente Unsicherheit und Zeit eingeführt, da diese ebenfalls

für die Repräsentation von BIS relevant sind125.

Die

Integration

betrifft die Kombination von Modellen einzelner Aspekte eines

BIS zu einem Gesamtmodell. Dazu zählen nach dem hier zugrundegelegten

Verständnis von BIS Prozess-, Daten- und Organisationsstruktur.

123 Vgl. hierzu auch Zelewski (1996), S. 378.

124 Vgl. Zelewski et al. (1996), S. 213.

125 Vgl. hierzu bspw. Guth et al. (1997) und Janssens et al. (2000), S.5 f.

---

71

Für die Bewertung der Integration leisten die bewerteten Kriterien der Mo-

dellierungsfähigkeit einen wesentlichen Beitrag. Eine Integration von Daten-

und Prozessstruktur hat insb. dann stattgefunden, wenn beschrieben werden

kann, welche Daten beim Schalten einer Transition wie manipuliert werden.

Die Schaltbedingungen und Filtertabellen geben dabei an, unter welchen Be-

dingungen eine Transition schaltet und welche Wirkung dieses Schalten auf die

Daten des BIS hat. Dabei ist jeder Transition eine Organisationseinheit zuzu-

ordnen, die der Organisationsstruktur zu entnehmen ist. Diese Aktivitäten wer-

den eine bestimmte Zeit beanspruchen und könnten möglicherweise mit einer

bestimmten Wahrscheinlichkeit stattfinden. Mitunter können verschiedene Ak-

tivitäten nebenläufig, d.h. ohne Kausalzusammenhang stattfinden.

Der Aspekt der

Flexibilität

betrifft den Umstand, dass die Strukturen eines BIS

im Zeitablauf Änderungen unterworfen sind. Flexibilität wird als die Fähigkeit

interpretiert, innerhalb einer Zeitspanne mit gegebenen Mitteln eine bestimmte

Änderung zu bewirken126. In bezug auf die Modellierungstechnik können diese

Änderungen die Prozess-, Daten- und Organisationsstruktur betreffen. Mit dem

Flexibilitätsaspekt soll bewertet werden, ob und wie gut solche Änderungen in

bestehende Modelle übernommen werden können.

5.2 Bewertung der Modellierungstechnik

5.2.1 Modellierungsfähigkeit

In dieser Arbeit wurde ausführlich dargelegt, dass Petrinetze, insb. NR/T-

Netze, sehr gut für die Konstruktion formaler und semiformaler Modelle von

Prozessstrukturen geeignet sind (vgl. Kapitel 2.2 und Kapitel 4).

Die Ablauflogik betrieblicher Prozesse kann formal sehr gut durch prädika-

tenlogische Schaltregeln beschrieben werden127. Hinsichtlich einer semiforma-

len Beschreibung bestehen jedoch leichte Schwächen, da kein Konzept für eine

126 Vgl. Antweiler (1995), S. 91-93.

127 Es bestehen jedoch noch zwei kleinere Defekte hinsichtlich der Schaltregel: So ist es nicht

möglich, denselben (Sub-)Tupel derselben Stelle zu entnehmen und gleichzeitig hinzuzufü-

gen. Das könnte jedoch bei reinen ,,Lesezugriffen" die Modellierung erleichtern. Weiter be-

steht kein Konzept für die Beschreibung von Sprungbefehlen im Falle

nicht

erfüllter Be-

dingungen. Auch wurde hier keine modallogische Erweiterung (z.B. ,,Fakt-Transitionen")

behandelt, die aber prinzipiell möglich ist, vgl. Oberweis (1996a), S. 159-168. Zu den letz-

ten beiden Punkten (Sprungbefehle bei nicht erfüllten Bedingungen und modallogische Er-

weiterung) siehe auch Zelewski (1996), S. 374.

---

72

intuitiv verständliche Beschreibung dieser teilweise komplizierten Schaltregeln

besteht. Die Möglichkeit der Beschriftung von Transitionen mit entsprechen-

den prädikatenlogischen Ausdrücken wird als ,,mittelmäßig" bewertet.

Eine klare Stärke der NR/T-Netze ist die Möglichkeit der Modellierung von

Nebenläufigkeit. Neben dem allgemein bekannten Verständnis von Nebenläu-

figkeit bei Petrinetzen (vgl. Kapitel 2.2.1) erfahren die NR/T-Netze eine Erwei-

terung: Die Nebenläufigkeit bezieht sich auch auf disjunkte Sub-Tupel eines

Datenobjekts, d.h. es können

einer

Stelle unterschiedliche Sub-Tupel nebenläu-

fig ,,entnommen" werden (vgl. insb. Kapitel 4.2.3).

Der Aspekt der Unsicherheit wird dagegen gar nicht erfasst. Zwar können

bspw. mit K/I-Netzen Prozessstrukturen beschrieben werden, die nicht deter-

miniert sein müssen. Eine Beschreibung von Eintrittswahrscheinlichkeiten ist

jedoch nicht ohne zusätzliche Erweiterungen der hier vorgestellten Model-

lierungstechnik möglich. Dieser Aspekt wird mit daher mit ,,sehr schlecht"

bewertet.

Auch die Modellierung von Zeitaspekten ist mit der Modellierungstechnik

nur über Umwege, bspw. über die Verwendung eines zu konstruierenden ,,Uhr-

Mechanismus" in Datenobjekten128, möglich. Ein klares Konzept zur Model-

lierung von Zeitaspekten bietet die Modellierungstechnik jedoch nicht. Daher

wird dieses Kriterium mit ,,schlecht" bewertet, auch hier besteht Erweiterungs-

bedarf.

Für die Modellierung der Datenstruktur wird einerseits die E-R-Technik ver-

wendet, andererseits werden Ausschnitte aus einem mit dieser Technik zu

erstellenden globalen E-R-Modell in genestete Relationen transformiert. Das

ermöglicht eine sehr gute semiformale Beschreibung, aber auch eine sehr gute

formale Beschreibung der Datenstruktur (vgl. Kapitel 3.1 und Kapitel 3.2).

Eine weitere Stärke dieser Modellierungstechnik sind die Möglichkeiten zur

Beschreibung von Datenmanipulationen. Der Kern des hier beschriebenen

Konzepts löst ein zentrales Problem in bezug auf die Datenmanipulation kom-

plexer Datenobjekte und bietet eine intuitiv verständliche grafische Sprache für

eine semiformale Beschreibung solcher Manipulationen. Daraus ergibt sich

128 Vgl. Oberweis (1996a), S. 180 f.

---

73

eine sehr gute Modellierungsfähigkeit in bezug auf die Datenmanipulation (vgl.

Kapitel 3.3.3 und Kapitel 3.3.4).

Die Organisationsstruktur, hier verstanden als die Struktur der Aufbauorgani-

sation, kann mit diesem Modellierungsansatz nicht direkt modelliert werden.

Die Verwendung der hier erarbeiteten Modellierungstechnik fokussiert viel-

mehr die Prozess- und Datenstruktur. Zwar ist prinzipiell eine informale Be-

schriftung der Transitionen mit Organisationseinheiten möglich, und formal

eine Beschreibung der Organisationseinheiten mit Datenobjekten129. Ein Kon-

zept für die explizite semiformale und formale Beschreibung ­bspw. eines Or-

ganigramms­ existiert jedoch nicht. Daher wird die Modellierungsfähigkeit

hinsichtlich der Organisationsstruktur als ,,schlecht" bewertet, hier besteht Er-

weiterungsbedarf.

Modellierungsfähigkeit

semiformal

formal

1 2 3 4 5 1 2 3 4 5

Prozessstruktur

Ablauflogik

Nebenläufigkeit

Unsicherheit

Zeit

Datenstruktur

Datenmanipulation

Organisationsstruktur

Mittelwert

Gesamtbewertung

gut

1=sehr schlecht, 2=schlecht, 3=mittelmäßig, 4=gut, 5=sehr gut

Tabelle 30: Bewertung der Modellierungsfähigkeit

5.2.2 Integration

Mit der in dieser Arbeit behandelten Modellierungstechnik ist es möglich, Pro-

zess- und Datenstruktur sowohl semiformal als auch formal in

einem

Gesamt-

modell zu beschreiben.

Schwächen bestehen bei der Modellierungstechnik jedoch hinsichtlich der

Modellierung von Zeitaspekten, Unsicherheit und der Organisationsstruktur.

129 Vgl. Oberweis (1996a), S. 181-184. Ebenso Jaeschke (1996), S.87-89, der lediglich eine

Funktionshierarchie als ,,Aufbauorganisation" vorschlägt.

---

74

Die Schwächen hinsichtlich der Zeitaspekte und der Unsicherheit werden der

Integration der Prozessstruktur zugeordnet, da dies eher funktionale Aspekte

eines BIS betrifft. Hinsichtlich des Zeitaspekts wird konkret bemängelt, dass

nicht ohne weiteres beschrieben werden kann, wie lange eine Transition für die

Ausführung einer Aktivität benötigt. Hinsichtlich des Aspekts der Unsicherheit

wird konkret bemängelt, dass nicht ohne weiteres beschrieben werden kann,

wie stochastische Einflüsse auf die Aktivierung bestimmter Transitionen wir-

ken. Aufgrund dieser Mängel wird die Integration der Prozessstruktur auf der

Ordinalskala ­statt mit fünf von fünf Punkten­ mit vier Punkten, d.h. ,,gut"

bewertet.

Diese Mängel betreffen zwar implizit auch die Datenstruktur, da Funktionen

Daten manipulieren. Die Datenstruktur selbst ist aber ,,sehr gut" integriert, da

mit der Modellierungstechnik die Probleme, die üblicherweise aus der Norma-

lisierung von Datenstrukturen resultieren, beseitigt wurden.

Die Organisationsstruktur ist dagegen nur ,,schlecht" integriert. Diese Bewer-

tung wird damit begründet, dass ein Konzept wünschenswert wäre, das bspw.

Organigramme sowohl semiformal, vor allem aber auch formal integriert.

Integration

1 2 3 4 5

Prozessstruktur

Datenstruktur

Organisationsstruktur

Gesamtbewertung

gut

1=sehr schlecht, 2=schlecht, 3=mittelmäßig, 4=gut,

5=sehr gut

Tabelle 31: Bewertung der Integration

5.2.3 Flexibilität

Änderungen der Prozessstruktur können über Modifikationen der Flussrelation

und durch hinzufügen/entfernen von Stellen und Transitionen verhältnismäßig

einfach auf das Modell übertragen werden. Ausgehend von der Prozessstruktur

kann die Flexibilität daher mit ,,sehr gut" bewertet werden.

Problematischer sind jedoch Interdependenzen zwischen Daten- und Prozess-

struktur. So könnten Änderungen der Datenobjekte zugleich Änderungen bei

---

75

den Filtertabellen und den Schaltregeln erforderlich machen. Diese Schwächen

sind primär auf mögliche Änderungen der Datenstruktur zurückzuführen und

werden dieser zugeordnet.

Problematisch sind auch Interdependenzen zwischen dem globalen und den

lokalen Datenmodellen. Verändert sich die Datenstruktur, müssen Änderungen

an dem globalen E-R-Modell vorgenommen werden. Die bereits bestehenden,

aus dem ursprünglichen E-R-Modell abgeleiteten komplexen Datenobjekte

könnten bei Änderungen des E-R-Modells aber ungültig werden. Die Flexibi-

lität hinsichtlich der Datenstruktur hängt damit entscheidend von einer Unter-

stützung durch eine entsprechende Modellierungssoftware ab, die solche Inter-

dependenzen automatisch erkennt. Aufgrund dieser Probleme wird die Flexibi-

lität hinsichtlich der Datenstruktur mit ,,mittelmäßig" bewertet. Es wird aber

angemerkt, dass eine entsprechend realisierte Softwareunterstützung, die nicht

Thema dieser Arbeit war, diese Probleme beseitigen könnte.

Die Organisationsstruktur kann formal nur über Datenobjekte beschrieben

werden. Ändert sich die Organisationsstruktur, so kann dies mit der hier be-

handelten Modellierungstechnik ebenfalls nur über den Umweg der Änderung

des E-R-Modells und den daraus zusätzlich resultierenden Problemen (s.o.)

modelliert werden. Durch diesen notwendigen ,,Umweg" ist die Flexibilität

hinsichtlich der Organisationsstruktur schlechter als die der Datenstruktur.

Wünschenswert wäre dagegen die Möglichkeit der direkten Änderung von Or-

ganisationsmodellen. Die Flexibilität der Organisationsstruktur wird daher mit

,,schlecht" bewertet.

Flexibilität

1 2 3 4 5

Prozessstruktur

Datenstruktur

Organisationsstruktur

Gesamtbewertung

mittelmäßig

1=sehr schlecht, 2=schlecht, 3=mittelmäßig, 4=gut,

5=sehr gut

Tabelle 32: Bewertung der Flexibilität

---

76

5.3 Kritische

Würdigung

In Tabelle 33 ist eine Zusammenfassung der Bewertung der in dieser Arbeit

behandelten Modellierungstechnik dargestellt. Insgesamt werden die Model-

lierungsfähigkeit und die Integration mit ,,gut", d.h. mit 4 von 5 Punkten auf

der Ordinalskala, bewertet. Die Flexibilität wird mit ,,mittelmäßig", d.h. mit 3

von 5 Punkten auf der Ordinalskala, bewertet130. Das führt unter Hinnahme des

Skalenbruchs hinsichtlich der verwendeten Kriterien zu dem Ergebnis, dass es

sich um eine Modellierungstechnik handelt, die ,,gut" für die Repräsentation

betrieblicher Informationssysteme geeignet ist.

1 2 3 4 5

Modellierungsfähigkeit

Integration

Flexibilität

Gesamtbewertung

1=sehr schlecht, 2=schlecht, 3=mittelmäßig, 4=gut,

5=sehr gut

Tabelle 33: Gesamtbewertung der Modellierungstechnik

Dabei ist jedoch zu beachten, dass bei dieser Bewertung bestimmte Annahmen

getroffen wurden, die so nicht unbedingt erfüllt sein müssen. Insb. bei dem

Kriterium der Flexibilität spielt eine evtl. Softwareunterstützung der Model-

lierungstechnik eine wesentliche Rolle. Da die Modellierungstechnik durchge-

hend formal beschrieben wurde, ist es denkbar, mit einer auf dieser Basis er-

stellten Modellierungssoftware evtl. notwendige Änderungen bei den verschie-

denen Modellebenen zu automatisieren. Daher wird die Hypothese vertreten,

dass eine solche Automatisierung die Flexibilität erhöhen würde.

Umgekehrt ist fraglich, inwieweit eine solche Modellierungstechnik ohne ent-

sprechende Softwareunterstützung überhaupt einen praktischen Anwendungs-

nutzen besitzt. Eine Bewertung entsprechender Softwareprodukte war jedoch

nicht Thema dieser Arbeit. Insofern wäre es interessant, eine Evaluation von

Softwareprodukten zur Unternehmensmodellierung im Hinblick auf die Unter-

130 Zu den Begründungen vgl. Kapitel 5.2

---

77

stützung der hier vorgestellten Anforderungen an eine Modellierungstechnik

zur Repräsentation betrieblicher Informationssysteme vorzunehmen. Kandida-

ten für eine solche Evaluation sind bspw. die in Kapitel 2.2.1, Fußnoten 41 und

42, genannten Softwareprodukte.

Weiter führte die ,,schlechte" Modellierungsfähigkeit, Integration und Flexibi-

lität der Organisationsstruktur zu einer Abwertung der Modellierungstechnik.

Hier ist eine Analyse der Erweiterungsmöglichkeiten von Interesse. Auch

könnte eine Kombination der Modellierungstechnik mit Konzepten für Zeit-

aspekte und Unsicherheit eine weitere Verbesserung bewirken.

Abschließend ist zu bemerken, dass sowohl die Auswahl der Kriterien als auch

die Bewertung dieser nur scheinbar eine objektive Gesamtbewertung ergeben.

Bspw. hängt das Eignungsurteil auch davon ab, welche konkreten Model-

lierungszwecke verfolgt werden131. Es wird daher darauf aufmerksam gemacht,

dass die Bewertungen zwar begründet wurden, aber dennoch eine gewisse

Subjektivität beinhalten.

131 Vgl. hierzu auch Zelewski (1996), S. 379-380.

---

78

Literaturverzeichnis

Aalst (1996):

van der Aalst, W.M.P.: Three good reasons for using a petri-net-based

workflow management system. In: Navathe, S.; Wakayama, T. (Hrsg.):

Proceedings of the International Working Conference on Information

and Process Integration in Enterprises (IPIC′96), Cam-

bridge/Massachusetts 1996, S. 179-201

Antweiler (1995):

Antweiler, J.: Wirtschaftlichkeitsanalyse von Informations- und Kom-

munikationssystemen (IKS): Wirtschaftlichkeitsprofile als Entschei-

dungsgrundlage. Köln 1995

Bancilhon/Khoshafian (1989):

Bancilhon, F.; Khoshafian, S.: A Calculus for Complex Objects. In:

Journal of Computer and System Sciences, Ausgabe 38 (1989), S. 326-

340

Baumgarten (1990):

Baumgarten, B.: Petri-Netze: Grundlagen und Anwendungen. Mann-

heim et al. 1990

Beasley/Cao (1998):

Beasley, J.E.; Cao, B.: A dynamic programming based algorithm for the

crew scheduling problem. In: Computers & Operations Research, Aus-

gabe 25 (1998), Nr. 7-8, S. 567-582

Chen (1976):

Chen, P.P.: The entity-relationship model: Toward a unified view of

data. In: ACM Transactions on Database Systems, Ausgabe 1 (1976),

Nr. 1, S. 166-192

Chen (1977):

Chen, P.P.: The entity-relationship approach to logical data base design.

In: Data Base Management, Nr. 6 (1977)

Chu et al. (1997):

Chu, H.D.; Gelman, E.; Johnson, E.L.: Solving large scale crew

scheduling problems. In : European Journal of Operational Research,

Ausgabe 97 (1997), Nr. 2, S. 260-268

---

79

Cosa (o.D.):

COSA Solutions, Software-Ley GmbH, Pullheim, Deutschland, Inter-

net: http://www.ley.de, Zugriff am 20. September 2002

Dittmann (2002):

Dittman, L.: Sprachen zur Repräsentation von Wissen ­ eine unter-

suchende Darstellung ­. Projektbericht Nr. 3, Projekt KOWIEN, Institut

für Produktion und Industrielles Informationsmanagement, Universität

Essen, Essen 2002. Internet: http://www.kowien.uni-

essen.de/publikationen/Sprachen_zur_Wissensrepraesentation.pdf,

Zugriff am 20. September 2002

Gruhn/Kampmann (1996):

Gruhn, V.; Kampmann, M.: Modellierung unternehmensübergreifender

Geschäftsprozesse mit FUNSOFT-Netzen. In: Wirtschaftsinformatik,

38. Jg. (1996), Heft 4, S. 383-390

Guth et al. (1997):

Guth, V.; Oberweis, A.; Zimmer, T.: Zeit- und Kostenanalyse von Ge-

schäftsprozessen mit höheren Petri-Netzen. In: Proc. Fachtagung

,,Workflow-Management in Geschäftsprozessen im Trend 2000",

Schmalkalden 1997, S. 99-110

Heuser et al. (1993) :

Heuser, C.A.; Peres, E.M.; Richter, G.: Towards a Complete Concep-

tual Model ­ Petri Nets and Entity-Relationship Diagrams. In: Informa-

tions Systems, Ausgabe 18 (1993), Nr. 5, S. 275-298

Income (o.D.):

INCOME, Promatis AG, Karlsbad, Deutschland, Internet:

http://www.get-income.com, Zugriff am 23. September 2002

Jaeschke (1996):

Jaeschke, P.: Integrierte Unternehmensmodellierung ­ Techniken zur

Informations- und Geschäftsprozessmodellierung. Wiesbaden 1996

Jaeschke et al. (1993):

Jaeschke, P.; Oberweis, A.; Stucky, W.: Extending ER Model Cluster-

ing by Relationship Clustering. In: Elmasri et al. (Hrsg.): Entity-Re-

lationship Approach ­ ER `93: Proceedings of the 12th International

---

80

Conference on the Entity-Relationship Approach, Arlington/Texas

1993, S. 451-462

Jaeschke et al. (1994) :

Jaeschke, P. ; Oberweis, A.; Stucky, W.: Deriving Complex Structured

Object Types for Business Process Modelling. In: Loucopoulos, P.

(Hrsg.): Entity-Relationship Approach ­ ER `94: Proceedings of the

13th International Conference on the Entity-Relationship Approach.

Manchester 1994, S. 28-45

Janssens et al. (2000) :

Janssens, G.K. ; Verelst, J. ; Weyn, B.: Techniques for Modelling

Workflows and Their Support of Reuse. In: van der Aalst, W.M.P.; De-

sel, J.; Oberweis, A. (Hrsg.): Business Process Management ­ Models,

Techniques, and Empirical Studies. Berlin et al. 2000, S. 1-15

Krieger (1998):

Krieger, D.J.: Einführung in die allgemeine Systemtheorie. 2. Aufl.,

München 1998.

Lagerholm et al. (2000):

Lagerholm, M.; Peterson, C.; Soderberg, B.: Airline crew scheduling

using Potts mean field techniques. In: European Journal of Operational

Research, Ausgabe 120 (2000), Nr. 1, S. 81-96

Lamersdorf/Schmidt (1983):

Lamersdorf, W.; Schmidt, J.W.: Rekursive Datenmodelle. In: Schmidt,

J.W. (Hrsg.): Sprachen für Datenbanken, Fachgespräch auf der 13. GI-

Jahrestagung Hamburg, Berlin et al. 1983

Langner et al. (1997):

Langner, P.; Schneider, C.; Wehler, J.: Prozessmodellierung mit ereig-

nisgesteuerten Prozessketten (EPKs) und Petri-Netzen. In: Wirt-

schaftsinformatik, 38. Jg. (1997), Heft 5, S. 479-489

Lehner (1996) :

Lehner, F.: Gedanken zur theoretischen Fundierung der Wirtschaftsin-

formatik und Versuch einer paradigmatischen Einordnung. In: Heil-

mann, H.; Heinrich, L.J.; Roithmayr, F. (Hrsg.): Information Engi-

neering ­ Wirtschaftsinformatik im Schnittpunkt von Wirtschafts-, So-

zial- und Ingenieurwissenschaften. München; Wien 1996, S. 68-85

---

81

Levine (1996):

Levine, D.: Application of a hybrid genetic algorithm to airline crew

scheduling. In: Computers & Operations Research, Ausgabe 23 (1996),

Nr. 6, S. 547-558

Lotus (o.D.):

Lotus Workflow 3.0, Lotus Development Corporation, Cambridge,

USA, Internet: http://www.lotus.com/products/domworkflow.nsf,

Zugriff am 25. September 2002

Oberweis (1996a):

Oberweis, A.: Modellierung und Ausführung von Workflows mit Petri-

Netzen. Stuttgart; Leipzig 1996

Oberweis (1996b):

Oberweis, A.: An integrated approach for the specification of processes

an related complex structured objects in business applications. In: Deci-

sion Support Systems, Ausgabe 17 (1996), S. 31-53

Oberweis/Sander (1996):

Oberweis, A.; Sander, P.: Information System Behavior Specification

by High-Level Petri Nets. In: ACM Transactions on Information Sys-

tems, Ausgabe 14 (1996), Nr. 4, S. 380-420

Oberweis et al. (1997a):

Oberweis, A.; Schätzle, R.; Stucky, W.; Weitz, W.; Zimmermann, G.:

INCOME/WF ­ A Petri Net Based Approach to Workflow Manage-

ment. In: Krallmann, H. (Hrsg.): Wirtschaftsinformatik `97, Berlin et al.

1997, S. 557-580

Oberweis et al. (1997b):

Oberweis, A.; Schätzle, R.; Stucky, W.; Weitz, W.; Zimmermann, G.:

Der Einsatz von Petri-Netzen im INCOME/STAR- und INCOME/WF-

Projekt. In: Stucky, W.; Winand, U. (Hrsg.): Petri-Netze zur Model-

lierung verteilter DV-Systeme. Erfahrungen im Rahmen des DFG-

Schwerpunktprogramms ,,Verteilte DV-Systeme in der Betriebswirt-

schaft". Bericht 350, Institut für Angewandte Informatik und Formale

Beschreibungsverfahren, Universität Karlsruhe, 1997, S. 6-14

Österle (1996):

---

82

Österle, H.: Business Engineering: Von intuitiver Organisation zu ra-

tionalen Workflows. In: Österle, H.; Vogler, P. (Hrsg.): Praxis des

Workflow-Managements: Grundlagen, Vorgehen, Beispiele. Braun-

schweig; Wiesbaden 1996

Ozdemir/Mohan (2001):

Ozdemir, H.T.; Mohan, C.K.: Flight graph based genetic algorithm for

crew scheduling in airlines. In: Information Sciences, Ausgabe 133

(2002), Nr. 3-4, S. 165-173

Petri (1962):

Petri, C.A.: Kommunikation mit Automaten, Dissertation, Bonn 1962

Popper (2002):

Popper, K.R.: Alles Leben ist Problemlösen. 7. Aufl., München 2002

Protos (o.D.):

Protos, Pallas Athena BV, Niederlande, Internet: http://www.pallas.nl,

Zugriff am 25. September 2002

Rauh/Stickel (1997):

Rauh, O.; Stickel, E.: Konzeptuelle Datenmodellierung. Stuttgart et al.

(1997)

Reisig (1985):

Reisig, W.: Systementwurf mit Netzen. Berlin et al. 1985

Reisig (1991):

Reisig, W.: Petrinetze - Eine Einführung. 2. Aufl., Berlin et al. 1991

Richter (1993):

Richter, G.: Ereigniszähler. In: Scheschonk, G.; Reisig, W.: Petri-Netze

im Einsatz für Entwurf und Entwicklung von Informationssystemen.

Berlin et al. 1993, S. 72-84

Ropohl (1978):

Ropohl, G.: Einführung in die allgemeine Systemtheorie. In: Lenk, H.;

Ropohl, G. (Hrsg.): Systemtheorie als Wissenschaftsprogramm.

Königstein/Taunus 1978, S. 9-49

Roth et al. (1988):

Roth, M.A.; Korth, H.F.; Silberschatz, A.: Extended Algebra and

Calculus for Nested Relational Databases. In: ACM Transactions on

Database Systems, Ausgabe 13 (1988), Nr. 4, S. 389-417

---

83

Rozenberg (1991):

Rozenberg, G..: Ein Meilenstein für die Informatik. In: GMD-Spiegel

3/4 (1991), S. 52-57, Internet: http://www.informatik.uni-

hamburg.de/TGI/mitarbeiter/profs/petri/laudatio.html, Zugriff am 20.

September 2002

Salimifard/Wright (2001):

Salimifard, K.; Wright, M.: Petri net-based modelling of workflow

systems: An overview. In: European Journal of Operational Research,

Ausgabe 134 (2001), S. 664-676

Sander (1992):

Sander, P.: Boolean lattices of nested relations as a foundation for rule-

based database languages. In: Data & Knowledge Engineering,

Ausgabe 8 (1992), S. 93-130

Sander (1993):

Sander, P.: Eine ordnungsbasierte Regelsprache für NF2-Relationen.

Aachen 1993

Schek/Scholl (1983):

Schek, H.-J.; Scholl, M.H.: Die NF²-Relationenalgebra zur einheitlichen

Manipulation externer, konzeptueller und interner Datenstrukturen. In:

Schmidt, J.W. (Hrsg.): Sprachen für Datenbanken ­ Fachgespräch auf

der 13. GI-Jahrestagung, Hamburg (1983), S. 113-133

Schek/Scholl (1986):

Schek, H.-J.; Scholl, M.H.: The Relational Model with Relation-Valued

Attributes. In: Information Systems, Ausgabe 11 (1986), Nr. 2, S. 137-

147

Scheer (1996) :

Scheer, A.-W.: Architekturen für das Information Engineering. In:

Heilmann, H.; Heinrich, L.J.; Roithmayr, F. (Hrsg.): Information

Engineering ­ Wirtschaftsinformatik im Schnittpunkt von Wirtschafts-,

Sozial- und Ingenieurwissenschaften. München; Wien 1996, S. 236-260

Scheer (1998):

Scheer, A.-W.: ARIS ­ Vom Geschäftsprozeß zum

Anwendungssystem. 3. Aufl., Berlin et al. 1998

Schmidt (1999):

---

84

Schmidt, G.: Informationsmanagement ­ Modelle, Methoden,

Techniken. 2. Aufl., Berlin et al. 1999

Schütte (1997):

Schütte, R.: Die neuen Grundsätze ordnungsmäßiger Modellierung.

Paper zum Forschungsforum `97, Leipzig 16.09.-20.09.1997

Schütte (1998):

Schütte, R.: Grundsätze ordnungsmäßiger Referenzmodellierung ­

Konstruktion konfigurations- und anpassungsorientierter Modelle.

Wiesbaden 1998

Sinz (1996):

Sinz, E.J.: Ansätze zur fachlichen Modellierung betrieblicher

Informationssysteme ­ Entwicklung, aktueller Stand und Trends. In:

Heilmann, H.; Heinrich, L.J.; Roithmayr, F.: Information Engineering ­

Wirtschaftsinformatik im Schnittpunkt von Wirtschafts-, Sozial- und

Ingenieurwissenschaften. München; Wien 1996, S. 123-143

Spitzer (1961):

Spitzer, M.: Solution to the crew scheduling problem. Spring Valley

Conference, Airline Group, International Federation of Operations

Research Societies, 1961

Stucky et al. (1993) :

Stucky, W. ; Oberweis, A.; Scherrer, G.: INCOME/STAR: process

model support for the development of information systems. In:

Niedereichholz, J. (Hrsg.): Wirtschaftsinformatik. Frankfurt a.M. 1993,

S. 145-165

Thalheim (2000) :

Thalheim, B. : Entity-relationship modelling: foundations of database

technology. Berlin; Heidelberg 2000

Verbandstheorie (o.D.) :

o.V. :

Verbandstheorie.

Internet:

http://www.begriffslogik.de/artikel/bookdip/node3.html, Zugriff am 14.

November 2002

Yan/Tu (2002a) :

---

85

Yan, S.; Tu, Y.-P.: A network model for airline cabin crew scheduling.

In: European Journal of Operational Research, Ausgabe 140 (2002), Nr.

3, S. 531-540

Yan/Tu (2002b):

Yan, S. ; Tu, Y.-P. : Airline cockpit crew scheduling. In : European

Journal of Operational Research, Ausgabe 136 (2002), Nr. 3, S. 501-

511

Zelewski (1996):

Zelewski, St.: Eignung von Petrinetzen für die Modellierung komplexer

Realsysteme ­ Beurteilungskriterien. In: Wirtschaftsinformatik, 38. Jg.

(1996), Heft 4, S. 369-381

Zelewski et al. (2001):

Zelewski, St.; Schütte, R.; Siedentopf, J.: Ontologien zur

Repräsentation von Domänen. In: Schreyögg, G. (Hrsg.): Wissen in

Unternehmen ­ Konzepte, Maßnahmen, Methoden. Berlin 2001, S.

183-221

Zloof (1975):

Zloof, M.M.: Query-by-Example: The Invocation and Definition of

Tables and Forms. In: Proceedings of the International Conference on

Very Large Data Bases, Ausgabe 1 (1975), Nr. 1, S. 1-24

---

86

Anhang: Petrinetz-Definitionen

Definition A-1: Allgemeine Netzdefinitionen

In einem Netz

N

= (

S

,

T

,

F

) sei

X

=

S

T

die Vereinigung aller Stellen und

Transitionen.

(i) Für

x

X

heißt

x

= {

y

X

| (

y

,

x

)

F

} der Vorbereich und

x

= {

y

X

| (

x

,

y

)

F

} der Nachbereich von

x

.

F

(

x

) = {(

a

,

b

)

F

|

a

=

x b

=

x

} bezeichnet die Menge aller ein-

und ausgehenden Pfeile von

x

.

(ii)

Ein Paar (

s

,

t

) (

S T

) heißt Schlinge, falls (

s t

) (

t s

).

N

heißt

rein, falls

F

keine Schlingen enthält.

(iii)

x

X

heißt isoliert, falls

x

x

=

(iv)

N

heißt schlicht, falls verschiedene Elemente nicht denselben Vor-

und Nachbereich besitzen, falls also gilt:

(

x

,

y

N

x

=

y x

=

y

)

x

=

y

.

Definition A-2: Bedingungs/Ereignis-Netz (B/E-Netz)

In B/E-Netzen stellen die

S

-Elemente Bedingungen, die

T

-Elemente Ereignisse

dar. Bedingungen sind elementare logische Aussagen und können entweder

wahr oder falsch sein. Ein Ereignis kann stattfinden, wenn alle seine Eingangs-

Bedingungen markiert (wahr) und alle seine Ausgangs-Bedingungen nicht

markiert (unwahr) sind.

Ein B/E-Netz ist ein Tupel

BEN

= (

S

,

T

,

F

,

M0

), für welches gilt:

(i) (

S

,

T

,

F

) ist ein Netz.

(ii)

M

:

S

{0, 1} weist den Stellen im Netz eine Markierung zu.

M0

ist

die Startmarkierung.

Ist ein

S

-Element

s

markiert, d.h. ist

M

(

s

) = 1, dann ist die betreffende Bedin-

gung wahr. Ereignisse ändern den Wahrheitswert von Bedingungen. Sind alle

---

87

S

-Elemente im Vorbereich einer Transition

t

markiert und sind alle Stellen im

Nachbereich von

t

nicht markiert, dann ist

t

aktiviert, d.h.

t

kann schalten und

eine Folgemarkierung erzeugen. Beim Schalten von

t

werden aus den

S

-

Elementen im Vorbereich von

t

die Marken entnommen, und es wird in alle

Stellen im Nachbereich von

t

jeweils eine Marke abgelegt.

Definition A-3: Schaltregel für B/E-Netze

Gegeben sei ein B/E-Netz

BEN

= (

S

,

T

,

F

,

M

).

Ein Ereignis

t

T

heißt aktiviert unter

M

, falls gilt:

(i)

s

t

:

M

(

s

) = 1,

(ii)

s

t

:

M

(

s

) = 0.

Wenn ein Ereignis

t

unter

M

aktiviert ist, dann kann

t

schalten. Das

Schalten von

t

unter

M

überführt

M

in die Folgemarkierung

M

′ wobei

gilt:

M

(

s

) ­ 1

falls

s

t

M

′(

s

) =

M

(

s

) + 1

falls

s

t

M

(

s

)

sonst

Definition A-4: Stellen/Transitionen-Netz (S/T-Netz)

Ein Stellen/Transitionen-Netz (S/T-Netz) ist ein 6-Tupel

ST

= (

S

,

T

,

F

,

K

,

W

,

M

0), für welches gilt:

(i) (

S

,

T

,

F

) ist ein Netz,

(ii)

K

:

S

IN { } weist jeder Stelle eine Aufnahmekapazität der

Marken zu, die nicht überschritten werden darf,

(iii)

W

:

F

IN weist jeder Kante im Netz eine Gewichtung zu,

(iv)

M

:

S

IN0, wobei

s

S

:

M

(

s

)

K

(

s

), weist jeder Stelle eine be-

stimmte Anzahl von Marken zu.

M0

ist die sogenannte Startmar-

kierung.

---

88

Definition A-5: Schaltregel für S/T-Netze

Gegeben sei ein S/T-Netz

ST

= (

S

,

T

,

F

,

K

,

W

,

M0

).

Eine Transition

t

T

heißt aktiviert unter einer Markierung

M

, falls

gilt:

(i)

s

t

:

M

(

s

)

W

(

s

,

t

),

(ii)

s

t

:

M

(

s

)

K

(

s

) ­

W

(

t

,

s

).

Wenn eine Transition

t

unter

M

aktiviert ist, dann kann

t

schalten. Das

Schalten von

t

unter

M

überführt

M

in die Folgemarkierung

M

′ wobei

gilt:

M

(

s

) ­

W

(

s

,

t

) falls

s

t

und

s

t

M

′(

s

) =

M

(

s

) +

W

(

t

,

s

) falls

s

t

und

s

t

M

(

s

) ­

W

(

s

,

t

) +

W

(

t

,

s

) falls

s

t

und

s

t

M

(

s

) sonst

Definition A-6:Prädikate/Transitionen-Netz (Pr/T-Netz)

Ein (striktes) Pr/T-Netz ist ein Tupel

PT

= (

S

,

T

,

F

, ,

KB

,

TI

,

M0

), für welches

gilt:

(i) (

S

,

T

,

F

) ist ein Netz, wobei

S

als Menge von Prädikaten mit

veränderlichen Ausprägungen (Relationen) und

T

als Menge von

Transitionsschemata interpretiert wird.

(ii)

= (

D

,

FU

,

PR

) ist eine Struktur, bestehend aus endlichen Indivi-

duenmengen

D

sowie einer Menge

FU

von auf

D

definierten Funk-

tionen und einer Menge

PR

von auf

D

definierten Prädikaten mit

unveränderlichen Ausprägungen.

(iii)

KB

beschriftet Kanten aus

F

mit Mengen von Variablentupeln, de-

ren Stelligkeit der Stelligkeit des adjazenten Prädikats entspricht.

(iv)

TI

weist einigen Transitionen einen aus Operationen und Prädikaten

in gebildeten prädikatenlogischen Ausdruck als Inschrift zu. Jede

---

89

freie Variable in diesem Ausdruck muss in der Beschriftung einer

zur jeweiligen Transition adjazenten Kante vorkommen.

(v)

M0

ist eine Markierung der Prädikate mit Mengen von konstanten

Individuentupeln (Relationen, deren Stelligkeit der Stelligkeit des

Prädikats entspricht.

Die Prädikatenlogischen Ausdrücke zu einer Struktur = (

D

,

FU

,

PR

) ergeben

sich wie folgt:

Definition A-7: Pr-Term

Sei

X

eine Menge von Variablen.

T

, die Menge der

PR-Terme

, ist die kleinste

Menge, für die gilt:

(i) Jede

Variable

X

i

X

ist ein Pr-Term.

(ii) Falls

f

eine

n

-stellige Funktion in

FU

und

X

1, ...,

X

n

X

, dann ist

f

(

X

1, ...,

X

n) ein Pr-Term.

Definition A-8: Prädikatenlogischer Ausdruck

Die Menge

P

der prädikatenlogischen Ausdrücke zu einer Struktur = (

D

,

FU

,

PR

) ist die kleinste Menge, für die gilt:

(i)

TRUE ist ein prädikatenlogischer Ausdruck.

(ii) Sei

P

ein

n

-stelliges Prädikat in

PR

und seien

t

1,...,

t

n Pr-Terme.

Dann ist

P

(

t

1,...,

t

n) ein prädikatenlogischer Ausdruck.

(iii) Falls

p

1,

p

2 prädikatenlogische Ausdrücke sind, dann sind auch

p

1

p

2,

p

1

p

2,

p

1

p

2 sowie

p

1 prädikatenlogische Ausdrücke.

Definition A-9: Pr-(Variablen-)Belegung

Sei

D

eine Menge von Konstanten,

X

eine zu

D

diskunkte Menge von Variab-

len und

T

eine Menge von Pr-Termen.

---

90

(i) Eine

Abbildung

:

X

D

heißt Pr-Belegung von

X

.

(ii)

kann erweitert werden zu :

T

D

durch (

f

(

t1

,...,

tn

)) :=

f

( (

t1

),..., (

tn

)).

Statt < (

t1

), (

t2

),..., (

tn

)> wird auch verkürzend (

t1

,

t2

,...,

tn

) geschrieben.

Definition A-10: Pr-Wahrheitswert

Die Struktur = <

D

,

FU

,

PR

> induziert für jeden prädikatenlogischen Aus-

druck

a

P

und jede Pr-Belegung einen Wahrheitswert durch die Funktion

′ :

P

{0,1}.

1

a

= TRUE

1

a

=

P

(

t

) und (

t

)

P

0

a

=

P

(

t

) und (

t

)

P

′ (

a

) =

min( ′ (

a1

), ′ (

a2

))

a

=

a1 a2

max( ′ (

a1

), ′ (

a2

))

a

=

a1 a2

′ (

a1 a2

)

a

=

a1

a2

1 ­ ′ (

a1

)

a

=

a1

Definition A-11: Schaltregel für Pr/T-Netze

Sei

PT

= (

S

,

T

,

F

, ,

KB

,

TI

,

M0

) ein (striktes) Prädikate/Transitionen-Netz.

Jedes Element aus

T

repräsentiert eine Klasse von elementaren Transitionen,

die beim Schalten jeweils Marken aus den Eingangs-Stellen entnehmen und

Marken in die Ausgangs-Stellen ablegen.

Eine Transition

t

T

ist unter einer Markierung

M

für eine Pr-Bele-

gung der Variablen in den Beschriftungen der adjazenten Kanten ak-

tiviert, wenn gilt:

(i)

′ (

TI

(

t

)) = 1 und

(ii)

s

t

(

kb

KB

(

s

,

t

) ( (

kb

)

M

(

s

))) und

(iii)

s

t

(

kb

KB

(

t

,

s

) ( (

kb

)

M

(

s

))).

---

91

Wenn eine Transition

t

unter

M

für eine Pr-Belegung aktiviert ist,

dann kann

t

schalten. Das Schalten von

t

unter

M

überführt

M

in die

Folgemarkierung

M

wobei gilt:

M

(

s

) \ (

KB

(

s

,

t

))

falls

s

t

und

s

t

M

(

s

)

(

KB

(

t

,

s

))

falls

s

t

und

s

t

M

′(

s

) =

(

M

(

s

) \ (

KB

(

s

,

t

))

(

KB

(

t

,

s

))

falls

s

t

und

s

t

M

(

s

)

sonst

Wenn eine Transition

t

mit einer Pr-Belegung schaltet, werden in einem

Schritt aus allen Stellen

s

t

für jeden Pr-Term

kb

KB

(

s

,

t

) Konstantentupel

(

kb

) entfernt und in alle Stellen

s

t

für jeden Pr-Term

kb

KB

(

t

,

s

) Kon-

stantentupel (

kb

) hinzugefügt.

---

92

Anhang: Fallstudie

Grundlage für die Fallstudie bildet der Artikel ,,Airline cockpit crew sche-

duling" von YAN/CHANG132. In diesem Artikel wird ein Modell für das Sche-

duling von Cockpit-Crews einer taiwanesischen Fluggesellschaft beschrieben.

Nach diesem Artikel besteht eine Cockpit-Crew üblicherweise aus einem Pi-

loten, einem Copiloten und evtl. einem Flugingenieur (,,Navigator"). Für das

Scheduling werden Daten über Flugpläne, Flugrouten und verschiedene ge-

werkschaftliche, gesetzliche und betriebsinterne Regelungen benötigt.

YAN/CHANG nehmen an, dass Flugplan, Flugrouten, relevante Regelungen und

Kosten für die Crew-Mitglieder bekannt sind. Daher bietet es sich an, beispiel-

haft ein (stark vereinfachtes) BIS zu modellieren, das entsprechende Prozess-

und Datenstrukturen repräsentiert.

Das Ziel der Fallstudie ist jedoch nicht, eine Grundlage für die Anwendung

des von YAN/CHANG beschriebenen Algorithmus zu bieten. Vielmehr soll an-

hand eines praxisrelevanten Beispiels die Mächtigkeit der in dieser Arbeit be-

schriebenen Modellierungssprache ansatzweise demonstriert werden.

Dem Artikel ist zu entnehmen, dass Mitglieder der Cockpit-Crew nur Flug-

zeug-Typen fliegen dürfen, für die sie eine entsprechende Lizenz besitzen. Die

Anzahl der Cockpit-Crew-Mitglieder ist abhängig vom Flugzeug-Typ. Die

Fluggesellschaft verwendet zwei Cockpit-Crew-Konfigurationen. Eine wird als

,,Standard-Crew" bezeichnet, die andere als ,,erweiterte Crew"133. In der

Fallstudie wird zur Vereinfachung angenommen, dass nur ,,Standard-Crews"

verwendet werden. Weiter wird angenommen, dass Flüge immer auf dem Start-

flughafen, d.h. dem Heimatflughafen, enden.

Die Regelungen der Fluggesellschaft beschränken u.a. die Flugzeit, die Ar-

beitszeit und die verbleibende Zeit eines 24-Stunden-Zeitfensters. Die Arbeits-

zeit errechnet sich aus der Flugzeit zzgl. 2:20h Briefing und 1:00h Debriefing

nach dem letzten Flug. Dabei darf die Flugzeit nicht mehr als 10 Stunden

betragen, die Restzeit muss mindestens 10 Stunden betragen.

132 Vgl. Yan/Chang (2002), S. 501-504.

133 Eine erweiterte Crew besteht aus mehreren Piloten, Copiloten und evtl. Navigatoren und

wird für Langstreckenflüge benötigt.

---

93

Prozessstruktur-Modell

Im ersten Schritt wird ein semiformales Modell der Prozessstruktur als K/I-

Netz modelliert (vgl. Abbildung A-1). Dafür wurde ein stark vereinfachtes

Beispiel von JAESCHKE134 erweitert (vgl. Kapitel 2.2.2.1, S. 12). Nach dem

,,Abarbeiten" eines zu erstellenden Flugplans werden die während der Abar-

beitung belegten Flugzeuge und die zugehörige Cockpit-Crew wieder verfüg-

bar. Damit wird angenommen, dass nach erfolgter Abarbeitung der Flug erneut

durchgeführt werden muss, z.B. in einem wöchentlichen Zyklus. Das Netz

ließe sich aber auch verfeinern derart, dass abgearbeitete Flüge z.B. von einem

Sachbearbeiter entweder gelöscht oder mit einem neuen Flugtermin bestätigt

werden.

Abbildung A-1: Prozessstruktur als K/I-Netz

Datenstruktur-Modell

Nach der Modellierung eines natürlich sprachlich beschrifteten K/I-Netzes

wird die Datenstruktur als E-R-Modell semiformal modelliert. In diesem

Schritt werden noch keine Attribute verwendet, um die Komplexität des Mo-

dells zu reduzieren. Das Flugpersonal135 arbeitet an bestimmten Arbeitstagen

und ist für bestimmte Aufgaben qualifiziert. Diese Aufgaben werden von be-

134 Vgl. Jaeschke (1996), S. 183. Das von JAESCHKE verwendete Beispiel ist mitunter inkon-

sistent, vgl. Jaeschke (1996), S. 183, Abbildung 5.2; und Jaeschke (1996), S. 186, Abbil-

dung 5.7. Dort werden zwei voneinander verschiedene Datenstrukturen für dieselbe Stelle

,,Crewanforderung" verwendet.

135 In diesem Fall wird nur die Cockpit-Crew betrachtet.

---

94

stimmten Flugzeug-Typen benötigt, um mit den entsprechenden Flugzeugen

Flüge durchführen zu können. Ein Flug besteht aus Flugabschnitten, die jeweils

an einem Flughafen beginnen und enden.

Abbildung A-2: Datenstruktur als E-R-Modell

Konstruktion der komplexen Datenobjekte

Für jede Stelle des K/I-Netzes ist nun ein komplexes Datenobjekt zu modellie-

ren. Dabei wird wie in Kapitel 3.2.2.3 beschrieben vorgegangen. Zu modellie-

ren sind die komplexen Datenobjekte ,,Verfügbares-Flugpersonal", ,,Flug-

durchführung", ,,Verfügbare-Flugzeuge", ,,Crewanforderung" und ,,Flugplan".

Komplexes Datenobjekt ,,Verfügbares-Flugpersonal"

Es werden Daten über das Flugpersonal, dessen Arbeitstage und Aufgaben

benötigt, was mit dem in Abbildung A-3 dargestellten Ausschnitt aus dem glo-

balen E-R-Modell semiformal dargestellt wird. In diesem Schritt werden dieje-

nigen Attribute dem Modell hinzugefügt, die hinsichtlich der Entity- und Be-

ziehungs-Typen für das komplexe Datenobjekt benötigt werden.

---

95

Abbildung A-3: E-R-Modell "Verfügbares-Flugpersonal"

Gemäß Kapitel 3.2.2.3 ergibt sich daraus die folgende Definitionsgleichung:

Verfügbares-Flugpersonal := {(Ma#, Name, Gehalt, Arbeitstag

:= {(Tag-Nr, Restzeit, Flugzeit)}, Aufgabe :=

{(Bezeichnung, Flugzeug-Typ := {(Typname)})})}

Diese Definitionsgleichung ist der entsprechenden Stelle des Netzes zuzuord-

nen.

Komplexes Datenobjekt ,,Flugdurchführung"

Es werden Daten über die Flüge mit den entsprechenden Flugabschnitten und

den zugehörigen Flughäfen benötigt, was mit dem in Abbildung A-4 darge-

stellten Ausschnitt aus dem globalen E-R-Modell semiformal, und mit der zu-

gehörigen Definitionsgleichung formal beschrieben wird.

Abbildung A-4: E-R-Modell "Flugdurchführung"

---

96

Flugdurchführung := {(Flug-Nr, Plätze, Flugabschnitt :=

{(Abschnitt-Nr, von := {(Startzeit, FH-Name)}, nach :=

{(Landezeit, FH-Name)})})}

In diesem Fall werden die Relationen ,,von" und ,,nach" als mengenwertige

Attribute verwendet, da so eindeutig beschrieben werden kann, von welchem

Flughafen gestartet bzw. gelandet wird. Dies hängt damit zusammen, dass

,,Flugabschnitt" und ,,Flughafen" sowohl hinsichtlich der Relation ,,von" als

auch hinsichtlich der Relation ,,nach" in Beziehung stehen.

Komplexes Datenobjekt ,,Verfügbare Flugzeuge"

Es werden Daten über Flugzeuge und die dafür erforderliche Cockpit-Crew

benötigt. Die Verfügbarkeit der Flugzeuge ergibt sich aus der Prozessstruktur:

Ein Flugzeug ist dann verfügbar, wenn es ,,in" der Stelle ,,Verfügbare-Flug-

zeuge" eingetragen ist. Hier wurde die 1:

n

-Kardinalität von Flugpersonal

Aufgabe in eine 1:1-Kardinalität geändert, da in bezug auf ein Flugzeug

ein

Mitglied der Cockpit-Crew nur

eine

Aufgabe erfüllen kann.

Abbildung A-5: E-R-Modell "Verfügbare-Flugzeuge"

Verfügbare-Flugzeuge := {(Flugzeug-Nr, Sitze, Typname,

Aufgabe := {(Bezeichnung, Ma#, Name)})}

Komplexes Datenobjekt ,,Crewanforderung"

Für die Crewanforderung werden nahezu alle in dem globalen E-R-Modell

dargestellten Daten benötigt. Auf das Entity ,,Arbeitstag" und auf das Attribut

,,Gehalt" des Entities vom Typ ,,Mitarbeiter" kann verzichtet werden, da diese

---

97

Daten hinsichtlich einer Crew-Anforderung (in diesem Modell) irrelevant sind.

Die 1:

n

-Kardinalität der Relation ,,qualifiziert für" kann hier in eine 1:1-Kardi-

nalität transformiert werden, da für ein Flugzeug jede Aufgabe nur einmal zu

erfüllen ist. Als Kern-Entity wird ,,Flug" gewählt, da es das komplexe Daten-

objekt eindeutig identifiziert. Alternativ könnte ,,Flugzeug" gewählt werden,

was aber semantisch nicht ganz korrekt wäre.

Abbildung A-6: E-R-Modell "Crewanforderung"

Crewanforderung := {(Flug-Nr, Plätze, Flugzeug-Nr, Sitze,

Typname, Aufgabe := {(Bezeichnung, Ma#, Name)},

Flugabschnitt := {(Abschnitt-Nr, von := {(Startzeit, FH-

Name)}, nach := {(Landezeit, FH-Name)})})}

Komplexes Datenobjekt ,,Flugplan"

Das komplexe Datenobjekt ,,Flugplan" entspricht überwiegend der ,,Crewan-

forderung". Jedoch wird das Attribut ,,Plätze" des Entity-Typs ,,Flug" wegge-

lassen, da die Anzahl der verfügbaren ,,Plätze" hier durch die im Flugzeug ver-

fügbaren Sitze determiniert ist.

---

98

Abbildung A-7: E-R-Modell Flugplan

Flugplan := {(Flug-Nr, Flugzeug-Nr, Sitze, Typname, Aufgabe

:= {(Bezeichnung, Ma#, Name)}, Flugabschnitt :=

{(Abschnitt-Nr, von := {(Startzeit, FH-Name)}, nach :=

{(Landezeit, FH-Name)})})}

Redundante Bezeichnungen eliminieren

Da für jede Stelle des Netzes aus dem globalen E-R-Modell eine

lokale

Sicht

abgeleitet wurde, ist der Defekt zu beobachten, dass einige Bezeichnungen der

verschiedenen Attribute in den lokalen komplexen Datenobjekten redundant

sind. In dieser Fallstudie ist konkret das Attribut ,,Aufgabe" von diesem Defekt

betroffen. Diese widersprüchlichen Bezeichnungen werden durch andere Be-

zeichnungen substituiert136. Hier könnte eine entsprechende Modellierungssoft-

ware unterstützend eingreifen, indem sie diese Widersprüche bereits bei der

Modellierung erkennt und zur Umbenennung der Attribute und/oder der Da-

136 Hinsichtlich einer Implementierung in eine auf genesteten Relationen basierende Daten-

bank wäre dieses Vorgehen noch einmal zu überprüfen, da diese Redundanzen evtl. er-

wünscht sein könnten. Aus dieser Sicht könnte aber auch zwischen interner Bezeichnung

der Datenbank und einer semantisch reichhaltigeren Bezeichnung unterschieden werden.

Dagegen wird dieses Vorgehen in der Fallstudie bevorzugt, um eine größere semantische

Reichhaltigkeit zu erreichen.

---

99

tenobjekte auffordert. Die ursprünglichen Objekte mit der Bezeichnung ,,Auf-

gabe" wurden im folgenden

fett

markiert und, falls erforderlich, bereits um-

benannt.

Verfügbares-Flugpersonal := {(Ma#, Name, Gehalt, Arbeitstag

:= {(Tag-Nr, Restzeit, Flugzeit)},

Qualifikation :=
{(Bezeichnung, Flugzeug-Typ := {(Typname)})}

)}

Verfügbare-Flugzeuge := {(Flugzeug-Nr, Sitze, Typname,

Aufgabe := {(Bezeichnung, Ma#, Name)}

)}

Crewanforderung := {(Flug-Nr, Plätze, Flugzeug-Nr, Sitze,

Typname,

Crewmitglied := {(Bezeichnung, Ma#, Name)}

,

Flugabschnitt := {(Abschnitt-Nr, von := {(Startzeit, FH-

Name)}, nach := {(Landezeit, FH-Name)})})}

Flugplan := {(Flug-Nr, Flugzeug-Nr, Sitze, Typname,

Crewmitglied := {(Bezeichnung, Ma#, Name)}

, Flugabschnitt

:= {(Abschnitt-Nr, von := {(Startzeit, FH-Name)}, nach :=

{(Landezeit, FH-Name)})})}

Formalisierung des K/I-Netzes

Nach der Modellierung der komplexen Datenobjekte ist das K/I-Netz weiter zu

formalisieren. Dafür können die Kanten des K/I-Netzes zuvor mit Filtertabellen

und die Transitionen mit Schaltregeln beschriftet werden. Es ist jedoch darauf

zu achten, dass die Struktur der Filtertabellen im Nachbereich der Struktur der

vorgelagerten Datenobjekte der Stellen entspricht. Auch muss die Struktur der

Filtertabellen im Vorbereich der Struktur der nachgelagerten Datenobjekte der

Stellen entsprechen. Weiter ist darauf zu achten, dass einer Stelle nicht das-

selbe Tupel zugleich entnommen und zugefügt wird (um z.B. das Lesen von

Daten zu ,,simulieren"), da sonst die Transition nicht schalten kann (vgl. Kapi-

tel 4.2.3). Die weitere Formalisierung beschränkt sich auf die Kanten und

Transitionen, da den Stellen lediglich die bereits formalisierten komplexen

Datenobjekte zuzuordnen sind.

Im folgenden wird beispielhaft der in Abbildung A-8 dargestellte Ausschnitt

aus Abbildung A-1 erläutert und formalisiert. Die Kanten wurden bereits mit

---

100

entsprechenden Filtertabellen beschriftet. Abschließend wird eine Startmarkie-

rung

M0

für dieses Netzelement modelliert und die Schaltwirkung anhand der

Filtertabellen sowie einer möglichen Folgemarkierung

M1

veranschaulicht.

Abbildung A-8: NR/T-Netzelement

Die in Abbildung dargestellten Filtertabellen lassen sich folgendermaßen ent-

sprechend der Definition

AI

( ,

O

) formal beschreiben:

AI(Flugdurchführung, Flugzeug-Zuweisung) :=

(({(Flug-Nr: Fn, Plätze: Pl, Flugabschnitt: Fa)}),

(=Flug-Nr, =Plätze, =Flugabschnitt))

AI(Verfügbare-Flugzeuge, Flugzeug-Zuweisung) :=

(({(Flugzeug-Nr: Fl, Sitze: Si, Typname: Ty, Aufgabe:

Au)}),

(=Flugzeug-Nr, =Sitze, =Aufgabe))

AI(Flugzeug-Zuweisung, Crew-Anforderung) :=

(({(Flug-Nr: Fn, Plätze: Pl, Flugzeug-Nr: Fl, Sitze: Si,

Typname: Ty, Crewmitglied: Cr, Flugabschnitt: Fa)}),

(=Flug-Nr, =Plätze, =Flugzeug-Nr, =Sitze, =Typname, =Plätze, =Crewmitglied,

=Flugabschnitt))

Die Schaltregel für die Transition ,,Flugzeugzuweisung" lautet:

TI(Flugzeugzuweisung) = (Pl Si),

d.h. die Anzahl der in einem Flugzeug verfügbaren Sitzplätze muss größer oder

gleich der für den Flug erforderlichen Plätze sein.

---

101

Startmarkierung M0

Die Startmarkierung

M0

stellt Instanzen der den Stellen zugeordneten komple-

xen Datenobjekte dar. Für den Ausschnitt aus dem Modell der Prozessstruktur

in Abbildung A-8 sind das im Einzelnen die Datenobjekte ,,Flugdurchführung",

,,Verfügbare-Flugzeuge" und ,,Crewanforderung"137.

Die Instanz des Datenobjekts ,,Flugdurchführung" beschreibt drei durchzu-

führende Flüge. Der Flug 566 besteht dabei aus zwei Flugabschnitten (Düssel-

dorf

München, München Fuerteventura).

Flugdurchführung

Flug-Nr Plätze Flugabschnitt

Abschnitt-Nr von nach

Startzeit FH-Name

Landezeit

FH-Name

344 150

1

17.12.2002-09:15 Düsseldorf 17.12.2002-10:45

Rom

455 150

1

17.12.2002-18:00 Rom 17.12.2002-19:50

Düsseldorf

1 18.12.2002-12:00

566 300

Düsseldorf 18.12.2002-13:00

München

2 18.12.2002-13:45 München

18.12.2002-17:15

Fuerteventura

Tabelle A-1: Startmarkierung für "Flugdurchführung"

Die Instanz des Datenobjekts ,,Verfügbare-Flugzeuge" beschreibt drei Flug-

zeuge, einen Airbus-320, einen Airbus-330 und eine Fokker-50. Den zu erfül-

lenden Aufgaben sind noch keine Cockpit-Crew-Mitglieder zugeordnet.

Verfügbare-Flugzeuge

Flugzeug-Nr Sitze Typname Aufgabe

Bezeichnung Ma#

Name

12 155

Airbus-320 Pilot

Copilot

24 320

Airbus-330 Pilot

Copilot

48 50

Pilot

Fokker-50

Copilot

Tabelle A-2: Startmarkierung für "Verfügbare-Flugzeuge"

Die Instanz des Datenobjekts ,,Crewanforderung" beinhaltet noch keine Tupel,

d.h. es existieren noch keine Crewanforderungen.

137 Die Tabelle ,,Crewanforderung" wurde aus Platzgründen in zwei Teile aufgeteilt.

---

102

Crewanforderung (Teil 1)

Flug-

Plätze Flugzeug- Sitze Typname Crewmitglied

Nr

Nr

Bezeichnung Ma# Name

Crewanforderung (Fortsetzung)

Flugabschnitt

Abschnitt- von nach

Nr

Startzeit FH-Name Landezeit FH-Name

Tabelle A-3: Startmarkierung für "Crewanforderung"

Folgemarkierung M1

Die Folgemarkierung

M1

ergibt sich aus dem einmaligen Schalten der Transi-

tion ,,Flugzeug-Zuweisung". Die Schaltbedingung (Pl Si) ist für mehrere

Tupel-Kombinationen ,,TRUE". Daher ist die Folgemarkierung nicht determi-

niert. Die hier dargestellte Folgemarkierung ist eine

mögliche

Kombination.

Die Transition könnte dann noch einmal für die Kombination Flug

344/Flugzeug 12 oder alternativ für die Kombination Flug 455/Flugzeug 12

schalten.

Der Instanz von ,,Flugdurchführung" wurde das Tupel von Flug 566 ,,ent-

nommen", d.h. gelöscht.

Flugdurchführung

Flugabschnitt

Flug-Nr Plätze

Abschnitt-Nr von nach

Startzeit FH-Name

Landezeit

FH-Name

344 150

344-1

17.12.2002-09:15 Düsseldorf 17.12.2002-10:45

Rom

455 150

455-1

17.12.2002-18:00 Rom 17.12.2002-19:50

Düsseldorf

Tabelle A-4: Folgemarkierung für "Flugdurchführung"

Der Instanz von ,,Verfügbare-Flugzeuge" wurde das Tupel von Flugzeug 24

entnommen.

Verfügbare-Flugzeuge

Flugzeug-Nr Sitze Typname Aufgabe

Bezeichnung Ma#

Name

12 155

Airbus-320 Pilot

Copilot

48 50

Pilot

Fokker-50

Copilot

Tabelle A-5: Folgemarkierung für "Verfügbare-Flugzeuge"

Der Instanz von ,,Crewanforderung" wurden die Werte entsprechend ihrer Da-

tenstruktur hinzugefügt.

---

103

Crewanforderung (Teil 1)

Flug-

Plätze Flugzeug- Sitze Typname Crewmitglied

Nr

Nr

Bezeichnung Ma# Name

566 300 24

320

Pilot

Airbus-320

Copilot

Crewanforderung (Fortsetzung)

Flugabschnitt

Abschnitt- von nach

Nr

Startzeit FH-Name

Landezeit

FH-Name

566-1 18.12.2002-12:00

Düsseldorf 18.12.2002- München

13:00

566-2 18.12.2002-13:45

München

18.12.2002- Fuerteventura

17:15

Tabelle A-6: Folgemarkierung für "Crewanforderung"

Beispiel für die Objektordnung

Im vorangegangenen Beispiel für das Schalten einer Transition wurden in be-

zug auf zusammengesetzte Attribute nur geschlossene Terme (d.h. die Inklu-

sionsordnung) verwendet. Daher wurden die entsprechenden Tupel vollständig

entnommen. Abschließend wird noch ein Beispiel für das Hinzufügen eines

Sub-Tupels durch die Verwendung offener Terme gegeben. Dafür soll der Fol-

gemarkierung

M1

für ,,Crewanforderung" das Cockpit-Crew-Mitglied ,,Smith"

als Pilot zugeordnet werden. Das geschieht mit folgender Filtertabelle138:

Abbildung A-9: Filtertabelle mit offenen Termen

Da in dieser Filtertabelle offene Terme verwendet werden, wird das mit ihr

beschriebene Tupel nicht an die Instanz ,,angehangen", sondern mit dem be-

reits bestehenden Flug 566 verschmolzen. Das Ergebnis ist, dass der Mitarbei-

ter Smith mit Mitarbeiter-Nr. 1024 als Pilot für diesen Flug eingetragen wurde.

138 In dieser Filtertabelle werden keine Variablen dargestellt. Man könnte diese Filtertabelle

alternativ auch als Instanziierung entsprechender Variablen auffassen.

---

104

Crewanforderung (Teil 1)

Flug-

Plätze Flugzeug- Sitze Typname Crewmitglied

Nr

Nr

Bezeichnung Ma# Name

566 300 24

320

Pilot 1024

Airbus-320

Smith

Copilot

Crewanforderung (Fortsetzung)

Flugabschnitt

Abschnitt- von nach

Nr

Startzeit FH-Name

Landezeit

FH-Name

566-1 18.12.2002-12:00

Düsseldorf 18.12.2002- München

13:00

566-2 18.12.2002-13:45

München

18.12.2002- Fuerteventura

17:15

Tabelle A-7: Hinzufügen von Sub-Tupeln

---

105

Eidesstattliche Versicherung

Ich versichere an Eides statt durch meine Unterschrift, dass ich die vorstehende

Arbeit selbständig und ohne fremde Hilfe angefertigt und alle Stellen, die ich

wörtlich oder annähernd wörtlich aus Veröffentlichungen entnommen habe, als

solche kenntlich gemacht habe, mich auch keiner anderen als der angegebenen

Literatur oder sonstiger Hilfsmittel bedient habe. Die Arbeit hat in dieser oder

ähnlicher Form noch keiner anderen Prüfungsbehörde vorgelegen.

Dortmund, 21. November 2002

_____________________

Urs Lässer

---