Master-Arbeit - is.informatik.uni-kiel.dehjk/masterarbeit_Ralfs.pdf · Selbstst andigkeitserkl arung Ich erkl are hiermit, daˇ ich die vorliegende Arbeit selbstst andig und nur unter

Master-Arbeit

Konzeptbasierte Generierung von Anfrageoberflachenfur wissenschaftliche Datenbanken

Christian-Albrechts-Universitat zu KielInstitut fur Informatik

Arbeitsgruppe Technologie der Informationssysteme

angefertigt von: Florian Ralfsbetreuender Hochschullehrer: Prof. Dr. Hans-Joachim KleinBetreuer: Prof. Dr. Hans-Joachim Klein

Kiel, 15.05.2014

Aufgabe

Name, Vorname: Florian RalfsImmatrikulations-Nr: 931331Studiengang: Informatik

betreuender Hochschullehrer: Prof. Dr. Hans-Joachim KleinBetreuer: Prof. Dr. Hans-Joachim KleinInstitut: Institut fur InformatikArbeitsgruppe: Technologie der Informationssysteme

Beginn am: 18.11.2013Einzureichen bis: 18.05.2014

Aufgabenstellung:

Entwurf einer konzeptbasierten Anfragesprache fur relationale Datenbanken. Fernerdie Implementierung einer auf dieser Sprache basierenden Software und die Instal-lation dieses Systems in einer bestehenden Infrastruktur.

i

Selbststandigkeitserklarung

Ich erklare hiermit, daß ich die vorliegende Arbeit selbststandig und nur unter Ver-wendung der angegebenen Literatur und Hilfsmittel angefertigt habe.

...............................................................Florian Ralfs

iii

Inhaltsverzeichnis

1. Einfuhrung 1

2. Aufgabenstellung 3

3. Verwendete Beispiele 53.1. CrystalDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.2. OpenVigil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63.3. Beispiel Fahrzeugbau . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.4. Das Bankbeispiel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 93.5. Das modifizierte Bankbeispiel . . . . . . . . . . . . . . . . . . . . . . 9

4. Losungsentwurf 134.1. Voraussetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 164.2. Konzept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

4.2.1. Definition Konzept . . . . . . . . . . . . . . . . . . . . . . . . 204.2.2. Auswertung von Konzepten . . . . . . . . . . . . . . . . . . . 214.2.3. Aquivalenz von Konzepten . . . . . . . . . . . . . . . . . . . 22

4.3. Operationen auf Konzepten . . . . . . . . . . . . . . . . . . . . . . . 224.3.1. Erzeugung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.3.2. Projektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 224.3.3. Selektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3.4. Schnitt . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 234.3.5. Vereinigung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.3.6. Differenz . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.3.7. Join . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 244.3.8. Projizierende Vereinigung . . . . . . . . . . . . . . . . . . . . 25

4.4. Anfrageformulierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 264.4.1. Der print-Befehl . . . . . . . . . . . . . . . . . . . . . . . . . 274.4.2. Selektion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274.4.3. Anfragesemantiken bei mehrzeiligen Anfragen . . . . . . . . . 284.4.4. Aggregation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

4.5. Ubersetzung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344.5.1. Relationale Algebra . . . . . . . . . . . . . . . . . . . . . . . 344.5.2. SQL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37

4.6. Ausdruckskraft . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.7. Weiterfuhrende Betrachtung . . . . . . . . . . . . . . . . . . . . . . . 51

4.7.1. Zur Notwendigkeit eindeutiger Attributbezeichner . . . . . . 51

v

4.7.2. Verbandseigenschaft von Konzepten . . . . . . . . . . . . . . 53

5. Vergleichbare Arbeiten 57

6. Implementierung 596.1. Grundlegende Architektur . . . . . . . . . . . . . . . . . . . . . . . . 596.2. Uberblick uber die Schichten der Serversoftware . . . . . . . . . . . . 606.3. Einstellungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 616.4. Initialer Konzeptimport . . . . . . . . . . . . . . . . . . . . . . . . . 616.5. Konzeptgenerierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 636.6. Anfrageformulierung . . . . . . . . . . . . . . . . . . . . . . . . . . . 686.7. Anfrageauswertung . . . . . . . . . . . . . . . . . . . . . . . . . . . . 726.8. Verwaltung des Systems . . . . . . . . . . . . . . . . . . . . . . . . . 756.9. Ubersetzung der Software . . . . . . . . . . . . . . . . . . . . . . . . 75

7. Fazit und Ausblick 777.1. Ein graphischer Konzepteditor . . . . . . . . . . . . . . . . . . . . . 777.2. Ergebnisausgabe in einem Austauschformat . . . . . . . . . . . . . . 777.3. Erweiterung der Anfrageschnittstelle um inhaltsspezifische Kompo-

nenten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 787.4. Graphische Anfragekomponente . . . . . . . . . . . . . . . . . . . . . 78

A. ER-Schema 81

B. Relationale Ubersetzung des verwendeten Schemas 83

C. Relationales Schema zu 3.1 85

D. Relationales Schema zu 3.2 87

E. Relationales Schema zu 3.3 89

F. Relationales Schema zu 3.4 91

G. Relationales Schema zu 3.5 93

vi

Abbildungsverzeichnis

3.1. ERM CrystalDB . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53.2. ERM OpenVigil . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73.3. ERM Fahrzeugbau . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83.4. ERM zum Bankbeispiel . . . . . . . . . . . . . . . . . . . . . . . . . 103.5. ERM zum modifizierten Bankbeispiel nach [FMU82] . . . . . . . . . 11

4.1. OpenVigil - Professional Mode, 16.04.2014 . . . . . . . . . . . . . . . 15

6.1. Tabellen und View Import . . . . . . . . . . . . . . . . . . . . . . . . 626.2. Konzeptgenerierung - Workbench . . . . . . . . . . . . . . . . . . . . 646.3. Konzeptgenerierung - Darstellung des erzeugten Konzepts . . . . . . 666.4. Die Anfrageschnittstelle . . . . . . . . . . . . . . . . . . . . . . . . . 696.5. Darstellung eines Anfrageergebnisses . . . . . . . . . . . . . . . . . . 73

7.1. Mockup einer graphischen Anfragekomponente auf Konzeptbasis . . 79

A.1. Das verwendete Schema als ER-Modell . . . . . . . . . . . . . . . . . 81

vii

Abkurzungen

AJAX Asynchronous JavaScript and XMLDBMS Datenbank Management SystemFDA U.S. Food and Drug AdministrationIUSOO infinite units of strongly overlapping orbitalsjsf JavaServer FacesMVC Model-View-ControllerQbE Query by Example, [Zlo77]SQL structured query languagexhtml Extensible HyperText Markup LanguageXML Extensible Markup Language

ix

1. Einfuhrung

Wird einer großeren Zielgruppe uber eine Anfrageschnittstelle Zugriff auf eine Daten-bank angeboten, so kann von zwei Nutzergruppen ausgegangen werden. Die ersteGruppe setzt sich aus erfahrenen ’Experten’ zusammen, die in der Lage sind, unterKenntnis des zugrundeliegenden Datenbankschemas komplexe Anfragen in Kalkul-sprachen wie TRC oder Anfragesprachen wie SQL zu formulieren. Bei Benutzernaus dieser Gruppe treten selten schwere Fehler in der Anfrageformulierung auf unddie von ihnen erstellten Anfragen sind meist geeignet, die intendierte Informationaus der Datenbank zu extrahieren.

Auf der anderen Seite steht die Gruppe der weniger erfahrenen Nutzer, die zumeistauf eine Fuhrung bei der Formulierung ihrer Anfragen durch die verwendete Schnitt-stelle angewiesen sind. Sie erwarten etwa Menustrukturen oder graphische Anfrage-schnittstellen, die bereits durch ihren Entwurf die Form der Anfrage vorgeben. Auchwenn Kenntnisse von boolescher Logik oder Anfragesprachen vorhanden sein mogen,kann bei dieser Gruppe nicht von diesen ausgegangen werden. Steht einem Benutzerdieser Gruppe die volle Ausdruckskraft einer Sprache zur Verfugung, etwa in Formeiner SQL-Schnittstelle zu einem komplexen Schema, so ist es weniger wahrschein-lich, daß dieser korrekte Anfragen formuliert, die zudem Ergebnisse liefern, die denAnforderungen der gewunschten Anfrage genugen.

Eine Anfrageschnittstelle steht im Spannungsfeld zwischen diesen Nutzergruppen.Sie muß machtig genug sein, um auch die Formulierung komplexer Anfragen zu er-moglichen und gleichzeitig unerfahreneren Benutzern Anleitung und genugend Hin-weise bieten, um diesen die Ubersetzung ihrer Anfrage in eine Form zu ermoglichen,deren Auswertung genau die Ergebnisse liefert, die diese erwarten.

In dieser Arbeit wird eine Anfragesprache vorgeschlagen, die eine Einteilung der Op-erationen der relationalen Algebra als Grundlage fur Anfragen in mehreren Schrit-ten nutzt. Basierend auf dem verwendeten Datenbankschema wird eine Abstraktionvon Relationen oder Tabellen in dem Benutzer vertraute Konzepte aus dem jeweili-gen Fachbereich vorgenommen. In einem ersten Schritt wird hierfur unter Kenntnisdes Schemas eine Ubersetzungsvorschrift angegeben, die Relationen oder Tabellen inKonzepte ubersetzt. Eine Menge von Operationen erlaubt die Kombination grundle-gender Konzepte zu komplexeren Strukturen.

Der Benutzer beschreibt seine Anfrage als Anforderungen an solch vertraute Konzep-te. Hierfur kann direkt aus dem Konzept eine dynamische Schnittstelle generiert wer-den. Unter Verwendung einer zu QbE [Zlo77] ahnlichen Syntax ist die Formulierungvon Anfragen moglich.

Da der Benutzer bei der Anfrageerstellung mit ihm vertrauten Begriffen konfron-tiert wird, verringert sich die Wahrscheinlichkeit von Fehlformulierungen, die auf

1

1. Einfuhrung

Missverstandnissen des Datenbankschemas beruhen.Schließlich wird in dieser Arbeit eine Umsetzung dieser Anfragesprache als Web-Interface einer wissenschaftlichen Datenbank beschrieben. Basierend auf einem re-lationalen Datenbanksystem wird das Erstellen von Konzepten unter Verwendungder erwahnten Operationen ermoglicht. Die erstellten Konzepte werden in SQL-Statements ubersetzt. Ein dynamisch generiertes Interface erlaubt schließlich Darstel-lung und Anfrageformulierung.Nutzeranfragen werden unter Verwendung der SQL-Ubersetzung auf der Datenbankausgewertet. Resultate werden als zur Anfrage passende Auspragungen des genutztenKonzepts prasentiert.

2

2. Aufgabenstellung

Bei der Erstellung von Anfrageschnittstellen fur Datenbanken steht der Entwerfendeim Spannungsfeld zwischen den Moglichkeiten und Anforderungen der verwende-ten Anfragesprache und den Anforderungen und Fahigkeiten der zu erwartendenBenutzergruppe. Wird eine Schnittstelle konzipiert, die eine große Freiheit in derAnfrageformulierung ermoglicht, muß haufig von erfahrenen Benutzern mit hoherKenntnis der Schnittstelle und der zugrundeliegenden Datenbank ausgegangen wer-den. Eine SQL-Schnittstelle erlaubt etwa die volle Ausdruckskraft der Sprache zunutzen, doch sind auch vielfaltige Formulierungen moglich, die das System starkbelasten konnen. Ist etwa mit einem großen Datenvolumen der zugrundeliegendenDatenbank zu rechnen, kann bereits eine unvollstandige Join-Bedingung zu einemKreuzprodukt und dem Stillstand des Systems fuhren. Diese Gefahr steigt nochdurch Besonderheiten des genutzten Datenbankschemas. Normalisierung, Abkurzun-gen in Bezeichnern oder eingefugte Redundanzen machen seitens des Benutzers eineTransferleistung erforderlich. Er muß den Elementen des Schemas Begriffe zuordnen,die er versteht und auf denen seine eigentliche Anfrage basiert.Wird hingegen eine Schnittstelle angeboten, die den Benutzer stark einschrankt,ihm nur Anfrageformulierungen nach einem strikten Muster erlaubt, so kann zwardie Gefahr von Fehlern reduziert werden, doch muß haufig die Menge moglicherAnfragen eingeschrankt werden.Im Rahmen dieser Arbeit soll eine Anfragesprache fur wissenschaftliche Datenbankenerstellt werden. Unter wissenschaftlichen Datenbanken sind hier Datenbanken zu ver-stehen, die eine hierarchische Struktur aufweisen, was Analysevorgange und derenErgebnisse abbildet, und deren Schemata zu einem gewissen Grad normalisiert sind.Sie soll auf existierenden Datenbanken benutzbar sein, ohne Anpassungen des Daten-bankschemas zu erfordern. Benutzer sollen ohne Kenntnis des Schemas und ohneuber vertiefende Kenntnisse in Datenbanksprachen zu verfugen, Anfragen formulierenkonnen. Es sollen ausreichend komplexe Anfragen moglich sein, etwa statistischeAuswertungen, gleichzeitig sollen Fehlformulierungen, etwa die erwahnten ungewoll-ten Kreuzprodukte, soweit wie moglich ausgeschlossen werden.Basierend auf dieser Sprache soll dann ein webbasiertes System erstellt werden. Essoll zunachst als Anfrageschnittstelle einer Kristallstruktur-Datenbank verwendetwerden, jedoch nicht auf diese beschrankt, sondern unter geringem Aufwand mitanderen Datenbanken kombinierbar sein.

3

3. Verwendete Beispiele

Im Folgenden werden die Beispielschemata beschrieben, die im Laufe der Arbeitverwendet werden, um Aspekte der Losung zu veranschaulichen. Die ersten zweiSchemata sind realen Systemen entnommen, die anderen sind theoretischer Natur.

3.1. CrystalDB

Das in Abbildung 3.1 dargestellte Schema wird zur Speicherung von Strukturin-formationen chemischer Verbindungen verwendet. Der hier verwendete Ausschnittstellt den Kern des Schemas da. Er wurde um Komponenten reduziert, die fur dieVerwendung als Beispiel nicht relevant sind. Das Schema ist stark hierarchisch undstark zyklisch.

crysno_cccrystal_nameformulayeartchm_ful

CRYSTAL_STRUCTURE

strength_factor

ANALYSIS

IONS

CONN_UNIT

conn_unit_no

PART OF

elementatom_nooxidationcoordination

0,n

0,1

IUSOOS

iusoo_nodimensionalitytypestrengthsymop

CATIONS ANIONS

EDGES

anion_sym_opcation_sym_optranslationdistancestruct_bv

PATHS

path_noEDGE_IN_PATH

0,n

1,n

edge_no

1,1

0,n

Abbildung 3.1.: ERM CrystalDB

5


Die Ubersetzung des Schemas in ein relationales Datenbankschema ist unter AnhangC beigefugt.

Eine Kristallstruktur wird als CRYSTAL_STRUCTURE abgebildet. Die Analyse der Aus-gangsdaten wird unter einem variablen strength-factor vorgenommen. So konnen zujeder Struktur verschiedene Analyseergebnisse ANALYSIS entstehen.

Die Kristallstrukturen setzen sich aus Ionen, IONS, zusammen, die innerhalb derStruktur Zusammenhangskomponenten, CONN_UNIT, bilden.

Ionen wiederum unterteilen sich in Anionen und Kationen, ANIONS und CATIONS.Gehen Anion und Kation eine Bindung ein, so wird dies als Kante interpretiert,EDGES.

Je nach gewahltem strength-factor werden innerhalb der Zusammenhangskompo-nenten IUSOOs identifiziert, im Schema als IUSOOS abgebildet. IUSOOs setzen sichaus Pfaden von Kanten zusammen. Sie sind also jeweils Teilgraph einer Zusammen-hangskomponente der Struktur. Welche Kanten und Pfade Teil der IUSOO sind, istvom strength-factor der jeweiligen Analyse abhangig. Im Schema werden Kanten,die sich qualifizieren, als EDGE_IN_PATH einem Pfad, PATHS, zugeordnet und so mitder IUSOO verknupft.

Eine auf dem vollstandigen Schema basierende Datenbank wird verwendet, um imRahmen der Supraleiterforschung generierte Analyseergebnisse zu speichern. Die imRahmen dieser Arbeit erstellte Software soll als Anfrageschnittstelle fur diese Daten-bank verwendet werden.

3.2. OpenVigil

Bei OpenVigil handelt es sich um ein Werkzeug zur Analyse von FDA AdverseEvent Reporting System Daten im Rahmen der Pharmakovigilanz. Die FDA bundeltin diesen Datensatzen die durch ein Meldesystem gesammelten Informationen zupharmazeutischen Produkten und unerwunschten Nebenwirkungen im Rahmen ihrerAnwendung. Das System wird in den Arbeiten [Egg13] und [Zie13] beschrieben.

Im Rahmen des Imports ermoglicht OpenVigil die Bereinigung fehlerhafter Daten,die Transformation der Information in einheitliche Formate und das abschließendeSichern in einer eigenen Datenstruktur.

Abbildung 3.2 zeigt einen Ausschnitt aus dem vollstandigen OpenVigil Schema. DasSchema weist, ebenso wie das in 3.1 beschriebene, Kreise auf. Allerdings besteht indiesem Fall eine XOR-Beziehung zwischen PP_APPL und D_APPL. Die Ubersetzungin ein relationales Schema ist unter Anhang D angefugt.

Berichte uber Nebenwirkungen werden als REPORT abgebildet. Hier werden etwaAngaben wie das Datum des Auftretens der Nebenwirkung oder das Geschlecht desPatienten vermerkt. Zu einem Report gehort eine Menge von Ereignissen, EVENT,Quellen, REPORT_SOURCE, Ausgangen der Behandlung, OUTCOME, sowie eine Mengevon Anwendungen, DRUGUSAGE. Ferner sind Berichte einem Fall, CASE, zugeordnet.

Als Anwendung wird die Behandlung entweder mit einem Produkt eines spezifischenHerstellers, PP_APPL und PHARMAPRODUCT, das sich aus Inhaltsstoffen, DRUG, zusam-

6

3.2. OpenVigil

REPORT_SOURCE

codemeaning

OUTCOME

codemeaning

codemeaning

codemeaning

EVENT

ptsysorgclass

codemeaning

CASE

case_id

REP_RSRC

REP_OC

REP_EV

INCL

REPORT

isrfoll_seqdateagegender

0,n

0,n

0,n

0,1

0..n

0..n

0..n

1..n

DRUGUSAGE

drug_seqroutedaily_dosis

RESULT1,n1,1

THERAPY

t_idstartenddurability

PHARMAPRODUCT

brand_nameproducer_nameformsalttype

DRUG

drug_namedrugbank_id

PRODUCT

D_APPLPP_APPL

0,1 0,n

0,n 0,n

0,n 0,n

Abbildung 3.2.: ERM OpenVigil

7


mensetzt, oder den Inhaltsstoffen selbst, D_APPL, bezeichnet. Es hat sich gezeigt, daßunerfahrene Nutzer haufig Schwierigkeiten haben, korrekte SQL-Statements unterBeachtung dieser XOR-Beziehung zu formulieren.

3.3. Beispiel Fahrzeugbau

Das folgende Schema beschreibt die Produktdatenbank eines fiktiven Herstellers vonPKW- und Nutzfahrzeug-Anhangern, der Firma K. Das Unternehmen produziertund verkauft sowohl komplette Fahrzeuge als auch Ersatzteile. Fahrzeuge konnendabei selbst produziert oder von anderen Anbietern angekauft sein. Auch einigeTeile werden aus eingekauften Komponenten von Firma K hergestellt.

Abbildung 3.3 zeigt das ER-Schema des Beispiels, die relationale Ubersetzung istunter Anhang E zu finden.

v_id_numberproduction_datedescriptionsale_price

TRAILER

of_type

nameexpected_m_hgen_typedescription

TRAILER_TYPE

namedescriptionsale_price_puunit

PART

parts_used1,n

0,1

0,n

0,n

amount

used in

needed

0,n

0,n

amount

Abbildung 3.3.: ERM Fahrzeugbau

Zum Verkauf angebotene Fahrzeuge werden als TRAILER abgespeichert. Sie werdenuber ihre Fahrgestellnummer identifiziert. Eventuell sind auch das Herstellungsda-tum und eine kurze Beschreibung verfugbar.

Wurden sie von Firma K produziert, so entsprechen sie einem ProduktionsmusterTRAILER_TYPE. Hier sind Angaben wie die fur die Produktion zu erwartende Anzahl

8

3.4. Das Bankbeispiel

an Personenstunden und der Fahrzeugtyp, etwa ’Viehanhanger’, abgelegt.Fur die Produktion eines Fahrzeugs nach einem solchen Muster sind verschiedeneTeile PART notwendig. Ein Teil kann dabei von einer Fremdfirma eingekauft odervon Firma K produziert sein. In letzterem Fall konnen fur die Herstellung weit-ere Teile notwendig sein. Fur einen Fahrzeugrahmen konnten etwa unter anderem’Stahltrager’ und ’Winkelstahl’ benotigt werden.Das Schema weist mit der used in/needed-Relation eine rekursive Komponenteauf. Sie spannt innerhalb der Menge der Ersatzteile Baume auf. Fur das Zusammen-stellen aller zur Produktion eines Ersatzteils notwendigen Grundkomponenten istdie Bestimmung der Blattmenge des zugehorigen Baumes notwendig. Die transitiveHulle der used in/needed-Relation zu einem Ersatzteil beschreibt die Menge allerim Laufe der Produktion notwendigen Teile.

3.4. Das Bankbeispiel

Das Bankbeispiel ist eine Variante des in [FMU82] vorgestellten Beispiels, Abbildung3.4 zeigt das zugehorige Schema, eine relationale Ubersetzung ist im Anhang Fbeigefugt. Es bildet die Beziehung zwischen Banken, BANK, und Kunden, CUSTOMER,ab. Ein Kunde kann bei einer Bank ein Konto halten, im Schema ACCOUNT, odereinen Kredit abschließen, im Schema LOAN.

3.5. Das modifizierte Bankbeispiel

In der oben beschriebenen Form weist die Modellierung eine Schwache in der Zuord-nung von Kunden zu Banken auf. So geht etwa aus der naturlichsprachlichen Anfrage

”Gib alle Kunden der Bank A.”

nicht hervor, ob Kunden gefordert sind, die ein Konto bei Bank A fuhren, solche,die dort einen Kredit aufgenommen haben oder beide.In [FMU82] wird eine Uberladung des Begriffes Kunde in diesem Zusammenhangals Problem identifiziert. Eine dort vorgeschlagene Losungsmoglichkeit ist das Auf-spalten der Entitat CUSTOMER in DEPOSITOR und BORROWER, wie in Abbildung 3.5dargestellt. Erneut ist eine relationale Ubersetzung unter Anhang G zu finden.

9


name

BANK

a_nobalance

ACCOUNT

l_noamount

LOAN

cust_noaddress

CUSTOMER

1,1 1,1

1,1 1,1

0,n

1,1

0,n

0,n

0,n

Abbildung 3.4.: ERM zum Bankbeispiel

10

3.5. Das modifizierte Bankbeispiel

name

BANK

a_nobalance

ACCOUNT

l_noamount

LOAN

1,1 1,1

1,1 1,1

0,n

1,1

0,n

DEPOSITOR

BORROWER

0,n

0,n

cust_noaddress

CUSTOMER

Abbildung 3.5.: ERM zum modifizierten Bankbeispiel nach [FMU82]

11

4. Losungsentwurf

Um sowohl das zugrundeliegende Datenbanksystem vor ungewunschten Anfragen be-ziehungsweise Angriffen zu schutzen, gleichzeitig dem Benutzer aber eine moglichstumfangreiche Formulierung sinnvoller Anfragen zu erlauben, wird eine Anfragefor-mulierung in zwei Stufen verwendet. Die Operationen der zugrundeliegenden An-fragesprache sind hierfur in zwei Klassen einteilbar: solche, deren Ziel die Erzeu-gung von Relationen fur spatere Anfrageformulierungen ist, und solche, die beimabschließenden Formulieren von Anfragen verwendet werden sollen.Mit der Unterteilung der Anfrageformulierung in zwei Stufen geht auch eine Vertei-lung der Verantwortung auf zwei Stellen einher: eine erste Instanz, etwa der Daten-bankadministrator, die unter Kenntnis des Schemas Strukturen als Grundlage furAnfragen vorbereitet, und der Benutzer, der ohne Kenntnis der zugrundeliegendenDatenbank Anfragen an diese Strukturen formuliert.Dieser Ansatz weist Vorteile gegenuber einem einstufigen auf. So steht etwa einemBenutzer, der seine Anfragen in SQL formuliert, zwar die volle Ausdruckskraft derSprache zur Verfugung, doch bieten sich ihm auch zahllose Moglichkeiten, in sein-er Anfrage vermeidbare Fehler zu begehen. Ein fehlerhaft oder unvollstandig for-mulierter Join etwa, kann bestenfalls zu inkorrekten Ergebnissen fuhren, und imschlimmsten Fall das gesamte System zum Erliegen bringen.Wird der Endbenutzer hingegen auf eine Ahnlichkeitssuche nach fur ihn verstand-lichen Konzepten beschrankt, entfallen viele dieser Fehlerpotentiale.Um zu verdeutlichen, wie eine solche Suche aufgebaut ist, sei die folgende Benutzer-anfrage an das Bank-Beispiel 3.4 gegeben:

Gib alle Kontoinhaber der Bank A, die eine ausgeglichene oder positiveKontobilanz haben.

Der Benutzer verwendet in dieser Anfrage Konzepte, so daß die Anfrage erst nacheiner Transferleistung auf dem System ausgewertet werden kann. So existiert imSchema kein Objekt ’Kontoinhaber’ und auch eine ’ausgeglichene oder positive Kon-tobilanz’ ist ein schemafremdes Konzept.Die schemanahere Form der selben Anfrage ware:

Gib alle Kunden, die uber ein Konto bei der Bank A verfugen und derenKontostand großer oder gleich null ist.

Hier ist die Transferleistung vollzogen, die Konzepte ’Kontoinhaber’ und ’ausgeglich-ene oder positive Kontobilanz’ sind Begriffen des Schemas zugeordnet.Der entscheidende Schritt ist nun, dem Benutzer Anfrageschnittstellen zur Verfugungzu stellen, die ihm ermoglichen, solche Konzepte zu verwenden. Stellte das System

13

4. Losungsentwurf

etwa eine Eingabemaske bereit, in der der Benutzer Kontoinhaber suchen konnte,mußte er lediglich nach solchen suchen, deren Kontostand großer oder gleich null ist.Alternativ konnte das System ermoglichen, Kontoinhaber zu suchen, die eine ’aus-geglichene oder positive Kontobilanz’ haben, also einen Kontostand großer oder gle-ich null aufweisen.In einem solchen theoretischen Beispiel erscheint dies trivial, doch schon das Beispiel3.2 liefert eine ahnliche Anfrage:

Gib alle Meldungen zusammen mit den beteiligten Inhaltsstoffen.

Mit ’beteiligten Inhaltsstoffen’ sind hier zum einen Inhaltsstoffe gemeint, die direktbei einer Anwendung angegeben wurden, zum anderen solche, die als Teil einesPharmaprodukts einem Ereignis zugeordnet werden konnen.In einer Formulierung der Anfrage in SQL konnte dies etwa als Join zwischen REPORT

und DRUGUSAGE und zweier ODER-verknupfter Existenzaussagen umgesetzt werden.Eine solche Formulierung setzt jedoch die Kenntnis des Schemas und dessen genauerSemantik sowie Erfahrung in einer Anfragesprache wie SQL voraus.Dem Endbenutzer muß also eine Anfrageschnittstelle angeboten werden, die voneiner solchen Anfrageformulierung abstrahiert und es ermoglicht, Anfragen zu for-mulieren, die sich auf den gewunschten Zusammenhang, das gewunschte Konzept,beschranken.Ein moglicher Ansatz ist, dem Benutzer eine Menge situationsspezifischer Anfrage-masken zur Verfugung zu stellen. So bietet etwa OpenVigil unter anderem einetextbasierte Suche und ein Maske zur Formulierung boolescher Ausdrucke, Abbil-dung 4.1. Doch ist es im Allgemeinen nicht sinnvoll, beziehungsweise nicht realisier-bar, fur jedes angebotene Konzept eigene Anfragemasken zu programmieren. Beieiner hohen Anzahl anzubietender Konzepte steht Implementierungs- und Wartungs-aufwand haufig nicht mehr im Verhaltnis zum entstehenden Nutzen.Es ist daher sinnvoll solche Masken zu generieren. Das System muß folglich einer’eingeweihten’ Instanz, etwa dem zustandigen Administrator, ermoglichen, Konzeptefur den Benutzer zu erstellen. Das System ubernimmt dann die Ubersetzung dieserKonstruktion in die verwendete Datenbank-Anfragesprache und die Generierungpassender Eingabemasken.Anschließend kann der Endbenutzer diese nutzen, um die von ihm gewunschte In-formation zu extrahieren. Die hierzu genutzte Anfragesprache muß dabei fur ein-fache Anfragen eine moglichst direkte Ubersetzung von naturlichsprachlicher For-mulierung in Anfrageparameter ermoglichen, jedoch auch machtig genug sein, umdie Formulierung komplexer Anfragen zu erlauben.Hier bietet sich eine Abwandlung der Sprache Query-by-Example, QbE [Zlo77],an. Unter Verwendung vordefinierter Konzepte, ist das Vorgehen, Anfragen uberBeispiele zu formulieren, sehr naturlich.Wurde etwa ein Konzept fur die oben erwahnte Anfrage nach Kontoinhabern derBank A mit ausgeglichener oder positiver Kontobilanz erstellt, das Banken undderen Kontoinhaber reprasentiert, ware eine Eingabemaske denkbar, die unter an-derem eine Eintragung fur Banknamen und Kontobilanz ermoglicht. Unter Nutzung

14

Abbildung 4.1.: OpenVigil - Professional Mode, 16.04.2014

15

4. Losungsentwurf

von QbE genugte der Eintrag von ’Bank A’ als Banknamen und ’>= 0’ als Konto-stand, um das gewunschte Anfrageergebnis zu erhalten. Fur statistische Anfragen,etwa nach dem durchschnittlichen Kontostand, kann diese Syntax um Funktionenerweitert werden.

Im Folgenden werden zunachst die fur ein solches System notwendigen Konstrukteund Operationen definiert. Danach wird ein QbE-Dialekt entworfen, der als Anfrage-sprache verwendet werden kann. Zur Semantikdefinition wird dabei die Ubersetzungin die Relationale Algebra verwendet.

In Kapitel 6 wird schließlich ein System beschrieben, das auf der hier entworfenenKonstrukten basiert.

4.1. Voraussetzung

Um eine Anfragesprache zu definieren, die oben erwahnten Anforderungen entspricht,sind die folgenden Voraussetzungen notwendig.

Zunachst wird fur die einleitenden Definition das relationale Datenmodell sowie dierelationale Algebra nach [KK93] benotigt. Die relevanten Definitionen werden imFolgenden zusammengefaßt:

Ein Relationstyp ist ein Tupel bestehend aus einem Bezeichner und einer nicht-leeren Menge von Attributen.

Fur eine endliche, nicht-leere Menge von Attributbezeichnern

{A1, . . . , Ak}, k > 0

einer Menge nicht-leerer Wertebereiche

{D1, . . . , Dl}, l > 0

und eine Wertebereichsfunktion

dom : {A1, . . . , Ak} → {D1, . . . , Dl}

ist ein Relationstyp ein Tupel (R, {A1, . . . , Ak}), wobei R ein Relationsbezeichnerist. (R, {A1, . . . , Ak}) wird im Folgenden mit R identifiziert.

Ein relationales Datenbankschema σ ist eine nicht-leere Menge von Relationstypen

σ = {(R1, α1), . . . , (Rm, αm)}, m > 0

mit einem gemeinsamen Attributmenge α =m⋃i=1

αi und einer gemeinsamen Wer-

tebereichsfunktion dom : α → {D1, . . . , Dl}, l > 0. Dabei sei Ri 6= Rj fur alle0 < i, j ≤ m, i 6= j und fur alle Ri, 0 < i ≤ m, sei Ri /∈ α.

Abweichend von [KK93] wird hier zudem vorausgesetzt, daß αi ∩ αj = ∅ fur alle0 < i, j ≤ m. Diese Forderung stellt keine Einschrankung, weder des relationalen

16

4.1. Voraussetzung

Modells noch der relationalen Algebra dar. Aus der universal relation assump-tion [FMU82] folgt etwa direkt, daß jedes relationale Datenbankschema so modi-fiziert werden kann, daß es die Bedingung erfullt, ohne an Informationsgehalt oderMachtigkeit zu verlieren. Die Eindeutigkeit von Attributbezeichnern kann etwa durchvoranstellen des Relationsnamens erreicht werden. Sollte diese Bedingung in einemSchema nicht gegeben sein, so kann es fur die folgenden Betrachtungen auf dieseWeise modifiziert werden.

Eine Auspragung eines solchen Schemas ist nun ein Zustand, fur dessen Defini-tion zunachst die Begriffe Datenbanktupel und Datenbankrelation eingefuhrt werdenmussen.

Ein Datenbanktupel t uber einer Attributmenge {A1, . . . , Ak}, k ∈ N mit zuge-horiger Wertebereichsfunktion dom : {A1, . . . , Ak} → {D1, . . . , Dl} ist eine Funktion

t : {A1, . . . , Ak} →k⋃i=1

Di

mit

t(Ai) ∈ dom(Ai), fur alle 0 < i ≤ k

Ein Datenbanktupel bildet also Elemente einer Attributmenge, etwa die eines Rela-tionstyps, auf je ein Element des zugehorigen Wertebereichs ab.

Eine Datenbankrelation bezeichnet nun eine Menge von Datenbanktupeln. Zu einerAttributmenge α = {A1, . . . , Ak}, k ∈ N, mit zugehoriger Wertebereichsfunktiondom : {A1, . . . , Ak} → {D1, . . . , Dl}, l ∈ N, ist eine Datenbankrelation R eine Mengevon Datenbanktupeln uber α. R ist dann Datenbankrelation uber α.

Fur ein relationales Datenbankschema σ = {(R1, α1), . . . , (Rm, αm)}, m > 0, istein Zustand z zu σ eine Funktion, die jeden Relationstyp (Ri, αi) ∈ σ auf eineDatenbankrelation Ri uber αi abbildet.

Auf Basis des relationalen Datenmodells kann dann eine relationale Algebra definiertwerden. Im Folgenden werden erneut die wichtigsten Definitionen aus [KK93] zusam-mengefaßt.

Zunachst sind Mengenoperationen auf Relationen zu definieren. Da es sich bei Re-lationen um Mengen handelt, konnen Vereinigung ’∪’, Schnitt ’∩’ und Differenz ’−’fur zwei Relationen R und S mit gleicher Attributmenge αR = αS direkt uber dieMengenoperationen als R ∪ S, R ∩ S und R \ S definiert werden.

Zur Reduktion der Attributmenge einer Relation ist die Projektion notwendig. Fureine Relation R mit Attributmenge αR ist die Projektion auf eine Attributmengeβ ⊆ αR definiert als

R[β] = {t|β | t ∈ R}

Die Selektion ermoglicht die Einschrankung der Tupelmenge einer Relation auf eineTeilmenge, deren Elemente ein angegebenes Pradikat erfullen. Es genugt dabei, diezu verwendeten Pradikate auf solche zu beschranken, die durch einen einfachen Ver-gleichsausdruck zu der betreffenden Relation formulierbar sind.

17

4. Losungsentwurf

Ein einfacher Vergleichsausdruck zu einer Attributmenge {A1, . . . , Ak}, k ∈ N, istein Ausdruck der Form A � B oder A � c, fur c ∈ dom(A), A,B ∈ {A1, . . . , Ak},mit dom(A) = dom(B). Als Konstantensymbol fur c wird dabei ein Element ausdom(A) gewahlt. � ist dabei ein Vergleichsoperator. Ist eine Ordnung auf dom(A)definiert, so ist � ∈ {<,>,≤,≥,=, 6=}, ansonsten � ∈ {=, 6=}.Abweichend von [KK93] werden hier zudem true und false als Vergleichsausdruckezugelassen. Dabei entspricht offensichtlich fur eine beliebige Relation R mit Attribut-menge αR R[false] der leeren Relation uber αR und es gilt R[true] = R.Fur eine Datenbankrelation R mit Attributmenge αR und einem einfachen Vergle-ichsausdruck v uber αR ist die Selektion definiert als

R[v] = {t | t ∈ R ∧ t erfullt v}

Komplexe boolesche Ausdrucke konnen, entsprechend den bekannten Umformungs-regeln, uber die oben definierten Mengenoperationen ausgedruckt werden. Die Nega-tionen eines einfachen Vergleichsausdrucks kann als alternative Darstellung fur dasErsetzen des Vergleichsoperators durch seine jeweilige Negation, etwa < durch ≥,aufgefaßt werden.Fur einen solchen Ausdruck φ liefere zudem att(φ) die Menge der in φ auftretendenAttribute.Der Join ermoglicht das Verbinden von Relationen. Fur zwei Relationen R und Smit Attributmengen αR und αS ist der Join R ./ S definiert als

R ./ S = {t | t ist DB-Tupel uber αR ∪ αS ∧ t|αR ∈ R ∧ t|αS ∈ S}

Im Falle αR ∩ αS = ∅ liefert der Join das kartesische Produkt, in Zeichen R⊗ S.Schließlich ist eine Umbenennungsfunktion definiert, um die Attributbezeichner einesDatenbanktupels oder einer Datenbankrelation zu verandern.Sei t ein Datenbanktupel uber einer Teilmenge α′ einer ubergreifenden Attribut-menge α. Sei ferner α′′ ⊆ α′ mit α′′ = {A1, . . . , Ah} und β = {B1, . . . , Bh} eineAttributmenge mit α′′ ∩ β = ∅ und dom(Ai) = dom(Bi) fur alle 0 < i ≤ h. Aus tentsteht damit das Datenbanktupel t′ uber (α′ \ α′′) ∪ β durch die Umbenennungt[A1 → B1, . . . , Ah → Bh] mit t|α′\α′′ = t′|α′\α′′ und t′(Bi) = t(Ai) fur alle 0 < i ≤ h.Entsprechend wird die Umbenennung R′ einer Datenbankrelation R uber α′ definiertals

R′ = R[A1 → B1, . . . , Ah → Bh]

= {t[A1 → B1, . . . , Ah → Bh] | t ∈ R}

Bei Umbennenung in Attribute, die nicht in α vorkommen, ist die Wertebereichs-funktion dom entsprechend zu erweitern.Weiterhin ist eine Umbenennungsfunktion fur Relationstypen beziehungsweise Re-lationen sinnvoll. Fur den Relationstyp R = (R, {A1, . . . , Ak}), k > 0, kann etwa dieUmbenennung in R′, wobei R′ ein nicht im Schema auftretender Relationstypbeze-ichner ist, definiert werden als:

R[R→ R′] = (R′, {A1, . . . , Ak})

18

4.1. Voraussetzung

In jedem Zustand z gilt dann z(R) = z(R′).Bei den oben aufgezahlten Operationen haben einstellige Operatoren stets einehohere Prioritat als zweistellige. Es gelten ferner die ublichen Prioritatsregeln furMengenoperationen.Des weiteren wird ein grundlegender Aggregationsoperator auf Datenbankrelationenbenotigt.Zunachst mussen dafur Aggregatfunktionen auf Tupeln definiert werden. Wichtigist hierbei, daß bei der Definition von Aggregatfunktionen von Multimengenseman-tik bei Relationen ausgegangen wird. Dies vereinfacht die abschließende Definitionder Aggregation. Relationen mit Multimengensemantik werden durch einen demBezeichner angehangten ’∗’ markiert. Die Projektionsoperation mit Multimengense-mantik wird als R[α]∗ dargestellt.Als Aggregatfunktion wird eine Funktion bezeichnet, die auf einstelligen Relatio-nen anwendbar ist und diese auf eine einstellige Relation mit genau einem Tupelabbildet. Fur eine einstellige Relation R∗ mit Attributmenge {A}, einer arithmetis-chen Funktion f , die auf dom(A) definiert ist und einem Attributbezeichner B istdie Aggregationsfunktion fB definiert als

fB(R∗) = {t | wobei t ein Tupel uber {B} mit t(B) = f(R∗) ist}

Der Wertebereich von B kann dabei von dom(A) abhangen, etwa fur f = MIN,oder direkt von f , etwa bei f = COUNT. Sind diese jedoch nicht ausreichend großgewahlt, konnen durchaus Ergebniswerte entstehen, die nicht Teil des Wertebereichssind. Speziell bei arithmetischen Funktionen, wie etwa SUM oder AVG, ist diesmoglich.Es ist daher notwendig, die Wertebereiche entweder von vornherein ausreichend großanzunehmen oder im Fall des Entstehens eines neuen Wertes diesen entsprechend zuerweitern.Im weiteren Verlauf werden hauptsachlich die aus SQL bekannten Aggregatfunktio-nen SUM, MIN, MAX, COUNT und AVG auftreten. Wird eine beliebige aber festeOrdnung auf den Tupeln einer Relation angenommen, sind zudem Funktionen wieFIRST und LAST denkbar.Fur eine Datenbankrelation R mit Attributmenge αR, einer Attributmenge β ={B1, . . . , Bk} ⊆ αR, k ≥ 0, einem Attribut A ∈ αR, einer zu A kompatiblen Ag-gregatfunktion f und einem Attribut F /∈ β ist nun die AggregationsoperationΓ(R, β, f,A, F ) definiert als

Γ(R, β, f,A, F ) =⋃t∈R

(t[β]⊗ fA(R[φt][A]∗))

Wobei φt die fur die Zuordnung von Gruppe und Funktionswert notwendige Joinbe-dingung ist. In dem Aggregationsausdruck ist φt fur jedes Tupel durch den folgendenVergleichsausdruck zu ersetzen:

φt =

k∧i=1

(Ai = t(Ai))

19

4. Losungsentwurf

Zu jeder Wertekombination fur β in R wird also die Aggregationsfunktion berechnetund an das jeweilige Tupel angebunden.Im Sonderfall β = ∅ wird entsprechend f uber allen Tupeln der Relation ausgewertet:

Γ(R, ∅, f, A, F ) =⋃t∈R

(t[∅] ./ fB(R[true][A]∗)) (4.1)

= fB(R[A]∗) (4.2)

4.2. Konzept

concept (Philosophy): An idea or mental image which corresponds to some distinctentity or class of entities, or to its essential features, or determines the applicationof a term (especially a predicate), and thus plays a part in the use of reason orlanguage.

- Oxford Dictonaries zur Definition des Begriffes concept, [Pre14]

Ein Konzept ist ein abstrahiertes Modell einer Klasse von Objekten. Es beschreibtEigenschaften, die zu dieser Klasse gehorende Objekte von anderen unterscheiden.Konzepte ermoglichen demnach eine Klassifikation des aus einer Informationsmengeableitbaren Wissens. Sie entsprechen in dieser Eigenschaft Pradikaten.Es wurde bereits das Konzept des Kontoinhabers erwahnt. Aus der Menge derBankkunden qualifizieren sich genau diejenigen, die uber ein Konto verfugen.Aus dem Wissen um die Menge der Kunden ist also nur derjenige Anteil von Be-deutung, der Kunden beschreibt, die die Bedingung, ein Konto zu fuhren, erfullen.Ein Konzept zu dem Beispiel des Fahrzeugbaus 3.3 waren etwa Baumuster fur PKW-Anhanger. Dieses Konzept beschreibt aus der Menge aller Baumuster diejenigen,deren Typ die Zeichenfolge ’PKW’, ’Pkw’ oder ’pkw’ enthalt.

Fur ein Datenbankschema bezeichne nun ein Konzept eine Konstruktionsvorschriftfur Relationen. Diese sei so gewahlt, daß in jedem Zustand des Schemas die resul-tierende Relation jene Tupel enthalt, die diejenigen Objekte reprasentieren, die zudem zugehorigen abstrahierten Modell passen. In diesem Sinne kann ein Konzept alsVorschrift zur Erzeugung einer UR, etwa [FMU82], betrachtet werden.

4.2.1. Definition Konzept

Eine Konzept C ist ein Tripel C = (V, φ, P ). Dabei sind V eine nicht-leere Mengevon Relationstypen, φ ein aus einfachen Vergleichsausdrucken uber

⋃R∈V

αR aufge-

bauter logischer Ausdruck und P ⊆⋃R∈V

αR eine nicht-leere Attributmenge, die eine

Projektion festlegt.Sei σ ein relationales Datenbankschema. C ist kompatibel zu σ, wenn jeder in Cverwendete Relationstyp in σ vorkommt oder durch Umbenennung aus einem Rela-tionstypen in σ erzeugbar ist.

20

4.2. Konzept

Fur das Beispielschema des Fahrzeugbaus 3.3 ware etwa folgendes Konzept moglich:

EIGENBAU = ({TRAILER, TRAILER TYPE},TRAILER.type name = TRAILER TYPE.name,

{TRAILER.v id number, TRAILER TYPE.name,

TRAILER TYPE.type, TRAILER TYPE.description})

Es beschreibt die Menge der Eigenbauten, die aktuell zum Verkauf angeboten wer-den.

4.2.2. Auswertung von Konzepten

Fur einen Zustand z soll eine Funktion θz definiert werden, die einem KonzeptC = (V, φ, P ) eine Menge von Datenbank-Tupeln uber P zuordnet. In einem erstenVersuch kann folgende Definition betrachtet werden:

θz(C) = (./R∈V

z(R))[φ][P ]

Da fur alle R,R′ ∈ V gilt, daß αR∩αR′ = ∅, ist der Join hier stets ein Kreuzprodukt.

Jedoch ist in dieser Formulierung das stets θz(C) = ∅, falls eine Relation R ∈ Vexistiert, die leer ist. Dies kann zu unerwunschten Resultaten fuhren. Betrachte etwadas folgende Konzept zum Bankbeispiel 3.4:

BANK-CUST = ({BANK, ACCOUNT, LOAN, CUSTOMER},BANK.name = ACCOUNT.bankname

∧ ACCOUNT.cust no = CUSTOMER.cust no

∨ BANK.name = LOAN.bankname

∧ LOAN.cust no = CUSTOMER.cust no,

{BANK.name, CUSTOMER.cust no, CUSTOMER.address})

Das Konzept beschreibt Banken und deren Kunden. Also Kunden, die entweder einKonto fuhren, oder einen Kredit aufgenommen haben. Ist jedoch in einem Zustandetwa die LOAN-Relation leer, so werden Banken auch keine Kunden zugeordnet, dieuber ein Konto mit einer Bank verbunden sind. Diese Interpretation ist offensichtlichnicht die fur das Konzept BANK-CUST gewunschte.

Es wird daher die folgende rekursive Definition vorgeschlagen, die naher an der Be-deutung eines Konzepts ist. Zunachst wird C in einer aquivalenten Form angenom-

21

4. Losungsentwurf

men, in der die Selektionskomponente in Negationsnormalform uberfuhrt wird.

θz((V, φ, P )) = (./R∈V

z(R))[φ][P ]

fur ein Konzept (V, φ, P )

wobei φ ein einf. Vergleichsausdruck oder

ein negierter einf. Vergleichsausdruck ist.

θz((V, φ ∧ ψ, P )) = θz((W,φ, P )) ∩ θz((W ′, ψ, P ))

fur ein Konzept (V, φ ∧ ψ, P )

wobei W = {R | R ∈ V,∃A ∈ αR ∧ (A ∈ att(φ) ∨A ∈ P )}

und W ′ = {R | R ∈ V,∃A ∈ αR ∧ (A ∈ att(ψ) ∨A ∈ P )}

θz((V, φ ∨ ψ, P )) = θz((W,φ, P )) ∪ θz((W ′, ψ, P ))

fur ein Konzept (V, φ ∨ ψ, P )

wobei W = {R | R ∈ V,∃A ∈ αR ∧ (A ∈ att(φ) ∨A ∈ P )}

und W ′ = {R | R ∈ V,∃A ∈ αR ∧ (A ∈ att(ψ) ∨A ∈ P )}

4.2.3. Aquivalenz von Konzepten

Die Aquivalenz von Konzepten ist uber die Gleichheit der erzeugten Relationenausdruckbar. Fur zwei Konzepte C,C ′ zu einem Schema σ gilt also C ≡ C ′ genaudann, wenn fur alle Zustande z des Schemas gilt: θz(C) = θz(C

′).

4.3. Operationen auf Konzepten

4.3.1. Erzeugung

Ist R ein Relationstyp mit Attributmenge αR, so ist CR = ({R}, true, αR) das zuge-horige Konzept. Es gilt offensichtlich in allen Schemata σ, die R enthalten oder indenen R durch Umbenennung aus einem in σ enthaltenen Relationstyp erzeugbarist, und allen Zustanden z zu σ:

θz(CR) = z(R)[true][αR] = R

4.3.2. Projektion

Zur Verkleinerung der Projektionskomponente eines Konzepts wird die Projektioneingefuhrt. Fur ein Konzept C = (V, φ, P ) und eine Attributmenge P ′ ⊆ P ist

C[P ′] = (V, φ, P ′)

22


die Projektion von C auf P ′. Fur einen Zustand z zu einem Schema, das die Elementevon V beinhaltet, ist die Projektion damit analog zur Projektion der relationalenAlgebra definiert. Im Falle der naiven Ubersetzung also:

θz(C[P ′]) = (./R∈V

z(R))[φ][P ′] (4.3)

= (./R∈V

z(R))[φ][P ][P ′] (4.4)

= (θz(C))[P ′] (4.5)

Im Falle der komplexen Tupelzuordnung gilt die Gleichheit entsprechend.

4.3.3. Selektion

Ebenfalls analog zur Selektion der relationalen Algebra kann eine Selektion aufKonzepten definiert werden. Fur ein Konzept C = (V, φ, P ) und einen einfachenVergleichsausdruck ψ uber

⋃R∈V

αR ist die Selektion definiert als

C[ψ] = (V, φ ∧ ψ, P )

Erneut ist damit fur alle Zustande z zu einem Schema, das die Elemente von Vbeinhaltet, diese Operation analog zur relationalen Algebra definiert:

θz(C[ψ]) = (./R∈V

z(R))[φ ∧ ψ][P ] (4.6)

= (./R∈V

z(R))[φ][ψ][P ] (4.7)

(4.8)

Im Falle der komplexen Tupelzuordnung:

θz(C[ψ]) = θz(C) ∩ θz((V, ψ, P )) (4.9)

4.3.4. Schnitt

Fur zwei Konzepte mit identischer Projektion C = (V, φ, P ) und C ′ = (V ′, ψ, P )wird der Schnitt wie folgt definiert:

C ∩ C ′ = (V ∪ V ′, φ ∧ ψ, P )

Fur beliebige Schemata σ, die C,C ′ enthalten, und Zustande z zu σ ist damit

θz(C ∩ C ′) = θz((V ∪ V ′, φ ∧ ψ, P )) (4.10)

= ( ./R∈V ∪V ′

z(R))[φ ∧ ψ][P ] (4.11)

(∗)= (./

R∈Vz(R))[φ][P ] ∩ ( ./

R∈V ′z(R))[ψ][P ] (4.12)

= θz(C) ∩ θz(C ′) (4.13)

zu (∗): Die Gleichheit gilt hier, da P ⊆ V ∩ V ′ und in φ, beziehungsweise ψ, jeweilsnur Attribute der Elemente von V , beziehungsweise V ′, auftreten.Fur die komplexe Tupelzuordnung folgt die Analogie zur Algebra direkt aus derDefinition von θ.

23

4. Losungsentwurf

4.3.5. Vereinigung

Ahnlich dem Schnitt wird die Vereinigung zweier Konzepte mit gleicher ProjektionC = (V, φ, P ) und C ′ = (V ′, ψ, P ) definiert als

C ∪ C ′ = (V ∪ V ′, φ ∨ ψ, P )

Auch hier ist fur beliebige Schemata σ und zugehorige Zustande z die Vereinigungder Konzepte kompatibel zur Vereinigung der zugehorigen Relationen:

θz(C ∪ C ′) = θz((V ∪ V ′, P, φ ∨ ψ)) (4.14)

= ( ./R∈V ∪V ′

z(R))[φ ∨ ψ][P ] (4.15)

(∗)= (./

R∈Vz(R))[φ][P ] ∪ ( ./

R∈V ′z(R))[ψ][P ] (4.16)

= θz(C) ∪ θz(C ′) (4.17)

zu (∗): siehe 4.3.4.Fur die komplexe Tupelzuordnung folgt die Analogie zur Algebra erneut direkt ausder Definition von θ.

4.3.6. Differenz

Schließlich kann entsprechend Schnitt und Vereinigung die Differenz zweier KonzepteC = (V, φ, P ) und C ′ = (V ′, ψ, P ) wie folgt definiert werden:

C − C ′ = (V ∪ V ′, φ ∧ ¬ψ, P )

Auch die Differenz ist kompatibel zur entsprechenden Operation der relationalenAlgebra:

θz(C − C ′) = θz((V ∪ V ′, P, φ ∧ ¬ψ)) (4.18)

= ( ./R∈V ∪V ′

z(R))[φ ∧ ¬ψ][P ] (4.19)

(∗)= (./

R∈Vz(R))[φ][P ]− ( ./

R∈V ′z(R))[ψ][P ] (4.20)

= θz(C)− θz(C ′) (4.21)

zu (∗): siehe 4.3.4.Fur die komplexe Tupelzuordnung folgt die Analogie zur Algebra erneut direkt ausder Definition von θ.

4.3.7. Join

Der Join verbindet Konzepte uber gleiche Attributwerte. Fur zwei Konzepte C =(V, φ, P ) und C ′ = (V ′, ψ, P ′) ist also

C ./ C ′ = (V ∪ V ′, φ ∧ ψ, P ∪ P ′)

24


Im Fall V ∩V ′ = ∅ liefert dies das kartesische Produkt θ(C)⊗θ(C ′). Im Fall P∩P ′ = ∅liefert der Join der Konzepte jedoch aufgrund der Definition von θ im Allgemeinenkein kartesisches Produkt. Betrachte etwa die folgenden Konzepte:

C1 = ({A}, true, {a})

C2 = ({A}, true, {b})

zu einem Relationstyp (A, {a, b}). Fur einen Zustand z zu einem Schema, das Aenthalt, gilt

θz(C1 ./ C2) = z(A)i.A.6= z(A)[a] ./ z(A)[b]

Dieser interne Zusammenhang von Konzepten erfordert eine Umbenennung derbeteiligten Relationen, um das Verhalten der relationalen Algebra nachzubilden. Imobigen Beispiel konnte etwa ein Relationstyp B durch Umbenennung aus A erzeugtwerden. Das Kreuzprodukt ließe sich dann wie folgt erzeugen:

C1 = ({A[b→ b′]}, {a}, true)

C2 = ({B[a→ a′]}, {b}, true)

z(A)[a] ./ z(A)[b] = z(A)[a] ./ z(B)[b] = θz(C1 ./ C2)

4.3.8. Projizierende Vereinigung

Als weitere Operation bietet sich die Definition einer projizierenden Vereinigung an.Fur zwei Konzepte C = (V, φ, P ) und C ′ = (V ′, ψ, P ′) ist

C ∪proj C ′ = (V ∪ V ′, φ ∨ ψ, P ∩ P ′)

Diese Operation filtert gemeinsame Attribute zweier Konzepte heraus. Die pro-jizierende Vereinigung liefert also Tupel, die sich uber eine der beiden Ausgangs-konzepte qualifiziert haben, reduziert diese jedoch auf gemeinsame Attribute.

Es ware etwa denkbar, zum Bankbeispiel 3.4 die folgenden Konzepte zu bilden:

DEP = ({BANK, ACCOUNT, CUSTOMER},bank.name = account.bankname

∧ account.cust no = customer.cust no,

{bank.name, customer.cust no, customer.address})

BOR = ({BANK, LOAN, CUSTOMER},bank.name = loan.bankname

∧ loan.cust no = customer.cust no,

{bank.name, customer.cust no, customer.address})

25

4. Losungsentwurf

DEP beschreibt Banken und Kunden, die bei diesen ein Konto eroffnet haben, BORbeschreibt Banken und Kunden, die dort einen Kredit aufgenommen haben.

DEP ∪proj BOR beschreibt damit Banken und Kunden, die entweder ein Konto beidieser Bank fuhren, oder dort einen Kredit aufgenommen haben. Im Rahmen desSchemas aus Beispiels 3.4 beschreibt DEP∪proj BOR also Banken und all ihre zuge-horigen Kunden. Ob diese Kreditkunden oder Kontoinhaber sind, spielt dabei keineRolle.

4.4. Anfrageformulierung

Wie bereits in Kapitel 4 erwahnt, soll dem Endbenutzer die Moglichkeit gegeben wer-den, die zu einem Konzept gehorenden Tupel anhand eines Musters einzuschranken.

Die Anfragesprache QbE stellt hierfur den Ausgangspunkt dar. Allerdings fallt derJoin-Operation eine geringere Bedeutung zu, da ein vorbereitender Join bereits beider Konzeptdefinition durchgefuhrt wurde.

Der Benutzer gibt also als Anfrage eine Menge von Einschrankungen der Attributedes gewahlten Konzepts an, im folgenden Muster genannt. Fur das Konzept

P = (PART, true, {PART.name, PART.sale price pu, PART.unit})

zum Beispiel des Fahrzeugbaus 3.3 ware etwa das folgende Muster moglich

{PART.unit = 2,PART.sale price pu ≥ 20.00,PART.sale price pu < 100.00}

Die Ergebnismenge setzt sich dann aus den Tupeln von θ(P ) zusammen, die zudem eingegebenen Muster passen. Hier also diejenigen Ersatzteile, die in Paarenvertrieben werden und 20.00 oder mehr, aber weniger als 100.00 kosten.

Konzepte konnen dabei etwa uber ihre Projektion in Form einer Tabelle dargestelltwerden. Die Einschrankungen in einer Zeile reprasentieren dann ein Muster, diegesamte Tabelle eine Menge von Mustern.

In den hier verwendeten Beispielen wird die Eindeutigkeit von Attributbezeichnerndurch Voranstellen des Relationsnamens erreicht. Die Projektion eines Konzeptskann daher als gruppierte Tabelle dargestellt werden. Im Folgenden werden solchegruppierten Tabellen als Metapher bezeichnet

Hier etwa obige Anfrage in einer moglichen Metapherdarstellung.

PART

name sale price pu unit

≥ 20.00, < 100.00 2

Zur Interpretation dieser Menge sind verschiedene Semantiken denkbar. Allen gemein-sam ist jedoch die Grundvoraussetzung, daß ein Muster immer ein Tupel beschreibt,eine ODER-Verknupfung der Bedingungen verschiedener Attribute innerhalb einerZeile widerspricht dem und wird daher im Folgenden vernachlassigt.

26


4.4.1. Der print-Befehl

Ahnlich zu QbE, [Zlo77], wird ein expliziter print-Befehl verwendet, um die Auf-nahme eines Attributes in die Projektion des Suchergebnisses anzuzeigen. Er wirdhier durch Voranstellen des Buchstaben p vor den Attributnamen angezeigt. Ein pvor einem Relationsnamen kurzt den print-Befehl fur alle zugehorigen Attribute ab.In der endgultigen Implementierung kann der print-Befehl etwa durch Ausblendennicht gewahlter Attribute umgesetzt werden.Zu dem Schema des CrystalDB-Beispiel 3.1 ware etwa folgendes Konzept denkbar,das die zu einem Analyseergebnis gehorenden Strukturdaten beschreibt:

A = ({CRYSTAL STRUCTURES, ANALYSIS},CRYSTAL STRUCTURES.crysno cc = ANALYSIS.crysno cc,

{CRYSTAL STRUCTURES.crysno cc,

CRYSTAL STRUCTURES.crystal name,

CRYSTAL STRUCTURES.formula,

CRYSTAL STRUCTURES.year, ANALYSIS.strenght factor})

Die folgende Anfrage liefert die zu θ(A) gehorenden Tupels, projiziert auf die At-tribute CRYSTAL STRUCTURES.crysno cc, CRYSTAL STRUCTURES.formula,sowie alle Attribute der Relation ANALYSIS, die in der Projektion von A auftreten:

CRYSTAL STRUCTURES p.ANALYSIS

p.crysno cc crystal name p.formula year strength factor

Die Anfrage entspricht also dem Algebra-Ausdruck:

θ(A)[CRYSTAL STRUCTURES.crysno cc, CRYSTAL STRUCTURES.formula,

ANALYSIS.strength factor]

4.4.2. Selektion

Die Selektion von Tupeln eines Konzepts kann ebenfalls ahnlich zu QbE definiertwerden. Durch Angabe eines expliziten Wertes oder eines Vergleichs fur ein in derProjektion des Konzepts enthaltenes Attribut kann der Benutzer die Ergebnistu-pel auf solche einschranken, die diese Bedingungen erfullen. Vergleichsoperatorenund -werte mussen dabei jeweils mit dem Wertebereich des betreffenden Attributeskompatibel sein.Unter Verwendungen des in 4.4.1 eingefuhrten Beispiels konnen etwa durch die fol-gende Anfrage alle Analyseergebnisse mit einem strength factor von 1.2 der Jahreab 2000 erfragt werden:

p.CRYSTAL STRUCTURES p.ANALYSIS

crysno cc crystal name formula year strength factor

≥ 2000 1.2

27

4. Losungsentwurf

Der entsprechende Ausdruck der relationalen Algebra ist damit:

θ(A)[CRYSTAL STRUCTURE.year ≥ 2000 ∧ ANALYSIS.strength factor = 1.2]

4.4.3. Anfragesemantiken bei mehrzeiligen Anfragen

Neben einzeiligen Anfragen mit jeweils hochstens einem Vergleich pro Attribut sindnaturlich auch komplexere Anfragesemantiken denkbar. Im Folgenden werden viermogliche Semantiken fur Anfragen uber mehrere Zeilen und mehreren Vergleichenpro Attribut beschrieben, die je nach Einsatzgebiet gewahlt werden konnen.Konzepte werden hier wieder in Metapherform dargestellt. Vergleiche werden miteinem ’,’ getrennt.

4.4.3.1. Disjunktions-Semantik

Werden mehrzeilige Anfragen als Disjunktions-Anfragen interpretiert, so kann dasErgebnis als Vereinigung der Ergebnisse erzeugt werden, die bei unabhangigen An-fragen fur jede Zeile entstehen. Mehrere Vergleiche fur ein Attribut werden als UNDinterpretiert. Ein Tupel muß also mindestens die in einer Zeile formulierten Bedin-gungen erfullen.So kann etwa die folgende Anfrage zu dem in 4.4.1 eingefuhrten Beispiel unterDisjunktions-Semantik betrachtet werden:



≥ 1980, < 1990

≥ 2000

Sie entspricht dann der Anfrage:

Gib alle Analyseergebnisse und Strukturdaten zu Strukturen, die von Anfang 1980bis Ende 1989 oder ab 2000 beschrieben wurden.

Die geforderte Ergebnisrelation ergibt sich dann durch

R = θ((A[CRYSTAL STRUCTURE.year ≥ 1980

∧ CRYSTAL STRUCTURE.year < 1990]

∪ A[CRYSTAL STRUCTURE.year ≥ 2000])

[CRYSTAL STRUCTURES.crysno cc,



CRYSTAL STRUCTURES.year,

ANALYSIS.strength factor])

Aus diesem Beispiel wird bereits deutlich, daß Intervalle unter Verwendung derDisjunktions-Semantik sehr naturlich formulierbar sind.

28


Soll ein Attributwert jedoch in einer angegebenen Menge enthalten sein, analog zumIN-Konstrukt in SQL, muß fur jeden Wert eine Anfragezeile formuliert werden. Solletwa oben angegebene Anfrage auf Tupel beschrankt werden, deren strength_factor

in der Menge {1.1, 1.2, 1.3} enthalten sind, so wachst die Anfrage bereits betrachtlich:



≥ 1980, < 1990 1.1

≥ 2000 1.1

≥ 1980, < 1990 1.2

≥ 2000 1.2

≥ 1980, < 1990 1.3

≥ 2000 1.3

Die Disjunktions-Semantik eignet sich also fur Anfragesituationen, in denen haufigIntervalle auftreten, und seltener nach expliziten Wertemengen gesucht wird.

4.4.3.2. Konjunktions-Semantik

Es ist ebenfalls moglich, mehrzeilige Anfragen als konjunktive Formulierungen zuinterpretieren. Unter der Konjunktions-Semantik kann eine mehrzeilige Anfrage imGanzen als Beschreibung eines Tupels betrachtet werden. Mehrere Vergleiche proAttribut und Zeile werden ODER verknupft, ein Tupel muß auf jede Zeile passen,um in die Ergebnismenge aufgenommen zu werden. Diese Form der Anfrageinter-pretation liefert also Anfragen in konjunktiver Normalform.Fur das folgende Beispiel wird ein LIKE-Operator fur Zeichenfolgen ahnlich der gle-ichnamigen SQL-Funktion verwendet. Es wird erneut das Beispiel aus 4.4.1 verwen-det.Chemische Formeln enthalten die Kurzel der an der jeweiligen Verbindung betei-ligten Elemente, sowie Angaben zu deren Zahlenverhaltnissen. Soll also etwa nachStrukturen gesucht werden, die Barium und Yttrium oder Barium und Kupfer en-thalten, kann dies wie folgt formuliert werden:



LIKE %Ba%

LIKE %Y%, LIKE %Cu%

Mit Konjunktions-Semantik wird dies wie folgt ausgewertet:

R = θ((A[CRYSTAL STRUCTURE.formula LIKE %Ba%]

∩ A[CRYSTAL STRUCTURE.formula LIKE %Y%

∨ CRYSTAL STRUCTURE.formula LIKE %Cu%])

[CRYSTAL STRUCTURES.crysno cc,


29

4. Losungsentwurf


CRYSTAL STRUCTURES.year,

ANALYSIS.strength factor])

Auch Listen von moglichen Werten, wie im letzten Beispiel in 4.4.3.1, lassen sichaufgrund der ODER-Verknupfung von Werten fur ein Attribut in einer Zeile sehrnaturlich formulieren. Allerdings kann die Formulierung von Intervallen sehr komplexwerden. Schon die Anfrage:

Gib alle Strukturen, die von 1970 bis 1980 oder von 1990 bis 2000 beschriebenwurden.

erfordert die folgende Formulierung:

p.CRYSTAL STRUCTURES ANALYSIS


≥ 1970, ≥ 1990

≥ 1970, ≤ 2000

≤ 1980, ≥ 1990

≤ 1980, ≤ 2000

beziehungsweise deren minimierte Form:

p.CRYSTAL STRUCTURES ANALYSIS


≥ 1970

≤ 1980, ≥ 1990

≤ 2000

Da diese Formulierung nicht sehr naturlich ist, eignet sich die Konjunktions-Semantikweniger fur Anwendungsfalle, in denen solche Intervallanfragen haufig auftreten. Sieist eher fur Anfragen geeignet, bei denen nach Wertlisten, entsprechend dem SQL-Konstrukt IN, gesucht wird.

4.4.3.3. Disjunktions-Semantik mit einleitender Projektion

Statt die Projektion nach der Selektion anzuwenden, konnen Disjunktions- undKonjunktions-Semantik auch mit einleitender Projektion, also Projektion vor Vere-inigung beziehungsweise Schnitt, definiert werden.Im Falle der Disjunktions-Semantik liefert die Voranstellung der Projektion jedochfur alle Anfragen das gleiche Ergebnis, wie die reine Disjunktions-Semantik, sowohlunter Mengen-, als auch unter Multimengensemantik. Der folgende Beweis machtdies deutlich.

Beh.: Disjunktions-Semantik und Disjunktions-Semantik mit einleitender Projek-tion liefern stets das selbe Ergebnis.

30


Bew.: Sei zu einem Schema σ und einem Zustand z zu σ und Q eine Anfragefor-mulierung zu einem Konzept C = (V, φ, P ). Q habe die Form

Q = ({ψ1, . . . , ψn},P), n ∈ N

Wobei ψi, 1 ≤ i ≤ n, die in der i-ten Zeile formulierte Selektion ist und P ⊆ P diein der Anfrage formulierte Projektion.Unter Disjunktions-Semantik wird das Ergebnis durch den folgenden Ausdruck beschrieben:

θz((C[ψ1] ∪ . . . ∪ C[ψn])[P]) (4.22)

=Def. Proj.

θz(C[ψ1] ∪ . . . ∪ C[ψn])[P] (4.23)

=ψi def. uber P

(θz(C[ψ1]) ∪ . . . ∪ θz(C[ψn]))[P] (4.24)

=Ausdr. der rel. Alg.

θz(C[ψ1])[P] ∪ . . . ∪ θz(C[ψn])[P] (4.25)

=Def. Vereinigung

θz(C[ψ1][P] ∪ . . . ∪ C[ψn][P]) (4.26)

Dieser Ausdruck entspricht der Interpretation von Q unter Disjunktions-Semantikmit einleitender Projektion.

q.e.d.

4.4.3.4. Konjunktions-Semantik mit einleitender Projektion

Auch die Konjunktions-Semantik kann mit einer einleitenden Projektion kombiniertwerden.Zum OpenVigil-Schema 3.2 kann etwa folgendes Konzept betrachtet werden, esbeschreibt Medikamente und darin enthaltene Inhaltsstoffe.

ING = ({DRUG, PRODUCT, PHARMAPRODUCT},PHARMAPRODUCT.brandname = PRODUCT.brandname

∧ PHARMAPRODUCT.producer name = PRODUCT.producer name

∧ DRUG.drugname = PRODUCT.drugname,

{PHARMAPRODUCT.brandname, PHARMAPRODUCT.producer name,

DRUG.drugname, DRUG.drugbank id})

Durch die vorangestellte Projektion bei der Interpretation der Anfrage, konnen An-fragen nach der Existenz von Wertekombinationen mit geringem Aufwand formuliertwerden. Soll etwa nach Praparaten gesucht werden, die Aspirin in Kombination mitCalciumcarbonat, Diphenhydramin oder Coffein enthalt, ist dies wie folgt formulier-bar:

p.PHARMAPRODUCT DRUG

brandname producer name drugname drugbank id

Aspirin

Calciumcarbonat, Diphenhydramin,Coffein

31

4. Losungsentwurf

Die Auswertung der Anfrage verdeutlicht, daß das Resultat Pharmaprodukte be-schreibt, zu denen ein Inhaltsstoff Aspirin und mindestens ein Inhaltsstoff Calcium-carbonat, Diphenhydramin oder Coffein existiert.

R = θ(ING[DRUG.drugname = Aspirin]

[PHARMAPRODUCT.brandname,

PHARMAPRODUCT.producer name]

∩ING[DRUG.drugname = Calciumcarbonat

∨ DRUG.drugname = Diphenhydramin

∨ DRUG.drugname = Coffein])

[PHARMAPRODUCT.brandname,

PHARMAPRODUCT.producer name]

Im Gegensatz zur Disjunktions-Semantik mit einleitender Projektion unterscheidetsich hier das Anfrageergebnis im Allgemeinen von dem, das unter Anwendung derreinen Konjunktiven-Semantik erzeugt wird. Fur obige Anfrage ware unter Kon-junktiver-Semantik das Ergebnis stets leer.

4.4.4. Aggregation

Schließlich soll dem Benutzer die Moglichkeit gegeben werden, statistische Anfragenzu formulieren. Nach dem Vorbild des SQL GROUP BY-Konstrukts soll ein Gruppierenvon Ergebnistupeln und die Anwendung von Funktionen auf den zu der jeweiligenGruppe gehorenden Werten angeboten werden.Bisher sind die fur Konzeptgenerierung und Anfrageformulierung stets Operationendefiniert worden, die auf Konzepte angewandt und zu Konzepten ausgewertet wur-den. Aufgrund der Definition der Aggregationsoperation der relationalen Algebra alsRelationsoperation, und da Aggregationsoperationen sehr stark auf Relationen undderen Tupel bezogen sind, ist es sinnvoll die Aggregation fur Konzepte ebenfalls aufderen Auswertung zu definieren.Nach Definition der Aggregation auf Relationen in Abschnitt 4.1 kann eine Aggre-gationsoperation auf einer Relation R durch Angabe einer Menge zu aggregierenderAttribute β ⊆ αR, der anzuwendenden Funktion f sowie des AttributbezeichnersA, auf den sie angewandt werden soll, und eines Bezeichners F fur das entstehendeAttribut beschrieben werden.Wird also zu einem Konzept C ein entsprechendes Tupel γ = (β, f,A, F ) angegeben,ist die Auswertung zu einer Ergebnisrelation uber die Aggregation der relationalenAlgebra direkt moglich.

Γ(C, γ) = Γ(θ(C), β, f, A, F )

Hier kann sogar eine Schachtelbarkeit erreicht werden. Werden die angegebenen Pa-rameter um ein kompatibles Tupel γ′ = (β′, f ′, A′, F ′), mit β ⊆ β′ ∪ {F ′} und

32


A ∈ β′∪{F ′}, erweitert, kann dies als Schachtelung von Aggregationen interpretiertwerden. Eine solche Anfrage der Form γ = (β, f,A, F, γ′) ist dann auswertbar zu

Γ(C, γ) = Γ(Γ(C, γ′), β, f, A, F )

Hierbei handelt es sich bei dem außeren Γ-Operator um die Aggregation der rela-tionalen Algebra.Betrachte etwa die folgende Ergebnisrelation R einer Anfrage zum Beispiel desFahrzeugbaus 3.3.

TRAILER

v id number production date description sale price

123-456 1983 Pkw-Anhanger, 0.8t 400.00

14-08-05/7 2014 Motorradtrailer, 2M. 2200.00

0815 1983 Tieflader 250.00

03-12-06/2 2003 Pferdeanhanger, kurz 1400.00

14-04-04/12 2014 Kippbar, 1.5t, 2.2x1.8 4000.00

Die Bestimmung des durchschnittlichen Verkaufspreises der Tupel dieses Ergebnisseserfolgt uber den Aggregationsausdruck

(∅,AVG, sale price,Durchschnittspreis)

Die Auswertung Γ(R, ∅,AVG, sale price,Durchschnittspreis) liefert dann das gesuchteErgebnis.

Durchschnittspreis

1650.00

Als weiteres Beispiel kann etwa zum CrystalDB-Beispiel die durchschnittliche Pfadan-zahl pro IUSOO innerhalb eines Analyseergebnisses bestimmt werden.Dafur ist zunachst ein Konzept C erforderlich, daß ANALYSIS, IUSOOS und PATHS

geeignet verknupft und dessen Projektion mindestens die Attribute ANALYSIS.crys-no_cc, ANALYSIS.strength_factor, IUSOOS.iusoo_no und PATHS.path_no enthalt.Die Pfadanzahl pro IUSOO ist uber den Ausdruck

γ = ({ANALYSIS.crysno cc, ANALYSIS.strength factor, IUSOOS.iusoo no},COUNT,PATHS.path no, path-count})

bestimmbar. Γ(R, γ) liefert dann eine RelationR′ mit der Attributmenge {ANALYSIS.crysno_cc, ANALYSIS.strength_factor, IUSOOS.iusoo_no, path-count}. Die in R′

enthaltenen Tupel liefern zu jedem Analyseergebnis und seinen IUSOOs die Anzahlder Pfade innerhalb der jeweiligen IUSOO. Wird anschließend der folgende Aggre-gationsausdruck γ′ auf R′ angewendet, liefert er den Durchschnitt Anzahl pro Anal-yseergebnis.

γ′ = ({ANALYSIS.crysno cc, ANALYSIS.strength factor},AVG,path-count, avg-path-count-per-analysis}, γ)

Γ(R, γ′) liefert dann etwa:

33

4. Losungsentwurf

TRAILER

ANALYSIS.crysno cc ANALYSIS.strength factor avg-path-count-per-analysis

412479-0 1.2 5.00

412998-0 1.2 7.00

412477-0 1.2 8.00

96265-0 1.2 1.00

281196-0 1.2 6.00

412371-0 1.2 1.67

280951-0 1.2 8.00

. . . . . . . . .

4.5. Ubersetzung

4.5.1. Relationale Algebra

Im Kapitel 4 wurden Konzepte und Konzeptoperationen uber die relationale Alge-bra definiert. Die Ubersetzung eines Konzepts in einen Ausdruck der relationalenAlgebra ist daher direkt moglich. Die dort verwendeten Ubersetzungen sind im Fol-genden zusammengefaßt. Es gelten zudem verschiedene Aquivalenzen und moglicheOptimierungen, die ebenfalls im Folgenden beschrieben werden.

Im Folgenden seien C = (V, φ, P ), C ′ = (V ′, ψ, P ′) jeweils Konzepte zu einem be-liebigen, aber festen, passenden Schema σ. z ist ein ebenfalls beliebiger, aber festerZustand zu σ.

Zunachst kann jedes Konzept direkt in einen Ausdruck der relationalen Algebraubersetzt werden.

θz(C) = (./R∈V

z(R))[φ][P ]

Offensichtlich tragen hierbei Relationstypen V , deren Attribute weder in P noch inφ auftreten, nichts zum Ergebnis bei. Die Mengensemantik in Verbindung mit derabschließenden Projektion sorgt dafur, daß die durch das Kreuzprodukt entstehen-den Dopplungen fur die Ergebnisrelation keine Bedeutung haben. Wird also V wiefolgt reduziert:

W = {R | R ∈ V, ∃A ∈ R ∧ (A ∈ P ∨A ∈ att(φ))}

gilt entsprechend:

θz(C) = θz((W,φ, P ))

Entsprechendes gilt fur die komplexe Tupelzuordnung.

Die Projektion ist direkt analog zur Projektion der relationalen Algebra definiert.Fur eine Attributmenge Q ⊆ P gilt wie in 4.3 gezeigt:

θz(C[Q]) = θz(C))[Q]

34

4.5. Ubersetzung

Die Selektion wurde als direkt in einen Algebraausdruck ubersetzbar definiert. EinAusdruck φ′ uber den Attributen der Relationstypen aus V kann in einer Konjunk-tion an φ gebunden werden.

C[φ′] = (V, φ ∧ φ′, P )

Offensichtlich ist die Selektion damit auch als Mengenoperation ausdruckbar.

C[φ′] = (V, φ ∧ φ′, P ) ≡ (V, φ, P ) ∩ (V, φ′, P ) = C ∩ (V, φ′, P )

Dementsprechend folgt

θ(C[φ′]) = (./R∈V

z(R))[φ][P ] (4.27)

∩(./R∈V

z(R))[φ′][P ] (4.28)

Die Gegenrichtung, die Ubersetzung von Mengenoperationen in Selektionen ist je-doch im Allgemeinen nicht ohne Modifikation der beteiligten Konzepte moglich.Betrachte etwa die folgenden Konzepte:

D = ({R,S}, R.A = S.A, {R.A,R.B}), D′ = ({R, T}, R.B = T.B, {R.A,R.B})

Die Anwendung der Definition aus 4.3 liefert etwa fur D ∩D′

D ∩D′ = ({R,S, T}, R.A = S.A ∧R.B = T.B, {R.A,R.B})

Eine mogliche Ubersetzung in einen Ausdruck der relationalen Algebra ist damit

θz(D ∩D′) = ( ./X∈{R,S,T}

z(X))[R.A = S.A][R.B = T.B][P ]

Schnitt und Differenz konnen analog ubersetzt werden.Wie bereits in 4.3 beschrieben lassen sich damit Mengenoperationen auf zwei KonzeptenC = (V, φ, P ), C ′ = (V ′, ψ, P ) mit gleicher Projektion wie folgt ubersetzen. Hierunter Verwendung der naiven Ubersetzung:

θz(C ∩ C ′) = θz((V ∪ V ′, φ ∧ ψ, P )) (4.29)

= ( ./R∈V ∪V ′

z(R))[φ ∧ ψ][P ] (4.30)

θz(C ∪ C ′) = θz((V ∪ V ′, φ ∨ ψ, P )) (4.31)

= ( ./R∈V ∪V ′

z(R))[φ ∨ ψ][P ] (4.32)

θz(C − C ′) = θz((V ∪ V ′, φ ∧ ¬ψ, P )) (4.33)

= ( ./R∈V ∪V ′

z(R))[φ ∧ ¬ψ][P ] (4.34)

Alternativ konnen die Mengenoperationen der relationalen Algebra verwendet wer-den, was der komplexen Tupelzuordnung entspricht:

θz(C ∩ C ′) = θz(C) ∩ θ(C ′) (4.35)

θz(C ∪ C ′) = θz(C) ∪ θ(C ′) (4.36)

θz(C − C ′) = θz(C)− θ(C ′) (4.37)

35

4. Losungsentwurf

Fur den Join ist hingegen im Allgemeinen nur die in der Definition aufgefuhrteUbersetzung moglich, da im Falle disjunkter Projektionen der zu joinenden Konzepteunter Umstanden kein Kreuzprodukt entsteht. Das Beispiel in 4.3.7 belegt dies.Daher ist die Ubersetzung zweier Konzepte C = (V, φ, P ), C ′ = (V ′, ψ, P ′) imAllgemeinen wie folgt durchzufuhren:

θ(C ./ C ′) = θ((V ∪ V ′, φ ∧ ψ, P ∪ P ′)) (4.38)

Schließlich existieren fur die projizierende Vereinigung ebenfalls verschiedene Uber-setzungen. Fur zwei Konzepte C = (V, φ, P ), C ′ = (V ′, ψ, P ′) gilt etwa nach Defini-tion 4.3.8

θ(C ∪proj C ′) = θ((V ∪ V ′, φ ∨ ψ, P ∩ P ′)) (4.39)

= ( ./R∈V ∪V ′

z(R))[φ ∨ ψ][P ∩ P ′] (4.40)

Offensichtlich gilt hier

θ(C ∪proj C ′) = θ((V ∪ V ′, φ ∨ ψ, P ∩ P ′)) (4.41)

= θ((V ∪ V ′, φ, P ∩ P ′) ∪ (V ∪ V ′, ψ, P ∩ P ′)) (4.42)

Sind Konzepte aus Anfrageoperationen entstanden, kann bei der Ubersetzung en-tweder auf den entstehenden Konzepten oder direkt bei der formulierten Anfrageangesetzt werden.Im Folgenden werden nur Ubersetzungen fur Disjunktions-Semantik vorgeschlagen.Die Ergebnisse lassen sich jedoch fur die anderen Anfragesemantiken modifizieren.Es sei nun jeweils C = (V, φ, P ) das fur eine Anfrage verwendete Konzept und Qeine Anfrage der Form

Q = ({ψ1, . . . , ψn},P), n ∈ N

Wobei ψi, 1 ≤ i ≤ n, die in der i-ten Zeile formulierte Selektion und P ⊆ P die inder Anfrage formulierte Projektion ist.Unter Disjunktions-Semantik laßt sich dies direkt in folgenden Algebra-Ausdruckubersetzen:

θ(C[ψ1 ∨ . . . ∨ ψn][P]) = θ(C)[ψ1 ∨ . . . ∨ ψn][P] (4.43)

Allerdings kann es sinnvoll sein, zunachst Teilziele zu berechnen, und diese zu vere-inigen, um die Ergebnismenge zu bestimmen. Insbesondere im Hinblick auf einespatere Ubersetzung in SQL ist dies von Vorteil. So kann Q auf C auch aufgefaßtwerden als

θ(C[ψ1][P]) ∪ . . . ∪ θ(C[ψn][P]) = θ(C)[ψ1][P] ∪ . . . ∪ θ(C)[ψn][P] (4.44)

Da jede Zeile ein Tupel beschreibt, befinden sich die ψi, 0 < i ≤ n, zudem in konjunk-tiver Normalform. ψi hat also die Form ψ′i1∧ . . .∧ψ′iki , ki > 0. Falls gewunscht, kann

36

4.5. Ubersetzung

daher auch das logische UND hier als Schnitt ubersetzt werden, um einen starkerenFokus auf Mengenoperationen zu erreichen:

θ(C[ψ1][P]) ∪ . . . ∪ θ(C[ψn][P]) = θ(C)[ψ11][P] ∩ . . . ∩ θ(C)[ψ1k1 ][P] (4.45)

∪ (4.46)

. . . (4.47)

∪ (4.48)

θ(C)[ψn1][P] ∩ . . . ∩ θ(C)[ψ1kn ][P] (4.49)

Die Ubersetzung einer Aggregationsanfrage schließlich kann wie in 4.4.4 beschriebenerfolgen. Da Aggregationen auf Konzepten bereits als reine Operationen auf denzugehorigen Relationen definiert sind, sind alternative Ubersetzungen hier nichtnotwendig.

4.5.2. SQL

Um konzeptbasierte Anfragen auf relationalen Datenbanksystem auszuwerten, kanneine Ubersetzung von Konzepten und Konzeptoperationen in SQL-Ausdrucke ange-geben werden. Die Ubersetzungsfunktion trans uberfuhrt nach den folgenden Regelnein Konzept C = (V, φ, P ) in ein SQL-Statement.Fur die Elemente einer Relationsmenge eines Konzepts werden Tabellen und Sicht-en zugelassen. Es wird jedoch im Folgenden stets davon ausgegangen, daß V keine’unbeteiligten’ Relationen, also solche, deren Attribute weder in att(φ) noch in Pauftreten, enthalt. Diese Bedingung kann bei einer moglichen Implementierung le-icht durch einen geeigneten Generierungsvorgang oder eine entsprechende Vorverar-beitung sichergestellt werden.Im Gegensatz zu den bisher betrachteten Ubersetzungen in Ausdrucke der rela-tionalen Algebra muß die Multimengensemantik und das mogliche Auftreten vonNullwerten beachtet werden. Um moglichst nah an der ursprunglich definierten Se-mantik fur Konzepte zu bleiben, wird fur reine Konzeptubersetzungen Mengense-mantik durch DISTINCT und Mengenoperationen erzwungen. Erst bei Anfragefor-mulierungen wird Multimengensemantik verwendet, um bei Aggregationen zur An-frage passende Ergebnisse zu erzielen.Nullwerte spielen vor allem bei den im Folgenden vorgeschlagenen Optimierungeneine Rolle, da bestimmte Aquivalenzen durch das in SQL angewandte Nullwert-konzept nicht gelten. Bei den Ubersetzungen werden auftretende Probleme jew-eils im Einzelfall beschrieben. Die Relation ≡N beschreibt die Aquivalenz zweierFormulierungen unter Nullwertfreiheit. Treten Nullwerte auf, konnen Anfragen, die≡N -aquivalent sind, verschiedene Ergebnisse liefern.Dabei erzeuge die Funktion τ aus einer Menge eine Zeichenkette.Als Reprasentant von Relationstypen wird hier der Relationsbezeichner gewahlt.Fur Attributbezeichner wird Eindeutigkeit durch Voranstellen des zugehorigen Re-lationsbezeichners sichergestellt, als Reprasentant wird daher der zugehorige Re-lationsbezeichner gefolgt von einem Punkt und dem Attributbezeichner gewahlt.

37

4. Losungsentwurf

Boolesche Ausdrucke konnen in SQL-Syntax, durch Ersetzung von Junktoren undVergleichsoperatoren in ihre SQL-Variante, ubersetzt werden. Konstanten werden alseine ihnen entsprechende Zeichenkette eines geeigneten SQL-Datentyps dargestellt.

τ wird demnach wie folgt definiert. Bei einelementigen Mengen werden Mengenklam-mern aus Grunden der Ubersichtlichkeit ausgelassen.

τ(R) →R fur einen Relationsbezeichner R

τ(R.A) →R.A fur einen Attributbezeichner R.A

τ(=) →=

τ(6=) →<>τ(>) →>τ(≥) →>=

τ(<) →<τ(≤) →<=

τ(P ) →R1.A1 , . . . , Rn.Am fur eine Attributmenge

P = {R1.A1, . . . , Rn.Am},m, n ∈ Nτ(V ) →R1, . . . ,Rn fur eine Menge von Relationstypen

V = {R1, . . . , Rn}, n ∈ Nτ(R.A� S.B) →R.A τ(�) S.B fur zwei Atributbezeichner R.A, S.B

mit kompatiblen Wertebereichen.

Falls eine zu dom(R.A) und dom(S.B)

kompatible Ordnung definiert ist,

so ist � ∈ {=, 6=, <,≤, >,≥}ansonsten

� ∈ {=, 6=}τ(R.A� c) →R.A τ(�) c

τ(c�R.A) →c τ(�) R.A fur einen Atributbezeichner R.A,

c ∈ dom(R.A),

falls auf dom(R.A) eine Ordnung herrscht,

so ist � ∈ {=, 6=, <,≤, >,≥}ansonsten

� ∈ {=, 6=}τ(¬φ) →NOT (τ(φ)) fur einen booleschen Ausdruck

uber einfachen Vergleichsausdrucken φ

τ(φ ∧ ψ) →(τ(φ)) AND (τ(ψ)) fur zwei boolesche Ausdrucke

uber einfachen Vergleichsausdrucken φ, ψ

τ(φ ∨ ψ) →(τ(φ)) OR (τ(ψ)) fur zwei boolesche Ausdrucke

38

4.5. Ubersetzung

uber einfachen Vergleichsausdrucken φ, ψ

Mit τ kann nun die Funktion trans eingefuhrt werden, die ein Konzept C = (V, φ, P )in ein SQL-SELECT-Statement ubersetzt.

trans(C) = SELECT DISTINCT τ(P )FROM τ(V )WHERE τ(φ)

Diese Form der Ubersetzung wird im Folgenden als naive Ubersetzung bezeichnet.Das Konzept DU DRUG zu OpenVigil 3.2, das Inhaltsstoffe und Anwendungen en-tweder direkt oder uber Pharmaprodukte verbindet. Im Beispiel wird die naive Tu-pelzuordnung verwendet, das Resultat fur die komplexe Zuordnung ist uber SQL-Mengenoperationen entsprechend formulierbar:

DU DRUG = ({DRUGUSAGE, PHARMAPRODUCT, DRUG,

D APPL, PRODUCT},DRUGUSAGE.brandname =

PHARMAPRODUCT.brandname

∧ DRUGUSAGE.producer name =

PHARMAPRODUCT.producer name

∧ PHARMAPRODUCT.brandname =

PRODUCT.brandname

∧ PHARMAPRODUCT.producer name =

PRODUCT.producer name

∧ DRUG.drug name =

PRODUCT.drug name

∨DRUGUSAGE.drug seq =

D APPL.drug seq

∧ DRUG.drug name =

D APPL.drug name,

{DRUGUSAGE.drug seq, DRUG.drug name})

kann damit in folgenden SQL-Ausdruck ubersetzt werden.

SELECT DISTINCT DRUGUSAGE. drug seq , DRUG. drug nameFROM DRUGUSAGE, PHARMAPRODUCT, DRUG, D APPL, PRODUCTWHERE DRUGUSAGE. brandname = PHARMAPRODUCT. brandnameAND DRUGUSAGE. product name = PHARMAPRODUCT. product nameAND PHARMAPRODUCT. brandname = PRODUCT. brandnameAND PHARMAPRODUCT. product name = PRODUCT. product nameAND PRODUCT. drug name = DRUG. drug name

39

4. Losungsentwurf

OR DRUGUSAGE. drug seq = D APPL. drug seqAND DRUGUSAGE. drug name = DRUG. drug name

Allerdings wird hier schon ein Nachteil der naiven Ubersetzung deutlich. Das KonzeptDU DRUG ist offensichtlich aus einer projizierenden Vereinigung zweier Konzepteentstanden. Das erste verbindet DRUGUSAGE uber PHARMAPRODUCT mit DRUG, daszweite verbindet DRUGUSAGE uber D_APPL mit DRUG. Da jedoch die naive Uberset-zung auf einem Kreuzprodukt der beteiligten Relationen basiert und die Selektionauf oberster Ebene eine Disjunktion enthalt, muß fur die Anfrageauswertung hi-er eine sehr große Zwischenmenge erzeugt und aus dieser dann Duplikate entferntwerden.

Eine Formulierung wie

SELECT ∗FROM ( (SELECT DRUGUSAGE. drug seq , DRUG. drug name

FROM DRUGUSAGE, PHARMAPRODUCT, DRUG, PRODUCTWHERE DRUGUSAGE. brandname = PHARMAPRODUCT. brandnameAND DRUGUSAGE. product name

= PHARMAPRODUCT. product nameAND PHARMAPRODUCT. brandname = PRODUCT. brandnameAND PHARMAPRODUCT. product name

= PRODUCT. product nameAND PRODUCT. drug name = DRUG. drug name )

UNION(SELECT DRUGUSAGE. drug seq , DRUG. drug nameFROM DRUGUSAGE, DRUG, D APPLWHERE DRUGUSAGE. drug seq = D APPL. drug seqAND DRUGUSAGE. drug name = DRUG. drug name ) ) AS x

ist hier besser auswertbar, da nur kleinere Zwischenmengen ohne Kreuzprodukteerzeugt werden mussen. Diese Formulierung ist zudem naher an den fur die Erzeu-gung von DU DRUG verwendeten Operationen. Es ist daher sinnvoll die naive Uber-setzung um mogliche Ubersetzungen fur einzelne Operationen zu erweitern.

Eine der grundlegenden Optimierungen dieser Ubersetzung ist das Umwandeln vonJunktoren in Mengenoperationen, wie bereits in Abschnitt 4.5.1 erwahnt. Allerdingskann diese Optimierung, bei Auftreten von Nullwerten in den Werten der Attributeaus att(φ), zu nicht aquivalenten Ergebnissen fuhren.

Fur ein Konzept C = (V, φ∨ψ, P ) konnen also die Relationstypmengen W,W ′ ⊆ Vmit

W = {R | R ∈ V, ∃A ∈ R ∧ (A ∈ P ∨A ∈ att(φ))}

W ′ = {R | R ∈ V, ∃A ∈ R ∧ (A ∈ P ∨A ∈ att(ψ))}

gebildet werden. Die Reduktion der Menge der Relationstypen erlaubt dann folgendeUmformung der Ubersetzung:

trans(C) = SELECT DISTINCT τ(P )

40

4.5. Ubersetzung

FROM τ(W )WHERE τ(φ)UNIONSELECT DISTINCT τ(P )FROM τ(W ′)WHERE τ(ψ)

Durch die Reduktion der in den jeweiligen FROM-Klausel auftretenden Relationenwerden die Auswertungskosten in vielen Situationen stark reduziert.

4.5.2.1. Projektion

Fur die Projektion eines Konzepts C = (V, φ, P ) auf eine Attributmenge P ′ ⊆ P istneben τ(C[P ′]) auch die folgende Ubersetzung moglich:

trans(C[P ′]) ≡ SELECT DISTINCT τ(P ′)FROM trans(C) AS C

4.5.2.2. Selektion

Fur ein Konzept C = (V, φ, P ) und einen kompatiblen Vergleichsausdruck ψ kanndie Selektion C[ψ] wie folgt ubersetzt werden:

trans(C[ψ]) ≡ SELECT DISTINCT τ(P )FROM τ(V )WHERE (τ(φ))AND (τ(ψ))

Je nach Selektionskraft von ψ kann auch eine Ubersetzung in einen Schnitt sin-nvoll sein. Hier kann es jedoch zu nicht aquivalenten Ergebnismengen kommen, daMengenoperatoren Nullwerte beachtet, wahrend boolesche Ausdrucke in der WHERE-Klausel nach dreiwertiger Logik berechnet werden.Die Entscheidung fur eine Ubersetzungsstrategie hangt also stark von der jeweiligenSituation ab.

trans(C[ψ]) ≡N SELECT τ(P )FROM τ(V )WHERE τ(φ)INTERSECTSELECT τ(P )FROM τ(V )WHERE τ(ψ)

4.5.2.3. Schnitt

Der Schnitt C ∩ C ′ = (V ∪ V ′, φ ∧ ψ, P ), C = (V, φ, P ), C ′ = (V ′, ψ, P ), kann alsSQL-INTERSECT-Statement ubersetzt werden. Jedoch kann es auch hier aufgrundder Nullwertbehandlung in SQL zu nicht aquivalenten Ergebnissen kommen.

41

4. Losungsentwurf

trans(C ∩ C ′) ≡N trans(C)INTERSECTtrans(C ′)

4.5.2.4. Vereinigung

Die Vereinigung C ∪ C ′ = (V ∪ V ′, φ ∨ ψ, P ), C = (V, φ, P ), C ′ = (V ′, ψ, P ), kannanalog zum Schnitt als SQL-UNION-Statement ubersetzt werden. Jedoch kann eshier ebenfalls aufgrund der Nullwertbehandlung in SQL zu nicht aquivalenten Ergeb-nissen kommen.

trans(C ∪ C ′) ≡N trans(C)UNIONtrans(C ′)

4.5.2.5. Differenz

Als dritte Mengenoperation kann auch die Differenz zweier Konzepte C − C ′ =(V ∪V ′, φ∧¬ψ, P ), C = (V, φ, P ), C ′ = (V ′, ψ, P ), analog als SQL-MINUS-Statementubersetzt werden. Erneut konnen nicht aquivalente Ergebnismengen auftreten.

trans(C − C ′) ≡N trans(C)MINUStrans(C ′)

4.5.2.6. Join

Fur zwei Konzepte C = (V, φ, P ), C ′ = (V ′, ψ, P ′) kann der Join C ./ C ′ direktubersetzt werden. Es gilt also

trans(C ./ C ′) ≡ SELECT τ(P ∪ P ′)FROM τ(V ∪ V ′)WHERE (τ(φ))AND (τ(ψ))

Alternativ kann eine Ubersetzung nach der komplexen Tupelzuordnung gewahlt wer-den.

4.5.2.7. Projizierende Vereinigung

Ein aus einer projizierenden Vereinigung entstandenes Konzept kann erst nach ein-er Optimierung effizient ausgewertet werden. Das einfuhrende Beispiel dieses Ab-schnitts zeigt dies deutlich. Fur die projizierende Vereinigung zweier Konzepte C =(V, φ, P ), C ′ = (V ′, ψ, P ′), C ∪proj C ′ = (V ∪ V ′, φ∨ψ, P ∩P ′) ist das Auftreten vongroßen Zwischenergebnissen ein direkt aus der Definition der Operation hervorge-hendes Problem.Eine einfache Umformulierung macht dies deutlich:

42

4.5. Ubersetzung

trans(C ∪proj C ′) ≡N SELECT τ(P ∩ P ′)FROM τ(V ∪ V ′)WHERE τ(φ)UNIONSELECT τ(P ∩ P ′)FROM τ(V ∪ V ′)WHERE τ(ψ)

Erneut kann es hier zu Unterschieden in den Ergebnisrelationen kommen, falls dieAusgangsrelationen Nullwerte enthalten.

Da φ nur uber V , ψ nur uber V ′ selektiert, entspricht dies dem Algebra-Ausdruck

(θ(C)⊗ (V ′ − V ))[P ∩ P ′] ∪ (θ(C ′)⊗ (V − V ′))[P ∩ P ′]

Es kann daher sinnvoll sein, eine projizierende Projektion in Teilziele zu zerlegenund anschließend zu vereinigen:

trans(C ∪proj C ′) ≡N SELECT τ(P ∩ P ′)FROM τ(V )WHERE τ(φ)UNIONSELECT τ(P ∩ P ′)FROM τ(V ′)WHERE τ(ψ)

4.5.2.8. Anfrageauswertung

Ahnlich zu der fur die relationale Algebra angegebenen Ubersetzung, kann ein auseiner Anfrageformulierung entstandenes Konzept entweder direkt oder auf Grund-lage der Anfrage selbst ubersetzt werden. Erneut werden hier nur Anfragen inDisjunktions-Semantik betrachtet. Die im Folgenden vorgestellten Ubersetzungsmoglichkeit-en konnen leicht fur die drei anderen Semantiken angepaßt werden.

Wurde also zu einem Konzept C = (V, φ, P ) die Anfrage

Q = ({ψ1, . . . , ψn},P), n ∈ N

mit P ⊆ P und ψi, 0 < i ≤ n , die in der i-ten Zeile formulierte Selektionsbedingunguber C.

Bei Anfragen kann es zudem sinnvoll sein, die Entfernung von Duplikaten in derErgebnismenge explizit zu fordern. Im Folgenden werden die Teilanfragen, in de-nen die Duplikatentfernung vorgenommen werden muß, durch ?DISTINCT? markiert.Diese Zeichenkette ist in der gesamten Anfrage einheitlich durch DISTINCT oder denleeren String zu ersetzen.

Zunachst ist eine naive Ubersetzung moglich. Entsprechend der Disjunktions-Semantikkann C durch Q eingeschrankt und auf P projiziert werden.

43

4. Losungsentwurf

SELECT ?DISTINCT? τ(P)FROM τ(V )WHERE (τ(φ))AND (τ(ψ1)OR . . .OR τ(ψn))

Es ist jedoch haufig sinnvoller, Anfragen, wie bereits in 4.5.1 beschrieben, in Teilzielezu zerlegen und uber Mengenoperationen zu verbinden. Fur obige Anfrage lautet alsoeine alternative Ubersetzung, wie folgt.

WITHC AS(SELECT τ(P )FROM τ(V )WHERE τ(φ) ) ,

tmp AS(SELECT τ(P )FROM CWHERE τ(ψ1)

UNION

. . .

UNION

SELECT τ(P )FROM CWHERE τ(ψn))SELECT ?DISTINCT? τ(P)FROM tmp

Die verwendeten Bezeichner C und tmp sind dabei Relationsbezeichner, die nicht imSchema vorkommen.

Erneut kann es bei Nullwerten in den Tupeln der Relationen aus V zu Unterschiedenin den Ergebnismengen der beiden Ubersetzungen kommen.

Eine Aggregationsanfrage γ = (β, f,A, F ), wobei β = {B1, . . . , Bk} ⊆ P, k ∈N, die zu gruppierende Attributmenge, A ∈ P, f eine zu A kompatible SQL-Aggregatfunktion und F /∈ β ein Attributbezeichner. Zusatzlich kann eine SQLkompatible HAVING-Klausel H fur die Gruppierung β angegeben werden.

Erneut sind die beiden oben vorgestellten Ubersetzungen moglich. Zum einen dienaive Ubersetzung:

WITH C AS(SELECT ?DISTINCT? τ(P)

44

4.5. Ubersetzung

FROM τ(V )WHERE (τ(φ))AND (τ(ψ1)OR . . .OR τ(ψn) ) )

SELECT τ(β) , f(τ(A)) AS FFROM CGROUPBY τ(β)HAVING H

Zum anderen eine auf Mengenoperationen basierende:



UNION

. . .

UNION

SELECT τ(P )FROM CWHERE τ(ψn) ) ,

Q AS(SELECT ?DISTINCT? τ(P)FROM tmp)SELECT τ(β) , f(τ(A)) AS FFROM QGROUPBY τ(β)HAVING H

in beiden Versionen entfallen die GROUP BY- und HAVING-Klausel, falls β = ∅,beziehungsweise die HAVING-Klausel, falls H leer ist.

Entsprechend kann eine geschachtelte Aggregationsanfrage γ′ = (β′, f ′, A′, F ′, γ)und einem moglichen weiteren HAVING-Statement H ′ durch eine Erweiterung desWITH-Teils obiger Anfragen ubersetzt werden.

WITH C AS

45

4. Losungsentwurf

(SELECT ?DISTINCT? τ(P)FROM τ(V )WHERE (τ(φ))AND (τ(ψ1)OR . . .OR τ(ψn) ) ) ,

AG AS(SELECT τ(β) , f(τ(A)) AS FFROM CGROUPBY τ(β)HAVING H)

SELECT τ(β′) , f ′(τ(A′)) AS F ′

FROM AGGROUPBY τ(β′)HAVING H ’

oder



UNION

. . .

UNION

SELECT τ(P )FROM CWHERE τ(ψn) ) ,

Q AS(SELECT ?DISTINCT? τ(P)FROM tmp ) ,

AG AS(SELECT τ(β) , f(τ(A)) AS FFROM QGROUPBY τ(β)HAVING H)

46

4.6. Ausdruckskraft

SELECT τ(β′) , f ′(τ(A′)) AS F ′

FROM AGGROUPBY τ(β′)HAVING H ’

Bei C, Q, AG handelt es sich erneut um nicht belegte Bezeichner.

4.6. Ausdruckskraft

In diesem Abschnitt wird die Ausdruckskraft von konzeptbasierten Anfragen mit derder relationalen Algebra verglichen. Zunachst kann gezeigt werden, daß zu jedemAusdruck der Relationalen Algebra ohne Aggregation e zu einem Schema σ einKonzept Ce existiert, so daß in jedem Zustand z zu σ die Auswertung von e diegleichen Tupel enthalt wie θz(Ce).Da die in 4.3 definierten Operationen auf denen der relationalen Algebra basieren,liegt diese Annahme nahe. Allerdings ist auf Konzepten keine Umbenennung definiert,sondern nur vor der Konzepterzeugung vorgesehen. Es muß daher zunachst gezeigtwerden, daß e in eine Form gebracht werden kann, in der Umbenennungen nur aufRelationstypen des Schemas angewandt wird, nicht auf solchen, die durch Operatio-nen entstehen.

Beh.: Zu jedem Ausdruck der relationalen Algebra e, zu einem relationalen Daten-bankschema σ existiert ein Ausdruck e′, bei dem Umbenennung nur auf Relation-stypen des Schemas angewandt wird.Bew.: Sei σ ein relationales Datenbankschema und e ein Ausdruck der relationalenAlgebra zu σ. Betrachte die Funktion f , die einen Ausdruck der relationalen Algebraso umformt, daß Umbenennungen nur auf Relationstypen des Schemas angewandtwird. Sie sei wie folgt definiert:

(i) f((e′ � e′′)[A1 → B1, . . . , Ak → Bk])= f(e′[A1 → B1, . . . , Ak → Bk])� f(e′′[A1 → B1, . . . , Ak → Bk])Fur � ∈ {∪,∩,−}, e′, e′′ Ausdrucke der relationalen Algebra und[A1 → B1, . . . , Ak → Bk] einer Umbenennung von e′ � e′′.

(ii) f((e′ ./ e′′)[A1 → B1, . . . , Ak → Bk])= f(e′[C]) ./ f(e′′[D])Fur e′, e′′ Ausdrucke der relationalen Algebra,[A1 → B1, . . . , Ak → Bk] einer Umbenennung von e′ ./ e′′ undC = {A→ B | A→ B ∈ {A1 → B1, . . . , Ak → Bk}, A ∈ αe′}D = {A→ B | A→ B ∈ {A1 → B1, . . . , Ak → Bk}, A ∈ αe′′}

(iii) f(e′[φ][A1 → B1, . . . , Ak → Bk])= f(e′[A1 → B1, . . . , Ak → Bk])[φ[A1 → B1, . . . , Ak → Bk]]Fur einen Ausdruck der relationalen Algebra e′,φ einem Selektionsausdruck uber e′ und

47

4. Losungsentwurf

[A1 → B1, . . . , Ak → Bk] einer Umbenennung von e′[φ].φ[A1 → B1, . . . , Ak → Bk] sei dabei die Selektionsbedingung, die aus φ durchUmbenennung gemaß [A1 → B1, . . . , Ak → Bk] entsteht.

(iv) f(e′[C][A1 → B1, . . . , Ak → Bk]) = f(e′[A1 → B1, . . . , Ak → Bk])[D]Fur einen Ausdruck der relationalen Algebra e′,C ⊆ αe′ einer Attributmenge, die eine Projektion induziert,[A1 → B1, . . . , Ak → Bk] einer Umbenennung von e′[C] undD = {B | A→ B ∈ {A1 → B1, . . . , Ak → Bk}, A ∈ C}. D entsteht also durchAnwendung der Umbenennung auf die Projektion.

(v) f(e′[C1 → D1, . . . , Cl → Dl][A1 → B1, . . . , Ak → Bk]) = f(e′[U ])Fur einen Ausdruck der relationalen Algebra e′,[C1 → D1, . . . , Cl → Dl] einer Umbenennung von e′,[A1 → B1, . . . , Ak → Bk] einer Umbenennung von e′[C1 → D1, . . . , Cl → Dl]undU = {C → D | C → D ∈ {C1 → D1, . . . , Cl → Dl},¬∃D → B ∈ {A1 →B1, . . . , Ak → Bk}}∪{C → B | C → D ∈ {C1 → D1, . . . , Cl → Dl}, D → B ∈ {A1 →B1, . . . , Ak → Bk}}

(vi) f(R[A1 → B1, . . . , Ak → Bk]) = R[A1 → B1, . . . , Ak → Bk]Fur R ∈ σ und [A1 → B1, . . . , Ak → Bk] einer Umbenennung von R.

(vii) f(R) = RFur R ∈ σ.

Jeder Ubersetzungsschritt durch f fuhrt zu aquivalenten Ausdrucken:zu (i): Offensichtlich gilt hier die Aquivalenz, da die Projektion der beiden Teilaus-drucke gleich ist und die Umbenennung auf beiden angewandt wird.zu (ii): Hier wird die Umbenennung auf die beiden Teilausdrucken aufgeteilt. DieJoinbedingung bleibt also erhalten, die Aquivalenz gilt entsprechend.zu (iii): Da die Umbenennung auf die Selektionsbedingung angewandt wird, gilt auchhier Aquivalenz.zu (iv): Die Anpassung der Projektion ermoglicht die Ausfuhrung der Umbenennungvor der Selektion. Die Aquivalenz gilt entsprechend.zu (v): Die zwei Umbenennungsoperationen werden hintereinander ausgefuhrt. Dader ursprungliche Ausdruck korrekt ist, treten bei der Hintereinanderausfuhrungkeine Konflikte auf.zu (vi): In diesem Fall ist f = id.zu (vii): In diesem Fall ist f = id.Fur jeden Ausdruck e liefert f(e) also einen aquivalenten Ausdruck. Offensichtlichtreten in f(e) Umbenennungen nur auf Relationstypen des Schemas auf, es folgt dieBehauptung.

q.e.d.

48

4.6. Ausdruckskraft

In Kapitel 4.3 wurde bereits gezeigt, daß fast alle Konzeptoperationen analog zuOperationen der relationalen Algebra angewandt werden konnen. Einzig im Falle desJoins kann die Ubersetzung bei bestimmten Operandenkombinationen problematischwerden. In 4.3 ist dieses Problem als interner Zusammenhang diskutiert.

Es kann nun der folgende Beweis formuliert werden.

Beh.: Zu jedem Ausdruck der relationalen Algebra e zu einem Schema σ, der keinKreuzprodukt enthalt, existiert ein Konzept Ce, das zu σ paßt, so daß gilt z(e) =θz(Ce).

Bew.: In einem ersten Schritt wird ein Ausdruck e′ erzeugt, indem jeder in e auftre-tende Join wie folgt in ein Kreuzprodukt mit anschließender Selektion umgeformt:Ersetze jeden Join der Form

A ./ B

in e durch

(A[αA → r(αA)] ./ B[αB → s(αB)])[∧

a∈αA∩αB

r(a) = s(a)]

[r(αA) ∪ s(αB \ αA)]

[r(αA)→ αA]

[s(αB \ αA)→ (αB \ αA)]

[α → r(α)] und [α → s(α)] fur eine Attributmenge α, stehe fur die Umbenennungjedes Attributes aus α in einen innerhalb von e eindeutigen Attributbezeichner. Einsolcher kann etwa unter Nutzung der Position des jeweiligen Join innerhalb derBaumdarstellung von e und des Symbols r beziehungsweise s erzeugt werden.

[r(α) → α] beziehungsweise [s(α) → α] stehe fur die Umkehrung dieser Umbenen-nung. Jeder Join wird also durch ein Kreuzprodukt von Relationen mit umbenanntenAttributen, die in den ursprunglichen Joinattributen Wertgleich sind, ersetzt. DieAttributmenge dieser Kreuzprodukte wird durch Projektion und Umbenennung aufdie ursprungliche Attributmenge des Joins gebracht.

Erzeuge nun aus e′ den Ausdruck e′′ = f(e′), mit der Funktion f aus dem vorherge-henden Beweis. In e′′ tritt Umbenennung nur auf Relationstypen des Schemas aufund es wird kein Kreuzprodukt als Teilziel generiert, daß zu Ungleichheiten im Sinnedes internen Zusammenhangs fuhrt.

Betrachte nun den e′′ reprasentierenden Operationsbaum. Seine Blatter sind Rela-tionen des Schemas. Ihre Attribute werden, nach Definition von f , hochstens einmalumbenannt. Ersetze nun jede Relation, auf die eine Umbenennung folgt, durch eineRelation, die durch Umbenennung aus ihr entsteht. Benenne die Relationen dabeiso um, daß Relationen, die nach der Umbenennung jeweils Relationen mit gleicherAttributmenge erzeugen, den gleichen Bezeichner erhalten.

Bezeichne den entstehenden Ausdruck als e∗. e∗ baut auf Relationen auf, die ausRelationen des Schemas durch Umbenennung entstehen, falls die entsprechende Re-lation des Schemas in e an einem Join beteiligt war. In e∗ sind zudem jene Relationen

49

4. Losungsentwurf

gleich benannt, die eine gleiche Attributmenge haben. Der Fall, daß Relationen aneinem Join beteiligt sind, die durch Umbenennung oder Projektion aus der selbenBasisrelation entstehen, dies sind genau diejenigen, die zu Ungleichheiten im Sinnedes internen Zusammenhangs fuhren, tritt also in e∗ nicht auf.Betrachte nun die Funktion g, die Ausdrucke der relationalen Algebra in Konzepteubersetzt und wie folgt definiert ist:

(i) g(R) = ({R}, true, αR)Fur einen Relationstypen des Schemas R ∈ σ oder einen Relationstypen R, deraus einem Relationstypen R′ ∈ σ durch Umbenennung entsteht.

(ii) g(R[A1 → B1, . . . , Ak → Bk]) = ({R′}, true, αR′)Fur einen Relationstypen des Schemas R ∈ σund R′ = R[A1 → B1, . . . , Ak → Bk].

(iii) g(A�B) = g(A)� g(B)Fur � ∈ {∪,∩,−} und A,B Ausdrucke der relationalen Algebra.Es gilt z(A�B) = θ(g(A)�g(B)) wie in der Definition der Mengenoperationenauf Konzepten in 4.3 gezeigt.

(iv) g(A ./ B) = (g(A)[∧

a∈αA

a = a]) ./ (g(B)[∧

b∈αB

b = b])

Fur A,B Ausdrucke der relationalen Algebra.Aufgrund der Reduzierung ’unbeteiligter’ Relationen eines Konzepts bei derTuplezuordnung, mussen hier Tautologien an die Selektion angehangt werden,um das Verhalten des Joins bei disjunkten Attributmengen und leeren Rela-tionen zu simulieren.Da bereits in 4.1 vorausgesetzt wurde, daß keine Nullwerte in den Zustandenvon σ auftreten, gilt z(A ./ B) = (g(A)[

∧a∈αA

a = a]) ./ (g(B)[∧

b∈αB

b = b]).

Wie bereits gezeigt wurde, fuhrt der interne Zusammenhang von Konzeptenhier nicht zu Ungleichheiten.

(v) g(A[A1, . . . , Ak]) = g(A)[A1, . . . , Ak]Fur einen Ausdruck der relationalen Algebra A und eine zugehorige Projektion[A1, . . . , Ak].Die Gleichheit wurde bereits in 4.3 gezeigt.

(vi) g(A[φ]) = g(A)[φ]Fur einen Ausdruck der relationalen Algebra A und eine zugehorige Selektion[φ].Auch hier wurde die Gleichheit bereits in 4.3 gezeigt.

Fur jeden Ausdruck e liefert g(e∗) also ein Konzept Ce, so daß z(e) = θz(Ce).

q.e.d.

50

4.7. Weiterfuhrende Betrachtung

Auf der anderen Seite sind Konzeptanfragen auf endliche, nicht-rekursive Anfragenbeschrankt. Soll etwa zu einem Ersatzteil aus 3.3 die Menge aller zum Bau benotigtenTeile bestimmt werden, so ist eine Rekursions- oder Fixpunktoperation notwendig.

Auch die relationale Algebra mit Aggregationsoperation ist offensichtlich Ausdrucks-starker, als Konzeptanfragen mit Aggregation. Da in Ausdrucken der Algebra ausAggregationen entstehende Relationen in komplexeren Ausdrucken verwendet wer-den kann.

Betrachte etwa den folgenden Ausdruck zum Bankbeispiel 3.4:

(Γ((ACCOUNT ./ CUSTOMER)[CUSTOMER.cust no = ACCOUNT.cust no],

{CUSTOMER.cust no},SUM, ACCOUNT.balance, sum acc}./

Γ((LOAN ./ CUSTOMER)[CUSTOMER.cust no = LOAN.cust no],

{CUSTOMER.cust no},SUM, LOAN.amount, sum loan})[sum loan ≤ sum acc]

Es wird hier bestimmt, welche Kunden einen Gesamtkredit fuhren, der kleiner ist,als die Summe seiner Kontostande. Zwei aus Aggregationen entstehende Relationenwerden gejoint und anschließend eine Selektion ausgefuhrt. Da bei Konzeptanfragendie Aggregation stets die letzte Operation ist, kann es keine aquivalente, konzept-basierte Formulierung geben.


4.7.1. Zur Notwendigkeit eindeutiger Attributbezeichner

Als notwendige Voraussetzung fur eine konzeptbasierte Behandlung von relationalenSchemata wurde die Eindeutigkeit von Attributbezeichnern uber alle Relationstypendes Schemas gefordert. Um dies weiter zu diskutieren, kann zunachst ein Versuchunternommen werden, Konzepte unter Auslassung dieser Forderung zu definieren.

Wie erwahnt, sollte ein Konzept eine Menge von Objekten innerhalb des in einemSchema enthaltenen Wissens beschreiben. Fur ein Konzept C = (V, φ, P ) heißt dies,daß Werte aus den Elementen von V relevant sind, daß C Objekte beschreibt, dieuber Eingenschaften verfugen, die durch Attribute aus P abgebildet werden und daßdiese Objekte sich durch Erfullen des Pradikats φ von allen Objekten aus (V, true, P )unterscheiden. Ist keine Eindeutigkeit von Attributbezeichnern gegeben, so kanndiese Vorstellung jedoch nicht mehr angewendet werden. Es sei etwa das folgenderelationale Schema σ gegeben, das eine Bestellubersicht abbildet.

σ = ({ (KUNDE, { id , name} , { id } ) ,(ARTIKEL, { id , bezeichnung , p r e i s } , { id } ) ,

51

4. Losungsentwurf

(BESTELLUNG, {k id , a id , menge} , {k id , a id } )} ,{BESTELLUNG[ k id ] ⊆ KUNDE[ id ] ,BESTELLUNG[ a id ] ⊆ ARTIKEL[ id ] } )

Offensichtlich sind die Attributmengen der Relationstypen nicht disjunkt. Die Defi-nition aus 4.1 sei fur die folgende Betrachtung entsprechend erweitert. Es soll zudemnicht, nach dem dort beschrieben Verfahren, eine Eindeutigkeit hergestellt werden.

Sind Kunden und von ihnen bestellte Artikel gesucht, so wird ein Konzept KAgefordert, das folgende Anforderung abbildet:

Informationen uber KUNDEN und ARTIKEL, die uber BESTELLUNG verbunden sind.

Nach oben beschriebenem Vorgehen sind also alle drei Relationen am KonzeptKA beteiligt, jedoch sind nur Attribute von KUNDE und ARTIKEL gefordert. Daszu erfullende Pradikat ist hier KUNDE.id = BESTELLUNG.k_id ∧ ARTIKEL.id =BESTELLUNG.a_id. KA konnte demnach als

KA = ({ARTIKEL,BESTELLUNG,KUNDE},KUNDE.id = BESTELLUNG.k id ∧ARTIKEL.id = BESTELLUNG.a id,

{id, name, bezeichnung, preis})

formuliert werden. Jedoch wird hier schon deutlich, daß durch die Mengeneigenschaftder Projektion KUNDE.id und ARTIKEL.id nicht mehr unterscheidbar ist.

Auch die Auswertung auf einem passenden Zustand z ist hier nicht eindeutig moglich,denn um die oben geforderte Semantik zu erhalten ist ein Kreuzprodukt aus KUNDE,BESTELLUNG und ARTIKEL notwendig. Jedoch ware hier X = KUNDE ⊗ BESTEL-LUNG ⊗ ARTIKEL nur formulierbar, wenn fur ⊗ eine einheitliche, implizite Um-benennung angenommen wird, da ansonsten die Attributmenge des Ergebnisses αXnicht eindeutig definiert ware.

Entsprechend mußte also, falls eine Umbenennung etwa von ARTIKEL.id nach id’und von KUNDE.id nach id” angenommen wird, AK wie folgt geandert werden:


{id”, name, id’, bezeichnung, preis})

In diesem Fall ware jedoch eine explizite und sinnvollere Umbenennung, etwa inArtikelnummer und Kundennummer, sehr viel hilfreicher und auch naher an derKonzeptidee. Jedoch ware eine solche Umbenennung auch vor der Konzepterstel-lung moglich, nach universal relation assumption [FMU82] sogar schemaweit undohne Informationsverlust, was wieder zu der ursprunglich geforderten Eindeutigkeitvon Attributbezeichnern fuhrt.

Alternativ mag die Redefinition von θ denkbar erscheinen. Wird statt des Kreuzpro-duktes der Join verwendet, um Tupel Konzepte zuzuordnen entfallt die Problematik

52


einer impliziten Umbenennung beim Kreuzprodukt. Fur ein Konzept C = (V, φ, P )also:

θz(C) = ./R∈V

(z(R))[φ][P ]

Dies fuhrt jedoch ebenfalls zu keiner sinnvollen Definition. So ware etwa im Allge-meinen fur obiges C und einen Relationstyp R /∈ V

C = (V, φ, P ) 6≡ (V ∪R,φ, P )

da R eine selektierende Wirkung hat, falls ein S ∈ V existiert mit αR ∩ αS 6=∅. Zudem ist in diesem Fall die ursprungliche Forderung, namlich, daß KonzepteObjekte entsprechend ihrer Konstruktion beschreiben, verletzt. Schon obiges Beispielzeigt dies.


{id, name, bezeichnung, preis})

θz(AK) liefert hier nur solche Kunden, die Artikel bestellt haben, deren Artikelnum-mer ARTIKEL.id mit ihrer eigenen Kundennummer KUNDE.id ubereinstimmen, dadie Join-Operation KUNDE und ARTIKEL uber id verbindet. Was naturlich nicht dergeforderten Bedeutung von KA entspricht.

4.7.2. Verbandseigenschaft von Konzepten

Ein Verband, etwa [Ber12], ist eine algebraische Struktur (V,t,u). V ist dabei einenicht-leere Tragermenge und t,u : V → V sind Infix-Operationen, die fur allea, b, c ∈ V die folgenden Verbandsaxiome erfullen:

(i) a t (b t c) = (a t b) t c

(ii) a u (b u c) = (a u b) u c

(iii) a t b = b t a

(iv) a u b = b u a

(v) (a t b) u a = a

(vi) (a u b) t a = a

Es kann nun gezeigt werden, daß unter Verwendung der Aquivalenz als Gleichheit-srelation die Menge aller Konzepte zu einem relationalen Datenbankschema mit denOperationen Join und Projizierende Vereinigung einen Verband bildet. Hieraus fol-gt dann direkt, daß jede nicht-leere Teilmenge dieser Menge mit den OperationenSchnitt und Vereinigung ebenfalls einen Verband bildet. Der Beweis hierzu verlauft

53

4. Losungsentwurf

direkt entlang der Verbandsaxiome sowie der Definitionen der Konzeptoperationen.

Beh.: Die Menge Cσ aller Konzepte zu einem Datenbankschema σ bildet mit denOperationen Join und Projizierende Vereinigung den Verband (Cσ,∪proj, ./), soferndie Konzeptaquivalenz als Gleichheitsrelation verwendet wird.

Bew.: Sei also σ ein beliebiges, aber festes relationales Datenbankschema und Cσdie Menge aller zu σ mittels der Konzeptoperationen erzeugbaren Konzepte. Seienferner a = (Va, φa, Pa), b = (Vb, φb, Pb), a = (Vc, φc, Pc) ∈ Cσ Konzepte zu σ. Zuzeigen ist, daß die Verbandsaxiome in (Cσ,∪proj, ./) erfullt sind.zu (i):

a ∪proj (b ∪proj c) = a ∪proj (Vb ∪ Vc, φb ∨ φc, Pb ∩ Pc) (4.50)

= (Va ∪ Vb ∪ Vc, φa ∨ φb ∨ φc, Pa ∩ Pb ∩ Pc) (4.51)

= (Va ∪ Vb, φa ∨ φb, Pa ∩ Pb) ∪proj c (4.52)

= (a ∪proj b) ∪proj c (4.53)

zu (ii):

a ./ (b ./ c) = a ./ (Vb ∪ Vc, φb ∧ φc, Pb ∪ Pc) (4.54)

= (Va ∪ Vb ∪ Vc, φa ∧ φb ∧ φc, Pa ∪ Pb ∪ Pc) (4.55)

= (Va ∪ Vb, φa ∧ φb, Pa ∪ Pb) ./ c (4.56)

= (a ∪proj b) ./ c (4.57)

zu (iii):

a ∪proj b = (Va ∪ Vb, φa ∨ φb, Pa ∩ Pb) (4.58)

=Komm. Mengenop. und log. Op.

b ∪proj a (4.59)

zu (iv):

a ./ b = (Va ∪ Vb, φa ∧ φb, Pa ∪ Pb) (4.60)

=Komm. Mengenop. und log. Op.

b ./ a (4.61)

zu (v):

(a ∪proj b) ./ a = (Va ∪ Vb, φa ∨ φb, Pa ∩ Pb) ./ a (4.62)

= (Va ∪ Vb ∪ Va, (φa ∨ φb) ∧ φa, Pa ∩ Pb ∪ Pa) (4.63)

= (Va ∪ Vb, φa, Pa) (4.64)

≡ a (4.65)

zu (vi):

(a ./ b) ∪proj a = (Va ∪ Vb, φa ∧ φb, Pa ∪ Pb) ∪proj a (4.66)

= (Va ∪ Vb ∪ Va, φa ∧ φb ∧ φa, (Pa ∪ Pb) ∩ Pa) (4.67)

= (Va ∪ Vb, φa, Pa) (4.68)

≡ a (4.69)

54


q.e.d.

In obigem Beweis entspricht fur den Spezialfall Va = Vb = Vc der Join der Schnitt-operation und die Projizierende Vereinigung der Vereinigung. Es folgt also, daß fureinen Verband (Cσ,∪proj, ./) zu einen relationalen Datenbankschema σ, jede Teil-menge C ⊆ Cσ, mit Px = Py fur alle x = (Vx, φx, Px), y = (Vy, φy, Py) ∈ C, einenVerband (C,∪,∩) bildet.

55

5. Vergleichbare Arbeiten

Bei der Betrachtung vergleichbarer Arbeiten sollte zunachst Query-by-Example,[Zlo77], erwahnt werden. Da die in dieser Arbeit vorgeschlagene Anfrageformulierungauf Konzepten ahnlich zu QbE definiert ist. QbE ist eine Anfragesprache, die aufder Ubersetzung von Beispielmustern in Anfragen basiert. QbE-Anfragen konnenin SQL-Statements ubersetzt werden, es existieren etwa Implementierungen vonIBM innerhalb der DB2 Query Management Facility (http://www-03.ibm.com/software/products/en/qmf).

Allerdings liegt der Fokus von QbE nicht auf der Generierung von Anfrageschnitt-stellen. Eine Anfrage in QbE wird formulierte, um direkt ausgewertet zu werden,nicht um daraus wiederverwendbare Schnittstellen zu erzeugen. Zudem werden An-fragen in QbE auf Elementen des Datenbankschemas formuliert, was Kenntnisse desSchemas beim Benutzer voraussetzt.

Da ein Konzept als Konstruktionsvorschrift fur eine universal relation der enthal-tenen Relationstypen betrachtet werden kann, kann der hier vorgestellt konzept-basierte Ansatz auch mit UR-Sprachen verglichen werden. In [BB83] etwas wirdeine auf QUEL basierende Anfragesprache vorgeschlagen. Zur Generierung der zu-grundeliegenden UR werden Join-Pfade genutzt, die festlegen entlang welcher Rela-tionstypen Joins durchgefuhrt werden. Dieser Ansatz bietet den von UR bekanntenVorteil, Daten als zusammenhangenden Datensatz, etwa als Tabellenzeile, darstell-bar zu machen. Im Gegensatz zum konzeptbasierten Ansatz werden in [BB83] jedochkeine Operationen fur die Kombination von Join-Pfaden beschrieben.

Auch der Ansatz graphischer Anfrageeditoren sollte hier erwahnt werden. Eine Viel-zahl von Systemen bietet eine graphische Darstellung des Datenbankschemas alsBasis fur Anfrageformulierungen. Das in [KK95] vorgestellte NQS-System etwa nutztdie network query language in Kombination mit einer graphischen Darstellung desSchemas. Der Benutzer definiert Pfade innerhalb des Datenbankschemas und stelltBedingungen an die zu diesen Pfaden erzeugbaren Tupel. Anfragen konnen geschach-telt und um Funktionsausdrucke erweitert werden.

Allerdings setzt die Anfrageformulierung mit Hilfe graphischer Editoren voraus, daßdem Anwender die Struktur des Schemas vertraut ist, er etwa in der Lage ist, Kreiseim Schema korrekt zu interpretieren.

In [TCY92] wird ein Ansatz beschrieben, naturlichsprachliche Anfrageformulierun-gen in Konstrukte des Entity-Relationship-Modells und schließlich Ausdrucke derrelationalen Algebra zu uberfuhren.

Im dort vorgestellten Verfahren, werden Anfragen in naturlicher Sprache zunachstanalysiert. Entsprechend des Satzbaus werden die in der Anfrage verwendeten Kon-strukte, etwa Subjekt, Verb, Objekt, mit Hilfe eines Worterbuchs auf Entitaten

57

http://www-03.ibm.com/software/products/en/qmf

http://www-03.ibm.com/software/products/en/qmf

5. Vergleichbare Arbeiten

und Relationen des zugrundeliegenden Schemas sowie Selektionen abgebildet. Dasverwendete ER-Modell wird dabei um Elemente erweitert, die Quantifizierung undNegation von Relationships erlauben. In dieser Form beschreibt die transformierteAnfrage eine Menge von Pfaden in der erweiterten Form des Schemas. Abschließendwerden Ubersetzungsvorschriften angegeben, nach denen die Pfadbeschreibungen inAusdrucke der relationalen Algebra ubersetzt werden konnen.Die Ubersetzung naturlichsprachlicher Anfrageformulierungen liegt nicht im Fokusdieser Arbeit, und [TCY92] beschreibt keine Implementierung. Zudem liegt derFokus dort eher auf der dynamischen Ubersetzung von Anfragen, statt auf Gener-ierung von Anfrageschnittstellen. Doch ahnelt der Ansatz sprachlich formulierteAnfragen in Pfadinformationen zu transformieren, die eine einfache Ubersetzung inAusdrucke der relationalen Algebra, und damit auch in SQL-Statements, ermoglicht,der Verwendung von Konzepten zur Abstraktion von Elementen des Schemas. Die in[TCY92] vorgestellte logical form beschreibt unter anderem eine Menge von Entitiesund Relationships und deren Verknupfung. Sie ist darin einem Konzept nicht unahn-lich. Jedoch entfallt bei der Anfrageformulierung uber Konzepte die Notwendigkeitdas ER-Modell zu erweitern, da das Konzept selbst eine Konstruktionsvorschrift furTupel, und damit direkt in einen Ausdruck der relationalen Algebra ubersetzbar ist.Auch der in [Tha04] beschriebene Ansatz der view-suites ahnelt in Grundzugenden hier beschriebenen Konzepten. Bei view-suites werden Ansatze aus dem Bere-ich der objektorientierten Programmierung auf Sichten ubertragen. Statt eine Sichtals einen Relationstypen, der durch eine Anfrage aus Relationstyp eines Schemasentsteht, zu betrachten, wird eine view-suite hier als Objekt im Sinne der objektori-entierten Programmierung interpretiert. Eine view-suite beschreibt eine Menge vonDatenbank-Objekten, die ihre Basis bilden, eine Integrationsvorschrift, nach der diereprasentierte Information in das Schema einzubinden ist und eine Reihe von Zu-sicherungen, die sicherstellen, daß der Inhalt der view-suite bei Anderungen an denBasisobjekten stets aktuell gehalten wird.Erweitert wird dieser Ansatz, erneut im Sinne der objektorientierten Programmierung,durch die Erweiterung von view-suites um Methoden, sogenannten services. Sie kon-nen fur die Verarbeitung der in der View enthaltenen Daten genutzt werden.Statt eine große Zahl von Sichten fur die jeweiligen Einsatzzwecke zu generieren, wirdalso eine view-suite erstellt, die, unter verschiedenen Interfaces angesprochen, jeweilsgemaß ihrer Integrationsvorschrift Informationen liefert. Werden also beim konzept-basierten Ansatz komplexe Konzepte durch die Kombination von Basiskonzeptenerzeugt, auf denen dann Anfragen formuliert werden konnen, beschreiben view-suiteseine Menge von Sichten, die nach vorgegebenen Operationen fur ebenso vorgegebeneSchnittstellen Informationen bereitstellen. Der Vorteil dieser Herangehensweise liegtdarin, daß eine view-suite als Ganzes entworfen werden kann, wahrend Konzepte imAllgemeinen bottom-up aus Basiskonzepten zusammengestellt werden.Allerdings wird in [Tha04] kein existierendes System erwahnt, daß auf den angegebe-nen Definitionen basiert. Auch Implementierungsdetails oder Ubersetzungen in SQL-Statements werden nicht erwahnt.

58

6. Implementierung

Im Rahmen dieser Arbeit wurde eine Implementierung der in Kapitel 4 beschriebe-nen Anfragesprache erstellt. In dem folgenden Kapitel wird die Implementierung aufeiner hohen Ebene beschrieben.Das Programm bietet eine Webschnittstelle, die die Auswahl von Konzepten und dieFormulierung von Anfragen entsprechend 4.4 erlaubt. In eine dynamisch generierteAnfragemaske konnen Einschrankungen und ein Aggregations-Ausdruck formuliertwerden, die dann vom System als Selektion des Konzepts interpretiert werden.Konzept, Selektion und Aggregation werden dann gemaß 4.5.2 in SQL-Statementstransformiert und auf der zugrundeliegenden Datenbank ausgewertet. Schließlichwerden die resultierenden Datenbanktupel in eine Darstellungsform uberfuhrt, dieder Anfragemaske entspricht und dem Benutzer als Ergebnis prasentiert.Privilegierten Benutzern steht eine ebenfalls webbasierte Schnittstelle zur Verfugung,die den Import von Datenbanktabellen erlaubt. Diese konnen als Grundlage verwen-det werden, um Konzepte fur die Anfragekomponente zu erstellen. Hierbei werdenauf den Definitionen aus 4.3 basierende Operationen verwendet. Das System gener-iert dann aus dem von Benutzer formulierten Ausdruck eine Konzeptbeschreibung,die in der Datenbank zur Verwendung fur Anfragen abgelegt wird.

6.1. Grundlegende Architektur

Aus den Anforderungen an das zu erstellende System geht bereits ein grober Ar-chitekturentwurf hervor. Bei der zu verwendenden Datenbank handelt es sich umein postgresql-DBMS, die Losung soll webbasiert entworfen werden und die unterKapitel 4 beschriebene Anfragesprache verwenden.Es mussen also webbasierte Benutzerschnittstellen zur Verfugung gestellt werden, diees ermoglichen, die in der Datenbank vorhandenen Tabellen und Sichten in Konzeptezu uberfuhren und diese zu speichern. Zudem muß ein Interface angeboten werden,das die Kombination solcher Konzepte nach den unter Kapitel 4 definierten Opera-tionen erlaubt.Die so erzeugten Konzepte konnen in einer geeigneten Form gespeichert und alsSichten fur Anfragen bereitgestellt werden.Da die Erstellung von Konzepten Benutzern mit entsprechender Berechtigung vor-behalten sein soll, muß das System zudem uber eine Benutzerverwaltung verfugen.Das eigentliche Anfrageinterface kann ahnlich zu der in 4.4 vorgeschlagenen Darstel-lung aus den Konzepten generiert werden. Da diese auf den Relationen und At-tributen der Konzept-Projektion gebildet wird, ist eine dynamische Generierungunter Nutzung der vorliegenden Konzeptdefinitionen moglich.

59

6. Implementierung

Diese Front- beziehungsweise Backend-Schnittstellen werden browserbasiert nachdem MVC-Muster implementiert. Fur Darstellung und Kommunikation zwischenBrowser und Server wird das JSF-Framework in Version 2.0 verwendet. Server-seitigverarbeitet eine in drei Schichten modellierte Anwendung die Client-Anfragen, uber-setzt Operationen und Anfragen auf Konzepten in entsprechende SQL-Ausdruckeund wertet diese auf der existierenden Datenbank aus.

Es ist hierbei keine starke Kopplung zwischen dem geplanten Anwendungsfall undder entwickelten Software vorhanden. Die notwendigen Anforderungen, etwa ein JSF2.0 fahiger Applicationcontainer und eine geeignetes relationales Datenbankmanage-mentsystem, sind technischer Natur, der Einsatz des Programms selbst, erfordertnur eine initiale Konfiguration. Modifikationen des Codes fur die Verwendung mitunterschiedlichen Datenbankschemata sind nicht notwendig.

6.2. Uberblick uber die Schichten der Serversoftware

Die Software ist in drei Schichten implementiert: Database-Layer, Logic-Layer undPresentation-Layer. Jede Schicht stellt Dienste fur die jeweils hohere Schicht bereit.Die Kommunikation zwischen den Schichten, sprich die Methodenaufrufe, die vonKlassen einer Schicht an die darunter liegende Schicht gerichtet werden, erfolgt nachdem Facade-Pattern uber die Fassade-Klasse der jeweiligen Schicht. Innerhalb derPresentation-Layer kommunizieren die Beans uber ein Objekt der Klasse LogicFa-

cadeAdapterBean mit dem Logic-Layer.

Die zum Database-Layer gehorenden Klassen tragen das Namensprafix DB und befind-en sich im Paket db. Sie sind fur die Kommunikation mit der Datenbank, das Ausle-sen von gespeicherten Konzepten und die Ubersetzung von neu erstellten Konzeptenund Anfragen in SQL-Statements zustandig. Die Klassen des Logic-Layers prufenund verarbeiten Nutzereingaben bei Konzeptgenerierung und Anfrageformulierung.In beiden Fallen werden Nutzereingaben geparst und auf Fehler uberpruft. Im Fehler-fall wird der Presentation-Layer informiert. Sind die Eingaben korrekt, werden ent-sprechende Konzepte, beziehungsweise Anfrageobjekte, erzeugt und an den Database-Layer ubergeben. Bei Anfragen werden die vom Database-Layer gelieferten Ergeb-nisse fur die Darstellung aufbereitet und anschließend an den Presentation-Layerweitergegeben. Klassen des Logic-Layers sind im Paket logic zu finden. Ihnenist das Prafix Logic vorangestellt. Fur die Generierung der graphischen Benutzer-schnittstellen, etwa fur Konzeptgenerierung oder Anfrageformulierung und Darstel-lung von Anfrageergebnissen, sind die Klassen des Presentation-Layers, aus demPaket presentation und die jsf-formatierten xhtml-Dateien im WebContent Ordnerverantwortlich. Der Logic-Layer liefert die vom Benutzer angeforderten Informatio-nen in entsprechenden Objekten, die von Beans aus dem Presentation-Layer fur dieDarstellung in dessen Browser bereitgestellt werden. Die Kommunikation zwischenBrowser und Server-Beans erfolgt uber jsf-generierte AJAX-Aufrufe.

Da die Beans des Presentation-Layer jeweils session-scoped sind, sie also mit Erzeu-gung einer Client-Session instantiiert und mit deren Verfall verworfen werden, ist

60

6.3. Einstellungen

eine Synchronisation notwendig, um fehlerfrei mit der zugrundeliegenden Datenbankinteragieren zu konnen. Da im Allgemeinen zu jedem Zeitpunkt von jeweils hoch-stens einer Anfrage pro Benutzer ausgegangen werden kann, wird jedem Benutzer einThread zugestanden. Die Synchronisation erfolgt in der Fassade des Logic-Layers.Benutzer konnen also innerhalb ihres Browsers nebenlaufig mit dem Server inter-agieren. Anfragen an Logic-Layer und folgend Database-Layer werden jedoch proBenutzer sequentiell abgearbeitet.

Klassen, die von allen Schichten genutzt werden konnen, etwa eine Tuple-Implemen-tierung, sind im Paket util zu finden. Das Paket webfilters beinhaltet Filter-Klassen, die fur Login und Logout genutzt werden, um nur autorisierten NutzernZugriff auf das Backend der Software zu erlauben.

6.3. Einstellungen

Eine große Zahl der im Programm verwendeten Parameter ist variabel gehalten.Parameter, wie etwa auf welchen Datentyp FLOAT gecastet oder mit welchem SQL-Statement die Namen der verfugbaren Tabellen und Views ausgelesen werden soll,sind als Eintrage in der Tabelle misc_settings abgelegt. misc_settings enthaltSchlussel-Wert-Paare, die um ein Flag, daß anzeigt, ob der jeweilige Eintrag aktivist, und eine Klartextbeschreibung erweitert wurden. Schlussel und Wert aktiverEintrage sind im Programm in Form einer Map verfugbar.

Die Fassaden der jeweiligen Schichten stellen Methoden bereit, um die Map zu erzeu-gen. Objekte der Klasse db.DBSettingsManager lesen schließlich die in misc_set-

tings enthaltenen Daten aus, und liefern sie als Map. Ein Ruckschreiben von An-derungen ist nicht vorgesehen, die Map wird nur lesend verwendet.

Sollten im Zuge einer Modifikation oder Erweiterung der Software zusatzliche Pa-rameter notwendig werden, konnen diese ebenfalls in der Tabelle misc_settings

abgelegt werden.

6.4. Initialer Konzeptimport

In Kapitel 4 wurde die Generierung von Konzepten aus Relationstypen definiert.In der Implementierung muß also eine Moglichkeit existieren, um aus Tabellen undViews der zugrundeliegenden Datenbank, Konzepte zu erzeugen und diese in einemgeeigneten Format abzulegen.

Eine Bean des Typs presentation.ImportConceptBean steuert den Import. Nacheinem erfolgreichen Log-in kann der Benutzer im Backend Import auswahlen. Erwird aufgefordert, aus einer Liste von in der Datenbank verfugbaren Tabellen undSichten diejenige auszuwahlen, die importiert werden soll. Die Liste wird nach demunter dem Key db.get_importable_names in misc_settings hinterlegten State-ment erzeugt. Methoden zum Erzeugen der Liste werden von den Fassaden der jew-eiligen Schicht angeboten.

61

6. Implementierung

Nach Auswahl eines zu importierenden Objekts werden dessen Name, Anzeigename,bezeichnet als Screen name, und Attribute in einer Ubersicht angezeigt. Abbildung6.1 zeigt einen Import fur eine Tabelle der Datenbank zu 3.1. Attribute und zuge-

Abbildung 6.1.: Tabellen und View Import

horige Attributinformationen werden mittels des unter dem Key db.get_importa-

ble_attributes abgelegten Statement zusammengestellt. Der Typ des Attributeswird aus einem der vom System unterstutzen Typen - STRING, INTEGER, BOOLEAN,FLOAT - gewahlt. Er ist kompatibel zu dem Attributtyp der Datenbank. Im Fall un-bekannter Datentypen fallt die Wahl auf STRING zuruck. Der Benutzer kann denTyp des Attributes anpassen. Bei der Erzeugung von Sichten fur Konzepte, die furAnfragen verwendet werden sollen, werden Attribute auf die unter db.cast_float,

62

6.5. Konzeptgenerierung

db.cast_string, db.cast_boolean und db.cast_integer hinterlegten Typen ge-castet. Da der Typ eines Attributs nach dem initialen Import nicht langer gean-dert werden kann, muß auf kompatible Typen sowohl bei den aktuell in der Daten-bank vorhandenen, als auch bei zukunftig auftretenden Werten geachtet werden.Attribute, die nicht Teil des Schlussels sind, konnen vom Import ausgeschlossenwerden.

Die Werte in den mit Name bezeichneten Feldern werden als Schlusselwert verwendet,um das Konzept, die Relation und ihre Attribute zu identifizieren. Sie stellen sicherdaß Attributbezeichner global eindeutig sind, und mussen daher im jeweils aktuellenDatenbankzustand ebenfalls eindeutig sein. Screen names sind Anzeigenamen, dieBenutzern bei der Anfrageformulierung angezeigt werden.

Sind die Anpassungen abgeschlossen kann der Benutzer mit Import die Erzeugungdes Konzepts einleiten. Die Software ubergibt die erzeugten Objekte zum Database-Layer, wo entsprechende Eintrage in den Tabellen CRYSTALCLEAR_RELATIONS undCRYSTALCLEAR_ATTRIBUTES angelegt werden. Anschließend wird ein Konzept ohneview_name in TEMPLATE_CONCEPTS und die zugehorigen Relationen und Attribute inTEMPLATE_RELATIONS und TEMPLATE_ATTRIBUTES eingefugt.

Da Schlusselattribute nicht vom Import ausgeschlossen werden konnen, kann beiBasiskonzepten, die durch den hier beschriebenen Import erzeugt wurden, von Men-gensemantik ausgegangen werden.


Unter Metaphor/Concept creation ist das in Abbildung 6.2 gezeigt Interface zufinden. Es dient der Generierung von Konzepten mittels der unter 4.3 vorgestell-ten Operationen. Fur die Konzeptgenerierung wird eine Bean des Typs presenta-

tion.MetaphorCreationBean genutzt.

Zunachst wahlt der Benutzer die gewunschten Konzepte aus. Die Liste der ver-fugbaren Konzepte wird mittels des unter db.select_metaphor_names abgelegtenStatements erzeugt.

Hat der Benutzer ein Konzept ausgewahlt, wird ein entsprechendes Objekt aus den inder Datenbank verfugbaren Daten erzeugt. Das Auslesen erfolgt hauptsachlich durchObjekte der Klassen logic.LogicMetaphorManagerImpl und db.DBMetaphorMan-

agerImpl. Die jeweiligen Fassaden stellen entsprechende Methoden bereit.

Die ausgewahlten Konzepte werden im Workbench in einer Ubersicht angezeigt. Zujedem Konzept werden die an der Projektion beteiligten Relationen und die zuge-horigen Attribute dargestellt sowie die jeweilige Konzeptbeschreibung angezeigt.

Konzepten und Attributen wird jeweils ein Variablenbezeichner zugewiesen. BeiKonzepten ist dies das in misc_settings unter variable_prefix angegebene Pra-fix und der Konzeptname, bei Attributen ist es das Prafix, der Relationsname unddruch einen Punkt getrennt der Attributbezeichner. Uber diese Variablen konnenKonzepte und Attribute im Konstruktionsausdruck angesprochen werden.

Auf Wunsch kann der Benutzer bereits hier die Tooltips der Attribute fur die

63

6. Implementierung

Abbildung 6.2.: Konzeptgenerierung - Workbench

64


Anzeige im Anfrageinterface editieren. Anderungen hier sind nur im Resultat derErzeugung von Bedeutung. Der Datenbankeintrag des geladenen Konzepts wird nichtverandert.

Sind die gewunschten Konzepte geladen, formuliert der Benutzer einen Konstruk-tionsausdruck um ein neues Konzept zu erstellen. Einem Konstruktionsausdruckkann eine eindeutige Folge von Konzeptoperationen zugeordnet werden. Die verwen-dete Syntax orientiert sich hierbei an der in 4.3 eingefuhrten.

Ist C die Menge der geladenen Konzepte so sind Konstruktionsausdrucke der folgen-den Form moglich:

Konstruktionsausdruck Konzeptoperation

C C Variable, die einemC ∈ C zugeordnet ist.

K[φ] K Konstruktionsausdruck Selektionφ Selektion uber KJunktoren und Vergleichsop.in SQL-Syntax

K[P] K Konstruktionsausdruck ProjektionP Komma getrennte Attribut-Variablen-Liste uber K

JOIN(K, K’) K, K ′ Konstruktionsausdrucke Join, K ./ K ′

UNION(K, K’) K, K ′ Konstruktionsausdrucke Vereinigung, K ∪K ′INTERSECT(K, K’) K, K ′ Konstruktionsausdrucke Schnitt, K ∩K ′MINUS(K, K’) K, K ′ Konstruktionsausdrucke Differenz, K −K ′PU(K, K’) K, K ′ Konstruktionsausdrucke Proj. Vereinigung,

K ∪proj K ′

Ein Konstruktionsausdruck ist gultig, sofern ihm eine nach 4.3 gultige Operations-folge zugeordnet wird.

Der angegebene Konstruktionsausdruck wird geparst und validiert. Dies geschiehtim Logic-Layer. Im Fehlerfall wird der Benutzer informiert und aufgefordert, seinenFehler zu korrigieren.

Wurde der Ausdruck erfolgreich validiert, so wird er ausgewertet. Dabei wird einneues Konzept generiert. Die verwendeten Klassen sind in den Paketen db.cre-

ation.metaphor, logic.creation.metaphor und presentation.creation.meta-

phor enthalten. Aus dem Erzeugungsprozeß gehen Objekte der Klasse DBModifi-

ableConcept, LogicModifiableConcept und ModifiableConcept hervor. Sie bildendas erstellt Konzept ab. Die Objekte enthalten jeweils eine Liste der beteiligten Rela-tionen, die wiederum eine Liste ihrer Attribute vorhalten. Zudem wird die Selektion-skomponente des Konzepts in Form von Objekten aus den Paketen db.constraint,logic.constraint und presentation.constraint vorgehalten.

Das erstellte Konzept wird dem Benutzer dann als Vorschau angezeigt. Abbildung6.3 zeigt ein Beispiel fur eine solche Vorschau. Im oberen Bereich wird eine Uber-sicht uber die in der Projektion des Konzepts enthaltenen Attribute dargestellt.

65

6. Implementierung

Abbildung 6.3.: Konzeptgenerierung - Darstellung des erzeugten Konzepts

66


Hier konnen Anzeigename und Tooltip der einzelnen Attribute und ihrer Relatio-nen modifiziert werden. Die eingetragenen Werte werden in der Anfrageschnittstelleangezeigt. Uber die Checkboxen unter Show? kann die Projektion des Konzepts ab-schließend modifiziert werden. Auch hier wird Mengensemantik verwendet.Schließlich wird das erzeugte Konzept in der Darstellung prasentiert, die im An-frageinterface verwendet wird. So ist eine Abschatzung der Ausmaße der Darstel-lung moglich. Uber die Schaltflachen << und >> kann die Anordnung von Relationeninnerhalb des Konzepts und Attributen innerhalb der Relationen verandert werden.Der Button Create lost das Schreiben des Konzepts in die Datenbank aus. Dabeiwerden von einem Objekt der Klasse db.DBMetaphorManager entsprechende Ein-trage in den Tabellen TEMPLATE_CONCEPTS, TEMPLATE_RELATIONS, TEMPLATE_AT-

TRIBUTES, TEMPLATE_COMP_EXP, TEMPLATE_CONSTANT_COMPARISON und TEMPLATE_

ATTRIBUTE_COMPARISONS vorgenommen.Fur die Speicherung wird das unter Anhang A beigefugte Schema verwendet.Ist der Haken bei Create Metaphor gesetzt, so soll das erstellte Konzept fur Anfra-gen und nicht nur fur die Konstruktion weiterer Konzepte verwendbar sein. In diesemFall wird in der Datenbank eine entsprechende Sicht angelegt. Fur den Namen derSicht wird das unter dem Schlussel db.view_name_prefix angegebene Prafix mitdem Namen des erzeugten Konzepts kombiniert. Sei im Folgenden C = (V, φ, P ) daserzeugte Konzept.Vor der eigentlichen Sichterzeugung wird die Selektionskomponente des Konzeptsin Negationsnormalform und in konjunktive Normalform uberfuhrt. φ hat also dieForm

(X11 ∨ . . . ∨X1m1) ∧ . . . ∧ (Xn1 ∨ . . . ∨Xnmn), n,m1, . . . ,mn ∈ N

Wobei Xi,j , 0 < i ≤ n und 0 < j ≤ mn, entweder ein moglicherweise negierterVergleich von Attributen oder eines Attributes mit einer Konstanten ist.Ferner sei

Wi = {R | R ∈ V, ∃A ∈ R ∧ (A ∈mi⋃j=1

att(Xij) ∨A ∈ P}, 0 < i ≤ n

Die Sicht wird dann entsprechend 4.2.2 und 4.5.2 nach dem folgenden Schemaerzeugt:

CREATEVIEW viewname AS(WITH C AS

(SELECT τ(P )FROM τ(W1)WHERE τ(X11)OR . . .OR τ(X1m1)

INTERSECT

67

6. Implementierung

. . .

INTERSECT

SELECT τ(P )FROM τ(Wn)WHERE τ(Xn1)OR . . .OR τ(Xnmn))

SELECT τ(P )FROM C)

τ muß dabei entsprechend modifiziert werden, um mit den unter den Schlusselndb.cast_float, db.cast_string, db.cast_boolean und db.cast_integer einge-tragenen Casts, gultige WHERE- und SELECT-Klauseln zu erstellen.

Durch den Eintrag des Sichtnamens in TEMPLATE_CONCEPTS.view_name wird dasKonzept fur Anfragen verwendbar.

Bei dieser Form der Ubersetzung wird stets das erzeugte Konzept als Grundlagefur die Erzeugung der Sicht verwendet. Bereits erzeugte Konzepte werden in ihrerdefinierten Form, nicht als Relation benutzt. Dies bietet bei der Sichterzeugung denVorteil, daß generierte Sichten nur auf den als Basiskonzepten importierten Daten-bankobjekten basieren. Es werden keine Sichten erzeugt, die von anderen generiertenSichten abhangen.

Sollte es bei der vom Programm generierten Sicht zu Performanceproblemen kom-men, so kann diese nach der Konzeptgenerierung manuell durch eine fur den aktuellenDatenbestand optimierte Formulierung ersetzt werden. Die Sicht muß dabei in ihrerProjektion mit der erzeugten ubereinstimmen. Durch eine Anderung des Eintragsview_name in der entsprechenden Zeile der Tabelle TEMPLATE_CONCEPT kann danndie optimierte Sicht eingehangt werden.


Sind Konzepte und Sichten erstellt worden, kann die Anfrageschnittstelle genutztwerden, um gemaß 4.4 Anfragen zu formulieren. Abbildung 6.4 zeigt die Schnittstellemit einer einfachen Anfrageformulierung. Die zugrundeliegende Bean ist vom Typpresentation.QueryBean. Im oberen Bereich kann zunachst aus der Liste verfug-barer Konzepte das gewunschte ausgewahlt werden. Die Liste wird unter Nutzungdes unter Schlussel db.select_metaphor_names abgelegten Statements generiert.Es handelt sich um die Konzepte, fur die eine Sicht generiert wurde.

Die Attribute der Projektion des Konzepts werden in Metapherform dargestellt.Uber Add row kann der Benutzer weitere Zeilen hinzufugen. Es wird Disjunktions-Semantik verwendet. Tragt der Benutzer also uber mehrere Zeilen verteilt Ein-schrankungen ein, so soll die Ergebnismenge aus Tupeln bestehen, die jeweils die Be-

68


Abbildung 6.4.: Die Anfrageschnittstelle

dingungen aus mindestens einer Zeile erfullen. Bedingungen konnen durch ein Kom-ma getrennt werden, dies wird gemaß Disjunktions-Semantik als UND-Verknupfunginterpretiert. Leere Zeilen werden ignoriert, sofern in anderen Zeilen Einschrankun-gen eingetragen wurden. Ist die uneingeschrankte Ausgabe aller dem Konzept zuge-ordneten Tupel gewunscht, so sollte die gesamte Metapher leer sein.

Einschrankungen sind dabei Vergleichsausdrucke. Es stehen in der aktuellen Versiondie folgenden Vergleichsoperatoren zur Verfugung:

Zeichenfolge Vergleich

= =

<> 6=< <

> >

<= ≤>= ≥LIKE SQL LIKE

Das Fehlen eines Operators wird als = interpretiert. Uber den enum-Typ util.

ConstraintType kann diese Liste erweitert werden. Es konnen fur Attribute jeweilsnur die zu ihrem Typ kompatiblen Vergleichsoperatoren verwendet werden:

Typ Verwendbare Vergleichsoperatoren

STRING =, <>, <, >, <=, >=, LIKE

INTEGER =, <>, <, >, <=, >=

FLOAT =, <>, <, >, <=, >=

BOOLEAN =

69

6. Implementierung

Die unter dem Schlussel negation_symbol eingetragenen Zeichenkette, in der ak-tuellen Version das Symbol !, ermoglicht die Negation eines Vergleichs. Der Eintrag

< 5, ! > 7

fur Attribut X entspricht etwa der Selektion

X < 5 ∧ ¬(X > 7)

Im enum-Typ util.AttributType sind die verwendbaren Datentypen definiert. Hi-er sind die regularen Ausdrucke abgelegt, die zur Prufung von Eingaben genutztwerden. Sie stellen sicher, daß etwa fur FLOAT-Attribute nur Ganzzahlen oder Kom-mazahlen akzeptiert werden.

Im Fall der Kombination von STRING und LIKE wird ahnlich zu SQL das Symbol %als Wildcard genutzt.

Uber einen Klick auf den Namen eines Attributes kann dieses aus der Projektionentfernt oder wieder hinzugefugt werden. Um eine Entfernung zu markieren, wirddie entsprechende Spalte der Tabelle ausgegraut. Uber den Relationsnamen konnenalle Attribute der betreffenden Relation ein- oder ausgeblendet werden. Die Pro-jektion erfolgt dabei wie in 4.4 nach der durch die Anfrage formulierten Selektion.Uber den Haken Remove copies kann die abschließende Duplikatentfernung ges-teuert werden. Genauer wird hier entschieden, ob in die entstehenden SQL-Anfrageein abschließendes DISTINCT eingefugt wird, oder nicht (siehe 6.7).

Durch aktivieren der Checkbox Activate variables wird die zeilenweise Nutzungvon Variablen in der Anfrageformulierung moglich. Jedem Attribut wird eine ein-deutige Variable zugewiesen. Sie besteht aus dem unter dem Schlussel variable_prefix abgelegten Symbol, in der aktuellen Version das Symbol @, und einer Num-mer.

Mit Variablen konnen Vergleiche zwischen Attributen innerhalb einer Zeile formuliertwerden. Die folgende Anfrage an ein Konzept C zum Bankbeispiel 3.4 macht diesdeutlich. Es ist ersichtlich, daß Kunden angefragt werden, deren Kontostand großerist, als ihr Kreditwert oder deren Kontostand gleich ihrem Kreditwert und kleiner500 ist.

p.CUSTOMER LOAN ACCOUNT BANK

@0:cust no @1:address @2:amount @3:balance @4:name

> @2

< 500 = @2

Entsprechend Disjunktions-Semantik fuhrt dies zu dem folgenden Konzept:

C[ACCOUNT.balance > LOAN.amount][CUSTOMER.cust_no, CUSTOMER.address]∪

C[ACCOUNT.balance < 500 ∧ACCOUNT.balance =LOAN.amount][CUSTOMER.cust_no, CUSTOMER.address]

70


Werden Attribute verglichen, so mussen ihre Typen kompatibel sein. Jeder Typ istzu sich selbst kompatibel, zudem sind FLOAT und INTEGER kompatibel.

Durch die Checkbox Use Aggregation wird ein Eingabefeld fur Aggregationsaus-drucke eingeblendet. Hier konnen Aggregationsausdrucke angegeben werden, die ineine Aggregation nach 4.4.4 uberfuhrbar sind. Aggregationsausdrucke sind entsprechendagg_stmt im folgenden EBNF-Ausdruck gebildete Ausdrucke.

f unc t i on = ”COUNT” | ”SUM” | ”MIN” | ”MAX”| ”AVG” | ”FIRST” | ”LAST”;

neg = ”NOT”;b op = ”AND” | ”OR”;v a r i a b l e = ”@” , s t r i n g ;comp sym = ”=” | ”<>” | ”<” | ”<=”

| ”>” | ”>=” | ”LIKE ”;comp op = v a r i a b l e

| f unc t i on , ”( ” , v a r i a b l e , ”) ”;comparison = comp op , comp sym , comp op

| comp op , comp sym , s t r i n g| s t r i n g , comp sym , comp op ;

comp ex = comparison| ”( ” , comp ex , ”) ”| neg , comp ex| comp ex , b op , comp ex ;

per stmt = v a r i a b l e , {” , ” , v a r i a b l e } ;agg f = func t i on , ”( ” , v a r i a b l e , ”) ” ,

”AS” , v a r i a b l e ;per = ”PER” , ”( ” , per stmt , ”) ”;having = ”HAVING” , ”( ” , comp ex , ”) ”;s agg stmt = agg f

| agg f , per| agg f , per , having| per , having| per ;

agg stmt = s agg stmt ,[ ”IN ” , ”( ” , agg stmt , ”) ”] ;

Unter string sind dabei Zeichenketten zu verstehen, die auf den folgende regularenAusdruck passen:

[a-zA-Z0-9%_/\-\+\.]+

Am Beispiel des folgenden Aggregationsausdrucks zum oben verwendeten Beispielfur das Konzept C, wird die Ubersetzung in einen Aggregationsausdruck nach 4.4.4deutlich:

COUNT(@0) AS @cust-count PER (@4)

71

6. Implementierung

Dies entspricht der Aggregation

Γ(θ(C), {BANK.name},COUNT,CUSTOMER.cust no, cust-count)

Aggregationsausdrucke beginnen mit der zu verwendenden Funktion und dem At-tribut auf das sie angewandt werden soll. Auf AS folgt dann der gewunschte At-tributbezeichner fur die Ergebnisrelation. Die eigentliche Gruppierung erfolgt durchden PER-Anteil des Ausdrucks.Zusatzlich kann eine HAVING-Beschrankung angegeben werden. Fur die hier nutzbarenAttribute gelten die aus SQL bekannten Einschrankungen im Bezug auf die Grup-pierung.Schachtelung ist schließlich durch Angabe eines weiteren Aggregationsausdrucksnach dem IN Schlusselwort moglich. Hier ist zu beachten, daß durch eine Aggre-gation aus einer Relation eine neue Relation erzeugt wird. Fur die Formulierungdes außeren Aggregationsausdrucks stehen also nur die Attribute jener Relation zurVerfugung, welche durch den inneren Ausdruck erzeugt wird.Hat der Benutzer eine Anfrage formuliert, kann er die Auswertung durch einen Klickauf Search auslosen. Die Anfrage wird an den Logic-Layer ubergeben und ausgew-ertet. Die Auswertung von Anfragen wird im folgenden Abschnitt 6.7 beschrieben.Das Anfrageresultat wird dem Benutzer in Metapherform angezeigt. Abbildung A.1zeigt ein Beispiel. Uber die oberhalb der Metapher angeordneten Relationsnamenkonnen einzelne Relationen aus der Ergebnisdarstellung ein- und ausgeblendet wer-den. Es handelt sich hierbei nicht um eine Projektionsoperation. Die Attribute aus-geblendeter Relationen werden lediglich aus der Anzeige entfernt, beziehungsweiseder Anzeige hinzugefugt.

6.7. Anfrageauswertung

Hat der Benutzer eine Anfrage formuliert und die Suche gestartet, wird sie an dieFassade des Logic-Layer ubergeben. Ein Objekt der Klasse logic.LogicQueryMan-

agerImpl ubernimmt die Vorbereitung der Suche. Zu diesem Zeitpunkt besteht dieAnfrage aus einem Objekt der Klasse MetaphorSkeleton, das die vom Benutzerangegebenen Selektionen beinhaltet, dem vom Benutzer angegebenen Aggregation-sausdruck als String und zwei Flags, die angeben, ob Variablen verwendet wurdenund ob fur das Ergebnis eine Menge oder eine Multimenge gewunscht ist.Da die Benutzereingaben bereits gepruft wurden, wird davon ausgegangen, daß dieBenutzereingaben valide sind. Das Parsen der Benutzereingaben erfolgt daher alsbest-effort. Wurden Variablen verwendet, werden diese aufgelost. Die Zeilen der An-frage werden in Zeilen von Constraints ubersetzt. Die zugehorigen Klassen stammenaus dem Paket logic.constraints. Jedes Constraint kann negiert sein und bestehtaus einem Vergleichsoperator, einem Verweis auf ein Attribut und einem Wert odereinem Vergleichsoperator und zwei Verweisen.Sollte ein Aggregationsausdruck angegeben worden sein, wird dieser geparst und einentsprechendes Objekt der Klasse LogicQueryAggregation erzeugt.

72

6.7. Anfrageauswertung

Abbildung 6.5.: Darstellung eines Anfrageergebnisses

73

6. Implementierung

Die Anfrage liegt nun in einer vollstandig geparsten Form vor. Constraints verfu-gen uber einen Verweis auf die beteiligten Attribute und vom Benutzer eingegebeneVergleichswerte liegen im korrekten java-Datentyp, String, int, double, boolean,vor. Dies ist notwendig, um sie im folgenden Schritt als Parameter eines Prepared-Statements zu verwenden.Ist die Anfrage vorbereitet wird sie an den Database-Layer ubergeben. Hier wird da-raus ein SQL-Statement erzeugt und auf der Datenbank ausgewertet. Dies geschiehtin einem Objekt der Klasse DBQueryManagerImpl. Zu jedem Konzept, das fur An-fragen verwendet werden kann, existiert eine Sicht in der Datenbank. Wurde also zueinem Konzept C = (V, φ, P ), dessen zugehorige Sicht view_c ist, eine Anfrage mitden Constraints

{{X11, . . . , X1m1}, . . . , {Xn1, . . . , Xnmn}}, n,m1, . . . ,mn ∈ N

formuliert, bei der die Attributmenge {A1, . . . , Ak} ⊆ P = {A1, . . . , Al}, k, l ∈ N,aktiviert wurde. So wird das folgende SQL-Statement daraus generiert.

WITH X0 AS(SELECT A1, . . . , AlFROM view cWHERE X11

AND . . .AND X1m1

UNION

. . .

UNION

SELECT A1, . . . , AlFROM view cWHERE X11

AND . . .AND Xnmn )

SELECT ?DISTINCT? A1, . . . , AkFROM C

Der Platzhalter ?DISTINCT? wird durch DISTINCT ersetzt, falls der Benutzer dieEntfernung von Duplikaten aktiviert hat, ansonsten durch den leeren String.Wurde eine Aggregation angegeben, so wird die Ubersetzung, wie in Kapitel 4.5.2beschrieben, erweitert.Die Anfrage wird auf der Datenbank ausgewertet und das Ergebnis in Form einesObjektes der Klasse DBResultImpl an den Logic-Layer ubergeben. Hier wird einentsprechendes Objekt des Logic-Layers daraus erzeugt und an den Presentation-Layer zuruckgegeben.

74

6.8. Verwaltung des Systems

6.8. Verwaltung des Systems

Neben den bereits erwahnten Funktionen bietet das Backend Funktionen zum Ver-walten von Benutzern und dem Loschen von Konzepten.Das Log-in geschieht unter Nutzung einer Bean des Typs LoginBean. Sie stellt Meth-oden bereit, um einen Benutzer anhand von Benutzernamen und Paßwort zu au-thentifizieren. Browser-seitig wird uber die im Paket webfilters vorhandenen Fil-ter sichergestellt, daß nur angemeldete Benutzer auf Seiten des Backends zugreifenkonnen.Eine Bean der Klasse DeleteConceptBean steuert das Loschen von im Systemvorhandenen Konzepten. Ein Konzept wird uber seinen Namen identifiziert. Logic-und Database-Layer stellen daher Methoden bereit, um ein Konzept anhand seinesNamens zu loschen. Sollte es sich um ein Konzept handeln, fur das eine Sicht erzeugtwurde, so wird auch diese geloscht. Fur den Loschvorgang werden die Statementsverwendet, die unter den db.delete_ beginnenden Schlusseln in misc_settings

abgelegt sind.Fur die Benutzerverwaltung wird eine Bean des Typs UserManagementBean genutzt.Sie bietet Methoden zum Erstellen und Loschen von Systembenutzern. Uber Logic-und Database-Layer werden die vom Benutzer gewunschten Aktionen auf der Daten-bank ausgefuhrt. Benutzerinformationen werden in der Tabelle CRYSTALCLEAR_USERSabgelegt. Komplexitatsanforderungen an Benutzernamen oder Paßwort werden inder aktuellen Version nicht gestellt.

6.9. Ubersetzung der Software

Vor dem Ubersetzen der Software, mussen Parameter gesetzt werden, damit dasProgramm korrekt auf die gewunschte Datenbank zugreifen kann. In der Datei

WebContent/META-INF/context.xml

mussen url, Benutzername und Passwort der Datenbank fur den vom Programmverwendeten Connection-Pool gesetzt werden. Uber die maxActive-, maxIdle- undmaxWait-Parameter kann gesteuert werden, wie der Connection-Pool auf Verbindungs-anfragen reagiert.Um die Datenbank vorzubereiten, muß zunachst im SQL-Skript create.sql dieWerte der misc-settings-Eintrage db.import_user und db.import_schema ange-paßt werden. Sie legen fest, welcher Schema- und Benutzername bei der Suche nachimportierbaren Objekten verwendet wird. Sind die zu importierenden Tabellen etwavom Benutzer user1 im Schema public angelegt, so mussen die Eintrage in dercreate.sql wie folgt abgeandert werden:

INSERT INTO m i s c s e t t i n g s (key , value , a c t ive , d e s c r i p t i o n )VALUES ( ’ db . import user ’ , ’ user1 ’ , TRUE,

’ User name f o r view/ t a b l e import ’ ) ;

75

6. Implementierung

INSERT INTO m i s c s e t t i n g s (key , value , a c t ive , d e s c r i p t i o n )VALUES ( ’ db . import schema ’ , ’ pub l i c ’ , TRUE,

’ Schema name f o r view/ t a b l e import ’ ) ;

Eine spatere Anderung ist uber ein UPDATE der Tabelle misc_settings ebenfallsmoglich. Danach muß das Skript create.sql auf der Datenbank ausgefuhrt werden.Es erzeugt die notwendigen Tabellen und Sichten.Zur Ubersetzung der Software wurde eine ant build.xml-Datei erstellt. Sie bietetdie build-targets clean, welches den Arbeitsbereich saubert, compile welches dasProjekt ubersetzt, package, welches ubersetzt und eine .war-Datei erzeugt und de-

ploy, welches zusatzlich zu package die .war-Datei in das unter der property de-

ployment.dir angegebene Verzeichnis kopiert.Der Aufruf erfolgt innerhalb des Projektordners mit dem Befehl

ant <target>

Die fur die Ubersetzung erforderlichen .jar-Dateien sind im Verzeichnis

WebContent/WEB-INF/lib

abgelegt.Die entstehende .war-Datei kann dann auf dem gewunschten Application-Serverdeployed werden.

76

7. Fazit und Ausblick

Im Rahmen dieser Arbeit wurde eine unterteilte Anfragesprache entworfen, die dieFormulierung komplexer Anfragen ermoglicht. Durch die Unterteilung der Anfrage-formulierung in eine vorausgehende Konzeptdefinition, die durch erfahrene Benutzervorgenommen werden sollte, und darauf folgend die Formulierung der eigentlichenAnfragen unter Nutzung dieses Konzepts, kann Endbenutzern eine vielfaltige, dy-namische Schnittstelle geboten werden. Da das System frei an ein gewahltes Daten-bankschema anpaßbar ist, kann es als Schnittstelle fur verschiedene Datenbankeneingesetzt werden.

Es sind Erweiterungen des Systems denkbar, die dessen Nutzen weiter steigern wur-den. Im Folgenden werden mogliche Erweiterungen skizziert, die im Rahmen dieserArbeit nicht realisierbar sind. Neben den hier vorgestellten Erweiterungen des Sys-tems sind naturlich auch Erweiterungen der zugrundeliegenden konzeptbasierten An-fragesprache denkbar.

7.1. Ein graphischer Konzepteditor

In der vorliegenden Version des Systems werden Konzepte durch Angabe eines Erzeu-gungsausdrucks generiert. Die Syntax ahnelt der der relationalen Algebra. Stattdieser Form der Konzeptdefinition ware auch eine graphische Konzeptgenerierungdenkbar. Konzepte konnten als Teilgraphen innerhalb des Datenbankschemas odereinem entsprechenden ER-Modell dargestellt werden. Ist eine Entitat oder eine Re-lation Teil des gewahlten Konzepts, so ist die entsprechende Relation Teil der Re-lationsmenge. Joinausdrucke ließen sich als solch ein Teilgraph mit beschriftetenKanten fur die Joinbedingung darstellen. Mengenoperationen konnten als Kombina-tion verschiedener Instanzen der Darstellung realisiert werden, die vom Benutzer ingewunschter Form kombiniert werden konnen.

7.2. Ergebnisausgabe in einem Austauschformat

In der vorliegenden Version werden Suchergebnisse stets in Metapherform, also alsgruppierte Tabelle dargestellt. Sollen Ergebnisse maschinell verarbeitet werden, etwazur graphischen Aufbereitung der Ergebnisse oder um sie in einem eigenen Systemweiter auszuwerten, so ist diese Darstellung unzureichend. Da die Ergebnisse einerAnfrage im Logic-Layer in Relation-Attribut-Form vorliegen, konnte eine alternativeAusgabe angeboten werden. Es ware etwa denkbar Suchergebnisse in CSV-Formatoder in ein xml-Austauschformat zu transformieren.

77

7. Fazit und Ausblick

Eine solche Transformation konnte auf Basis der Anfrageresultate innerhalb desLogic-Layers durchgefuhrt werden. Uber eine einfache Erweiterung der Benutzer-schnittstelle konnte dem Benutzer die Moglichkeit gegeben werden, sein Ergebnis ineinem der angebotenen Formate zu erhalten.

7.3. Erweiterung der Anfrageschnittstelle uminhaltsspezifische Komponenten

Die aktuell verwendete Ergebnisdarstellung gibt Anfrageresultate in Metapherformder Rohdaten aus. Es ware sinnvoll hier eine Transformation der Ergebniswertein Betracht zu ziehen. Innerhalb des Logic-Layer konnten Ergebnisse anhand einervorher festgelegten Transformationsvorschrift umgewandelt werden. Solche Transfor-mationen konnten in der Datenbank abgelegt und dort im Zuge der Anfrageauswer-tung abgerufen werden.

Zu der CrystalDB 3.1 existiert etwa ein System, daß die Darstellung der Polyed-erstrukturen der gespeicherten Strukturen ermoglicht. Es ware sinnvoll crysno_cc-Werte in Links zu wandeln, die direkt zu der entsprechenden Darstellung fuhren.

Auch die Markierung ’auffalliger’ Werte ware denkbar; ist ein Ergebniswert Teil einesvordefinierten Wertebereichs, so konnte er optisch hervorgehoben werden. In derCrystalDB etwa ungewohnliche Bindungsstarken innerhalb von Pfaden, in OpenVigil3.2 die Namen von Inhaltsstoffen, die besonders haufig an Reports beteiligt sind.

7.4. Graphische Anfragekomponente

Zu der in 3.1 beschriebenen Kristallstruktur-Datenbank ist eine Anfrageschnittstellegeplant, die eine Kombination textueller Anfragen mit einer graphischen Anfrage-formulierung erlaubt. Sie wird etwa in [Kle12] vorgeschlagen.

Es ware moglich, Konzepte als Zwischensprache fur die Anfrageauswertung zu nutzen.Eine graphische Komponente, etwa wie in 7.1 skizziert, konnte fur die geometrischeKomponente der Anfrage genutzt werden. Die vom Benutzer erstellte geometrischeForm konnte in eine Folge von Konzeptoperationen ubersetzt werden. Im Beispielhat der Benutzer etwa zwei Silizium-Tetraeder ausgewahlt, die uber eine Ecke ver-bunden sind. Unter der Annahme, daß Konzepte fur Tetraeder oder Polyeder undfur eine Eckenverbindung existieren, konnte ein Konzept fur die Benutzeranfrage ausdiesen Konzepten anhand einer Kombinationsvorschrift generiert werden.

Im Beispiel konnte etwa der Join der Konzepte Polyeder1, Polyeder2 und Ecken-

verbindung genugen, um das gewunschte Konzept zu erzeugen. Der Join der dreiKonzepte ware hier als die Konstruktionsvorschrift zu verstehen.

Das bestehende System konnte fur die Formulierung textueller Anfragen genutztwerden. Da eine Transformation der graphischen Formulierung in Konzepte erfol-gen wurde, konnten diese als Basis fur die existierende Anfrageschnittstelle genutztwerden. In der Skizze ist etwa das Anfrageinterface fur den beschriebenen Join

78

7.4. Graphische Anfragekomponente

Abbildung 7.1.: Mockup einer graphischen Anfragekomponente auf Konzeptbasis

dargestellt. Die Erzeugung von SQL-Statements ware auf Basis der Konzeptanfragedes Benutzers wie in 4.5.2 beschrieben moglich.

79

A. ER-Schema

nam

edb

_nam

e

RE

LAT

ION

S

nam

eke

y?

AT

TR

IBU

TE

S

TE

MP

LA

TE

_R

ELA

TIO

NS

scre

en_

nam

epo

sitio

nde

scrip

tion

in_p

roje

ctio

n?

TE

MP

LAT

E_

AT

TR

IBU

TE

S

scre

en_

nam

epo

sitio

nde

scrip

tion

nam

ecr

eato

rsc

reen

_na

me

desc

riptio

n

TE

MP

LAT

E_

CO

NC

EP

Tta

ble

s &

vie

ws

TE

MP

LAT

E_

CO

MP

_E

XP

id neg

ate

dop

era

tor

sele

ctio

n

proj

ectio

n

rela

tions

child

(0,n

)

(0,1

)

TE

MP

LA

TE

_C

ON

ST

RA

INT

S

com

par

iso

n_ty

pe

nega

ted

TE

MP

LAT

E_

AT

TR

IBU

TE

_C

OM

PA

RIS

ON

S

TE

MP

LA

TE

_C

ON

STA

NT

_C

OM

PA

RIS

ON

S

valu

e

left

righ

t

sele

ctio

n

pro

ject

ion

Abbildung A.1.: Das verwendete Schema als ER-Modell

81

B. Relationale Ubersetzung desverwendeten Schemas

({ (RELATIONS,{name , db name } ,{name} ) ,

(ATTRIBUTES,{ re lat ion name , name , i s k e y } ,{ re lat ion name , name} ) ,

(TEMPLATE CONCEPTS,{name , c reator , screen name , d e s c r i p t i o n } ,{name} ) ,

(TEMPLATE RELATIONS,{concept name , re lat ion name , screen name ,

po s i t i on , d e s c r i p t i o n } ,{concept name , re la t ion name } ) ,

(TEMPLATE ATTRIBUTES,{concept name , re lat ion name , attr ibute name ,

screen name , po s i t i on , d e s c r i p t i o n , i n p r o j e c t i o n } ,{concept name , re lat ion name , attr ibute name } ) ,

(TEMPLATE COMP EXP,{concept name , id , negated , operator , pa r en t id } ,{concept name , id } ) ,

(TEMPLATE ATTRIBUTE COMPARISON,{concept name , comp exp id , comparison type ,

l e f t r e l a t i o n n a m e , l e f t a t t r i b u t e n a m e ,r i gh t r e l a t i on name , r i ght a t t r ibute name , negated } ,{concept name , comp exp id , comparison type ,

l e f t r e l a t i o n n a m e , l e f t a t t r i b u t e n a m e ,r i gh t r e l a t i on name , r i gh t a t t r i bu t e name } ) ,

(TEMPLATE CONSTANT COMPARISON,{concept name , comp exp id , comparison type ,

re lat ion name , attr ibute name , value ,negated } ,{concept name , comp exp id , comparison type ,

re lat ion name , attr ibute name , va lue } )} ,{ATTRIBUTES[ re la t ion name ]

⊆ RELATIONS[ name ] ,

83

B. Relationale Ubersetzung des verwendeten Schemas

TEMPLATE RELATIONS[ concept name ]⊆ TEMPLATE CONCEPT[ name ] ,

TEMPLATE RELATIONS[ re la t ion name ]⊆ RELATIONS[ name ] ,

TEMPLATE ATTRIBUTES[ concept name , re la t ion name ]⊆ TEMPLATE RELATIONS[ concept name ,

re la t ion name ] ,TEMPLATE ATTRIBUTES[ re lat ion name , attr ibute name ]

⊆ ATTRIBUTES[ re lat ion name , name ] ,TEMPLATE COMP EXP[ concept name ]

⊆ TEMPLATE CONCEPTS[ name ] ,TEMPLATE COMP EXP[ parent id ]

⊆ TEMPLATE COMP EXP[ id ] ,TEMPLATE ATTRIBUTE COMPARISON[ concept name ,

comp exp id ]⊆ TEMPLATE COMP EXP[ concept name , id ] ,

TEMPLATE ATTRIBUTE COMPARISON[ concept name ,l e f t r e l a t i o n n a m e ,l e f t a t t r i b u t e n a m e ]

⊆ TEMPLATE ATTRIBUTES[ concept name ,re lat ion name ,attr ibute name ] ,

TEMPLATE ATTRIBUTE COMPARISON[ concept name ,r i gh t r e l a t i on name ,r i gh t a t t r i bu t e name ]


TEMPLATE CONSTANT COMPARISON[ concept name ,re lat ion name ,attr ibute name ]


TEMPLATE CONSTANT COMPARISON[ concept name ,comp exp id ]

⊆ TEMPLATE COMP EXP[ concept name , id ] } )

84

C. Relationales Schema zu 3.1

CrystalDB =({ (CRYSTAL STRUCTURE,{ crysno cc , crysta l name , formula , year , tc ,

hm fu l l } ,{ c rysno cc } ) ,

(ANALYSIS,{ crysno cc , s t r e n g t h f a c t o r } ,{ crysno cc , s t r e n g t h f a c t o r } ) ,

(IONS ,{ crysno cc , element , atom no , ox idat ion ,

coord inat ion , conn unit no } ,{ crysno cc , element , atom no } ) ,

(CONN UNIT,{ crysno cc , conn unit no } ,{ crysno cc , conn unit no } ) ,

(IUSOOS,{ crysno cc , s t r e n g t h f a c t o r , iusoo no ,

d imens iona l i ty , type , s t rength , symop ,conn unit no } ,{ crysno cc , s t r e n g t h f a c t o r , iusoo no } ) ,

(PATHS,{ crysno cc , s t r e n g t h f a c t o r , iusoo no ,

path no } ,{ crysno cc , s t r e n g t h f a c t o r , iusoo no ,

path no } ) ,(EDGES,{ crysno cc , cat ion e lement , cation atom no ,

cation sym op , anion element , anion atom no ,anion sym op , t r a n s l a t i o n , d i s tance ,s t ruc t bv } ,{ crysno cc , cat ion e lement , cation atom no ,

cation sym op , anion element , anion atom no ,anion sym op } ) ,

(EDGE IN PATH,{ crysno cc , s t r e n g t h f a c t o r , iusoo no , path no ,

cat ion e lement , cation atom no , cation sym op ,anion element , anion atom no , anion sym op ,

85

C. Relationales Schema zu 3.1

edge no } ,{ crysno cc , s t r e n g t h f a c t o r , iusoo no , path no ,

cat ion e lement , cation atom no , cation sym op ,anion element , anion atom no , anion sym op } )} ,

{ANALYSIS [ c rysno cc ]⊆ CRYSTAL STRUCTURE[ c rysno cc ] ,

IONS [ c rysno cc ]⊆ CRYSTAL STRUCTURE[ c rysno cc ] ,

IONS [ crysno cc , conn unit no ]⊆ CONN UNIT[ crysno cc , conn unit no ] ,

CONN UNIT[ c rysno cc ]⊆ CRYSTAL STRUCTURE[ c rysno cc ] ,

IUSOOS[ crysno cc , s t r e n g t h f a c t o r ]⊆ ANALYSIS [ crysno cc , s t r e n g t h f a c t o r ] ,

IUSOOS[ crysno cc , conn unit no ]⊆ CONN UNIT[ crysno cc , conn unit no ] ,

PATHS[ crysno cc , s t r e n g t h f a c t o r , iusoo no ]⊆ IUSOOS[ crysno cc , s t r e n g t h f a c t o r , iusoo no ] ,

EDGES[ crysno cc , cat ion e lement , cat ion atom no ]⊆ IONS [ crysno cc , element , atom no ] ,

EDGES[ crysno cc , anion element , anion atom no ]⊆ IONS [ crysno cc , element , atom no ] ,

EDGE IN PATH[ crysno cc , s t r e n g t h f a c t o r , iusoo no ,path no ]

⊆ PATHS[ crysno cc , s t r e n g t h f a c t o r , iusoo no ,path no ] ,

EDGE IN PATH[ crysno cc , cat ion e lement , cation atom no ,cation sym op , anion element ,anion atom no , anion sym op ]

⊆ EDGES[ crysno cc , cat ion e lement , cation atom no ,cation sym op , anion element ,anion atom no , anion sym op ] } )

86

D. Relationales Schema zu 3.2

OpenVigil =({ (REPORT,{ i s r , f o l l s e q , date , age , gender , c a s e i d } ,{ i s r } ) ,

(REPORT SOURCE,{code , meaning } ,{ code } ) ,

(REP RSRC,{ r e p i s r , r s r c c o d e } ,{ r e p i s r , r s r c c o d e } ) ,

(OUTCOME,{code , meaning } ,{ code } ) ,

(REP OC,{ r e p i s r , oc code } ,{ r e p i s r , oc code } ) ,

(EVENT,{pt , s y s o r g c l a s s } ,{pt })

(REP EV,{ r e p i s r , ev pt } ,{ r e p i s r , ev pt } ) ,

(DRUGUSAGE,{drug seq , route , d a i l y d o s i s , r e p i s r ,

brandname , producer name } ,{drug seq } ) ,

(THERAPY,{drug seq , t id , s t a r t , end , d u r a b i l i t y } ,{drug seq , t i d } ) ,

(PHARMAPRODUCT,{brandname , producer name , form , s a l t , type } ,{brandname , producer name } ) ,

(DRUG,{drug name , drugbank id } ,{drug name } ) ,

(D APPL,{drug seq , drug name } ,

87

D. Relationales Schema zu 3.2

{drug seq , drug name } ) ,(PRODUCT,{brandname , producer name , drug name } ,{brandname , producer name , drug name } )} ,

{REP RSRC[ r e p i s r ]⊆ REPORT[ i s r ] ,

REP RSCR[ r s r c c o d e ]⊆ REPORT SOURCE[ code ] ,

REP OC[ r e p i s r ]⊆ REPORT[ i s r ] ,

REP OC[ oc code ]⊆ OUTCOME[ code ] ,

REP EV[ r e p i s r ]⊆ REPORT[ i s r ] ,

REP EV[ ev pt ]⊆ EVENT[ pt ] ,

DRUGUSAGE[ r e p i s r ]⊆ REPORT[ i s r ] ,

DRUGUSAGE[ brandname , producer name ]⊆ PHARMAPRODUCT[ brandname , producer name ] ,

THERAPY[ drug seq ]⊆ DRUGUSAGE[ drug seq ] ,

D APPL[ drug seq ]⊆ DRUGUSAGE[ drug seq ] ,

D APPL[ drug name ]⊆ DRUG[ drug name ] ,

PRODUCT[ brandname , producer name ]⊆ PHARMAPRODUCT[ brandname , producer name ] ,

PRODUCT[ drug name ]⊆ DRUG[ drug name ] } )

88

E. Relationales Schema zu 3.3

Fahrzeugbau =({ (PART,{name , d e s c r i p t i o n , s a l e p r i c e p u , un i t } ,{name} ) ,

(USED IN NEEDED,{used in name , needed name , amount} ,{used in name , needed name } ) ,

(TRAILER TYPE,{name , expected m h , gen type , d e s c r i p t i o n } ,{name} ) ,

(PARTS USED,{ tt name , part name , amount} ,{ tt name , part name } ) ,

(TRAILER,{v id number , product ion date , d e s c r i p t i o n ,

s a l e p r i c e , tt name } ,{v id number } )} ,

{USED IN NEEDED[ used in name ]⊆ PART[ name ] ,

USED IN NEEDED[ needed name ]⊆ PART[ name ] ,

PARTS USED[ tt name ]⊆ TRAILER TYPE[ name ] ,

PARTS USED[ part name ]⊆ PART[ name ] ,

TRAILER[ tt name ]⊆ TRAILER TYPE[ name ] } )

89

F. Relationales Schema zu 3.4

Bankbe i sp i e l =({ (BANK,{name} ,{name} ) ,

(CUSTOMER,{ cust no , address } ,{ cust no } ) ,

(ACCOUNT,{a no , balance , bank name , cust no } ,{a no } ) ,

(LOAN,{ l i d , amount , bank name , cust no } ,{ l i d } )} ,

{ACCOUNT[ bank name ]⊆ BANK[ name ] ,

ACCOUNT[ cust no ]⊆ CUSTOMER[ cust no ] ,

LOAN[ bank name ]⊆ BANK[ name ] ,

LOAN[ cust no ]⊆ CUSTOMER[ cust no ] } )

91

G. Relationales Schema zu 3.5

Mod Bankbeispiel =({ (BANK,{name} ,{name} ) ,

(DEPOSITOR,{dep no , address } ,{ cust no } ) ,

(BORROWER,{bor no , address } ,{ cust no } ) ,

(ACCOUNT,{a no , balance , bank name , dep no } ,{a no } ) ,

(LOAN,{ l i d , amount , bank name , bor no } ,{ l i d } )} ,

{ACCOUNT[ bank name ]⊆ BANK[ name ] ,

ACCOUNT[ dep no ]⊆ DEPOSITOR[ dep no ] ,

LOAN[ bank name ]⊆ BANK[ name ] ,

LOAN[ bor no ]⊆ BORROWER[ bor no ] } )

93

Literaturverzeichnis

[BB83] Joachim Biskup and Hans Hermann Bruggemann. Universal RelationViews: A Pragmatic Approach. Proceedings of the 9th International Con-ference on Very Large Data Bases, pages 172–185, 1983.

[Ber12] Rudolf Berghammer. Ordnungen, Verbande und Relationen mit Anwen-dungen. Springer Vieweg, 2 edition, 2012.

[Egg13] Christian Eggeling. Datenqualitat in Pharmakovigilanzdaten. Master-Arbeit, Christian-Albrechts-Universitat zu Kiel, 2013.

[FMU82] Ronald Fagin, Alberto O. Mendelzon, and Jeffrey D. Ullman. A SimplifiedUniversal Relation Assumption and Its Properties. ACM Transactions onDatabase Systems, Vol. 7(No. 3):343–360, September 1982.

[KK93] P. Kandzia and H.-J. Klein. Theoretische Grundlagen relationaler Daten-banksysteme. BI-Verlag, 1993.

[KK95] H.-J. Klein and D. Kramer. NQS - a graphical query system for datamodels with binary relationship types. S. Spaccapietra and R. Jain (eds.):Visual Database Systems 3, pages 394–409, 1995.

[Kle12] H.-J. Klein. The use of periodic graphs for representing and analysingcrystal structures. Zeitschrift fur Kristallographie, Vol. 227:612–618, 2012.

[Pre14] Oxford University Press. Oxford Dictonaries: concept, 2014. URL: http://www.oxforddictionaries.com/definition/english/concept.

[TCY92] Frank S.C. Tseng, Arbee L.P. Chen, and Wei-Pang Yang. On mappingnatural language constructs into relational algebra through E-R represen-tation. Data & Knowledge Engineering, Vol. 9:97–118, 1992.

[Tha04] Bernhard Thalheim. Co-design of structuring, functionality, distribution,and interactivity for information systems. Proceeding APCCM ’04 Pro-ceedings of the first Asian-Pacific conference on Conceptual modelling, Vol.31:3–12, 2004.

[Zie13] Soren Zieger. Statistische Methoden des Data Mining in der Pharmakovig-ilanz. Master-Arbeit, Christian-Albrechts-Universitat zu Kiel, 2013.

[Zlo77] M. M. Zloof. Query-by-Example: a data base language. IBM SystemsJournal, Vol. 16(No. 4):324–343, 1977.

95

http://www.oxforddictionaries.com/definition/english/concept

http://www.oxforddictionaries.com/definition/english/concept

Documents

Master-Arbeit - is.informatik.uni-kiel.dehjk/masterarbeit_Ralfs.pdf · Selbstst andigkeitserkl arung Ich erkl are hiermit, daˇ ich die vorliegende Arbeit selbstst andig und nur unter