Integration, Indexierung und Interaktion hochdimensionaler Datenobjekte
©2009
Doktorarbeit / Dissertation
164 Seiten
Zusammenfassung
Inhaltsangabe:Einleitung:
Die Anforderungen an Computersysteme haben sich in den letzten Jahren besonders im privaten Bereich deutlich verändert, hin zu einem Speicher- und Wiedergabesystem für digitale Medien wie Musik, Videos und Fotos. Diese Entwicklung wird durch die noch immer wachsende Beliebtheit von MP3-Dateien und ihren Derivaten, digitaler Fotografie und neuerdings auch durch digitales hochauflösendes Fernsehen angetrieben. Sie hat ihren vorläufigen Höhepunkt in sog. Mediacenter-Applikationen gefunden, die digitale Medien endgültig im heimischen Wohnzimmer ankommen lassen.
Leider sind die von Betriebssystemen eingesetzten Dateisysteme nicht weiterentwickelt worden, um den veränderten Anforderungen beim Speichern und vor allem Wiederfinden tausender Dateien gerecht zu werden. Lediglich die physikalische Größe von Dateisystemen ist durch Einführung größerer Adressräume und effizienterer Datenstrukturen gewachsen. Auf logischer Ebene bieten die heute eingesetzten Dateisysteme als Ordnungsschema noch immer eine Verzeichnishierarchie an, die jedoch deutliche Nachteile aufweist. Dourish, P. et al. identifiziert einige dieser Nachteile, die teilweise bereits in Malone, T. W. beschrieben worden sind, dort allerdings bezogen auf Papierakten. Zunächst können Dateien nur an genau einem Platz in der Verzeichnishierarchie abgelegt werden.
Auf der obersten Ebene sind alle Fotos in Aufnahmen von Geburtstagsfeiern und Urlaubsfotos eingeteilt erstere dann nach Personen, letztere nach Ländern und schließlich weiter nach Orten. Dieses System weist jedoch prinzipielle Lücken auf: Wo sollen beispielsweise Fotos von Bertas Geburtstag abgelegt werden, wenn sie ihn auf Mallorca gefeiert hat ? Wenn entsprechende Bilder in beiden Zusammenhängen auffindbar sein sollen, müssen sie auch über beide Ordner zugänglich gemacht werden, etwa mittels Einführung symbolischer Links. Das Anlegen weiterer Kategorien, etwa des Aufnahmejahres, steigert diesen Aufwand zusehends weiter.
Darüber hinaus ist eine solche Verzeichnishierarchie auf die Mitarbeit des Benutzers angewiesen Mills, B., der geeignete Kategorien für seine Dateien finden, entsprechende Unterverzeichnisse anlegen und dann auch einsetzen muss. In der Praxis wird es zudem oft vorkommen, dass Dateien in den falschen Verzeichnissen gespeichert werden, so dass sie nicht mehr aufgefunden werden können und verloren gehen.
Für diesen Fall bieten Betriebssysteme mehr oder weniger gute Suchfunktionen an, die als […]
Die Anforderungen an Computersysteme haben sich in den letzten Jahren besonders im privaten Bereich deutlich verändert, hin zu einem Speicher- und Wiedergabesystem für digitale Medien wie Musik, Videos und Fotos. Diese Entwicklung wird durch die noch immer wachsende Beliebtheit von MP3-Dateien und ihren Derivaten, digitaler Fotografie und neuerdings auch durch digitales hochauflösendes Fernsehen angetrieben. Sie hat ihren vorläufigen Höhepunkt in sog. Mediacenter-Applikationen gefunden, die digitale Medien endgültig im heimischen Wohnzimmer ankommen lassen.
Leider sind die von Betriebssystemen eingesetzten Dateisysteme nicht weiterentwickelt worden, um den veränderten Anforderungen beim Speichern und vor allem Wiederfinden tausender Dateien gerecht zu werden. Lediglich die physikalische Größe von Dateisystemen ist durch Einführung größerer Adressräume und effizienterer Datenstrukturen gewachsen. Auf logischer Ebene bieten die heute eingesetzten Dateisysteme als Ordnungsschema noch immer eine Verzeichnishierarchie an, die jedoch deutliche Nachteile aufweist. Dourish, P. et al. identifiziert einige dieser Nachteile, die teilweise bereits in Malone, T. W. beschrieben worden sind, dort allerdings bezogen auf Papierakten. Zunächst können Dateien nur an genau einem Platz in der Verzeichnishierarchie abgelegt werden.
Auf der obersten Ebene sind alle Fotos in Aufnahmen von Geburtstagsfeiern und Urlaubsfotos eingeteilt erstere dann nach Personen, letztere nach Ländern und schließlich weiter nach Orten. Dieses System weist jedoch prinzipielle Lücken auf: Wo sollen beispielsweise Fotos von Bertas Geburtstag abgelegt werden, wenn sie ihn auf Mallorca gefeiert hat ? Wenn entsprechende Bilder in beiden Zusammenhängen auffindbar sein sollen, müssen sie auch über beide Ordner zugänglich gemacht werden, etwa mittels Einführung symbolischer Links. Das Anlegen weiterer Kategorien, etwa des Aufnahmejahres, steigert diesen Aufwand zusehends weiter.
Darüber hinaus ist eine solche Verzeichnishierarchie auf die Mitarbeit des Benutzers angewiesen Mills, B., der geeignete Kategorien für seine Dateien finden, entsprechende Unterverzeichnisse anlegen und dann auch einsetzen muss. In der Praxis wird es zudem oft vorkommen, dass Dateien in den falschen Verzeichnissen gespeichert werden, so dass sie nicht mehr aufgefunden werden können und verloren gehen.
Für diesen Fall bieten Betriebssysteme mehr oder weniger gute Suchfunktionen an, die als […]
Leseprobe
Inhaltsverzeichnis
Konstantin Koll
Integration, Indexierung und Interaktion hochdimensionaler Datenobjekte
ISBN: 978-3-8366-4534-8
Herstellung: Diplomica® Verlag GmbH, Hamburg, 2010
Zugl. Universität Dortmund, Dortmund, Deutschland, Dissertation / Doktorarbeit, 2009
Dieses Werk ist urheberrechtlich geschützt. Die dadurch begründeten Rechte,
insbesondere die der Übersetzung, des Nachdrucks, des Vortrags, der Entnahme von
Abbildungen und Tabellen, der Funksendung, der Mikroverfilmung oder der
Vervielfältigung auf anderen Wegen und der Speicherung in Datenverarbeitungsanlagen,
bleiben, auch bei nur auszugsweiser Verwertung, vorbehalten. Eine Vervielfältigung
dieses Werkes oder von Teilen dieses Werkes ist auch im Einzelfall nur in den Grenzen
der gesetzlichen Bestimmungen des Urheberrechtsgesetzes der Bundesrepublik
Deutschland in der jeweils geltenden Fassung zulässig. Sie ist grundsätzlich
vergütungspflichtig. Zuwiderhandlungen unterliegen den Strafbestimmungen des
Urheberrechtes.
Die Wiedergabe von Gebrauchsnamen, Handelsnamen, Warenbezeichnungen usw. in
diesem Werk berechtigt auch ohne besondere Kennzeichnung nicht zu der Annahme,
dass solche Namen im Sinne der Warenzeichen- und Markenschutz-Gesetzgebung als frei
zu betrachten wären und daher von jedermann benutzt werden dürften.
Die Informationen in diesem Werk wurden mit Sorgfalt erarbeitet. Dennoch können
Fehler nicht vollständig ausgeschlossen werden und der Verlag, die Autoren oder
Übersetzer übernehmen keine juristische Verantwortung oder irgendeine Haftung für evtl.
verbliebene fehlerhafte Angaben und deren Folgen.
© Diplomica Verlag GmbH
http://www.diplomica.de, Hamburg 2010
fåÜ~äíëîÉêòÉáÅÜåáë=
á=
fåÜ~äíëîÉêòÉáÅÜåáë=
1 Einleitung ... 1
1.1 Zielsetzung und Überblick ... 2
1.1.1 Integration... 2
1.1.2 Indexierung ... 3
1.1.3 Interaktion ... 3
1.2 Resultate ... 4
1.3 Veröffentlichungen ... 4
2 Existierende Lösungen ... 5
2.1 Lotus Magellan ... 5
2.1.1 Arbeitsweise ... 6
2.1.2 Steuerung der Indexierung ... 8
2.2 SFS und MetaFS ... 9
2.2.1 Weiterentwicklungen ... 11
2.2.2 Performanz ... 11
2.3 Rufus ... 12
2.3.1 Klassifizierer ... 12
2.3.2 Objekte ... 13
2.4 Microsoft OLE ... 13
2.4.1 Beispiel ... 14
2.4.2 Registry ... 16
2.4.3 Objekt-Manager ... 17
2.5 Microsoft Indexerstellung ... 18
2.6 Microsoft Windows Explorer ... 19
2.7 BeFS ... 21
2.7.1 Übersetzer ... 21
2.7.2 Postfächer ... 22
2.7.3 Suchfunktion ... 23
2.8 DBFS ... 24
2.9 Microsoft WinFS ... 27
2.9.1 WinFS Type Browser ... 28
2.9.2 StoreSpy ... 29
2.10 Moderne Desktop-Suchmaschinen ... 31
2.10.1 Linux Beagle ... 31
2.10.2 Apple Spotlight ... 32
2.10.3 Google Desktop ... 34
2.10.4 Yahoo Desktop ... 35
2.11 Fazit... 36
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
áá=
3 Existierende Indexe ... 37
3.1 Lucene ... 37
3.1.1 Compound File System ... 37
3.1.2 Performanz ... 40
3.2 BeFS ... 40
3.2.1 Indexierung ... 42
3.2.2 Performanz ... 42
3.3 Multidimensionale Indexierung ... 43
3.3.1 Der »Fluch der Dimensionen« ... 44
3.3.2 Partial Match Operationen ... 47
3.3.3 Ineffizienz von persistent gespeicherten Bäumen ... 48
3.3.4 Partiell belegter Datenraum ... 50
3.3.5 Performanz ... 51
3.4 Fazit ... 55
4 Integration ... 57
4.1 Libraries ... 58
4.2 Relationale Datenbanken... 60
4.2.1 BLOB-relationale Datenbanken ... 61
4.3 Dateisysteme ... 62
4.3.1 Abbildungsvorschrift ... 62
4.3.2 Semantische Dateisysteme ... 63
4.4 Vorteile ... 64
4.4.1 Zugriff ... 65
4.4.2 Operationen ... 66
4.4.3 Typsicherheit ... 66
4.4.4 Terminologie... 67
5 Indexierung ... 69
5.1 Master/Slave-Index ... 69
5.1.1 Generalisierung/Spezialisierung ... 69
5.1.2 Retrieval ... 71
5.1.3 Hinzufügen ... 74
5.1.4 Ändern ... 74
5.1.5 Löschen ... 74
5.1.6 Massen-Operationen ... 76
5.2 Performanz ... 78
5.2.1 Optimierung ... 79
5.2.2 Verifizierung ... 80
fåÜ~äíëîÉêòÉáÅÜåáë=
ááá=
6 Referenz-Library ... 81
6.1 Architektur... 81
6.1.1 Domains ... 82
6.1.2 Applikationen ... 83
6.1.3 Registry ... 85
6.2 Implementierung ... 85
6.2.1 Namensraum ... 85
6.2.2 Selektion ... 87
6.3 Performanz ... 89
6.3.1 Testumgebung ... 89
6.3.2 dobm ... 89
6.3.3 Ohne Index ... 90
6.3.4 Master/Slave-Index ... 90
6.3.5 Komprimierter Master/Slave-Index ... 91
6.4 Vorteile ... 92
6.4.1 Architektur ... 92
6.4.2 Implementierung... 94
7 Interaktion... 95
7.1 Shell ... 96
7.1.1 Moderne Shells ... 96
7.1.2 Anforderungen an eine Shell ... 98
7.1.3 Hypertext-Menus ... 98
7.1.4 Vorteile ... 102
7.2 Join-Operationen... 104
7.3 Benutzerdefinierte Filter ... 106
7.3.1 Shell-Integration... 106
7.3.2 Vorteile ... 107
7.4 Automatische Ordner ... 107
7.4.1 Kalenderansicht ... 109
7.4.2 Vorteile ... 109
7.5 Semantisches Tagging ... 110
7.5.1 Geotagging ... 111
7.5.2 Bewertung von Dateien... 113
7.5.3 Vorteile ... 115
7.6 Aufgabenorientierung ... 115
7.6.1 Vorteile ... 117
7.7 Webserver ... 117
7.7.1 »Fancy fancy indexing« ... 119
7.7.2 Vorteile ... 121
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
áî=
8 Zusammenfassung und Ausblick ... 123
8.1 Zusammenfassung ... 123
8.2 Integration in existierende Systeme ... 124
8.2.1 Master/Slave-Index ... 124
8.2.2 Erweiterung für Dateisysteme ... 124
8.2.3 Applikationen ... 125
8.3 Weiterentwicklungen... 126
8.3.1 Master/Slave-Index ... 126
8.3.2 Semantisches Tagging ... 127
8.3.3 Automatisches Tagging ... 127
8.3.4 Verbesserte Visualisierung ... 128
8.4 Ausblick ... 129
^åÜ~åÖ=
A Glossar ... 131
B Testprogramm zur Seek-Geschwindigkeit ... 133
B.1 pbbhqbpqKm^p ... 133
B.2 Messergebnisse ... 135
C Testprogramm »Microsoft SQL-Server 2005« ... 137
C.1 jbq^a^q^Kuji ... 137
C.2 jbq^a^q^Kupa ... 138
C.3 moldo^jK`p ... 138
D Testprogramm »PostgreSQL« ... 143
D.1 moldo^jK`p ... 143
Literaturverweise ... 147
Begriffe aus dem Glossar sind bei der ersten Verwendung kursiv gedruckt.
N=báåäÉáíìåÖ=
N=
N=báåäÉáíìåÖ=
Die Anforderungen an Computersysteme haben sich in den letzten Jahren besonders im privaten
Bereich deutlich verändert, hin zu einem Speicher- und Wiedergabesystem für digitale Medien wie
Musik, Videos und Fotos. Diese Entwicklung wird durch die noch immer wachsende Beliebtheit
von MP3-Dateien und ihren Derivaten, digitaler Fotografie und neuerdings auch durch digitales
hochauflösendes Fernsehen angetrieben. Sie hat ihren vorläufigen Höhepunkt in sog. »Mediacen-
ter«-Applikationen gefunden, die digitale Medien endgültig im heimischen Wohnzimmer ankom-
men lassen [Ker03].
Leider sind die von Betriebssystemen eingesetzten Dateisysteme nicht weiterentwickelt worden, um
den veränderten Anforderungen beim Speichern und vor allem Wiederfinden tausender Dateien ge-
recht zu werden. Lediglich die physikalische Größe von Dateisystemen ist durch Einführung größe-
rer Adressräume und effizienterer Datenstrukturen gewachsen. Auf logischer Ebene bieten die heute
eingesetzten Dateisysteme als Ordnungsschema noch immer eine Verzeichnishierarchie an, die je-
doch deutliche Nachteile aufweist. [Dou00] identifiziert einige dieser Nachteile, die teilweise be-
reits in [Mal83] beschrieben worden sind, dort allerdings bezogen auf Papierakten. Zunächst kön-
nen Dateien nur an genau einem Platz in der Verzeichnishierarchie abgelegt werden. Ein Beispiel
hierfür ist der folgende Verzeichnisbaum, in den ein fiktiver Nutzer seine Fotos einsortiert:
Abb. 1-1: Verzeichnishierarchie eines fiktiven Nutzers
Auf der obersten Ebene sind alle Fotos in Aufnahmen von Geburtstagsfeiern und Urlaubsfotos ein-
geteilt erstere dann nach Personen, letztere nach Ländern und schließlich weiter nach Orten. Die-
ses System weist jedoch prinzipielle Lücken auf: Wo sollen beispielsweise Fotos von Bertas Ge-
burtstag abgelegt werden, wenn sie ihn auf Mallorca gefeiert hat ? Wenn entsprechende Bilder in
beiden Zusammenhängen auffindbar sein sollen, müssen sie auch über beide Ordner zugänglich
gemacht werden, etwa mittels Einführung symbolischer Links. Das Anlegen weiterer Kategorien,
etwa des Aufnahmejahres, steigert diesen Aufwand zusehends weiter.
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
O=
Darüber hinaus ist eine solche Verzeichnishierarchie auf die Mitarbeit des Benutzers angewiesen
[Mil05], der geeignete Kategorien für seine Dateien finden, entsprechende Unterverzeichnisse anle-
gen und dann auch einsetzen muss. In der Praxis wird es zudem oft vorkommen, dass Dateien in
den falschen Verzeichnissen gespeichert werden, so dass sie nicht mehr aufgefunden werden kön-
nen und »verloren gehen«.
Für diesen Fall bieten Betriebssysteme mehr oder weniger gute Suchfunktionen an, die als Suchkri-
terium jedoch nur die Attribute erlauben, die das Dateisystem selbst verwaltet. Weitere Metadaten,
die insbesondere in modernen Multimedia-Dateiformaten enthalten sind, stehen oft nur in einigen
Programmen zur Verfügung, die solche Dateiformate öffnen können. Auf Betriebssystem-Ebene
sind diese Attribute unzugänglich, obwohl gerade sie eine sinnvolle Suche ermöglichen würden.
NKN=wáÉäëÉíòìåÖ=ìåÇ=§ÄÉêÄäáÅâ=
Das Hauptziel dieser Arbeit besteht darin, den Zugriff von Benutzern auf ihre Dateien, insbesondere
auf Multimedia-Inhalte, zu verbessern. Diese Aufgabenstellung erfordert die interdisziplinäre Bear-
beitung der Bereiche Integration ( Kap. 1.1.1), Indexierung ( Kap. 1.1.2) und Interaktion
(
Kap. 1.1.3). Auf der Basis einer Referenz-Library, welche die Integration und Indexierung von
hochdimensionalen Datenobjekten realisiert, kann die Interaktion durch diverse Verbesserungen op-
timiert werden:
Abb. 1.1-1: Resultate (blau) und ihre Vorteile für den Benutzer (orange)
Im Zusammenspiel erfüllen diese Innovationen das oben gesetzte Ziel eines verbesserten Zugriffs
auf eine große Anzahl Dateien. Abschließend werden Möglichkeiten zur Integration in bereits exis-
tierende Systeme sowie zur Weiterentwicklung vorgestellt (
Kap. 8).
NKNKN=fåíÉÖê~íáçå=
Als Teilziel »Integration« wird der uneingeschränkte Zugriff auf alle Attribute von Dateien und Tu-
peln relationaler Datenbanken auf Betriebssystem-Ebene realisiert.
oÉÑÉêÉåòJiáÄê~êóI=
6
Integration von
Datenbanken und
Dateisystemen,
4
Indexierung durch
Master/Slave-
Index,
5
Integration ins
Betriebssystem,
6
sÉêÄÉëëÉêíÉ=fåíÉê~âíáçåI=
7
Hypertext-
Shell
7.1
Joins
7.2
Benutzerdef.
Suchfilter
7.3
Automatische
Ordner
7.4
Semantisches
Tagging
7.5
Aufgaben-
Orientierung
7.6
»Fancy fancy
indexing«
7.7
N=báåäÉáíìåÖ=
P=
Marsden stellt hierzu in [Mar03] fest, dass Datenbanken ursprünglich in hierarchielosen Dateien
gespeichert wurden. Später wurden hierarchische Datenbanken eingeführt, die die Darstellung von
1:n-Beziehungen zwischen Entitäten erlaubten. Durch ein hierarchisches Datenmodell konnten je-
doch nicht alle Beziehungen zwischen Entitäten modelliert werden, weshalb Links eingeführt wur-
den, um die Hierarchie zu durchbrechen. Auf dieser Entwicklungsstufe befinden sich auch her-
kömmliche Dateisysteme [Mar03]. Inzwischen hat sich in der Datenbanktechnik jedoch das rela-
tionale Datenmodell [Cod70] durchgesetzt [Saa05], mit dem Beziehungen dynamisch durch die
Daten selbst modelliert werden.
Gifford et al. haben in [Gif91] den Begriff des semantischen Dateisystems eingeführt. Damit sind
Dateisysteme gemeint, die beliebige Attribute (Metadaten) zu Dateien abspeichern und verwalten
können. In
Kap. 4 wird das Datenmodell einer »Library« eingeführt, auf das sich die Modelle
von Dateisystemen und relationalen Datenbanken abbilden lassen. Auf diese Weise werden beide
Systeme auf logischer Ebene vereinigt, so dass alle Attribute für Applikationen zugänglich sind
[Sho93] und globale Gültigkeit [Imf02] erlangen. Beziehungen werden durch die Attribute selbst
modelliert, so dass keine von außen erzwungenen Hierarchien wie Verzeichnisbäume mehr benötigt
werden.
NKNKO=fåÇÉñáÉêìåÖ=
Die Attribute von Datenobjekten müssen indexiert werden, um auch bei großen Datenmengen einen
ausreichend schnellen Zugriff zu erzielen. Speziell bei der Indexierung von Dateiattributen werden
Probleme durch den hochdimensionalen Datenraum verursacht (»Fluch der Dimensionen«,
Kap. 3.3.1). Ebenfalls negativ wirkt sich aus, dass der Index in der Regel innerhalb eines physi-
kalischen Dateisystems gespeichert wird (
Kap. 3.3.3).
Das Teilziel »Indexierung« besteht darin, die oben genannten Probleme beim Indexieren von Datei-
attributen zu lösen. Dies wird durch eine neuartige Datenstruktur erreicht, die anhand einer Refe-
renz-Implementierung erprobt wird. Der »Master/Slave-Index« (
Kap. 5) ist für den Einsatz in
hochdimensionalen Datenräumen, die von heterogenen Objekt-Schemata erzeugt werden, geeignet.
Da außerdem alle Algorithmen sequenziell arbeiten und ohne Neupositionierung des Dateizeigers
auskommen, wird durch eine zusätzliche Komprimierung des Indexes eine weitere Leistungssteige-
rung erzielt.
NKNKP=fåíÉê~âíáçå=
Basierend auf der Integration und Indexierung wird als letztes Teilziel die Interaktion mit großen
Datenmengen durch die Realisierung fortschrittlicher Benutzerschnittstellen verbessert. In einer Re-
ferenz-Library können sehr viele Dateien anhand ihrer Metadaten sowie weiterer, vom Benutzer
vergebener Attribute schnell organisiert und aufgefunden werden.
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
Q=
NKO=oÉëìäí~íÉ=
Im Rahmen dieser Arbeit wurden folgende Resultate mit Neuheitswert erzielt:
·
Traditionell werden die Gebiete »Betriebssysteme« sowie »Datenbanken« als unabhängige Dis-
ziplinen angesehen. Daher bestand ein Bedarf an einer umfassenden Bestandsaufnahme bereits
existierender Ansätze zur Verbesserung von Dateisystemen (
Kap. 2). Im Zuge dieser Be-
standsaufnahme wurden auch eingesetzte Indexe untersucht ( Kap. 3).
·
Das Datenmodell für Libraries, auf das sich die Modelle von relationalen Datenbanken und Da-
teisystemen abbilden lassen, wird eingeführt ( Kap. 4).
·
Der »Master/Slave-Index« wird als neue Datenstruktur zur Indexierung eingeführt ( Kap. 5).
·
Zum Nachweis der praktischen Funktionsfähigkeit des Library-Modells wird eine Referenz-
Library vorgestellt (
Kap. 6).
·
Auf Basis einer Library als schnelles Speichersystem für Datenobjekte mit beliebigen Attributen
werden Verbesserungen an Benutzungsschnittstellen, und damit bei der Interaktion mit Dateien,
beschrieben (
Kap. 7).
NKP=sÉêÑÑÉåíäáÅÜìåÖÉå=
Die Resultate dieser Arbeit (
Kap. 1.2) stützen sich auf diverse Veröffentlichungen, deren alleini-
ger Autor Konstantin Koll ist. In [Kol08a] wird die Benutzung möglichst großer Zuordnungseinhei-
ten in Dateisystemen zur Steigerung der Zugriffsgeschwindigkeit gefordert. [Kol08b] beschreibt die
Architektur der Referenz-Library sowie die Schwierigkeiten bei ihrer Implementierung, insbesonde-
re bezüglich der Indexierung (
Kap. 6). Der Master/Slave-Index (
Kap. 5) und seine Leistungs-
fähigkeit (
Kap. 6.3) wird ausführlich in [Kol08c] beschrieben. Zuletzt waren Verbesserungen an
Webserver-Applikationen (
Kap. 7.7) Gegenstand eines Vortrages [Kol08d].
Darüber hinaus wurde 2007 der Master/Slave-Index (
Kap. 5) beim U.S. Patentamt unter der
Nummer 11/892071 unter Berufung auf ein provisorisches Patent vom 18.09.2006 zum Patent an-
gemeldet [Kol07a].
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
R=
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
Seit langer Zeit wird an Möglichkeiten gearbeitet, die Organisation von Dateisystemen zu optimie-
ren. In den letzten Jahren erfreuen sich vor allem sog. »Desktop-Suchmaschinen« (
Kap. 2.10)
großer Beliebtheit, die von Suchmaschinen-Betreibern wie Google und Yahoo für lokale Dateisys-
teme entwickelt wurden; ähnliche Programme existieren schon seit Anfang der 1990er-Jahre (Lotus
Magellan,
Kap. 2.1).
In diesem Kapitel werden verschiedene Ansätze untersucht, dokumentiert und bewertet
( Kap. 2.11). Neben Desktop-Suchmaschinen werden auch relevante Entwicklungen aus dem
akademischen Bereich und Techniken, die lediglich Teilaufgaben lösen, chronologisch vorgestellt.
Viele Ideen dieser Lösungen und Prototypen sind dabei in Weiterentwicklungen eingeflossen. Die
untersuchten Lösungen sind sehr unterschiedlicher Natur, sowohl hinsichtlich ihrer Zielsetzung als
auch ihrer Arbeitsweise. Dadurch wird ein direkter Vergleich erschwert.
Es lassen sich jedoch zwei unterschiedliche Ansätze definieren, die in einigen Systemen sogar kom-
biniert werden. Zum einen wird versucht, Dateien und Applikationen in eine objektorientierte Ge-
samtarchitektur einzubinden. Diese Entwicklung hat mit dem Rufus-Projekt (
Kap. 2.3) und Mic-
rosoft OLE ( Kap. 2.4) begonnen, und wurde mit moderneren Systemen wie Microsoft WinFS
(
Kap. 2.9) fortgesetzt. Andererseits wird versucht, die eingangs erwähnten Schwächen physikali-
scher Dateisysteme (
Kap. 1) durch Weiterentwicklungen oder Zusatzsoftware zu beheben. Das
Rufus-Projekt, BeFS (
Kap. 2.7) und Microsoft WinFS lassen sich beiden Kategorien zuordnen.
OKN=içíìë=j~ÖÉää~å=
1990 wurde von der Firma Lotus das DOS-Programm »Magellan« als eine der ersten Desktop-
Suchmaschinen veröffentlicht. Moderne Desktop-Suchmaschinen (
Kap. 2.10) basieren noch im-
mer auf dem Architekturmodell, das mit Magellan eingeführt wurde:
Physikalisches
Dateisystem
Betriebssystem
App
Suchmaschine
Index
Abb. 2.1-1: Architektur einer Desktop-Suchmaschine
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
S=
Desktop-Suchmaschinen sind normale Applikationen, die über das Betriebssystem auf das Dateisys-
tem zugreifen. Die Suchmaschine wird erst aktiv, wenn der Anwender nach Dateien sucht, die be-
stimmte Metadaten oder Schlüsselworte enthalten.
1990 existierten viele der heute verbreiteten Dateiformate wie PDF, MP3, JPEG, QuickTime oder
AVI [Kol03] [Kol07b] noch nicht, so dass auch die Metadaten-Attribute dieser Dateitypen weitge-
hend unbekannt waren. Aus diesem Grund unterstützt Magellan lediglich das Durchsuchen von Da-
teien nach Schlüsselworten und verwendet einen Volltext-Index. Die Extraktion von Textstellen
wird dabei von Plug-Ins (»Viewer« genannt) übernommen. Im Lieferumfang befinden sich Viewer
für viele damals benutzte Dateiformate, unter anderem:
·
Ascii-Text
·
CompuServe
·
dBase
·
GIF
·
Lotus 1-2-3
·
Lotus Agenda
·
Lotus Manuscript
·
Lotus Symphony
·
LotusWorks
·
Microsoft Excel
·
Microsoft Word
·
Multiplan
·
Paradox
·
PCX
·
Quark Express
·
Quicken
·
Quattro Pro
·
WordPerfect
·
Wordstar
Abb. 2.1-2: von Lotus Magellan unterstützte Dateiformate
Da die Magellan-Suchmaschine aufgrund ihres Alters besonders einfach aufgebaut ist, kann sie hier
exemplarisch die Funktionsweise moderner Desktop-Suchmaschinen (
Kap. 2.10) veranschauli-
chen, die ausnahmslos nach demselben Prinzip arbeiten.
OKNKN=^êÄÉáíëïÉáëÉ=
Nach dem Programmstart erscheint die Magellan-Oberfläche, die in der linken Spalte alle Dateien
von allen Datenträgern des Computers enthält. Die Verzeichnisstruktur wird dabei vollständig igno-
riert, denn Magellan dient ja gerade dem Auffinden von Dateien mit unbekanntem Pfad:
Abb. 2.1-3: Programmstart
Abb. 2.1-4: Suchen nach einem Begriff
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
T=
Beim ersten Programmstart kann die Suchanfrage allerdings noch nicht bearbeitet werden, da Ma-
gellan noch keine Dateien indexiert hat:
Abb. 2.1-5: fehlender Index
Vor dem Indexieren können bestimmte Dateiendungen angegeben werden.
W
beschreibt dabei alle
Dateien auf allen logischen Laufwerken, ausgenommen werden jedoch Dateien mit den Extensio-
nen, denen ein Minuszeichen vorangestellt ist (hier also alle ausführbaren Dateien):
Abb. 2.1-6: zu indexierende Dateitypen
Im Anschluss werden die oben ausgewählten Dateien ohne weitere Eigenaktivität des Benutzers in
ca. 40 Minuten indexiert:
Abb. 2.1-7: Indexierung
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
U=
Nach dem Indexieren der Dateien ist die Suche nach dem Begriff »procedure« erfolgreich und lie-
fert eine Dateiliste, die hier fast ausschließlich aus Quelltexten besteht:
Abb. 2.1-8: erfolgreiche Suche
Der dabei benutzte Index belegt in komprimierter Form auf der Festplatte über 21 MB, das sind et-
wa 2% der ursprünglichen Datenmenge. Die unterschiedlichen Dateien enthalten zudem Namen und
Dateizeit aller indexierten Dateien, um Veränderungen feststellen zu können.
OKNKO=píÉìÉêìåÖ=ÇÉê=fåÇÉñáÉêìåÖ=
Lotus Magellan setzt einen Volltext-Index ein, der vom Benutzer konfiguriert und an unterschiedli-
che Sprachen angepasst werden kann. Die Konfigurationsdatei
j^dbii^kKpvj enthält drei Tabel-
len (
pbm^o^qlop, `^pb und ploq), welche die Indexierung wesentlich beeinflussen:
pbm^o^qlop=
...
...
...SSSS...
0000000000...
.AAAAAAAAAAAAAAA
AAAAAAAAAAA...A
.AAAAAAAAAAAAAAA
AAAAAAAAAAA...
AAAAAAAAAAAAAAAA
AAAAAAAAAAAASA.S
AAAAAA...
...AAAA.....S.
...AA........
AAAAAAAAA...A.
AAAAAA.AAAAAAA..
...SS..........
`^pb=
...
...
...
...
.ABCDEFGHIJKLMNO
PQRSTUVWXYZ...
.ABCDEFGHIJKLMNO
PQRSTUVWXYZ...
ÇÜÉÂÄÀÅÇÊËÈÏÎÌÄÅ
ÉÆÆÔÖÒÛÙYÖÜØ.Ø..
ÁÍÓÚÑÑ...
...ÁÂÀ........
...ÃÃ........
ÐÐÊËÈ.ÍÎÏ...Ì.
Ó.ÔÒÕÕ.ÞÞÚÛÙÝÝ..
...
ploq=
...
...
...
...
...
...
.ABCDEFGHIJKLMNO
PQRSTUVWXYZ...
CUEAAAACEEEIIIAA
EAAOOOUUYOUO$O.$
AIOUNN..?...!""
...AAA.....$$.
...AA.......$
DDEEEIIII...I.
OSOOOO.Þ.UUUYY..
...
Abb. 2.1-9: wesentlicher Inhalt von
j^dbii^kKpvj
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
V=
Das Layout der Tabellen orientiert sich am Standard-Zeichensatz mit 256 Zeichen (8 Bit), angeord-
net als 16
×
16-Matrix. Die Tabelle
pbm^o^qlop definiert für jedes Zeichen, welche Bedeutung es
für die Aufteilung der Daten in einzelne Begriffe besitzen soll:
Effekt auf die Indexierung
p=
Das Zeichen trennt ein Wort und wird als alleinstehendes Symbol indexiert
^=
Das Zeichen ist Teil eines Wortes
M=
Das Zeichen ist Teil einer Zahl und wird als Nummer indexiert
K=
Das Zeichen trennt ein Wort, wird aber nicht indexiert
Abb. 2.1-10: Wertebereich der
pbmbo^qlop -Tabelle
Die
`^pb-Tabelle definiert für alle lateinischen Buchstaben und Umlaute bzw. internationalen Zei-
chen den zugehörigen Großbuchstaben, so dass alle Begriffe unabhängig von Groß- und Klein-
schreibung indexiert werden. Ähnlich wird die
ploq-Tabelle verwendet, um eine geeignete Sortie-
rung aller Begriffe zu ermöglichen. Eine Suche nach bestimmten Attributen (etwa »Künstler«) ist
nicht möglich, da der Ursprung der einzelnen Begriffe nicht erfasst wird.
OKO=pcp=ìåÇ=jÉí~cp=
Unix-Betriebssysteme können mehrere unterschiedliche Dateisysteme mounten; darunter auch das
»Network File System« (NFS) [RFC1094]. Gifford hat mit dem »Semantic File System« (SFS)
1991 einen NFS-Server implementiert, der dem Client ein semantisches Dateisystem liefert [Gif91].
Analog zu Lotus Magellan (
Kap. 2.1) verwendet SFS Module zur Extraktion und Indexierung
von Metadaten aus verschiedenen Dateiformaten; diese Module werden in [Gif91] »Transducer«
genannt. Damit auch ältere Applikationen auf das Semantic File System zugreifen können, wird es
noch unterhalb der Betriebssystem-Ebene eingebunden:
Semantic
File System
Betriebssystem
App
Physikalisches
Dateisystem
App
App
Abb. 2.2-1: Architektur des Semantic File Systems [Gif91]
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
NM=
SFS benutzt virtuelle Dateien bzw. Verzeichnisse, um Suchanfragen entgegenzunehmen und Ergeb-
nisse zurückzuliefern. Nachfolgend wird davon ausgegangen, dass der Mountpoint des Semantic Fi-
le System
LëÑë ist. Suchanfragen werden durch Zugriffe auf bestimmte Unterverzeichnisse realisiert.
Die Metadaten werden im Gegensatz zu vielen anderen Systemen (
Kap. 2.1,
Kap. 2.10.4) ge-
trennt nach Attribut (Absender, Empfänger, Datum usw.) indexiert, so dass für jedes Attribut ein vir-
tuelles Verzeichnis gebildet werden kann. Der Inhalt eines solchen Verzeichnisses sind weitere Un-
terverzeichnisse, die alle indexierten Attributwerte enthalten:
Abb. 2.2-2: Inhalt von
LëÑëLçïåÉê [Gif91]
Ein Unterverzeichnis enthält symbolische Links zu den eigentlichen Dateien, die sich in einem phy-
sikalischen Dateisystem befinden. Diese Liste wird dabei jedes Mal dynamisch erzeugt:
Abb. 2.2-3: alle Dateien von »Smith« [Gif91]
Mehrere Auswahlkriterien können in einem einzigen Pfadnamen zusammengefasst werden, das Er-
gebnis ist dann eine
^ka-Verknüpfung der einzelnen Filter:
Abb. 2.2-4: alle Dateien von »Smith«, die den Begriff »resume« enthalten [Gif91]
Das virtuelle Verzeichnis
ÑáÉäÇW zeigt alle verfügbaren Attributnamen als Unterverzeichnisse an. Das
Verzeichnis
íÉñíW gestattet dabei das Durchsuchen aller Dateikörper, was das Schema der einzelnen
Dateiformate durchbricht:
Abb. 2.2-5: virtuelles Verzeichnis
ÑáÉäÇW [Gif91]
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
NN=
OKOKN=tÉáíÉêÉåíïáÅâäìåÖÉå=
Die Idee, Verzeichnisse dynamisch und auf den Attributen bzw. dem Inhalt von Dateien basierend
zu erzeugen, wurde u.a. 1999 von Gopal et al. wieder aufgegriffen [Gop99], die sich explizit auf
das SFS aus [Gif91] berufen. Während SFS alle dynamisch erzeugten Verzeichnisse unter dem
Mountpoint
LëÑë erzeugt, vermischt das in [Gop99] entworfene Dateisystem HAC (für »Hierarchy
And Content«) die Verzeichnisstruktur des physikalischen Dateisystems mit virtuellen Ordnern.
Das 2005 von Mills in [Mil05] veröffentlichte MetaFS ist weitgehend identisch mit SFS, unterstützt
allerdings moderne Dateiformate wie MP3 und JPEG sowie deren Standards für Metadaten [Nil05]
[EXI07]. Darüber hinaus enthält MetaFS zusätzliche Befehle zur Manipulation der verschiedenen
Attribute.
OKOKO=mÉêÑçêã~åò=
In [Gif91] wird auch die Leistungsfähigkeit des Semantic File System untersucht. Da der Prototyp
keine Unterstützung für das Umbenennen oder Löschen von Dateien bietet, wird eine Liste mit ge-
löschten Dateien verwaltet, die bei Suchanfragen aus dem Suchergebnis entfernt werden. Die Ein-
träge im eigentlichen Index werden erst bei einer vollständigen Neuindexierung gelöscht.
[Gif91] beschreibt eine Neuindexierung von Testdaten, die am 23. Juli 1991 vorgenommen wurde.
An diesem Tag war die Gesamtgröße des Dateisystems 326 MB, wobei 230 MB von öffentlich les-
baren Dateien belegt wurden. Nur 68 MB konnten indexiert werden, da für die übrigen 162 MB
keine Übersetzer (»transducer« genannt) verfügbar waren. Die Dateien sind wie folgt klassifiziert:
Anzahl
Größe
Object
871
8.503 KB
Quelltext
2.755
17.991 KB
Text
1.871
20.638 KB
Andere
2.274
21.187 KB
7.771
68.319 KB
Abb. 2.2-6: indexierte Dateien am 23. Juli 1991 [Gif91]
Der erstellte Index hatte eine Größe von 10019 KB, wobei 6621 KB von Tabellen und 3398 KB
durch die Baumstruktur belegt wurden. Der Index belegt also ein Siebtel der ursprünglichen Da-
tenmenge. Die Zeit für die vollständige Neuindexierung von einer Million Attributwerten, die in
den Dateien enthalten waren, betrug 96 Minuten [Gif91]:
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
NO=
Zeit
Verzeichnisbaum lesen
0:07
Dateityp ermitteln
0:01
Transducer »Verzeichnis«
0:01
Transducer »Object«
0:08
Transducer »Quelltext«
0:23
Transducer »Text«
0:23
Transducer für andere Dateitypen
0:24
Indextabellen erzeugen
1:22
Indexbaum erzeugen
0:06
1:36
Abb. 2.2-7: Zeitbedarf für vollständige Neuindexierung am 23. Juli 1991 [Gif91]
[Gif91] bemerkt, dass das Erstellen des Index maßgeblich von der I/O-Geschwindigkeit abhängt, da
die CPU während 60% der Zeit unbelastet war. Auch die Bearbeitung von Suchanfragen hängt stark
von der Datenträgergeschwindigkeit ab. Die Zeit, die von Lotus Magellan (
Kap. 2.1) für eine
vollständige Neuindexierung benötigt wird, ist mit dem Zeitbedarf in [Gif91] vergleichbar.
OKP=oìÑìë=
Das Rufus-Projekt besteht aus den Applikationen
ñêìÑìë (grafische Applikation), êìÑìëíêå (erwei-
terter Usenet-Reader) und
êìÑìëÄäÇ (Indexierung), die alle auf Userebene ablaufen [Sho93]. Damit
entspricht das Rufus-Design prinzipiell dem einer Desktop-Suchmaschine (
Abb. 2.1-1).
Ähnlich wie das Semantic File System ( Kap. 2.2) zielt das Rufus-Projekt darauf ab, das Auffin-
den von Dateien zu verbessern. Rufus bietet dazu nicht nur eine einfache Suchfunktion, sondern
bettet aufgefundene Dateien in ein objektorientiertes Konzept ein [Sho93].
In [Sho93] wird festgestellt, dass ein ideales Dateisystem die Semantik der Dateiformate kennt, also
ein semantisches Dateisystem sein sollte. Für jeden Dateityp kann dann nicht nur eine Suchfunktion
bereitgestellt, sondern auch automatisch die geeignete Applikationen zur Bearbeitung aufgerufen
werden. Um dies zu erreichen, wird in [Sho93] ein Klassifizierer eingeführt, der die Klasse (also
Format bzw. Typ) einer gegebenen Datei ermittelt. Die erzeugten Objekte extrahieren die Attribute
der Dateien und sind somit ein wichtiger Bestandteil der Suchfunktion, die ihrerseits einen Index
über alle erkannten Attribute nutzt.
OKPKN=hä~ëëáÑáòáÉêÉê=
Eine zuverlässige Klassifizierung einer Datei ist notwendig, damit das richtige Modul die Metada-
ten zur Indexierung extrahieren kann. Jede Rufus-Klasse besitzt eine Funktion, die einen Wert zwi-
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
NP=
schen 0 und 10 zurückliefert, abhängig von der wahrscheinlichen Zugehörigkeit der untersuchten
Datei zur Klasse. Dabei sucht ein Klassifizierer nach bestimmten Schlüsselworten oder Binärmus-
tern, die typisch für ein bestimmtes Dateiformat sind. Als Test wurden 847 Beispieldateien ver-
schiedener Typen klassifiziert, davon jedoch nur 90% korrekt [Sho93].
OKPKO=lÄàÉâíÉ=
Basierend auf der jeweiligen Klasse wird für jede indexierte Datei ein Objekt erstellt, das neben den
extrahierten Metadaten auch spezifische Methoden enthält, beispielsweise zur Anzeige, zur Bearbei-
tung oder zum Drucken. Rufus-Objekte sind allerdings nicht in der Lage, Änderungen (etwa er-
gänzte Metadaten) auch an den Dateien im physikalischen Dateisystem durchzuführen [Sho93].
OKQ=jáÅêçëçÑí=lib=
OLE ist die Abkürzung für »Object Linking and Embedding« und bezeichnet die Objektorientie-
rung von Applikationen und ihren Dateiformaten, die 1993 mit Windows 3.1 veröffentlicht wurde.
OLE ist somit etwa gleichzeitig mit Rufus (
Kap. 2.3) entwickelt worden, und bettet wie Rufus
Dateien in ein objektorientiertes Konzept ein. Microsoft OLE zielt allerdings auf die Zusammenar-
beit verschiedener Programme ab und löst damit im Rahmen dieser Arbeit nur ein Teilproblem.
Ein Objekt wird als Menge von Informationen definiert, die entweder verknüpft (»linked«) oder in
ein anderes Dokument eingebettet (»embedded«) werden. Ein eingebettetes Objekt ist eine ins
Hauptdokument aufgenommene Kopie einer Datei, die mit einer anderen Anwendung erstellt wur-
de. Ein eingebettetes Objekt ist nicht mehr mit dem Original verbunden; wird das Objekt also geän-
dert, wirken sich diese Änderungen nicht auf die Quelldatei aus und umgekehrt [Mic93].
Wird im Gegensatz dazu ein verknüpftes Objekt erstellt, so wird eine Verbindung zwischen dem
Zieldokument und dem Quelldokument erschaffen. Obwohl das verknüpfte Dokument als Teil der
Zieldatei angezeigt und auch ausgedruckt wird, sind die Daten, aus denen das Objekt besteht, wei-
terhin nur im Quelldokument vorhanden. Wird ein verknüpftes Objekt modifiziert, ändert sich
gleichzeitig das Quelldokument. Umgekehrt wirken sich auch Änderungen des Quelldokuments auf
das verknüpfte Objekt im Zieldokument aus (es wird aktualisiert) [Mic93].
Das Verknüpfen und Einbetten von Objekten ist dem Kopieren und Einfügen sehr ähnlich. Das Er-
gebnis hängt davon ab, mit welcher Software gearbeitet wird. Wenn die Anwendung OLE unter-
stützt, wird ein verknüpftes oder eingebettetes Objekt erstellt. Andernfalls wird nur eine statische
Kopie der Quelldatei erzeugt [Mic93].
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
NQ=
Microsoft OLE greift nicht tief ins Betriebssystem ein, sondern stellt für OLE-kompatible Anwen-
dungen lediglich eine Registrierung aller anderen OLE-Anwendungen (
Kap. 2.4.2) und ein ent-
sprechendes API zur Verfügung. Mit dem Objekt-Manager (
Kap. 2.4.3) steht außerdem ein
Hilfsprogramm zur Verfügung:
Betriebssystem
App
Physikalisches
Dateisystem
App
App
Objekt-
Manager
MS OLE
Abb. 2.4-1: OLE-Architektur
OKQKN=_ÉáëéáÉä=
Als Zieldatei soll ein einfaches Word-Dokument dienen. Microsoft Word verfügt natürlich über
OLE-Fähigkeiten:
Abb. 2.4-2: einfaches Word-Dokument
In das Dokument kann nun ein OLE-Objekt eingefügt werden. Entweder wird dazu ein neues
Quelldokument erstellt und als Objekt eingebunden, oder das Objekt wird aus einer bereits gespei-
cherten Datei erzeugt:
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
NR=
Abb. 2.4-3: neues Objekt erstellen
Abb. 2.4-4: Objekt aus einer Datei erzeugen
OLE wird nicht nur von großen Applikationen unterstützt, sondern ist vor allem für Tools nützlich.
Zusammen mit MS Word werden einige kleinere Programme mitgeliefert, die OLE-Objekte erstel-
len können: u.a. MS Draw (Vektorgrafiken), MS Formel-Editor, MS Graph (Diagramme) und MS
WordArt (Texteffekte). In diesem Beispiel wird ein Formel-Objekt eingefügt; der Formel-Editor be-
nutzt ab OLE 2.0 das Word-Fenster, um sich selbst innerhalb des Zieldokuments darzustellen:
Abb. 2.4-5: Formel-Editor innerhalb des Word-Fensters
Wenn der Formel-Editor beendet wird, übernimmt die Ziel-Applikation, also Microsoft Word, wie-
der die Kontrolle über das Fenster. Das eingebettete Objekt wird nun innerhalb des Dokuments dar-
gestellt und kann auch ausgedruckt werden:
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
NS=
Abb. 2.4-6: eingebettetes Formel-Objekt
Wäre der Formel-Editor getrennt gestartet und die Formel als Datei gespeichert worden, hätte die
Datei als verknüpftes Objekt ins Zieldokument eingefügt werden können (
Abb. 2.4-4).
OKQKO=oÉÖáëíêó=
Damit das Erstellen und Einfügen von Objekten möglich ist, muss jedes Objekt einem Anwen-
dungsprogramm zugeordnet werden. Microsoft OLE benutzt dazu keinen Klassifizierer
( Kap. 2.3.1), sondern verwaltet in der Datei
obdKa^q im tfkaltp-Verzeichnis eine Registrie-
rung, in die sich OLE-kompatible Programme während der Installation eintragen:
Abb. 2.4-7: Registry unter Windows 3.11
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
NT=
Zu jedem Datentyp werden wichtige Informationen gespeichert, vor allem mögliche Befehle (
éêáåí
und
çéÉå in der Gruppe ëÜÉää) sowie die zuständige Programmdatei (bnkbafqKbub):
Abb. 2.4-8: Registrierung des Formel-Editors
Ab Windows 95 wurde die Registry aufgewertet und dient als zentrale Konfigurationsdatei für bei-
nahe alle Programme und Einstellungen; sie kann immer noch mit
obdbafqKbub bearbeitet werden,
und sogar die Angaben über Dateiformate und OLE-kompatible Programme sind noch vorhanden:
Abb. 2.4-9: Registrierungs-Editor ab Windows 95
OKQKP=lÄàÉâíJj~å~ÖÉê=
Der Objekt-Manager ist ein Systemprogramm und dient dazu, ein Dokument einer nicht OLE-
fähigen Anwendung als Symbol einzufügen. Dazu wird aus den Ursprungsdaten ein OLE-Paket er-
zeugt. Es handelt sich dabei um ein eigenständiges Objektformat, das mit der Programmdatei des
Objekt-Managers registriert wurde (
m^`h^dboKbub):
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
NU=
Abb. 2.4-10: Paket-Erstellung mit dem Objekt-Manager
Das erstellte Paket kann danach in ein Zieldokument eingebettet werden; Verknüpfungen sind nicht
möglich. Im obigen Beispiel (
Kap. 2.4.1) würde statt des eigentlichen Bildes also nur ein Symbol
innerhalb des Word-Dokuments erscheinen. Das Paket wird also ähnlich dargestellt wie eine an eine
EMail angehängte Datei.
OKR=jáÅêçëçÑí=fåÇÉñÉêëíÉääìåÖ=
Zusammen mit Microsoft Office 95 und 97 wird das Program »Indexerstellung« installiert und for-
tan im Hintergrund ausgeführt. Das Programm indexiert im Hintergrund alle Dateien, die zu MS Of-
fice kompatibel sind. In der Systemsteuerung erscheint ein neues Kontrollfeld, mit dem sich die In-
dexerstellung konfigurieren lässt:
Abb. 2.5-1: Indexerstellung in der Systemsteuerung
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
NV=
Der erstellte Index wird von den Office-Programmen (Word, Excel, PowerPoint usw.) benutzt, um
beim Öffnen von Dateien eine inhaltsbezogene Suche anzubieten:
Abb. 2.5-2: inhaltsbezogene Suche in Microsoft Word 97
Damit entspricht auch die Architektur der Microsoft Indexerstellung derjenigen einer Desktop-
Suchmaschine (
Abb. 2.1-1). Dafür ist es unerheblich, dass die Suche selbst nur innerhalb der Of-
fice-Software stattfindet. Vor einer Suche müssen jedoch, wie bei anderen Produkten auch, alle re-
levanten Dateien indexiert werden. In einem einfachen Test wurden alle Office- und Web-
Dokumente eines Windows-PCs, insgesamt 2067 Dateien, innerhalb von etwa 15 Minuten unter ho-
her Auslastung der Systemressourcen erfasst; der fertige Index belegte dabei ca. 5,1 MB.
Die starke Beanspruchung von Ressourcen ist wegen der alle 2 Stunden stattfindenden Neuindexie-
rung bedenklich. Deshalb zog die Microsoft Indexerstellung starke Kritik von Anwendern auf sich,
vielleicht auch weil von einem Office-Paket kein derartiges Verhalten erwartet wird. Durch diese
Kritik hat sich Microsoft schließlich veranlasst gefühlt, im WWW unter [Mic00] eine Anleitung
zum Deaktivieren der Indexerstellung bereitzustellen.
OKS=jáÅêçëçÑí=táåÇçïë=bñéäçêÉê=
Der »Explorer« ist seit Windows 95 der Datei-Manager des Betriebssystems und übernimmt auch
die Darstellung des Desktops und der Task-Leiste, die sich typischerweise am unteren Bildschirm-
rand befindet. Zur Darstellung von Dateieigenschaften und zum Ändern der Attribute bietet der Ex-
plorer eine Dialogbox an, die ohne weitere Maßnahmen für alle Dateiformate gleich ist:
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
OM=
Abb. 2.6-1: Eigenschaften einer normalen Datei
Applikationen haben jedoch die Möglichkeit, den Explorer durch ein Plug-In zu erweitern. Vor al-
lem die diversen Programme aus dem Office-Paket (Word, Excel, PowerPoint u.a.) machen von die-
ser Möglichkeit Gebrauch, aber auch der Windows Media Player. Dadurch wird der »Eigenschaf-
ten«-Dialog semantisch (also typabhängig) und zeigt abhängig vom jeweiligen Dateiformat zusätz-
liche Metadaten an:
Abb. 2.6-2: Powerpoint-Datei
Abb. 2.6-3: AVI-Video
Diese Plug-Ins sind als eine Erweiterung von Microsoft OLE (
Kap. 2.4) anzusehen, da sie für be-
stimmte Dateitypen (wie z.B. PowerPoint-Präsentationen oder AVI-Videos) in die Registry-Datei
(
Kap. 2.4.2) eingetragen wurden.
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
ON=
OKT=_Écp=
Die Firma Be Inc. wurde 1991 mit dem Ziel gegründet, ein neuartiges Betriebssystem und darauf
abgestimmte Hardware zu entwickeln. Eine erste Version von BeOS wurde im Sommer 1996 auf
der MacWorld Expo in Boston vorgestellt. Da BeOS von Grund auf neu entwickelt wurde, schleppt
das Betriebssystem keine Altlasten früherer Systeme mit sich herum und bringt außerdem viele Vor-
teile anderer Betriebssysteme wie Mac OS, Windows und Unix zusammen [Har05].
BeOS nutzt das »BeOS File System« (BeFS) als Dateisystem. Es weist Ähnlichkeiten zum ext2-
Dateisystem [Kol07b] auf, kombiniert dieses aber mit den Fähigkeiten eines semantischen Datei-
systems. BeFS verfolgt somit einen integrierten Ansatz:
Betriebssystem
App
Dateisystem
App
App
Index
Abb. 2.7-1: integrierte Architektur von BeOS
In diesem Abschnitt wird auf die besonderen Fähgkeiten von BeFS eingegangen: auf Übersetzer
(
Kap. 2.7.1), Postfächer (
Kap. 2.7.2) und auf die Suchfunktion (
Kap. 2.7.3).
OKTKN=§ÄÉêëÉíòÉê=
Unter BeOS besitzen die meisten Applikationen, wie bei anderen Betriebssystemen auch, einen
Menupunkt »Speichern unter«, durch den man neben einem anderen Namen auch ein anderes Datei-
format auswählen kann. Traditionell ist es Aufgabe der Anwendung, den Programmcode zum Spei-
chern der Datei bereitzustellen. Dadurch haben die Entwickler mehrfache Arbeit, da diese Module
in vielen Programmen implementiert werden müssen; besonders problematisch ist das Fehlen eines
bestimmten Formats in einer Applikation [Hac99].
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
OO=
BeOS stellt allen Programmen Übersetzungsmodule an einer zentralen Stelle zur Verfügung, die das
Laden und Speichern von Dateien übernehmen. Dadurch sind die Applikationen kleiner, und ihre
Fähigkeiten können mit neuen Modulen gemeinsam erweitert werden [Hac99]:
Abb. 2.7-2: BeOS-Übersetzer
Unter »Preferences« kann die Liste der installierten Übersetzer eingesehen werden. Viele Module
können hier auch konfiguriert werden: beispielsweise kann beim JPEG-Übersetzer die Bildqualität
für das Speichern eingestellt werden, da Bilder im JPEG-Format verlustbehaftet komprimiert wer-
den [Hac99].
OKTKO=mçëíÑ®ÅÜÉê=
Eine Besonderheit stellt auch der Umgang mit elektronischer Post dar. Während herkömmliche Be-
triebssysteme das Speichern der EMails einer Zusatzsoftware überlassen (
Kap. 4), ist unter BeOS
die entsprechende Funktionalität ins Dateisystem integriert. Die verschiedenen Ordner für den Post-
eingang, Postausgang und vom Benutzer angelegte Postverzeichnisse haben spezielle Attribute, die
die Anzahl der ungelesenen, zu sendenden oder bereits abgeschickten EMails anzeigen. Die Attribu-
te wie Absender, Empfänger, Thema oder Datum werden direkt als Eigenschaft der Datei angezeigt:
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
OP=
Abb. 2.7-3: Postfächer
Abb. 2.7-4: EMails als eigenständige Dateien mit besonderen Attributen
Das BeOS-Dateisystem bindet die besonderen Attribute von Maildateien ein, so dass es Aspekte ei-
nes semantischen Dateisystems besitzt. Da das Dateisystem aber auch nach wie vor für die physika-
lische Speicherung in einzelnen Blöcken sorgt, stellt BeFS eine Mischform dar. Detaillierte Infor-
mationen zum BeOS-Dateisystem, insbesondere auch zum physikalischen Teil und zur Performanz,
finden sich in [Gia99].
OKTKP=pìÅÜÑìåâíáçå=
Da BeFS die besonderen Attribute einiger Dateiformate einbindet, ist es einfach, eine inhaltsbezo-
gene Suche über diese Attribute zu implementieren. Natürlich ist eine einfache Suche nach Dateien
mit einem bestimmten Namen oder Namensteil möglich (»All files and folders« und »by Name«,
Abb. 2.7-5). Zusätzlich kann die Suche auf bestimmte Dateitypen eingegrenzt werden, da BeOS
das Dateiformat unabhängig von einer möglichen Namensendung verwaltet (»E-mail«,
Abb. 2.7-6). Eine Suche nach Dateien mit bestimmten Attributen (»by Attribute«,
Abb. 2.7-6)
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
OQ=
ist aber ebenso möglich. Wird also beispielsweise nach Maildateien gesucht, können alle bei diesem
Dateityp vorhandenen Metadaten in die Suchanfrage aufgenommen werden (
Abb. 2.7-7).
Abb. 2.7-5: Suche nach Dateien anhand des Namens bzw. der Endung
Abb. 2.7-6: Suche nach Mails
Abb. 2.7-7: Suche nach EMails anhand typspezifischer Attribute
OKU=a_cp=
Das »Database File System« (DBFS) wurde als Linux-Addon im August 2004 von Gorter im Rah-
men seiner Diplomarbeit an der Universität Twente implementiert [Gor04]. Bei DBFS handelt es
sich um ein semantisches Dateisystem, dessen Ziel die Überwindung der klassischen hierarchischen
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
OR=
Verzeichnisstruktur ist. Die Software greift tief ins Linux-System und die KDE-Oberfläche
[KDE06] ein, um sich nahtlos in bereits bestehende Applikationen zu integrieren. Die Architektur
wirkt dementsprechend komplex:
Betriebssystem
App
App
App
kdbfs
DBFS
Physikalisches
Dateisystem
Datenbank
(SQLite)
Abb. 2.8-1: Architektur des DBFS
Das DBFS schaltet sich als semantisches Dateisystem zwischen das physikalische Dateisystem und
das Betriebssystem ein. Einzelne Module der KDE-Oberfläche werden dabei ersetzt, so dass
alle KDE-Applikationen ein verändertes Dialogfenster für das Öffnen und Speichern von Dateien
aufrufen:
Abb. 2.8-2: Öffnen einer Datei mit
âïçêÇ bei installiertem DBFS [Gor04]
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
OS=
Abb. 2.8-3: Speichern einer Datei mit
âïçêÇ bei installiertem DBFS [Gor04]
Als Ergänzung zum KDE-Dateimanager dient das Programm
âÇÄÑë, das in wesentlichen Teilen dem
»Öffnen«-Dialog entspricht:
Abb. 2.8-4:
âÇÄÑë [Gor04]
Intern benötigt DBFS die Unterstützung einer SQL-kompatiblen Datenbank, um einen Index zu
verwalten [Gor04]. DBFS speichert in diesem Index allerdings keine Metadaten aus Dateien ab,
sondern setzt beim Speichern auf die Eingabe von Schlüsselworten durch den Benutzer
( Abb. 2.8-3). Das DBFS erfordert also genauso wie Verzeichnisbäume die aktive Mithilfe des
Benutzers, der einen entsprechenden Aufwand betreiben muss [Mil05].
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
OT=
OKV=jáÅêçëçÑí=táåcp=
»WinFS« ist die Abkürzung für »Windows Future Storage« und sollte ursprünglich mit Windows
Vista veröffentlicht werden, bis das Projekt auf unbestimmte Zeit verschoben und schließlich im
Juni 2006 eingestellt wurde [Wik05]. Am 29.08.2005 wurde jedoch eine erste Beta-Version von
Microsoft in Umlauf gebracht, die unter Windows XP lauffähig ist [Mic05]:
Abb. 2.9-1: WinFS Beta 1 [Mic05]
WinFS verwaltet keine Dateien aus dem physikalischen Dateisystem, sondern speichert Dateien
über den Microsoft SQL Server 2005 ( Kap. 3.3.5.1) in einer BLOB-relationalen Datenbank
( Kap. 4.2.1) ab. Um die Kompatibilität zu älteren Anwendungen zu gewährleisten, bildet ein
Modul von WinFS diese Datenbank ins Dateisystem ab:
Betriebssystem
App
App
App
App
Physikalisches
Dateisystem
Datenbank
(MS SQL)
WinFS
Abb. 2.9-2: Integration von WinFS in Microsoft Windows
Nach der Installation von WinFS erscheint im »Arbeitsplatz«-Fenster das neue Symbol »WinFS
Stores« [Mic08c]:
fåíÉÖê~íáçåI=fåÇÉñáÉêìåÖ=ìåÇ=fåíÉê~âíáçå=ÜçÅÜÇáãÉåëáçå~äÉê=a~íÉåçÄàÉâíÉ=
OU=
Abb. 2.9-3: Einbindung von WinFS in den Explorer
WinFS kann mehrere unabhängige Datenbanken (»Stores«) verwalten, z.B. eine für jeden Benutzer.
Beim Zugriff über den Windows-Explorer verhält sich ein Store wie eine normales Laufwerk mit
Dateien und Verzeichnissen, da WinFS hier abwärtskompatibel ist. Die eigentlichen Neuerungen
von WinFS werden erst beim nativen Zugriff sichtbar. Das Hilfsprogramm »WinFS Type Browser«
dient der Spezifikation von Dateiformaten, der »StoreSpy« ist ein rudimentärer Datei-Manager, der
im Gegensatz zum Explorer direkt auf WinFS zugreift.
OKVKN=táåcp=qóéÉ=_êçïëÉê=
Jede in WinFS gespeicherte Datei (»Item« genannt,
Kap. 4.4.4) entspricht einem vorher definier-
ten Schema, das von Anwendungen durch Vererbung erweitert werden kann:
Abb. 2.9-4: WinFS-Klasse
póëíÉãKpíçê~ÖÉKdÉåÉêáÅcáäÉ
O=bñáëíáÉêÉåÇÉ=iëìåÖÉå=
OV=
Diese objektorientierte Typhierarchie erscheint als konsequente Weiterentwicklung von Rufus
(
Kap. 2.3) und vor allem Microsoft OLE (
Kap. 2.4). Die Eigenschaften eines WinFS-Items
umfassen auch vielseitige Metadaten, wie das Beispiel einer Videoaufzeichnung zeigt:
Abb. 2.9-5: WinFS-Klasse
póëíÉãKpíçê~ÖÉKsáÇÉçKoÉÅçêÇÉÇqs
OKVKO=píçêÉpéó=
Der StoreSpy dient zur Betrachtung eines WinFS-Stores. Als Beispieldaten wurden etwa 400 JPEG-
Bilder mit Exif-Metadaten [EXI07] und etwa 150 PDF-Dokumente in einen WinFS-Store kopiert.
StoreSpy zeigt eine dreigeteilte Ansicht: links wird der Verzeichnisbaum des Stores angezeigt, in
der Mitte ist eine Liste mit allen Dateien untergebracht, und rechts davon sind die Eigenschaften der
ausgewählten Datei zu sehen:
Details
- Seiten
- Erscheinungsform
- Originalausgabe
- Jahr
- 2009
- ISBN (eBook)
- 9783836645348
- DOI
- 10.3239/9783836645348
- Dateigröße
- 14.5 MB
- Sprache
- Deutsch
- Institution / Hochschule
- Technische Universität Dortmund – Informatik
- Erscheinungsdatum
- 2010 (April)
- Note
- 2,0
- Schlagworte
- relationale datenbanken dateisystem relationenalgebra indexierung
