Kurzinfo Agentenorientiertes Software Engineering (AOSE) bezeichnet einen Bereich, der an der Schnittstelle zwischen Software Engineering einerseits und Agenten- und Multiagentensystemen andererseits entsteht. Gegenstand von AOSE sind Vorgehensweisen, Methoden, Techniken und Tools für die Erstellung und Handhabung von agentenorientierter Software

Erläuterung

Darunter versteht man Software, deren Struktur und Funktionalität unter dem Blickwinkel einer Menge von Agenten betrachtet wird. Ein Agent ist dabei charakterisiert als eine abgrenzbare Softwareeinheit, die zur Erreichung der von ihrem Benutzer oder Entwickler vorgegebenen Ziele und unter Wahrung seiner Interessen flexibel und autonom mit ihrer Umgebung und anderen Agenten interagiert. Ausgehend von diesem Agentenkonzept zielt AOSE vor allem auf Anwendungen ab, die mindestens eines der folgenden Merkmale aufweisen: Es sind viele dynamisch interagierende Komponenten involviert,

die nicht unbedingt alle a priori bekannt sind (vgl. offene Systeme wie das Internet),
die eine Fremdkontrolle nicht oder nur beschränkt gestatten (z.B. aufgrund individueller und konfliktträchtiger Ziele, Interessen, Rechte und Pflichten),
zwischen denen elaborierte Kommunikations- und Koordinationsprozesse erforderlich sind.

Solche Anwendungen finden sich mit zunehmender Rechnervernetzung und Plattform-Interoperabilität in verschiedensten Bereichen, von E- und M-Commerce über Supply Chain und Business Process Management bis hin zu Telekommunikation und Logistik. Nachfolgend werden die Grundlagen und der Entwicklungsstand von AOSE dargestellt.

Agenten und Objekte

Es gibt es drei herausragende Merkmale eines Agenten:

Flexibilität,
Autonomie und
Interaktivität.

Dabei bedeutet Flexibilität, dass ein Agent sowohl zu reaktivem (d.h. Umweltveränderungen in angemessener Zeit berücksichtigendem) als auch zu proaktivem (d.h. in Hinblick auf Zwischen- und Endziele vorausschauendem) Verhalten fähig ist.

Autonomie besagt, dass ein Agent bei Bedarf selbständig und unabhängig Entscheidungen über von ihm auszuführende zielrelevante Handlungen treffen kann und in diesem Sinn Kontrolle über seinen internen Zustand und sein Verhalten besitzt.

Schließlich impliziert Interaktivität insbesondere, dass Agenten auf hohem Niveau in Wechselwirkung treten können, also etwa im Rahmen von automatisierten Verhandlungen, Vertragsabschlüssen und verteilten Planungs- und Problemlösungsprozessen.

Mit dieser Charakterisierung werden auch die beiden als entscheidend betrachtenden Unterschiede zwischen dem agentenorientierten Paradigma und dem objektorientierten Paradigma deutlich (siehe z.B. [8]). Zum einen kapseln Objekte nur ihre Identität („wer"), ihren Zustand („was") und ihr Verhalten bzw. dessen Umsetzung („wie"), während Agenten zudem Freiheitsgrade in ihrer Aktionswahl und Interaktion („wann", „warum", „mit wem" und „ob überhaupt") kapseln. Zum anderen greift bloße Objektorientierung generell zu kurz, wenn es um adäquate, intuitive und natürliche Modellierung sowie programmiertechnische Umsetzung von komplexen Interaktionen (Kommunikation und Koordination, Kooperation und Konkurrenz) und Beziehungsstrukturen (dynamische Organisation und verteilte Kontrolle) zwischen Agenten geht.

Aufgrund dieser Unterschiede ermöglichen das Agenten- und das Objektkonzept auf qualitativ verschiedenen Abstraktionsebenen gleichermaßen relevante System- und Entwicklungssichten, die sich sinnvoll ergänzen statt gegenseitig ausschließen [12]. Die Agentensicht impliziert damit aber auch quer über alle Phasen der Softwareentwicklung zahlreiche neue, von der Objektsicht nicht abgedeckte Anforderungen und Fragestellungen.

Analyse und Design

Die verfügbaren Analyse- und Designmethoden für agentenorientierte Software lassen sich in drei Gruppen unterteilen:

Erweiterungen von objektorientierten Methoden (z.B. KGR [9]),
Erweiterungen von Methoden aus dem Knowledge Engineering (z.B. MAS-CommonKADS [7]) und
Methoden, die auf eine rein agentenspezifische Sicht ausgelegt sind (z.B. Gaia [15]).

Trotz ihrer verschiedenen disziplinären Wurzeln liegt das gemeinsame Hauptaugenmerk dieser Methoden auf der Modellierung von Prozessen und Ereignissen, die zwischen Agenten stattfinden. Dies soll anhand von Gaia illustriert werden.

Gaia sieht u.a. die Verwendung der folgenden drei Modelle vor:

Ein Rollenmodell zur Identifikation der verschiedenen Rollen, die von Agenten eingenommen werden können. Dabei sind Rollen definiert über Verantwortlichkeiten (zur Erhaltung erwünschter und Vermeidung unerwünschter Zustände), Zulässigkeiten (Rechte hinsichtlich Resourcen), Aktivitäten (die keine Interaktion erfordern) und Protokolle (zur Beschreibung der Art der Interaktion mit anderen Rollen).
Ein Interaktionsmodell, bestehend aus Interaktionsmustern zur Beschreibung von Abhängigkeiten und Beziehungen zwischen den verschiedenen Rollen in einem Multiagentensystem.
Ein Bekanntschaftsmodell zur Definition der möglichen Kommunikationspfade zwischen Agententypen, wobei ein Agententyp definiert ist über Rollenmengen.

Mit Hilfe der verschiedenen Modelle will Gaia agentenspezifische Konzepte „aufbrechen" und für objektorientierte und funktionale Techniken zugänglich machen.

Formale Spezifikation und Verifikation

Die formale Spezifikation und Verifikation von agentenorientierter Software gewinnt zunehmend an Bedeutung. Es lassen sich grob „traditionelle Formalismen" und „logikbasierte Formalismen" unterscheiden. Zu den traditionellen Formalismen zählen Repräsentationsformen und Techniken, die im Software und Knowledge Engineering zum Standard gehören, wie z.B. Z, VDM, UML, Petrinetze und funktionale Systemkomposition. Um agentenspezifische Konstrukte mit solchen Formalismen geeignet erfassen zu können, wurden entsprechende Erweiterungen und Anpassungen vorgeschlagen. Verwiesen sei hier lediglich auf den kompositionalen Modellierungsansatz DESIRE [2] für Multiagentensysteme und auf Agent-UML [13].

Inzwischen gibt es auch prototypische logikbasierte Ansätze, die speziell auf die Spezifikation und Verifikation von agentenorientierter Software ausgerichtet sind. Dabei handelt es sich häufig um erweiterte temporale Logiken bzw. um Sprachen, die auf solchen Logiken aufsetzen. Ein Beispiel hierfür ist die Logik TBL bzw. die Sprache Concurrent MetateM [5].

Implementierungssprachen

Es gibt drei Sprachtypen, die für die Realisierung von agentenorientierter Software und damit für AOSE zunehmend von Bedeutung sind. Diese Typen unterscheiden sich ebenfalls in ihrer fachlichen Verwurzelung und sie eröffnen damit unterschiedliche Zugänge zur programmiertechnischen Umsetzung von Agentensoftware.

Einer dieser Sprachtypen ist durch agentenorientierte Programmiersprachen gegeben, die als Weiterführung üblicher Programmiersprachen betrachtet werden können. Verschiedene Prototypen solcher Sprachen sind verfügbar, wie z.B. Derivate des „Klassikers" AGENT-0 [14] und die neuere Sprache 3APL [6]. Solche Sprachen unterstützen z.B. die Umsetzung von Verpflichtungen zwischen Agenten und planbasiertes Verhalten.

Einen zweiten relevanten Sprachtyp bilden Kommunikationssprachen, die ihre Wurzeln im Bereich der wissensbasierten Systeme haben. Bekannte Prototypen sind KQML, ARCOL und FIPA-ACL [10], die dem sprechaktbasierten Austausch von Wissen zwischen Agenten dienen. Andere „kommunikationsrelevante Sprachen" sind die Sprache KIF zur Beschreibung von Wissensinhalten und Sprachen wie ONTOLINGUA zur Konstruktion von Ontologien.

Der dritte relevante Sprachtyp sind Koordinationssprachen wie etwa COOL [1], die eine gewisse Nähe zu herkömmlichen Sprachen für parallele und verteilte Programmierung aufweisen. Konzeptionell ist dieser Sprachtyp „oberhalb" der beiden anderen angesiedelt. Koordinierungssprachen dienen der expliziten Handhabung von Abhängigkeiten zwischen Aktivitäten verschiedener Agenten.

Entwicklungstools

Es sind verschiedene Entwicklungstools für agentenorientierte Software verfügbar (z.B. JACK [3] und ZEUS [11]). Neben einigen kommerziellen Produkten handelt es sich dabei zumeist um Forschungsprototypen. Diese Tools betonen typischerweise Interaktionsaspekte (Kommunikation, Koordination und Organisation), wobei sie sich zum Teil deutlich in ihrer Funktionalität und Abdeckung des Software-Lebenszyklus unterscheiden. Um einen Eindruck von diesen Tools zu vermitteln, wird ZEUS kurz charakterisiert.

ZEUS wird am British Telecom Intelligent Systems Research Laboratory entwickelt und ist vollständig in Java 2 implementiert. Das Tool umfasst drei Komplexe:

eine Bibliothek mit funktionalen Agentenkomponenten wie z.B. TCP/IP-basierte Übermittlung von sprechaktbasierten Kommunikationsprimitiven, vordefinierte Koordinationsstrategien und Organisationsbeziehungen, einen allgemeinen Planungs- und Schedulingmechanismus und eine Schnittstelle zu existierender Software;
mehrere Editoren zur Beschreibung und Spezifikation verschiedener agentenspezifischer Aspekte wie z.B. Ontologien und organisationale Strukturen;
verschiedene Tools zur Visualisierung z.B. von Agent-Agent-Beziehungen, Aufgaben- und Ausführungsverteilung und statistischen Auswertungen.

ZEUS ist ein sehr umfangreiches Tool, da es auf die Abdeckung aller Phasen abzielt und ein recht allgemeines Agentenmodell verwendet.

Fazit

AOSE ist ein junger und sich schnell entwickelnder Bereich. Für das wachsende Interesse an AOSE und agentenorientierter Software gibt es verschiedene Gründe:

Anwendungspotential: AOSE stellt sich der ständig wachsenden Herausforderung, Softwaresysteme für immer komplexere – offene, verteilte, dynamische, heterogene und interaktive – Anwendungsfelder zu realisieren.

Industrielle und kommerzielle Resonanz: Die Industrie zeigt zunehmend Interesse an agentenorientierten Softwareprodukten. Dies spiegelt sich z.B. auch wider in den verschiedenen industrieseitig forcierten Standardisierungsbestrebungen im Umfeld von Agentensoftware [17].

Verträglichkeit: Agentenorientierung ist mit anderen Entwicklungen auf dem Gebiet des Software Engineering konsistent (z.B. Design Patterns) oder schließt an existierende Methodologien beinahe nahtlos an (z.B. aufgabenorientierte Softwareentwicklung). Darüber hinaus sind agenten- und objektorientierte Softwaresysteme prinzipiell integrierbar.

Natürliche Entwicklung: Allgemeiner kann Agentenorientierung als ein natürlicher nächster Schritt in der Programmierentwicklung betrachtet werden, denn ausgehend von maschinennaher bis hin zur objektorientierten Programmierung zeigt sich zunehmende Abstrahierung und Lokalisierung.

Diese Gründe sollten jedoch nicht darüber hinwegtäuschen, dass AOSE in verschiedenerlei Hinsicht noch in den Kinderschuhen steckt. Handlungsbedarf besteht in Hinblick auf eine weitere konzeptuelle und theoretische Fundierung von agentenspezifischen Konzepten ebenso wie die Weiterentwicklung von Analyse- und Designmethoden, Verifikations- und Testverfahren und Entwicklungstools. Die bislang existierenden agentenorientierten Hilfsmittel für die verschiedenen Softwareentwicklungsphasen bewegen sich größtenteils auf einer prototypischer Ebene. Hier ist weitere Grundlagenforschung und Anwendungserfahrung erforderlich.

Abschließend sei noch auf den erstmals ausgerichteten AOSE-Workshop [4] im Rahmen der letztjährigen 22nd International Conference on Software Engineering verwiesen; der Nachfolgeworkshop findet Ende Mai statt [16].

Artikelanfang Seitenanfang

Literatur

Barbuceanu, M., Fox, M. S.: Capturing and Modeling Coordination Knowledge for Multiagent Systems. International Journal of Cooperative Information Systems 5(2–3), 275–314 (1996)
Brazier, F. M. T., et al.: DESIRE: Modelling Multi-Agent Systems in a Compositional Formal Framework. International Journal of Cooperative Information Systems 6(1), 67–94 (1997)
Busetta, P., et al.: JACK Intelligent Agents – Components for Intelligent Agents in Java. Agentlink News 2, 2–5 (1999)
Ciancarini, G., Wooldridge, M. (eds.): Agent-Oriented Software Engineering. Berlin Heidelberg New York: Springer 2001
Fisher, M., Wooldridge, M.: On the Formal Specification and Verification of MultiAgent Systems. International Journal of Cooperative Information Systems 6(1), 37–65 (1997)
Hindriks, K. V., et al.: Agent Programming in 3APL. Autonomous Agents and Multiagent Systems 2(4), 357–401 (1999)
Iglesias, C. A., et al.: Analysis and Design of Multiagent Systems Using MAS-CommonKADS. Proceedings of the 4th International Workshop on Agent Theories, Architectures, and Languages (ATAL'97). Berlin Heidelberg New York: Springer 1998, pp. 313–327
Jennings, N. R.: On Agent-Based Software Engineering. Artificial Intelligence 117, 277–296 (2000)
Kinny, D., Georgeff, M., Rao, A.: A Methodology and Modelling Technique for Systems of BDI Agents. Proceedings of the 7th European Workshop on Modelling Autonomous Agents in a Multi-Agent World (MAAMAW'96). Berlin Heidelberg New York: Springer 1996, pp. 56–71
Kone, M. T., Shimazu, A., Nakajima, T.: The State of the Art in Agent Communication Languages. Knowledge and Information Systems 2, 259–284 (2000)
Nwana, H. S., et al.: ZEUS: A toolkit for Building Distributed Multiagent Systems. Applied Artificial Intelligence 13(1), 129–186 (1999)
Odell, J.: Objects and Agents: Is there room for both? Distributed Computing, 44–45 (November 1999)
Odell, J. , Parunak, H. V. D., Bauer, B.: Extending UML for agents. 2nd International Workshop on Agent-Oriented Information Systems (AOIS'2000)
Shoham, Y.: An Overview of Agent-Oriented Programming. In: Bradshaw, J. M. (ed.): Software Agents. AAAI Press 1997, pp. 271–290
Wooldridge, M., Jennings, N. R., Kinny, D.: The Gaia Methodology for Agent-Oriented Analysis and Design. Autonomous Agents and Multiagent Systems 3, 285–312 (2000)
2nd International Workshop on Agent-Oriented Software Engineering (AOSE'01) (www.csc.liv.ac.uk/ ~ mjw/aose/)
FIPA (www.fipa.org) und OMG Agents Working Group
(http://www.objs.com/ isig/agents.html)

Artikelanfang Seitenanfang

Autor & Copyright
Gerhard Weiß
Institut für Informatik,
Technische Universität München,
80290 München
weissg@in.tum.de

Artikelanfang Seitenanfang

Semantische Abfrageoptimierung

Erläuterung
Literatur
Autor & Copyright

Erläuterung

Der überwältigende Erfolg relationaler Datenbanksysteme ist vor allem auf die Verwirklichung des Begriffs der Datenunabhängigkeit zurückzuführen. Dadurch können Anwender für ihren jeweiligen Anwendungsbereich Datenbanken benutzen, ohne daß aus der fehlenden Kenntnis von systemnahen Details wie Zugriffspfade und Speicherstrukturen längere Antwortzeiten der Anfragen folgen oder gar die Formulierung von Anfragen beeinträchtigt wird. Dies vereinfachte die Anfrageformulierung für bisherige Nutzer und erweiterte die Akzeptanz von Datenbanksystemen erheblich.

Der damit verbundene Übergang von einer prozeduralen zu einer nichtprozeduralen Formulierung der Anfragen erfordert die Einführung einer weiteren Übersetzungsphase. Diese Ubersetzung muß die fehlende Information in Anfragen über Zugriffspfade und Speicherstrukturen durch beispielsweise algebraische Gesetze und Kostenmodelle kompensieren, um eine möglichst kostengünstige Beantwortung zu gewährleisten. Solche Techniken werden unter dem Begriff Anfrageoptimierung zusammengefaßt. Nach dem ökonomischen Prinzip wird durch Optimierung entweder das Ergebnis bei festem Verbrauch von Betriebsmitteln maximiert oder der Verbrauch von Betriebsmitteln bei gleichem Ergebnis minimiert. Durch Anfrageoptimierung wird immer der Verbrauch der Betriebsmittel minimiert, da das Ergebnis fest definiert ist.

Der Schwerpunkt bisheriger Optimierungen liegt dabei auf einer möglichst direkten Abbildung der nichtprozeduralen Sicht auf die physischen Objekte eines Datenbanksystems, wie Härder [4] betont. Das dafür dem System zur Verfügung stehende notwendige Wissen bezieht allerdings kein Wissen über den Anwendungsbereich selbst mit ein, obwohl dies zu erheblichen Verbesserungen der Leistungsmerkmale eines Datenbanksystems führen würde, wie Chakravarthy et al. [2] vermerken. Deshalb schlagen sie eine Erweiterung der Optimierung vor, die auch Wissen über die Bedeutung des Anwendungsbereichs miteinbezieht und bezeichnen dies als semantische Anfrageoptimierung. Date [3] sieht in dieser Anfrageoptimierung ein enormes Potential:

So far as this writer is aware, few commercial products do much in the way of semantic optimization. In principle, however, such optimization could provide very significant performance improvements – much greater improvements, very likely, than are obtained by any today’s traditional optimization techniques.

Nun interessieren natürlich die Gründe für die Diskrepanz zwischen Potential und wirklichem Einsatz. Dazu sollen zuerst drei exemplarische Arbeiten betrachtet werden, die auch drei prinzipielle Strategien der semantischen Anfrageoptimierung verdeutlichen.

Erfüllbarkeitsbasierte Strategie

Zur Überprüfung der Erfüllbarkeit von Anfragen eignen sich gut logikbasierte Anfragesprachen wie DATALOG. Basierend auf der Erfüllbarkeit können nun Probleme wie die Gleichheit oder Minimierung von Anfragen unter Berücksichtigung von Integritätsbedingungen untersucht werden. Levy und Sagiv [7] definieren semantische Anfrageoptimierung generell als einen Prozeß, Integritätsbedingungen zur Optimierung von Anfragen zu verwenden. Diese Definition ist allerdings zu eng gefaßt, wie im weiteren gezeigt wird.

Heuristikbasierte Strategie

Hier werden Heuristiken zur Anfrageoptimierung verwendet. King [6] verwendet beispielsweise die Heuristik in dem System QUIST: Füge in jede Anfrage Bedingungen über indexierte Attribute ein. Generell gilt, daß indexierte Attribute in einer Anfrage den Zugriff über eine Baumstruktur ermöglichen. Ohne indexierte Attribute muß sequentiell gesucht werden. Das verwendete Wissen besteht dabei aus Integritätsbedingungen, die Werte verschiedener Attribute einer Relation in Bezug setzen, unter anderem auch die Werte von indexierten Attributen.

Regelbasierte Strategie

Bei dieser Strategie werden Bedingungen aus Anfragen extrahiert, die bei Erfüllung durch die Wissensbasis immer zu einer Reformulierung führen. Beispielsweise verwenden Paulley und Larson [8] die Schlüssel einer Relation, um zu zeigen, daß Antwortmengen keine Duplikate enthalten können. Dementsprechend können distinct-Anweisungen in SQL-Anfragen entfernt werden, die sonst eine unnötige Prozedur zur Duplikateliminierung veranlassen.

Allerdings erklären diese Ansätze noch nicht die Diskrepanz von Potential und tatsächlichem Einsatz. Deshalb soll die Anfrageoptimierungen noch genauer betrachtet werden. Ein Datenbanksystem besteht nach Ullman [10] aus einem Datenbankmanagementsystem (DBMS), das alle Programme zur Datenverwaltung umfaßt, und den einzelnen Datenbanken, die die Daten beinhalten. Betrachtet man die Optimierungen unter dem Aspekt der Nutzung von Wissen, dann ist ein qualitativer Unterschied die Verfügbarkeit des Wissens: Zugriffspfade und Speicherungsstrukturen sind jeweils pro DBMS fest vorgegeben. Algebraische Gesetze gelten für alle DBMSe, und die Kostenmodelle basieren auf einfachen statistischen Merkmalen einer Datenbank. Dagegen impliziert der Inhalt einer Datenbank eine große Bandbreite für das zur semantischen Anfrageoptimierung vorausgesetzte Wissen. Wird semantische Anfrageoptimierung nun ausschließlich über Integritätsbedingungen definiert, dann ist der Erfolg der Anfrageoptimierung von Wissen abhängig, das Benutzer zuvor spezifizieren müssen.

Siegel [9] schlägt deshalb eine neue Definition für die semantische Anfrageoptimierung vor:

. . . defining semantic query transformation as the addition or removal of constraints to a query in accordance with a given rule set. The transformed query is semantically equivalent to the original query in the sense that if the database state satisfies the rules, then the transformed query will return the same answer from the database.

Damit werden Constraints nicht mehr als Integritätsbedingungen einer Datenbank, sondern als Wissen über einen Datenbankzustand betrachtet. Zur besseren Unterscheidung soll dieses Wissen als Metadaten bezeichnet werden. Diese neue Sichtweise erlaubt nicht nur, einzelne Datenbankzustände genauer zu beschreiben, sondern ermöglicht auch, maschinelle Verfahren zur Entdeckung der Metadaten einzusetzen. Beispiele hierfür sind:

Hsu und Knoblock [5] verwenden Anfrageergebnisse, um mit Techniken des maschinellen Lernens allgemeine Bedingungen abzuleiten, die sie dann zur Reformulierung neuer Anfragen benützen.
Bell [1] stellt Methoden zur Entdeckung aller derzeit in einer Datenbank gültigen funktionalen Abhängigkeiten und eine Optimierung durch das Entfernen unnötiger distinct- und group by-Anweisungen vor. Dabei werden bei Änderungen des Datenbankzustands die Metadaten auch gewartet.

Der Nachteil von Siegels Lösung ist, daß die Entdeckung und Wartung der Metadaten Kosten verursacht. Die Kosten der Entdeckung müssen allerdings nicht in die Kosten der Optimierung einfließen, da sie zu Zeiten niedriger Auslastung des Systems stattfinden kann. Damit kann die semantische Anfrageoptimierung auch als eine Art Lastverteilung betrachtet werden: Zu Zeiten niedriger Auslastung werden Metadaten entdeckt, die dann zu Zeiten höherer Auslastung die Beantwortung der Anfragen beschleunigen.

Die bisherigen Ansätze erlauben allerdings noch keine Aussage, ob Siegels Lösung Dates Prognose unterstützt, daß semantische Anfrageoptimierung einmal gewinnbringender als die anderen Optimierungen sein wird.

Artikelanfang Seitenanfang

Literatur

Bell, S.: Deciding distinctness of query result by discovered constraints. In Practical Application of Constraint Technology (1996)
Chakravarthy, U. S., Grant, J., Minker, J.: Logicbased Approach to semantic query optimisation. ACM Transaction on Database Systems 15, 2 (June 1990)
Date, C.: An Introduction to Database Systems, 6th ed. The Systems Programming Series. Addison-Wesley Publishing Company, 1995
Härder, T.: Realisierung von operationalen Schnittstellen. In Datenbankhandbuch.
Springer Verlag, 1987
Hsu, C. N., Knoblock, C. A.: Using inductive learning to generate rules for semantic query optimization. In Advances of Knowledge Discovery and Data Mining. AAAI Press, 1995, ch. 17
King, J. J.: Query optimization by semantic reasoning. Tech. Rep.
STAN-CS-81-857, Stanford University, May 198
Levy, A. Y., Sagiv, Y.: Semantic query optimization in datalog programs. In Proceedings of the 14th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (May 1995), ACM
Pauley, G., Larson, P.-A.: Exploiting uniqueness in query optimization.
In Proceedings of the 10th Conference on Data Engineering (1994), IEEE
Siegel, M. D. Automatic rule derivation for semantic query optimization.
In: Second internastional Conference on Expert Database Systems (198
Ullman, J. D. Principles of Database and Knowledgebase Systems, vol. 1. Computer Science Press, 1988

Artikelanfang Seitenanfang

Autor & Copyright
Siegfried Bell,
Universtät Dortmund,
Informatik VIII,
D-44221 Dortmund
bell@informatik.unidortmund.de

Artikelanfang Seitenanfang

Archivierung in Datenbanksystemen

Erläuterung
Literatur
Autor & Copyright

Erläuterung

Datenbanksysteme sind dafür geschaffen worden,um große Datenmengen adäquat behandeln zu können, d.h. diese Datenmengen strukturiert abzulegen sowie Such- und Änderungsdienste darauf bereitzustellen. Die heutigen relationalen Datenbanksysteme sind auch weitestgehend dazu in der Lage, die in sie gesetzten Erwartungen zu erfüllen. Probleme treten jedoch in der Praxis in vielen Fällen dann auf, wenn die Datenmengen wirklich sehr groß werden (etwa im Bereich vieler Hundert Gigabyte oder im Terabyte-Bereich): Es wird immer mehr Sekundärspeicher (Platten) benötigt, der „online" gehalten werden muß; die Zugriffszeiten zu den Daten wachsen an, da auch bei effektiver Speicherorganisation und Zugriffspfadnutzung ein größer werdender Datenbestand bzgl. der Performance nicht völlig neutralisiert werden kann; die Backup- und Recovery-Zeiten nehmen zu; gewisse Schwellwerte des Datenbank-Management-Systems (DBMS), wie z.B. Maximalgröße von Tabellenbereichen, werden erreicht und drohen,einen DBMS-Stillstand zu verursachen bzw. erfordern massives Eingreifen durch den Datenbankadministrator (DBA); die Übersichtlichkeit des Datenbestands leidet, da oftmals aktive und inaktive, weitgehend veraltete Daten vermischt im Datenbestand auftreten etc.

Die Probleme verschärfen sich dadurch weiter, daß gerade in jüngerer Zeit bzgl. der Datenhaltung Entwicklungstendenzen und Anwenderwünsche zu beobachten sind, die auf den ersten Blick nur schwer miteinander vereinbar erscheinen: Auf der einen Seite werden die Datenbestände typischerweise immer größer (so wird bereits von Datenbeständen im praktischen Einsatz berichtet, bei denen einzelne Tabellen -zig Milliarden Zeilen aufweisen [6]), auf der anderen Seite werden gleichzeitig immer höhere Verfügbarkeitsanforderungen gestellt in Richtung auf einen 24-Stunden-Betrieb an 365 Tagen im Jahr. Es liegt auf der Hand, daß beispielsweise klassische Verfahren der Datensicherung oder Datenreorganisation hier nicht mehr angemessen sind, wenn sie mit sehr großen Datenmengen umgehen sollen und gleichzeitig den OLTP-Betrieb (Online Transaction Processing) nicht wesentlich behindern dürfen; auch neue Verfahren schaffen nur begrenzt Abhilfe in Anbetracht des „Datenwusts".

Letztendlich gibt es aus praktischer Sicht zwei Möglichkeiten, auf die beschriebene Situation zu reagieren: Es wird versucht, durch Datenlöschungen das Anwachsen der Datenmengen zum Stillstand zu bringen oder wenigstens zu bremsen, oder es erfolgt eine Datenarchivierung aus der Datenbank heraus auf geeignete andere Speichermedien. Datenlöschungen sind oftmals nicht möglich oder im geforderten Umfang nicht erwünscht, da betriebswirtschaftliche oder rechtliche Gründe dagegensprechen (Wiederbenutzung (auch) der alten Daten für betriebliche Zwecke nicht auszuschließen, Daten werden für Revisionszwecke und aufgrund gesetzlicher Regelungen doch noch gelegentlich nachgefragt u. dgl. mehr). Da das Weiteranwachsen der Datenmengen auch keine Lösung darstellt, bleibt die Datenarchivierung somit als erwägenswerte Alternative.

Im einfachsten Fall kann Archivieren bedeuten, daß solche Datenbankinhalte, die aktuell nicht (mehr) oder nur noch sehr selten gebraucht werden,entladen werden auf geeignete (Tertiärspeicher-) Medien; diese werden dann „in den Schrank" gestellt, bis man die auf ihnen abgelegten Daten eventuell wieder einmal benötigt.

Das Lesen der archivierten Daten und ein mögliches Wiedereinladen in die Datenbank werden manuell angestoßen und zeigen schon die Schwerfälligkeit dieses Vorgehens, das jedoch in der Praxis weit verbreitet ist. Auch bekannte Anwendungssysteme,wie das System R/3 von SAP, verfolgen heute eine Archivierungslösung, die nicht sehr weit von jenem einfachen Vorgehen entfernt liegt [5]. Man spricht hier auch von datenbanksystembasierter Archivierung, denn die zu archivierenden Daten werden mittels einer Anwendungsschicht aus der Datenbank herausgeholt und in ein separates Archiv übertragen, das sich nicht unter Kontrolle des Datenbanksystems befindet. Dabei wird eine Verschiebesemantik verfolgt, die zu archivierenden Daten werden also ins Archiv bewegt und verbleiben nicht in der Datenbank, sondern werden dort gelöscht. Obwohl hier zusätzliche unterstützende Dienste denkbar sind (bspw. zur Verwaltung und zum Zurückladen archivierter Daten), besitzt diese nur sehr lose Anbindung von Datenbank und Archiv offensichtliche Nachteile, wenn man etwa an Forderungen denkt wie eine übergreifende Integritätsüberwachung zwischen Datenbank und Archiv, die Einbindung der Archivierung in Datenbanktransaktionen u. a.m. Ein Vorteil der datenbanksystembasierten Archivierung liegt in der vergleichsweise einfachen Realisierbarkeit, weil sie keine Eingriffe ins DBMS (funktionale Erweiterungen dort) erfordert.

Beispiele für praktisch eingesetzte Lösungen im Bereich der datenbanksystembasierten Archivierung sind das ADK (Archive Development Kit) des Systems R/3 [5] und CERA (Climate and Environmental Data Retrieval and Archiving System) vom Deutschen Klimarechenzentrum [3]. Das ADK ermöglicht die Entwicklung von Archivierungsprogrammen für die R/3-Anwendungen. Beim Archivieren werden Daten der Datenbank in Archivdateien geschrieben und anschließend aus der Datenbank gelöscht. Die Archivdateien befinden sich zunächst auf Magnetplatte, können aber auf Tertiärspeichermedien verschoben werden. CERA basiert auf Oracle und realisiert die Migration von Tabellenbereichen auf Bänder. Ausgenutzt wird hierbei die Möglichkeit, Tabellenbereiche in Oracle „offline" zu setzen und auf Tertiärspeicher auszulagern, bis eine spätere Nutzung eine Wiedereinlagerung erforderlich macht.

Der datenbanksystembasierten steht die datenbanksystemintegrierte Archivierung gegenüber. Dort bietet das DBMS integriert selbst Archivierungsdienste an, d.h. es kennt und kontrolliert auch das Archiv und bietet damit Möglichkeiten, die sonst der (zu) losen Anbindung zwischen Datenbank und Archiv wegen nicht ohne weiteres realisierbar wären. Idealerweise werden hier die Archivierungsdienste in Form von erweitertem SQL angeboten, um auf diesem Wege etwa die Archivierung von Daten zu veranlassen, im Archiv zu lesen oder Daten aus dem Archiv in die Datenbank zurückzuholen.

In den heutigen (relationalen) Datenbanksystemen ist solche Funktionalität jedoch noch nicht vorhanden; eine Möglichkeit, sich dem Idealzustand jedoch wenigstens anzunähern, liegt in einer Nachbildung des integrierten durch einen basierten Ansatz [4].

Eine wichtige Forderung bei der Bereitstellung von Archivierungsfunktionalität ist die Anwendungsorientierung. Anwendungsorientiertes Archivieren [2] läßt sich durch vier Eigenschaften charakterisieren:

Benutzerveranlassung, d.h. das Archivieren geschieht nicht primär implizit durch das DBMS veranlaßt, sondern explizit durch den Benutzer oder DBA.
Abstraktionsebene Datenmodell, d.h. es werden solche Granulate beim Archivieren angesprochen, die dem Benutzer/DBA auf der Ebene des Datenmodells bekannt sind (relational also etwa Tabellen oder Tupel, nicht aber bspw. Tabellenbereiche oder Dateien).
Datenauslagerung im Sinne der zuvor bereits erwähnten Verschiebesemantik, also Überführen von Daten ins Archiv und nicht einfaches Kopieren.
Archivzugriff schließlich, wofür Funktionalität gebraucht wird zum Lesen auf dem Archiv und ggf. auch zur Rückübertragung von Daten aus dem Archiv in die Datenbank.

Diese Forderung nach Anwendungsorientierung grenzt gleichzeitig ab zu anderen DBMS-Funktionalitäten, wo speziell in der Praxis manchmal auch von Archivieren gesprochen wird: Das Erstellen einer Sicherungskopie einer Datenbank (Backup) hat z.B. nichts mit (anwendungsorientiertem) Archivieren zu tun, denn u. A. wird hier nicht ausgelagert, sondern es werden Daten kopiert, und der Archivzugriff auf selektive Weise ist hier auch nicht möglich, es wird auch eine ganz andere Intention dabei verfolgt als beim Archivieren im Verständnis dieses Beitrags.

Wichtig fürs Archivieren ist die Möglichkeit zur Nutzung von Tertiärspeichermedien. Sekundärspeichermedien (i.w. Magnetplatten) werden zwar seit Jahren auch stets preiswerter und bieten immer höhere Kapazitäten, aber bei Datenbankgrößen im Terabyte-Bereich - und künftig auch darüber hinausgehend - spielt der Kostenfaktor dann doch auch heute und in Zukunft eine signifikante Rolle. Tertiärspeichernutzung für Archive bedeutet nach heutigen Technologien i.w. die Verwendung von Magnetbändern (und Bandrobotern) sowie von optischen Platten. Tertiärspeicher kann dabei auf verschiedene Weise ins DBMS eingebunden bzw. ans DBMS angebunden werden. Kommerziell verbreitet sind heute bereits die sog. HSM-Systeme (Hierarchical Storage Manager),wo Tertiärspeicher in einer Speicherhierarchie hinter dem Sekundärspeicher angeordnet wird und typischerweise ganze Dateien je nach Bedarf zwischen dem Sekundär- und dem Tertiärspeicher ausgetauscht werden. Dieser Austausch erfolgt aus Sicht der Anwendung, und damit auch des DBMS, transparent, d.h. es ist „lediglich" anhand der Performance zu verspüren, ob zugegriffene Daten bereits auf Sekundärspeicher waren oder ob sie erst vom Tertiär- auf den Sekundärspeicher geladen werden mußten. Für anwendungsorientiertes Archivieren eignet sich dieses Vorgehen somit nicht unmittelbar, da dort Benutzerveranlassung des Archivierens gefordert wird und auch eine sichtbare, physische Trennung zwischen Datenbank und Archiv. Lösungen,die sich hier für die Archivierung anbieten, liegen also außerhalb der HSM-Systeme; der Tertiärspeicher muß explizit angesprochen werden können übers DBMS (bei datenbanksystemintegriertem Archivieren) oder die zuständige Anwendungsschicht (bei datenbanksystem-basiertem Archivieren).

In Zusammenhang mit dem Archivieren in Datenbanksystemen ergibt sich eine Fülle von Aufgabenstellungen und Problemen, wobei grob gesagt werden kann, daß gute Lösungen eher absehbar sind beim datenbanksystemintegrierten als beim -basierten Ansatz. Ein Problembereich wurde schon erwähnt: Die Auswirkungen des Vorhandenseins eines Archivs auf die Integritätssicherung, d.h. wie bspw. übergreifende Integritätsbedingungen zwischen Datenbank und Archiv definiert und unterstützt werden können,wie auch im Fehlerfall sichergestellt werden kann, daß Datenmengen nicht „halbarchiviert" verbleiben usw. Ein weiterer Problembereich hängt mit der (in der Praxis alltäglichen) Evolution des Datenbankschemas zusammen: Das Datenbankschema ändert sich, und die Frage ist zu klären, was entsprechend mit dem Archivschema geschieht. Auch die Art der Tertiärspeichernutzung und mögliche -integration kann als Problembereich gesehen werden,denn heutige DBMS-Produkte bieten noch keine volle Integration hier an (Tertiärspeicher wirklich als „first class citizen" [1]). Die Praxis zeigt jedoch, daß vielerorts schon Archivierungslösungen entwickelt wurden und entwickelt werden, i.d.R. bisher mittels eines datenbanksystembasierten Ansatzes. D.h., obwohl die Datenbank-Management-Systeme immer bessere Lösungen auch zum Umgang mit sehr großen Datenmengen anbieten und obwohl Sekundärspeicher immer billiger wird und immer größere Kapazität aufweist, bieten die rapide anwachsenden Datenmengen offenbar genügend Veranlassung, auch weiterhin verstärkt über Archivierung nachzudenken und Lösungen zu entwickeln.

Artikelanfang Seitenanfang

Literatur

Carey, M.J., Haas, L.M., Livny, M.: Tapes Hold Data, Too: Challenges of Tuples on Tertiary Store. In: Proc. of ACM SIGMOD Int.
Conf. on Management of Data, pp. 413-417, Washington, DC, 1993
Herbst, A.: Anwendungsorientiertes DB-Archivieren: Neue Konzepte zur Archivierung in Datenbanksystemen. Berlin, Heidelberg: Springer 1997
Lautenschlager, M.: Concept of the Climate Database System at the DKRZ. In: Lautenschlager, M., Reinke, M. (eds.), Climate and Environmental Database Systems, pp. 11-24. Boston: Kluwer Academic Publishers 1997
Schaarschmidt, R., Bühnert, K., Herbst, A., Küspert, K., Schindler, R.: Konzepte und Implementierungsaspekte anwendungsorientierten Archivierens in Datenbanksystemen. Informatik Forschung und Entwicklung, 13(2): 79-89 (1998)
Schaarschmidt, R., Röder, W.: Datenbankbasiertes Archivieren im SAP System R/3. Wirtschaftsinformatik, 39(5): 469-477 (1997)
Winter, R., Auerbach, K.: The Big Time. Database Programming & Design, 11(8): 36-45 (1998)

Artikelanfang Seitenanfang

Autor & Copyright
Klaus Küspert, Ralf Schaarschmidt
Friedrich-Schiller-Universität Jena
Institut für Informatik
Lehrstuhl für Datenbanken und Informationssysteme
Ernst-Abbe-Platz 1 - 4
07743 Jena
kuespert@informatik.uni-jena.de
schaar@informatik.uni-jena.de

Artikelanfang Seitenanfang

Autostereogramme

Erläuterung
Literatur
Autor & Copyright

Erläuterung

In letzter Zeit werden großformatige Bilder, Postkarten und Bücher feilgeboten, auf denen man bunte Muster sieht, die sich wiederholen. Betrachtet man die Bilder unscharf, indem man hinter die Bildebene fokussiert, erscheint nach einiger Zeit eine räumliche Szene, die mit dem ursprünglichen Muster texturiert ist. Das Erkennen dieser Bilder erfordert einige Übung, und nicht alle Menschen sind in der Lage, den räumlichen Effekt zu erkennen.

Dieses Verfahren ist keineswegs so neu wie uns manche Anbieter glauben lassen möchten, und es kann auch auf heutigen Personal Computern durchgeführt werden. Es werden mehrere frei zugängliche Programme angeboten.

Diese Bilder bezeichnet man mit dem Oberbegriff Autostereogramm oder SIS (Single Image Stereogram). Damit können Informationen räumlich dargestellt werden. Andere Verfahren zur räumlichen Darstellung sind Stereogramme, die aus zwei separaten Bildern bestehen, Rot-Grün-Stereogramme, Shutter-Verfahren an speziellen Displays und Holographie. Anwendungen für SIS gibt es vor allem im künstlerischen Bereich. Ursprünglich wurden sie in Experimenten zur Physiologie des Stereosehens eingesetzt. Ein Autostereogramm besteht aus einem Rasterbild mit sich wiederholenden Mustern. Die räumliche Information wird dadurch gewonnen, daß die Wiederholungen nicht exakt identisch sind. Fokussiert man dieses Bildmuster mit beiden Augen etwas hinter der Bildebene, erscheint eine räumlich wirkende Figur, die das Bildmuster als Textur trägt. Die Muster können vorgegebene Rasterbilder sein oder aus Zufallswerten bestehen. Ein SIRDS (Single Image Random Dot Stereogram) ist ein Autostereogramm, das aus scheinbar zufällig verteilten Bildpunkten besteht. SIRTS (Single Image Random Text Stereogram) sind dagegen aus Buchstaben aufgebaut. Da diese einfach auf Papier oder einem Bildschirm dargestellt werden können, sind sie als Signatur in elektronischen Briefen beliebt.

Bei herkömmlichen Stereogrammen (Zeichnungen oder Fotografien) liegen die Ansichten für jedes Auge getrennt vor. Dieses Verfahren wurde früher für Fotografien benutzt. Das Betrachten wird durch eine Sehhilfe erleichtert, die sicherstellt, daß jedes Auge die richtige Ansicht sieht. Im Gehirn wird diese Information zu einem räumlichen Eindruck verarbeitet. Bei Autostereogrammen liegt die Information für beide Ansichten in einem einzigen Bild.

Allen Stereoverfahren ist gemeinsam, daß die Information über die Parallaxe im Datenmaterial enthalten sein muß. Als Parallaxe wird der Winkel bezeichnet, den die beiden Sehstrahlen bilden, wenn sie auf einen Punkt fokussiert werden. Meist wird nur die horizontale Parallaxe berücksichtigt, da sonst der Rechenaufwand zu groß würde. Daher verschwindet der räumliche Effekt, wenn man ein Autostereogramm beim Betrachten dreht.

Stereogramme haben eine lange Tradition vor allem in den Bereichen Computersehen und Computergraphik. Erste Versuche zu Random Dot Stenogrammen (RDS) wurden von B. Julesz etwa ab 1960 unternommen. Zu ihrer Erstellung wurden bereits Computer verwendet. D. Marr und T. Poggio stellen ihre umfassende Theorie über das menschliche Stereosehen auf und beschreiben unter anderem RDS, die jedoch aus zwei nebeneinanderliegenden Bildern bestehen [1].

Tyler und Clarke entwickeln 1990 das Autostereogramm, das nur mit einem Bild auskommt. Der Algorithmus wird von Thimbleby, Inglis und Witten [2] verbessert und über das Internet verbreitet, weshalb die meisten Programme in diesem vergleichsweise einfachen Algorithmus ihren Ausgangspunkt haben. Eingabe in den Algorithmus ist eine Höhenmatrix, ein Rasterbild aus Höhenwerten. Diese wird von einer Betrachterposition oberhalb der Matrix aus mit dem linken und dem rechten Auge betrachtet. Der Abstand der beiden Sehstrahlen auf einer Bildebene wird errechnet und die betroffenen Pixel der Bildebene werden ermittelt. In Abb. 1 wird dieser Zusammenhang erläutert. Zusätzlich müssen Verdeckungen berücksichtigt werden.

Abb. 1 Geometrischer Zusammenhang bei der Erzeugung von SIS. Der Wert d (Displacement) gibt den Abstand zwischen linkem und rechtem Sehstrahl bezüglich der gewählten Bildebene a, d variiert abhängig von den Tiefenwerten.

Da nur die horizontale Parallaxe von Interesse ist, geht man zeilenweise vor. Im Endresultat müssen die jeweiligen Pixel für linken und rechten Sehstrahl denselben Farbwert besitzen. Anhand der vorher ermittelten Pixelkoordinaten bildet man verkettete Listen aller Pixel, die denselben Farbwert erhalten müssen.

In einem zweiten Durchgang wird die Farbe der Pixel festgelegt, indem man jeder verketteten Liste einen Farbwert zuordnet und diesen wiederum an die entsprechenden Pixel weitervererbt. Die Wahl der Pixelfarben kann entweder durch Zufallszahlen oder anhand vorgegebener Bilder erfolgen.

Das Verfahren kann mit dem Raytracing Verfahren [3] auf beliebige, dreidimensionale Szenen erweitert werden. Dazu benötigt man zwei Augenpunkte, die bezüglich der Bildebene nur eine horizontale Parallaxe bilden. Zum linken Augenpunkt berechnet man den Trefferpunkt zwischen Anfragestrahl und Szene. Ein neuer Anfragestrahl vom Trefferpunkt zum rechten Auge bestimmt den Wert der Parallaxe, der wiederum zur Berechnung der verketteten Listen verwendet wird. Dieses Verfahren läßt sich leicht in einen Raytracer einbauen, da zusätzlich nur neue Strahlanfragen eingesetzt werden. Eventuelle Verdeckungen werden ohne Zusatzaufrufe ermittelt.

Es ist zwar möglich, farbige SIS zu erstellen, jedoch können die räumlichen Szenen nur mit dem Texturmuster des Originalbildes versehen werden. Die Darstellung der Szenen in den richtigen Farben ist dagegen nicht möglich.

Manche Beobachter sehen die Szenen auf den SIS invertiert, d.h. als Abdruck des Objektes. Dies hängt mit der Physiologie des Stereosehens zusammen. Beim Betrachten der SIS ist es nicht eindeutig, welche der Bildpunkte zusammengehören. Zudem ist es möglich so zu fokussieren, daß linker und rechter Punkt vertauscht werden, indem die Sehstrahlen überkreuzt werden.

Das Thema wird zur Zeit mit den NetNews intensiv diskutiert [4]. Einige der dort verbreiteten Informationen können jedoch nicht vorbehaltlos übernommen werden. Mehrere Künstler haben diese Technik adaptiert (teilweise in den USA patentiert), geben Bildbände heraus und vertreiben Bilder, Poster und Postkarten. Einige dieser Arbeiten zeichnen sich durch zusätzliche Experimente und Verzierungen aus. In einigen Zeitschriften werden auch Hinweise zum selber experimentieren veröffentlicht [5].

In Abb. 2 wird ein SIRDS dargestellt, das mit einer vom Autor modifizierten Raytracing Methode und dem Algorithmus von Thimbleby, Inglis und Witten erstellt wurde. Es empfiehlt sich, das Bild etwa aus dem Abstand einer Armlänge aus zu betrachten. Sehen Sie unscharf auf das Bild, indem Sie ein Objekt fokussieren, das etwa 30 cm hinter der Bildebene liegt. Nota bene: Beim Zukneifen eines Auges kommt der Effekt nicht zustande. Ex empfiehlt sich, das Bild beim Betrachten gut zu beleuchten. Die Szene ist in Abb. 3 dargestellt.

Abb. 3 Szene für das SIRDS aus Abbildung 2

Artikelanfang Seitenanfang

Literatur

D. Marr and T. Poggio. A computational theory of human stereo vision. Proc R. Soc. Lond. B., 204, 301-328, 1979
H. Thimbleby, S. Inglis, and I. Witten. Displaying 3d images: Algorithms for single image random stereograms. erhältlich über ftp:kaz.anu.edu.au:/pub/stergrams/papers/SIDRS-paer.ps.Z, erscheint in IEEE Computer, 1994
W. Leister, H. Müller and A. Stößer. Fotorealistische Computeranimation. Springer Verlag, Heidelberg 1991
S. Inglis, ed. Sterogram-FAQ. Net News Article in alt.3d,
www.cs.waikato.ac.nz/~singlis/sirds.html, 1994
Ute Claussen and Josef Pöpsel, Im Rausch der Tiefe. c’t, 7, 1994

Artikelanfang Seitenfang

Autor & Copyright
Dr. Wolfgang Leister,
Metronor AS,
Postboks 238,
N1362 Nesbru,
Norwegen
leister@oslonett.no

Artikelanfang Seitenanfang