Home

Integration, Indexierung und Interaktion

1. Damit entspricht auch die Architektur der Microsoft Indexerstellung derjenigen einer Desktop Suchmaschine gt 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 2 6 Microsoft Windows Explorer 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 Integration Indexierung und Interaktion hochdimens
2. VIDCreationDay int VIDCompressedHeader int VIDMultiStreams int E VIDArtist varchar 31 VIDComment varchar 31 VIDThema varchar 31 VIDVideoTitel varchar 31 VIDFirmware EN ID3Artist varchar 30 ID3Trackname varchar 30 ID3Albumname varchar 30 139 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte ID3Comment varchar 30 ID3Year varchar 4 ID3Genre int IMGL int IMGH int IMGFarbmodus int IMGCreationTime varchar 5 IMGCreationYear int IMGCreationMonth int IMGCreationDay int IMGEquipment varchar 127 IMGBelichtung varchar 127 IMGFirmware varchar 127 IMGTitel varchar 127 IMGCopyright varchar 127 IMGArtist varchar 127 IMGComment varchar 127 IMGFocus varchar 15 IMGBlende varchar 15 IMGChip varchar 11 AUDMin int AUDSec int AUDHund int AUDChannels int AUDBits int AUDSamples int AUDSampleRate int LSTAnzl int LSTAnz2 int LSTAnz3 int LSTAnz4 int LSTOptionen int LSTCreationTime varchar 5 LSTCreationYear int LSTCreationMonth int LSTCreationDay int conn cmd ExecuteNonQuery Indexe erstellen cmd new SqlCommand CREATE CLUSTERED INDEX fi ON Test File Typ FileBez FileKey FileSize File Time FileNew
3. 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 ls F sfs owner smith bio txt paper tex prop tex 7 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 AND Verkn pfung der einzelnen Filter x l F sfs ouner snith text resune bio tex d Abb 2 2 4 Alle Dateien von Smith die den Begriff resume enthalten Gif91 Das virtuelle Verzeichnis field zeigt alle verf gbaren Attributnamen als Unterverzeichnisse an Das Verzeichnis text gestattet dabei das Durchsuchen aller Dateik rper was das Schema der einzelnen Dateiformate durchbricht Is F sfs field exports owner ext priority imports sub ject name Abb 2 2 5 Virtuelles Verzeichnis field Gif91 2 Existierende L sungen 2 2 1 Weiterentwicklungen 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 sfs erzeugt vermischt das in Gop99 entworfene Dateisystem HAC f r Hierarchy And Content die Verzeichnisstruktur des physikali
4. Flug DUS FRA HEL 31 07 2007 00 00 00000056 Flug HEL FRA DUS 06 08 2007 00 00 00000028B m Ingo Olaf Schumacher 21 03 2003 15 41 11 10 2003 12 31 Unver ndert 07 01 2005 10 27 Unver ndert 00004DA8 Unver ndert HHUHDACH Unver ndert 00005980 Unver ndert 00008570 8 Jindra Jindra 8 Jindra 8 Jindra 8 Jindra Jindra B Jindra 8 Jindra Abb 6 2 1 Dateiname Dateizeit und ID F bzw Filekey f n o an a LI bk 86 6 Referenz Library 6 2 2 Selektion Die Auswahl von Dateien ist eine der wichtigsten Operationen einer Library zum einen ist das Ausw hlen bzw Auffinden bestimmter Dateien die Motivation f r die Entwicklung eines derartigen Informationssystems gt Kap 1 andererseits stellt die Selektion eine Vorstufe vieler anderer Ope rationen dar etwa f r das Massen l schen gt Kap 5 1 6 nicht mehr ben tigter Dateien Die heute wichtigste Abfragesprache f r Datenbanksysteme ist SQL Das bedeutet insbesondere dass viele Entwickler in der Industrie und im akademischen Umfeld mit dieser Sprache vertraut sind SQL gestattet durch den SELECT Befehl die Formulierung sehr komplexer Selektionen so dass ein Parser diese Ausdr cke in mehrere elementare Suchanfragen aufspalten und die Ergebnisse danach verkn pfen muss etwa durch Vereinigung der entstandenen Mengen Saa05 Im Interesse einer m glichst einfachen und effizienten Referenz Implementierung wird hier jedoch auf SQL als Abfragespr
5. 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 2 4 Microsoft OLE 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 gt 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 v
6. Beagle unterst tzt nicht nur die Suche nach Dateien sondern findet auch installierte Programme und greift auf Internet Suchmaschinen zu Es vereint damit verschiedene Suchfunktionen in einer einzigen Applikation Nov05 31 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Beagle Search Sc Search terms web Browser r Anywhere a 2 Find x 2 R in Addressbook E Conversations 3 Matches X in Mail IM with godbyk IM with nhislapshot9 IM with godbyk in Web Pages Started 07 18 2004 16 19 59 Started 01 31 2004 14 48 33 Started 08 04 2004 19 00 12 Finished 07 18 2004 16 48 47 Finished 01 31 2004 16 13 00 Finished 08 04 2004 22 22 53 in Chats ul Applications 3 Matches ve Web Browser Mozilla Firefox Mozilla 2 Browse the web Web Browser DD Web Browser ES Google 5 Matches Lei Mozilla Home of the Firefox webbrowser Thunderbird and the Firefox Rediscover the web ES nn If you can use the Firefox browser ZER USA m Learn more about Firefox Firefox 1 0 Today Tabbed Browsing View more than Preview Release The safer faster better one web page in a single window with this time web browser featuring tabbed browsing saving feature s integrated search and live bookmarks http www mozilla org products firefox 14k http www mozilla org 13k a el bz Browser A R Bi Netscane 7 2 Best 5 results of 14 are shown E Show More Results
7. Die Zeit f r die vollst ndige Neuindexierung von einer Million Attributwerten die in den Dateien enthalten waren betrug 96 Minuten Gif91 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Verzeichnisbaum lesen Dateityp ermitteln Transducer Verzeichnis Transducer Object Transducer Quelltext Transducer Text S Transducer f r andere Dateitypen 0 2 Indextabellen erzeugen Indexbaum erzeugen 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 gt Kap 2 1 f r eine vollst ndige Neuindexierung ben tigt wird ist mit dem Zeitbedarf in Gif91 vergleichbar 2 3 Rufus Das Rufus Projekt besteht aus den Applikationen xrufus grafische Applikation rufustrn erwei terter Usenet Reader und rufusbld Indexierung die alle auf Userebene ablaufen Sho93 Damit entspricht das Rufus Design prinzipiell dem einer Desktop Suchmaschine gt Abb 2 1 1 hnlich wie das Semantic File System gt 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 Konze
8. EXI07 Fli07 Gia99 Gif91 148 Brinkhoff T Hash B ume und andere mehrdimensionale Punktstrukturen zur Speicherung von Laserscanner Daten 2 Oldenburger 3D Tage Optische 3D Messtechnik Photogrammetrie Laser Scanning Wichmann Verlag 2003 http www fh oow de institute iapg personen brinkhoff paper 3D 2003 pdf Stand 23 10 2008 Codd E A Relational Model of Data for Large Shared Data Banks Communications of the ACM Volume 13 Ausgabe 6 Juni 1970 http portal acm org citation cfm id 362685 Stand 23 10 2008 Dourish P et al Extending document management systems with user specific active properties ACM Transactions on Information Systems TOIS Volume 18 Issue 2 April 2000 http portal acm org citation cfm id 348758 Stand 23 10 2008 http www exif org Stand 23 10 2008 erste Referenzierung 03 12 2007 FlickR http www flickr com Stand 23 10 2008 erste Referenzierung 04 12 2007 Giampaolo D Practical File System Design with the Be File System Morgan Kaufmann Publishers 1 Auflage 1999 Gifford D K et al Semantic file systems Proceedings of the 13th ACM Symposium on Operating Systems Principles Denver 1991 http portal acm org citation cfm id 121138 Stand 23 10 2008 Gno06 Gop99 Gor04 Gro07 Gut84 Hac99 Har05 Literaturverweise Gnome the free desktop project http www gnome org Stand 23 10 2008 erste Ref
9. Festnetz Telefon Mobiltelefon Fax 4 gt ass EMail A Bankverb indung a ES Sonst iges eegen Abb 7 2 2 Adresse die eine Telefonnummer enth lt Wird nun die SMS noch einmal ge ffnet so erscheint neben der Telefonnummer auch der zugeh ri ge Name der durch eine Join Operation ber die Telefonnummer gefunden wurde u Tina Geburtstag __ 05 53 Von Tina 491737064555 chi iepen TR ein Pe Hola geburtstagskind Wollte dir noch mal rucken einen sch nen abend mit den kollegen aus S eichern dortnund wiinschen LaB dich ordentlich S nden feiern Und danke f r gestern Tina Abb 7 2 3 Join von SMS und Adresse 105 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 7 3 Benutzerdefinierte Filter Die in gt Kap 7 1 vorgestellte Shell bietet einen Aufruf des Datei Managers anhand des Dateifor mats Dieses Attribut wurde gew hlt weil sich Benutzer in der Regel an den Typ einer gew nschten Datei erinnern wie etwa Audio Datei oder Bild Dar ber hinaus ist es jedoch erforderlich auch Suchanfragen bez glich anderer oder mehrerer Attribute zu stellen oder innerhalb des Datei Managers ein Suchergebnis durch Hinzuf gen weiterer Bedingungen zum Suchfilter gt Kap 6 2 2 zu verkleinern Zum Erstellen eines Suchfilters durch den Benutzer wurde ein Dialogfenster implementiert gt Abb 7 3 1 Mit der Schaltfl che Hinzuf gen kann ein Attribut des globalen Datenr
10. H Byte Verf gbarer Platz 47 471 034 368 Byte Verf gbarer Platz 47 471 034 368 Byte Abb 7 4 2 638 Bilder ohne Ordner Abb 7 4 3 638 Bilder mit Ordnern 108 7 Interaktion 7 4 1 Kalenderansicht Wenn automatische Ordner anhand von Tagen gebildet werden ist eine Kalenderansicht f r das Hauptverzeichnis verf gbar Ein Klick auf einen markierten Tag ffnet sofort das entsprechende Unterverzeichnis und zeigt somit alle Dateien eines bestimmten Tages Abb 7 4 4 Auf die Dateizeit bezogene Ordner in Kalenderdarstellung Automatische Ordner und damit auch die Kalenderdarstellung sind nur bei aktiver Sortierung ver f gbar Die Dateien im Suchergebnis werden vom Datei Manager mittels Heapsort in O n log n sortiert so dass bez glich des Sortierkriteriums gleiche Dateien jeweils aufeinander folgen Da durch ist es in O n m glich solche Gruppen zu erfassen und durch einen Ordner zu ersetzen 7 4 2 Vorteile Automatische Ordner scheinen zun chst Verzeichnisse im herk mmlichen Sinn zu sein die eigent lich vermieden werden sollen gt Kap 1 Es besteht jedoch ein gro er Unterschied denn diese Ordner werden automatisch anhand des Datenbestands gebildet Daher sind automatische Ordner immer aktuell zudem kann eine Datei nicht wie bei traditionellen Dateisystemen in einem falschen Ordner erscheinen Wird beispielsweise eine Datei die noch keinem Verzeichnis zugeordnet wurde umbenannt so erscheint sie ggf sofort im
11. In diesem Abschnitt wird gezeigt dass das relationale Datenmodell ohne Verlust von Informationen auf das Datenmodell einer Library abgebildet werden kann Da sowohl die Schemata relationaler Datenbanken als auch Library Schemata eine Menge von Relations bzw Objekt Schemata sind gen gt es zun chst eine Abbildungsvorschrift zu konstruieren die Relations Schemata durch ein Schema Mapping Les06 in Objekt Schemata einer Library berf hrt Ein Relations Schema R ist genau wie ein Objekt Schema R eine Menge von Attributen A Aq Neben diesen allgemeinen Attributen fordern Objekt Schemata jedoch ein Schl sselattribut F und ein Typ Attribut T Diese m ssen von einer Abbildungsvorschrift hinzugef gt werden so dass gilt 60 4 Integration R R U F T F T R A R A 4 13 Alle Attribute aus R werden unver ndert bernommen so dass bei der Abbildung keine Informa tionen verloren gehen F r die Attribute F und T muss die Bedingung 4 7 eingehalten werden Bei der Abbildung r R r R m ssen die Attributwerte f und t unter Beachtung der Vorschriften 4 3 4 5 4 6 und 4 12 vergeben werden 4 2 1 BLOB relationale Datenbanken Auch in umgekehrter Richtung R gt R kann eine Abbildung konstruiert werden so dass Objekt Schemata R in Relations Schemata R umgewandelt werden k nnen Da Relations Schemata belie bige Attribute enthalten d rfen k nnen sowohl alle Attribute A als auch das Schl sselattribut F und das Typ A
12. Q Datei in E Mail versenden X Datei l schen Andere Orte O Gemeinsame Dokumente E Eigene videos d Arbeitsplatz 2 Netzwerkumgebung Photoshoot mpg MPEG Datei Ge ndert am Samstag 19 Juni 2004 15 47 Keine Markierung Keine Markierung CH Bildaufgaben O Als Diashow anzeigen Abz ge online bestellen ty Bilder drucken Alle Elemente auf CD kopieren Datei und Ordneraufgaben J Neuen Ordner erstellen e Ordner im Web ver ffentlichen E Ordner freigeben Andere Orte gt Dateien von Besitzer A Gemeinsame Bilder d Arbeitsplatz SJ Netzwerkumgebung Details Eigene Bilder Dateiordner Ge ndert am Freitag 8 September 2006 10 32 Bilddatei markiert CH Bildaufgaben T Als Diashow anzeigen Abz ge online bestellen A n Bild drucken E Als Hintergrundbild Auf CD kopieren Bilder online kaufen Datei und Ordneraufgaben m Datei umbenennen L i Datei verschieben Datei kopieren amp Datei im Web ver ffentlichen CH Datei in E Mail versenden XK Datei l schen Andere Orte Cl Gemeinsame Bilder Cl Eigene Bilder E Arbeitsplatz Netzwerkumgebung Details Abb 7 6 2 Bildaufgaben von Windows XP Musikaufgaben D Alle wiedergeben Musik online kaufen Alle Elemente auf Audio CD kopieren Datei und Ordneraufgaben C Neuen Ordner erstellen fe Ordner freigeben Andere Orte CN Gemeinsame Musik a Eigene Musik 3 Arbeitsplatz Netzwe
13. hrend das Dateisystem und der Index auf der deut lich langsameren Festplatte gespeichert sind Das Massenl schen l uft im Index nun in zwei Phasen ab in der ersten Phase werden hnlich wie beim Suchen alle Eintr ge in den Indexen verarbeitet F r jeden Eintrag wird in der L schliste nach dem Filekey gesucht wird er gefunden werden alle Eintr ge der betroffenen Datei markiert Master Index Bilder Index MP3 Index L schliste Filekey Filekey Filekey ze Heres alen LL9ACX1 2GuIP7 D Filekey Typ Z6_HG7ES Bild gt IA Wl Laaen Bild 30 kuy JGUIP7SD_ MPS 30 KuXY Bild Abb 5 1 11 Vor dem Massenl schen Das L schen jener Dateien in der L schliste entspricht weitgehend der bereits vorgestellten Datei suche gt Kap 5 1 2 Die aktuelle Datei wird allerdings nicht auf das Erf llen einer Suchbedingung gepr ft oder an den Aufrufer zur ckgeliefert sondern in der L schliste gesucht Wird sie dort auf gefunden werden ihre Eintr ge im Master Slave Index markiert etwa durch Setzen eines Bits in einem speziellen Attribut oder durch berschreiben des Filekey mit Nullbytes Y d 2 N S N N Master Index Bilder Index MP3 Index L schliste Filekey Typ Filekey Filekey Filekey Weer Bid ZeHGVES al JOU aaen eid Borkum JGUIP7 D_ MP3 30 KUY Bild E zum L schen markierte E
14. kann also indivi duelle Datei Schemata verwalten gt Kap 4 3 1 Anwendungsprogramm das nach dem Booten oder nach dem Login als erstes gestartet wird und einen Mechanismus zur Eingabe oder Auswahl von Befehlen bietet und andere Programme starten kann gt Kap 7 1 Structured Query Language Abfragesprache f r Datenbanken Versehen von Dateien mit Zusatzinformationen gt Kap 7 5 Kleines Programm das ohne Fenster direkt auf dem Desktop dargestellt wird und kleine Aufgaben wie z B die Anzeige der Uhrzeit bernimmt gt Kap 7 1 1 1 B Testprogramm zur Seek Geschwindigkeit Anhang B Testprogramm zur Seek Geschwindigkeit Um in gt Kap 3 3 3 1 den Geschwindigkeitsunterschied zwischen sequenziellem Lesen und dem Lesen von Sektoren an beliebigen Positionen zu ermitteln wurde das folgende Testprogramm ers tellt Es kann mit Borland Pascal f r den Real Mode compiliert werden F r beide Zugriffsarten werden jeweils 10 Durchl ufe ausgef hrt bei jedem Durchlauf werden 1024 KB also 2048 Sektoren eingelesen F r den sequenziellen Zugriff wird bei jedem Durchlauf ein zuf lliger Startblock ausgew hlt also 10 Mal beim randomisierten Zugriff f r jeden einzelnen Sektor also 20480 Mal Anschlie end wird pro Zugriffsart die Gesamtzeit f r die 10 Durchl ufe ausgegeben mit einer Genauigkeit von einer achtzehntel Sekunde B 1 SEEKTEST PAS program Seeklest uses Dos Die folgende Funktion ruft das BIOS auf um Anz
15. 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 gt 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 Abb 2 2 1 Architektur des Semantic File Systems Gif91 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 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 sfs ist Suchanfragen werden durch Zugriffe auf bestimmte Unterverzeichnisse realisiert Die Metadaten werden im Gegensatz zu vielen anderen Systemen gt Kap 2 1 gt 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 ls F sfs owner jones root Abb 2 2 2 Inhalt von sfs owner Gif91
16. u gt euP ES ESCHER IS MP3 gt Linacx Bild JGUIP7 D_ MP3 gt 30 KUXY Bild Abb 5 1 5 Nach Bearbeitung der zweiten Datei Kol08c Die dritte Datei die der Master Index liefert ist wieder ein Bild Die Metadaten f r das Bild mit dem Schl ssel LL9 ACX1 finden sich wieder an der Stelle auf die der Merker im Bilder Index zeigt und so weiter Damit dieser Merge Join funktioniert m ssen alle Indexe die Merge Eigenschaft 5 7 erf llen Die brigen Operationen m ssen dazu auf Algorithmen basieren die dies stets gew hrleisten Kol08c 73 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 5 1 3 Hinzuf gen Sollen neue Dateien zum Index hinzugef gt werden so m ssen die entsprechenden Tupel ans Ende der Index Relationen angeh ngt werden Dadurch wird die Sortierung der bereits vorhandenen Tu pel nicht ge ndert Die neuen Tupel haben automatisch die h chste Position in den jeweiligen Rela tionen so dass auch f r sie die Merge Eigenschaft gilt 5 1 4 ndern Zum ndern eines Tupels wird der Index wie beim Retrieval gt Kap 5 1 2 sequenziell durchlau fen Wird das zu ndernde Tupel anhand des Schl ssels gefunden so wird es aktualisiert Dieser Vorgang kann die Reihenfolge von Tupeln nicht beeinflussen da die Position des Tupels innerhalb einer Index Relation selbst bei einer nderung des Filekeys unver ndert bleibt 5 1 5 L schen Wird eine
17. 16 Trackliste einer Audio CD dtHTML 18 HTML Text dtMail 19 EMail dtArchive 22 Archivdatei dtMP3 23 MP3 Klang dtVideoMPEG 25 MPEG Video dtBildTrue 26 Unkomprimiertes Echtfarben Bild dtSMS 33 SMS dtDigiFoto 34 JPEG Bild dtVideoAVI 35 AVI Video dtTrueType 36 Skalierbare Schriftart dtQuickTime 39 Quicktime Video dtSearch 42 Abgespeicherter Suchfilter gt Kap 7 3 LCARSFiletypes 44 Bislang h chste vergebene Nummer Der Wertebereich dom F der Referenz Implementierung besteht aus genau 8 Zeichen und ent spricht damit dem Datentyp String 8 Da das Attribut F nur f r ein einziges Dateiformat eine Schl sselfunktion bernehmen muss k nnen Applikations bzw Domain Klassen die Attributwerte f unabh ngig vergeben In der Referenz Implementierung wird f r in Heap Dateien zusammenge fasste Datenobjekte das physikalische Offset innerhalb der Heap Datei in hexadezimaler Schreib weise verwendet andernfalls ist der Schl ssel eine zuf llig gew hlte Zeichenkette Folgende Abbil dung zeigt eine Liste verschiedener Dateien in der u a die Attribute Bezeichnung und Filekey auf gef hrt sind Dateien mit Hashcodes als Prim rschl ssel sind rot markiert 8 Felizitas 23 Unver ndert Felizitas 24 08 03 2006 12 40 8 Felizitas 25 Unver ndert 4 Felizitas 26 Unver ndert Felizitas 27 Unver ndert e Felizitas 28 Unver ndert e Felizitas 29 Unver ndert DI Felizitas Ottemeier 07 01 1980 00 00 OOOD2A
18. 3 A formatieren Archiv einlesen 5 Diskette 5 formatieren Archiv einlesen Nachrichten DI EMail lesen oder schreiben 8 SMS lesen oder schreiben Programme Einstellungen Eingelegte PCMCIA Festplatte und DVD RAM Ereignisse o oY 1 IP Adresskonf likt 0 5 neue EMails D 8 neue Dateien 4 Termine DI 1 Geburtstag Eigene Dateien Externe Dateien O TOSHIBA MKZBB1MPL DUD RAM im HL DT ST DUDRAM GSA 4167B o CD Player G H Audio CD auslesen og CD DVD brennen aus gespeicherter Sitzung Y Nullmoden Kabel an LPT2 Meister Sklave Gi Dateien von DOS importieren Diskette 3 A formatieren Archiv einlesen 5 Diskette 5 B formatieren Archiv einlesen 9 Diamond Rio PMP an LPT1 intern SmartMedia Alarme Ereignisse Abb 7 1 11 Dynamisch erzeugte Menuseite 102 7 Interaktion In eine Menuseite eingebettete Hinweise sind wesentlich diskreter als die blicherweise verwen deten Fenster zur Darstellung von Warnungen und Fehlermeldungen da sie den Eingabefokus nicht blockieren Der Benutzer wird daher nicht gezwungen sofort auf Alarme zu reagieren Dies ist besonders vorteilhaft im Zusammenhang mit der AutoPlay Funktion von Microsoft Win dows Beim Einlegen eines externen Datentr gers CD DVD Flash Speicherkarte USB Festplatte usw erscheint umgehend ein Menu das dem Anwender diverse Aktionen pr sentiert die auf das eingelegte Medium angewendet werden k nnen
19. Abb 2 10 1 Linux Beagle Nov05 2 10 2 Apple Spotlight Die Hersteller von Betriebssystemen arbeiten ebenfalls daran die Funktionalit t von Desktop Suchmaschinen in ihre Produkte zu integrieren Das gilt z B f r die Firma Apple die Spotlight als Suchmaschine in Mac OS X ab Version 10 4 Tiger integriert Fr here Versionen von Mac OS X gestatteten nur die Suche nach den klassischen Attributen des physikalischen Dateisystems More Search Options Custom ei Find items whose file name contains content includes date created 5 12 30 01 O date modified s 12 30 01 O size s less than S W kind is document ei fa Advanced Options F file type is rei Dfile folder is locked creator KB Oj nameficon is locked Oversion is O has a custom icon B folder s Ee is nvisible Delete Save As Y f Cancel Co Abb 2 10 2 Klassische Suchparameter unter Mac OSX 32 2 Existierende L sungen Spotlight f gt sich durch eine Eingabezeile f r Suchbegriffe nahtlos in den Finder ein Bei der An zeige von Suchergebnissen stehen Kontrollelemente zum Eingrenzen der Suche zur Verf gung Kind Any Size Less than bookmarks 1 html 11 07 2005 22 25 bookmarks htmi 06 08 2005 23 10 Documents a wv Other D widget com apple widget wikipedia plist 16 07 2005 19 18 Wikipedia 06 08 2005 23 11 Wikipedia Today at 00 16 Select an item to see i
20. Abschlie end werden M glichkeiten zur Integration in bereits exis tierende Systeme sowie zur Weiterentwicklung vorgestellt gt Kap 8 1 1 1 Integration Als Teilziel Integration wird der uneingeschr nkte Zugriff auf alle Attribute von Dateien und Tu peln relationaler Datenbanken auf Betriebssystem Ebene realisiert 1 Einleitung 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 l 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 gt 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 da
21. E Removable Disk Di 7 E Always do this for pictures Pictures options View pictures ising Windows Media Center General options Open folder to view files Explorer Set AutoPlay defaults in Control Panel Abb 7 1 12 AutoPlay Menu von Windows Vista Dieses Menu erscheint umgehend nach dem Mounten des Datentr gers auch wenn der Benutzer zu diesem Zeitpunkt noch nicht mit den Dateien arbeiten oder sie direkt mit einem Programm ffnen m chte Unter Umst nden bietet das Menu die ben tigten Funktionen gar nicht an das Fenster st rt also Eine hypertextbasierte Shell verbessert diese Situation indem alle gemounteten Laufwerke zu sammen mit ihren jeweiligen Befehlen als Menueintrag pr sentiert werden Die Befehle k nnen so auf der Hauptseite mit einem Klick aktiviert werden ohne jedoch den Arbeitsfluss des Benutzers zu st ren of CD Player lt i Diamond Rio PMP an LPT1 oY Nullmodem Kabel an LPT2 a Diskette 3 A D Diskette Da Abb 7 1 13 Gemountete Laufwerke und ihre Befehle W hrend traditionelle Menus als Baum strukturiert sind gestatten Hypertext Seiten dar ber hinaus weitere Strukturen z B zirkul re Verweise ohne R ckkehr auf eine bergeordnete Seite 103 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte DI EMails Bu SMS amp Termine R Videos Systen EI Archive of Audio CDs eg CD DUD Sitzungen oY DOS Programne 29 Hilfethemen
22. Indexierung gt Abb 3 3 10 also genau anders als eigentlich beabsichtigt Dadurch ist der Microsoft SQL Server ungeeignet f r die Indexierung von Metadaten was die bereits festgestellten M ngel von Microsoft WinFS gt Kap 2 9 2 erkl rt Zus tzlich f hrt die Indexierung noch zu einem Ge schwindigkeitsverlust beim Hinzuf gen neuer Tupel gt Abb 3 3 11 52 3 Existierende Indexe Ohne Index Indexiert 10000 ms 10000 ms 1000 ms 1000 ms 100 ms 100 ms 10 ms 1 10 100 Dateien in Tausend 11 02 3 4 5 Abb 3 3 10 Leistungsf higkeit des Microsoft SQL Server Kol08c 1000 s 100s Dateien in Tausend Ohne Index Indexiert Abb 3 3 11 Ausf hrungszeiten f r XML bulk loading 3 3 5 2 PostgreSQL hnliche Effekte wie der im vorigen Abschnitt untersuchte Microsoft SQL Server 2005 zeigt auch das quelloffene DBMS PostgreSQL Analog zu gt Kap C wurde ein Testprogramm gt Kap D eingesetzt um die Leistung von PostgreSQL beim Indexieren von Metadaten zu messen PostgreSQL Datenbanken k nnen unterschiedliche Indexstrukturen einsetzen allerdings sind nur B B ume f r hochdimensinale Datenr ume mit heterogenen Datentypen z B String und int ge eignet Eine Datenbank mit den Attributen von 92288 Dateien und einem Index f r jedes Attribut belegte 101 MB 53 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte pgAdmin Ill Datei Bearbeiten Anzei
23. Jindra in Dortmund d London d Skifahrt 2004 W Jindras Selbstprasentation W SHDH15 W Toscana Einzelne Bilder suchen Nach Name Nach Datum Nach K nstler Nach Ort Weitere Dateien Flugplane Powered by a E DEKWO M Unterverzeichnisse 2 Version 9 0 Build 20102007 Abb 7 7 5 BILDER Die folgende Abbildung zeigt alle Bilder nach Aufnahmeort gt Kap 7 5 1 sortiert Der obere Ab schnitt enth lt automatische Ordner gt Kap 7 4 f r alle Dateien mit Ortsangabe darunter sind alle Dateien ohne Angabe dieses Attributs nach Dateiname sortiert ggf nach Dateinamen gruppiert Sienna BILDER IATA Opera Datei Bearbeiten Ansicht Lesezeichen Widgets Feeds Extras Hilfe S Gi S o P A 3 http sienna BILDERMATA 8DISPLAY 4 Kacheln iste Gro e Symbole leine Symbole amp Zur ck Bilder BFE Bielefeld Deutschland DUS D sseldorf Deutschland JOG Jogjakarta Indonesien NRW Nordrhein Westfalen Deu gt QSF San Francisco USA SUC San Jose USA ZPE Osnabr ck Deutschland Ohne Ortsangabe Abschlussvortrag Diplom Boeing 787 Dissertation Vortrag 3 Logo Persiflage SHDH15 WA wew deskwork de auf Blackberry Weitere Dateien Flugpl ne Name Bilder 2 7 808 120 Byte Unterverzeichnisse 36 CFU Korfu Griechenland EWR Newark USA KLU Klagenfurt sterreich NUE N rnberg Deutschland ROM
24. Random Clock 0 for Durchlauf 1 to 10 do begin write 13 Random Durchlauf for Chunk 1 to 2048 do begin LBA Random MaxLBA Read 1 LBA P end end writeln 13 Random Clock Ticks zu je 1 18 2s SetIntVec 08 OldInt8 FreeMem P 32768 end 134 B Testprogramm zur Seek Geschwindigkeit B 2 Messergebnisse Die folgende Tabelle zeigt die Messergebnisse des Testprogramms gt Kap B 1 f r verschiedene Datentr ger Der obere Tabellenabschnitt beschreibt mechanische Festplatten die beiden untersten Zeilen SSDs Solid State Discs die auf Flash Speicher basieren le Sequenziell _ Zuf llig _ Faktor Toshiba MK1924FCV 518 MB 8 330 ms 469 176 ms Western Digital WDC AC21000H 2 291 ms 339 670 ms e Seagate ST330630A_ 30GB 4 736ms 283 956ms 60 0 Transcend 2 5 SSD 32 GB 6 429 ms Gr n hervorgehoben schnellster Datentr ger Rot hervorgehoben langsamster Datentr ger Abb B 2 1 Zeitverhalten von Speichermedien 135 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 136 C Testprogramm Microsoft SQL Server 2005 Anhang C Testprogramm Microsoft SQL Server 2005 Um in gt Kap 3 3 5 1 die Leistung des Microsoft SQL Server zu messen wurde ein Testprogramm in CH entwickelt Das Programm gt Kap C 3 kann mit Microsoft Visual Studio f r die NET Umgebung compiliert werden Zur korrekten Ausf hrung ist neben einem installier
25. Semantisches Filesystem ObjectSFS Diplomarbeit Eidgen ssische Technische Hochschule Z rich http e collection ethbib ethz ch ecol pool dipl dipl_79 pdf Stand 23 10 2008 Jagadish H V et al iDistance An adaptive B tree based indexing method for nearest neighbor search ACM Transactions on Database Systems TODS Volume 30 Issue 2 Juni 2005 http portal acm org citation cfm id 1071612 Stand 23 10 2008 K Desktop Environment http www kde org Stand 23 10 2008 erste Referenzierung 10 09 2006 Kersten M et al A Database Striptease or How to Manage Your Personal Databases Proceedings of the 29th VLDB Conference Berlin 2003 http www vldb org conf 2003 papers S34P01 pdf Stand 23 10 2008 Koll K Analyse und Bewertung verschiedener wichtiger Videoformate Technische Universit t Dortmund 12 07 2003 http www deskwork de DOWNLOAD DOCS DIPL ARB PDF Stand 23 10 2008 Koll K Master slave index in computer systems United States Patent 11 892071 http www freepatentsonline com y2008 0071732 html Stand 23 10 2008 Kol07b Kol08a Kol08b Kol08c Kol08d Kre07 Literaturverweise Koll K Einf hrung in relationale Datenbanken und semantische Dateisysteme http www deskwork de DOWNLOAD DOCS INTRO PDF Stand 23 10 2008 erste Referenzierung 02 12 2007 Koll K File systems should be like burger meals supersize your allocation units Outrageous opinion st
26. Spei her 8 Korfu S u 08 sl B Korfu S e Korfu B og Log 5 ogo Persif lage London I woody 20 03 2005 15 4 09 04 2001 19 02 ystic Bytes Software 915 20 03 2005 15 A Miri 544 24 07 2002 23 46 gi SB Stecker 5 28 11 2000 01 iri Logo Persiflage Cheniesee 06 1998 16 Saalbach 2004 Logo Persif lage Hacksoft 5 06 1998 16 Sabine il 18 07 2005 18 03 Logo Persiflage Killakat 1998 16 A Sandra 079 23 09 2005 00 59 Logo Persiflage Kinder hoko S 09 05 2001 16 8 Skifahrt 2003 Logo Persiflage Kl i 01 06 1998 16 Skifahrt 2004 Logo Persif lage 5 01 06 1998 16 E Space Janiri Sprockh vel 3 30 09 2005 21 42 Logo Persif lage 13 07 2003 16 B Starpr inz Logo Persiflage Starr War S 251999812 Teaner Fahrt 2002 Logo Persiflage Hindous NT 05 1999 15 Toscana Logo Persiflage World donin 3 ES amp Unzug Fee London 1 ek 02 Unitanz London S ht 02 Ute in Indonesien London A 5 ted H D Ute Tragus Bi 19 03 2005 12 27 London A A B2 Wagrain Webcam i 13 11 2004 15 21 London 3 m 02 H A wuu deskuork de auf Blackberry A 19 03 2005 12 27 Systendateien ild 1844x 386 Punkte 256 Farben Ordner 6 weitere Dateien ep 2s es chlie en WEIEREN I chlie en WEI I 7 7 ps 31 Angezeigte Dateien 638 Angezeigte Dateien 14 Gesantgr e 1 830 804 025 Byte Gesantgr e 20 893 432 Byte Markierte Dateien H Markierte Dateien H Grofie 0 Byte Gr e
27. Texturen Wissenschaft Fraktale Attraktoren oY Fraktale Baume Fraktale Mengen ze Gravitat ions Simulat ionen Abb 7 1 10 Untermenu Vorhandene Dateien zeigen und ndern 7 1 4 Vorteile Hypertext Menus k nnen als Shell umfangreiche nicht auf Verzeichnisse bzw Dateinamen be schr nkte Optionen f r die Organisation von Dateien darstellen Somit eignen sich derartige Shells f r den Einsatz mit Libraries Dar ber hinaus k nnen Menuseiten abh ngig von Ereignissen dynamisch erzeugt werden etwa nach dem Einlegen von Datentr gern beim Erkennen von defekten Festplatten bei f lligen Termi nen und vielem mehr Auf diese Weise k nnen Widgets ersetzt werden Willkommen Will kommen Eigene Dateien Externe Dateien of CD Player G H Audio CD auslesen Ge CD DVD brennen aus gespeicherter Sitzung anond Rio PMP an LPT1 intern SmartMedia Nullmoden Kabel an LPT2 Meister Sklave amp Dateien von DOS import ieren Diskette 3 A formatieren Archiv einlesen 5 Diskette 5 B formatieren Archiv einlesen Nachr ichten DI EMail lesen oder schreiben 8 SMS lesen oder schreiben Progranne Einstellungen Hilfe Nur statische Komponenten Eigene Dateien Externe Dateien o oe DUD RAM in HL DT ST DUDRAM GSA 4167B o CD Player G H Audio CD auslesen og CD DVD brennen aus gespeicherter Sitzung ullmoden Kabel an LPT2 Meister Sklave amp Dateien von DOS import ieren Diskette
28. Webserver Als Zusatzoption fiir die Indexierung von Verzeichnissen stellt der Apache HTTPD das fancy inde xing bereit bei dem die einfache Listendarstellung unordered list HTML Tags lt UL gt lt UL gt durch eine Tabellendarstellung mit Icons und Zusatzinformationen ersetzt wird tj Index of STUFF Opera Datei Bearbeiten Ansicht Lesezeichen Widgets Feeds Extras Hilfe sx amp N A Je http www deskwork desSTUFF Index of STUFF wei Parent Directory IATA TXT Yellowstone gif 33k Apachell 3 Server at www deskwork de Port 80 Abb 7 7 3 Zugriff auf ein Verzeichnis mit fancy indexing 118 7 Interaktion 7 7 1 Fancy fancy indexing Im Rahmen dieser Arbeit werden zwei Verbesserungen an der Echtzeit Indexierung durch eine Webserver Applikation vorgeschlagen die in Anlehnung an die oben erw hnte Zusatzoption fancy fancy indexing genannt werden Zur Demonstration wurde die Referenz Library um eine Webser ver Applikation erg nzt Kol08d Neben einer modernen d h auf CSS basierenden Oberfl che ist es das Ziel die von der Library verwalteten Metadaten auch beim Zugriff ber HTTP nutzen zu k nnen Dies wird erreicht indem vom Webserver in Echtzeit eine virtuelle Ordnerstruktur erzeugt wird die sich von au en ber URLs ansprechen l sst Das Hauptverzeichnis bietet analog zur Shell gt Kap 7 1 3 1 nach Datei typen gegliederte Ordner an Kol08d Sienna Opera Datei
29. Y x x dom Yim ai NEE He eg ge ke f r R ut 5 6 5 1 2 Retrieval Suchanfragen k nnen als Natural Join Saa05 zwischen Master und Slave Indexen durchge f hrt werden also m DX s bis m D lt sr Die Zahl der beteiligten Slave Indexe ist aus Performanz gr nden zu minimieren Query containment gt Kap 6 2 2 1 so dass beispielsweise bei Abfra gen ber Dateien eines bestimmten Typs j nur m D lt s berechnet werden muss Da nun keiner der Indexe seine Elemente anhand des Prim rschl ssels F sortiert erscheint es bei naiver Betrachtung so als m sste die Join Operation durch Nested Loops in O n implementiert werden W ren die Slave Indexe hingegen bez glich des Prim rschl ssels F sortiert K nnte f r je den Eintrag im Master Index eine bin re Suche durchgef hrt werden so dass sich die Laufzeit auf O n log n verbessern w rde Eine bin re Suche ist jedoch gar nicht erforderlich denn tats chlich kann beim Master Slave Index der Join als Merge Join Saa05 in O n berechnet werden indem eine zus tzliche Eigenschaft eingef hrt wird f r zwei beliebige Dateien des selben Typs gilt dass ihre relative Position zueinan der im Master Index m und im zugeh rigen Slave Index s stets dieselbe sein muss Kol08c Dies kann auch formalisiert werden Vo o m z 0 7 0 A Pos z 0 m lt Pos z 0 m gt Pos z 0 5 lt Pos z 0 5 Pos f r Zeilenposition des T
30. Zweige zu Farben mit mindestens 50 Blauanteil unabh ngig vom jeweiligen Rotwert Wird nun ein Attribut etwa der Wert f r blau nicht spezifiziert so m ssen von jedem inneren Knoten der sich auf dieses Attribut bezieht beide Zweige verfolgt werden denn es gibt keinen At tributwert aus der Suchanfrage anhand dessen die Entscheidung f r die Traversierung nur eines Teilbaums getroffen werden k nnte Der Aufwand f r die Suche w chst somit exponentiell mit der Anzahl irrelevanter Attribute so dass Partial Match Operationen nicht effizient unterst tzt werden 3 3 3 Ineffizienz von persistent gespeicherten B umen Eine weiteres Problem das ausnahmslos alle Baumstrukturen betrifft ist das Aufzwingen einer zu s tzlichen Zeitkomplexit t durch das Speichermedium und das verwendete Dateisystem 3 3 3 1 Zeitkomplexit t durch das Speichermedium ber einen wichtigen Einfluss auf die Leistungsf higkeit von Indexen verf gt das Zugriffsmuster der zugrunde liegenden Algorithmen auf das Speichermedium Als Extrempunkte sind hier ein rein 48 3 Existierende Indexe sequenzieller Zugriff auf hintereinander liegende Sektoren und ein randomisierter Zugriff auf belie bige Sektoren zu unterscheiden Speichermedien sind ausschlie lich auf sequenzielle Operationen hin optimiert dies gilt bei moderner Hardware sogar abgeschw cht f r den RAM Speicher Um dies zu verdeutlichen wurde die Leistung beider Zugriffsmuster von einem Testp
31. anderem m sste die Applikation also einen JPEG Decoder und Encoder enthalten dar ber hinaus eine Programmroutine zum Skalieren von Bildern Durch konsequente Ausnutzung der Referenz Architektur ist die Flugplan Applikation tats chlich wesentlich kompakter Zun chst wird ein Objekt von DatBild erzeugt in das das Hintergrundbild geladen wird Die ffentliche Methode GetBuffer liefert einen Zeiger auf die Bilddaten zur ck so dass die Flugwege ber das Bild kopiert werden k nnen Danach wird mit Scale die Aufl sung an gepasst und die fertige Bilddatei mit Save gespeichert Die Klasse DatBild stellt diese Methoden zur Verf gung die so nicht noch einmal implementiert werden m ssen Verf gt eine neuere Version von DatBild beispielsweise ber einen schnelleren JPEG Decoder profitieren so auch andere Program me davon 6 4 2 Implementierung Die Implementierung der Referenz Library bietet weitere Vorteile gegen ber anderen Systemen Der Verzicht auf SQL als Abfragesprache und die Einf hrung der Filter Datenstruktur gt Kap 6 2 2 erm glicht die Portierung auf mobile Plattformen mit eingeschr nkter Rechenleis tung bei gleichzeitiger Unterst tzung einer Volltextsuche Durch die gleichzeitige Verwendung ei nes Master Slave Indexes Kap 5 wird eine hohe Leistung bei Suchanfragen sichergestellt gt Kap 6 3 5 94 7 Interaktion 7 Interaktion In diesem Kapitel werden die vielf ltigen Vorteile f r die Organisation und In
32. array like and a hierarchical R tree like directory It is also reasonable that for very high dimensionality a linear organization of the directory is more efficient The reason is that due to the high overlap most of the directory if not the whole directory has to be searched anyway Abb 3 3 5 Beschreibung des X Baums Ber96 Web98 beweist schlie lich dass dieser Sachverhalt nicht nur f r R B ume sondern unter An nahme der Gleichverteilung f r jeden denkbaren multidimensionalen Index gilt der den Daten oder Objektraum partitioniert Dieser Beweis wird nun kurz skizziert Alle Attributwerte werden zun chst auf das Intervall 0 1 skaliert so dass der Datenraum auf einen Hyperw rfel mit der Kantenl nge 1 normiert wird Q 0 1 Innerhalb des Datenraums soll ein beliebiger Algorithmus Elemente zu Bereichen zusammenfassen entweder durch Unterteilen des Datenraums Q ohne R cksicht auf die tats chlich enthaltenen Daten z B kd Baum oder durch Clustern der tats chlich vorhandenden Objekte also Partitionieren des Objektraums o z B R Baum Die entstehenden Bereiche haben drei grundlegende Eigenschaften Web98 1 Jeder Bereich besitzt eine minimal umgebende Form minimum bounding region 2 Jede mbr ist konvex 3 Jeder Bereich enth lt mindestens zwei Elemente Ohne diese Bedingung w rde das Untertei lungsproblem nur auf eine andere Knotenebene der Baumstruktur verschoben Die Wahrscheinlichkeit dass be
33. auf die weiteren Attribute der Dateien beziehen 87 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Im zweiten Abschnitt ist f r jedes gemeinsame also in allen Objekt Schemata enthaltene Attribut eine Variable vorhanden zusammen mit einem Byte das das Suchmuster definiert Enth lt bei spielsweise NameParam eine Zeichenkette so legt NameSuchmuster fest ob der Dateiname NameParam an beliebiger Stelle enthalten sein soll 1 identisch mit NameParam 2 sein bzw damit beginnen 3 oder enden 4 soll Analog dazu werden f r alle anderen Attribute Bedingungen definiert Zus tzlich enth lt die Sektion einen Parameter f r die Volltextsuche der sich auf alle At tribute und bei Textdateien sogar auf den Dateiinhalt bezieht Der dritte Abschnitt der Filterstruktur enth lt Parameter um Bedingungen f r alle typabh ngigen Attribute wie z B Erscheinungsjahr oder Titel zu definieren Zusammenfassend besteht ein Filter also aus einer Menge von Dateitypen und Bedingungen die f r die Aufnahme einer Datei ins Suchergebnis ausnahmslos erf llt sein m ssen Damit bietet ein Such filter weniger M glichkeiten als SQL ist aber besonders leicht zu interpretieren und noch m chtig genug f r die Formulierung der wichtigsten in der Praxis erforderlichen Suchanfragen Dar ber hi naus gestattet der Eintrag Volltextsuche die Angabe eines Suchbegriffs nach dem in allen Attribut werten und abh ngig vom Dateiformat sogar i
34. beispielsweise die Kennung QKL die Stadt Heidelberg als Busstation firmiert mit HDB Unter der Kategorie drei sind Orte aufgelistet die we der ber einen Airport noch ber einen Bahnhof oder eine Busstation verf gen aber dennoch wich tig f r das Linienfluggesch ft sind Darunter fallen beispielsweise die Standorte der Fluggesell schaften oder gro e Verkaufsst tzpunkte LHN03 Die Referenz Library f hrt einen ITATA Code als Attribut in jedes Objekt Schema ein gt Kap 4 1 Beim Erstellen eines Suchfilters gt 7 3 kann eine Ortsangabe als Bedingung hinzugef gt werden Suchbegr iff Durchsuchen 0 A Der IATA Code Abb 7 5 3 Suche nach Dateien aus der Metropolitan Area von JFK NYO Im obigen Beispiel ist als Modus liegt bei ausgew hlt Dadurch werden nicht nur alle Dateien ins Suchergebnis aufgenommen die als Ortsangabe JFK New York Kennedy Airport haben sondern auch alle Dateien mit Orten die in derselben Metropolitan Area hier NYC liegen Darunter fallen neben den anderen Verkehrsflugh fen auch diverse Orte in Manhattan die Heliports besitzen z B Hafen oder Wall Street Beim Erzeugen eines automatischen Ordners gt Kap 7 4 anhand der Ortangabe l st der Datei Manager die IATA Codes anhand einer internen Relation IATACodes zu Ortsnamen auf und f gt sie zum Ordnernamen hinzu F r unterschiedliche Sprachversionen der Software k nnen hier unter schiedliche Relationen mit den Ortsnamen in der
35. cmd new OleDbCommand st conn cmd ExecuteNonQuery Console WriteLine Load sw Peek 10 0 ms 145 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 146 Testfall 1 sw Reset cmd new OleDbCommand SELECT FROM Test WHERE FileNew 1 conn OleDbDataReader r cmd ExecuteReader r Read r Close Console WriteLine Case 1 sw Peek 10 0 ms Testfall 2 sw Reset cmd new OleDbCommand SELECT FROM Test WHERE FileTyp 6 OR FileTyp 15 OR FileTyp 26 OR FileTyp 34 conn r cmd ExecuteReader ponp r Read r Close Console WriteLine Case 2 sw Peek 10 0 ms Testfall 3 sw Reset cmd new OleDbCommand SELECT FROM Test WHERE FileTyp 5 OR FileTyp 7 OR FileTyp 23 OR FileTyp 32 conn r cmd ExecuteReader an r Read r Close Console WriteLine Case 3 sw Peek 10 0 ms Testfall 4 sw Reset cmd new OleDbCommand SELECT FROM Test WHERE FileTyp 6 OR FileTyp 15 OR FileTyp 26 OR FileTyp 34 AND IMGL gt 1024 conn r cmd ExecuteReader zus r Read r Close Console WriteLine Case 4 sw Peek 10 0 ms Testfall 5 sw Reset cmd new OleDbCommand SELECT FROM Test WHERE FileTyp 5 OR FileTyp 7 OR FileTyp 23 OR FileTyp 32 AND ID3Artist Anastacia conn r
36. darin dass die Dateiliste nicht mit herk mmlichen Funktionen des Betriebssystems gewonnen wird sondern das Ergebnis einer Datenbank Abfrage ist die beliebige Attribute einschlie en kann In gt Abb 2 9 6 werden nur Bilder angezeigt deren Breite gr er oder gleich 1024 Pixel ist Diese Filterung der Dateien k nnte beispielsweise durch das SQL Statement SELECT FROM DefaultStore WHERE Width gt 1024 realisiert werden tats chlich verwendet WinFS eine propriet re Abfragesprache namens OPath Mic08a Trotz eines leistungsstarken Rechners mit 64 Bit CPU Athlon 64 3200 und 1 GB RAM ben tig te WinFS f r die einfache Suche aller Items etwa 0 4 Sekunden bei der oben gezeigten Filterung nach Bildgr e sogar 1 1 Sekunden Weitere Versuche mit dem Microsoft SQL Server in gt Kap 3 3 5 1 zeigen dass die schlechte Performanz weniger WinFS als vielmehr einem ungeeig neten DBMS anzulasten ist 30 2 Existierende L sungen 2 10 Moderne Desktop Suchmaschinen Durch die gro e Beliebtheit des WWW haben diverse gro e Suchmaschinen Betreiber wie Google basierend auf ihrer Suchtechnologie Produkte entwickelt die Dateien im lokalen Dateisystem auf finden sollen hnliche Produkte werden auch von zahlreichen anderen Herstellern angeboten Im Gegensatz zu lterer Software wie Lotus Magellan gt Kap 2 1 haben moderne Desktop Suchmaschinen eine gro e Verbreitung erlangt und somit eine hohe Relevanz Sie entsprechen je doch imme
37. dass hier ohne Index ein Zeitaufwand von O n bzw O log n entsteht Ohne Index Master Slave Index FAT ext2 FAT ext2 O log n O n O n Ollog n O n Oog n O n O n O log do Gr n hervorgehoben Verbesserungen bei h ufigen Operationen Rot hervorgehoben Verschlechterungen bei seltenen Operationen Suche TO O log n O 1 Ol OU Abb 5 2 2 Operationen im Vergleich Die Verschlechterung beim ndern und L schen von Dateien innerhalb moderner Dateisysteme wird akzeptiert um im Gegenzug eine schnelle Dateisuche zu erm glichen Um diesen Nachteil auszugleichen bietet der Master Slave Index eine effiziente Unterst tzung f r Massen Operationen wie batch rename und batch delete gt Kap 5 1 6 so dass z B das L schen vieler Dateien nur unwesentlich mehr Zeit ben tigt als das L schen einer einzigen Datei 5 2 1 Optimierung Das Einf hren von Slave Indexen f r jedes Dateiformat l sst das Verfahren ineffizient erscheinen denn eine Library mit sehr viele Dateitypen ben tigt auch sehr viele Slave Indexe Bei pragmati scher Betrachtung stimmt dies jedoch nicht da jede Datei in h chstens einem Slave Index vor kommen kann Dadurch k nnen keine Kollisionen entstehen wenn ein Slave Index f r mehr als ein Dateiformat benutzt wird 79 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Offenbar ist das Verwenden eines Slave Indexes f r mehrere Dateiformate genau dann kein Prob lem
38. gespei cherten Datei erzeugt 2 Existierende L sungen Neu erstellen Dateiname Verzeichnisse bmp e daten Datei Manager G videos Microsoft Works Diagramm Laufwerke E I Mit Datei verkn pfen IT Als Symbol IT Als Symbol Ergebnis Ergebnis n F gt ein neues Microsoft Formel Editor n F gt den Inhalt der Datei in Ihr Dokument ein 2 0 Objekt in Ihr Dokument ein so da eine sp tere Bearbeitung in der Ursprungsanwendung erfolgt 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 Microsoft Word Dokument atei Bearbeiten Ansicht Format Formatvorlage Schriftgrad Fenster Hilfe re Oe 1 10 1 11 Word Tel n Z 2 2 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 geste
39. hrung eines neuen lt SECTION gt Tags realisiert werden lt SECTION TITLE Nachrichten gt lt SECTION gt Abb 7 1 6 Definition von Sektionen mit HTML In einer Referenz Implementierung eines Hypertext Menus werden Sektionen nicht nur als optische Gliederung eingesetzt sondern alle innerhalb einer Sektion befindlichen Elemente k nnen vom Be nutzer eingeklappt werden so dass voraussichtlich l nger nicht ben tigte Optionen versteckt werden Der Status jeder Sektion wird persistent gespeichert so dass die Menusektionen ihren Zu stand bis zur n chsten nderung auch ber mehrere Logins hinweg beibehalten 99 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Er DESKWORK 8 1 ROOT Sienna 63 85 Wl Willkommen Systemeinstel lungen ke oY Systeme instel lungen ur ck oru rts Diese Einstellungen wirken sich auf das ge nfang sante System und alle Accounts aus Nur f r den Systenverualter Nur f r berechtigte Benutzer Allgene ines Netzuerk Auf l sung DNS Boot vorgang Ethernet Adapter Feiertage Internet Zugang Klang Proxy Message of the day Standort Standarddrucker Systenzeit Videos Zugriff f r alle Benutzer Pers nliche Einstellungen Systeninfo Abb 7 1 7 Darstellung von Sektionen in einer Menuseite 7 1 3 1 Dateizugriff Derartige Hypertext Menus sind vorz glich geeignet den erweiterten Funktionsumfang einer Libra ry zug nglich zu machen Auf der Hauptseit
40. im Vergleich fehlen allerdings als unwichtig angesehene Dateiformate und Attribute Analog zu 4 9 seien als X die n Attribute aus common L bezeichnet welche in allen k Schemata R vertre ten sind nach Bedingung 5 2 also insbesondere F und T Y seien die m brigen Attribute aus R Dann gilt X common L A an o nz Jdom X x xdom X xdom Y X X dom n 5 3 RH 1 D ya Y ER jcommon L Ein vollst ndiger Master Slave Index ist eine Menge von Relationen die aus genau einer ausge zeichneten Relation Master Index m und einer Relation f r jedes der k zu indexierenden Datei formate besteht Slave Indexe sj 70 5 Indexierung Index m s Sx 5 4 Der Master Index m speichert die Werte aller n typunabh ngigen Attribute X bis X Die in m enthaltenen Tupel sind das Ergebnis einer Selektion o aller Datenobjekte der zu indexierenden Da teiformate projiziert auf die Attribute X bis X Gr und bezeichnen die Projektion bzw Selektion der Relationenalgebra mC Ty x Q L dom X x x dom Kal ge m le ke f r R ul 5 5 ja Ein Slave Index s speichert ebenfalls den Schl ssel aller jeweils indexierten Dateien R F sowie alle m Attribute Y die f r das jeweilige Objekt Schema R spezifisch sind und indexiert werden Die Tupel in s sind ebenfalls das Ergebnis einer Selektion in L mit anschlie ender Projektion S C Try y Q L dom F x dom
41. r Frankfurt HAM f r Hamburg oder MUC f r M nchen Eine Ausnahme stellt beispielsweise der alte Flughafen von Dubai dar der die Kennung DXB erhielt und damit einen Buchstaben f hrt der berhaupt nicht im Namen Dubai enthalten ist Der Grund ist einfach es gab bereits einen 3 Letter Code DUB den Flughafen von Dublin Der zuerst festgelegte Code bleibt grunds tzlich be stehen um die Eindeutigkeit zu gew hrleisten LHN03 111 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte F r gro e St dte die ber mehrere Flugh fen verf gen wurde zus tzlich noch ein bergeordneter sogenannter Metropolitan oder City Code eingef hrt So findet man unter dem City Code BER f r Berlin die Flugh fen TXL f r Tegel THF f r Tempelhof und SXF f r Sch nefeld Unter LON f r London weist das System die dazugeh rigen Flugh fen Gatwick LGW Heathrow LHR Luton LTN London City LCY oder Stansted STN aus hnlich ist es in New York NYC mit den Flugh fen John F Kennedy JFK La Guardia LGA und Newark EWR der sogar in einem ande ren US Bundesstaat liegt LHN03 Weniger problematisch sind die Bezeichungen der Orte die in der zweiten Kategorie des 3 Letter Code Systems aufgef hrt sind obwohl sie nicht in direkter Verbindung zu einem Flughafen stehen Es handelt sich um die Punkte die mit einem Flugticket durch ein anderes Verkehrsmittel wie Bahn oder Bus erreicht werden Der K lner Hauptbahnhof hat
42. und Dateisystemen zu einer umfassenden Library umsetzen k nnen die propriet re Datenbank des EMail Programms mounten also durch ein geeignetes Schema Mapping gt Kap 4 2 in die Library einbinden Die einzelnen Tupel wer den dabei gleichberechtigt mit Dateien als hochdimensionale Datenobjekte aufgefasst und sind f r die Dateisuche zug nglich Im Beispiel w rde also nicht die physikalische Datei EBAY MBX zum Suchergebnis hinzugef gt sondern individuelle EMail Objekte die das Suchkriterium erf llen Die enthaltenen Daten werden dadurch f r das Betriebssystem und andere Applikationen zug nglich 65 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 4 4 2 Operationen Die quivalenz der Datenmodelle impliziert dass auf der Management Ebene gt Abb 4 2 beide Konzepte auf dieselbe Weise genutzt werden k nnen insbesondere ein Technologieaustausch m g lich ist so k nnen beispielsweise Beziehungen zwischen Datenobjekten durch die enthaltenen Me tadaten statt durch Verzeichnisse modelliert werden und Suchvorg nge bzw Ver nderungen durch eine grafische Oberfl che gt Kap 7 statt einer Abfragesprache durchgef hrt werden hnlich wie relationale Datenbanken bei ihrer Einf hrung 1 n Beziehungen zu n m Beziehungen erweitert ha ben so implizieren Libraries das Durchbrechen einer starren durch Verzeichnisse vorgegebenen 1 n Hierarchie Mar03 Dar ber hinaus lassen sich viele allt gliche Operation
43. wenn die Metadaten Tupel der jeweiligen Dateitypen dieselbe Gr e haben Ist dies nicht der Fall k nnen k rzere Tupel durch Opfern von Speicherplatz in der Gr e angeglichen werden Ab h ngig vom Dateityp werden die Bin rdaten des Slave Index als Tupel mit den jeweiligen Metada ten interpretiert Um den zus tzlichen Speicherbedarf bei einer solchen Implementierung zu minimieren sollten bei Anwendung dieser Technik die Slave Indexe nicht mehr nach Dateiformat sondern exponentiell nach Gr enklassen eingerichtet werden also z B f r Dateitypen mit bis zu 128 Byte an Metada ten 256 Byte 512 Byte und so weiter In der kleinsten Klasse werden somit h chstens 127 Byte verschwendet in der n chsten Klasse ebenfalls da ja mindestens 129 Byte belegt sind damit ein Tupel dieser Klasse zugeordnet wird anschlie end 255 Byte 511 Byte und so fort Der maximal verschwendete Speicherplatz entspricht bei exponentieller Klasseneinteilung ab der zweiten Klasse also immer 0 5 Gr e 1 was relativ zur Klassengr e konstant ist 5 2 2 Verifizierung Der Merge Join w hrend der Bearbeitung eines Master Slave Indexes wird ber den Prim rschl s sel F gebildet Da der Schl ssel zu den Metadaten einer Datei geh rt und auch au erhalb des Inde xes von Bedeutung ist muss er zumindest im Master Index gespeichert werden In den Slave Indexen ist das wiederholte Speichern des Filekeys jedoch nicht erforderlich da der Merge Join implizi
44. zu traditionellen Dateisystemen enthalten alle Objekt Schemata einer Library mit T eine eindeutige Beschreibung f r das Format 4 6 Da alle Datenobjekte eines Schemas R densel ben Attributwert enthalten fungiert dieser als eindeutiger Typbezeichner des Schemas selbst etwa als Index von R in der Library Z 4 7 Analog zu XML Dateien die ihr Schema referenzieren Mic08d m ssen jedoch auch alle Datenobjekte einer Library ihr Objekt Schema eindeutig refe renzieren weshalb der Typbezeichner als Attribut 7 in R modelliert wurde Dadurch wird eine Lib rary inh rent typsicher so dass Klassifizierungs Module gt Kap 2 3 1 die den Dateityp anhand einer Heuristik ermitteln Sho93 berfl ssig werden Da auch der Dateiname bzw seine Endung nicht mehr f r die Codierung des Dateiformats ben tigt wird kann eine Datei problemlos beliebig umbenannt werden 4 4 4 Terminologie Eine weitere Konsequenz die sich aus den quivalenten Datenmodellen ergibt ist eine vereinheit lichte Terminologie f r Speichersysteme Die Tabelle in gt Abb 4 4 5 stellt zeilenweise die quiva lenten Begriffe von relationalen Datenbanken Libraries und Dateisystemen dar und vergleicht die se zus tzlich mit der propriet ren Nomenklatur von Microsoft WinFS gt Kap 2 9 Datenbanken Libraries Dateisysteme MS WinFS gt Kap 2 9 BLOB Dateik rper Tupel Datenobjekt Datei Item Schema Schema Dateiformat typ S
45. 0 Dateien in Tausend Ohne Index Indexiert Abb 3 3 14 Ausf hrungszeiten f r XML bulk loading 3 4 Fazit In diesem Kapitel wurden mehrere Ans tze zur Indexierung vorgestellt Leider haben alle betrachte ten Verfahren gravierende Nachteile die einem Einsatz zur Indexierung von Metadaten innerhalb eines Dateisystems entgegenstehen Mit der Lucene Bibliothek gt Kap 3 1 steht Anwendungsprogrammen eine generische Bibliothek zur Indexierung mit invertierten Listen zur Verf gung die unter anderem von einigen Desktop Suchmaschinen gt Kap 2 10 eingesetzt wird Luc07 Da an einem Dateisystem h ufig nderun gen vorgenommen werden z B bei jedem Speichern einer Datei muss ein Index nicht nur schnel le Suchergebnisse liefern sondern sich auch mit geringem Aufwand aktualisieren lassen Lucene leistet dies nicht aufgrund der invertierten Listen sind Aktualisierungen sogar sehr aufw ndig da zus tzlich zu den eigentlichen Informationen in den Felddaten Dateiendung fdt f r jeden Attri butwert Eintr ge im Feldindex Dateiendung fdx zu modifizieren sind gt Abb 3 1 3 Die bei Suchanfragen ber Dateien h ufig auftretenden Partial Match Operationen gt Kap 3 3 2 werden effizient von einem Wald aus B oder B B umen unterst tzt wie sie von BeFS gt Kap 2 7 eingesetzt werden Leider tritt hier bei Aktualisierungen dasselbe Problem wie oben beschrieben auf bei jeder nderung an einer Datei muss e
46. 7 BladeFTP CY WordPad G CDex Abb 7 1 1 Start Menu von Windows 98 Ausschnitt Leider wird die Menuhierarchie bei sehr vielen installierten Programmen schnell un bersichtlich und schwer handhabbar Zudem ist das Layout eines solchen Menus starr wie in gt Abb 7 1 1 zu 96 7 Interaktion sehen ist steht f r jeden Menupunkt nur ein kleines Symbol und eine Zeile Text zur Verf gung Das Layout ist f r alle Optionen identisch so dass besonders wichtige oder h ufig benutzte Menupunkte nicht hervorgehoben werden k nnen Diese Unzul nglichkeit und der gleichzeitge Wunsch vieler Benutzer Informationen oder Alarme wie neu eingetroffene EMails st ndig im Blickfeld zu haben hat zur Beliebtheit von Widgets bei getragen Dabei handelt es sich um kleine Programme die ohne die Kontrollelemente eines Fensters direkt auf dem Desktop dargestellt werden und diverse Aufgaben etwa die Anzeige der Uhrzeit der CPU Auslastung oder auch von Aktien Kursen bernehmen Pagelof2 os Album Art Battery Informa Blockade feed the cat Contacts CPU Meter Currency E BE 2 Dems in power as Co Picture Puzzle Postage Costs Slide Show Stocks Busta Rhymes arrest Thai authorities deny Get more gadgets online 2 kids stabbed to de Abb 7 1 2 Widgets in Windows Vista 7 1 1 2 Datei Manager Die zweite wichtige Komponente moderner Shells dient der Organisation des Dateisystems Der Datei Manager des Explor
47. 9 Einf Informatik 1 S3 2008 FOR Schleifen University of Applied Sciences and Arts Abb 7 7 11 Aufgabe mit Tabelle und Liste 8 Zusammenfassung und Ausblick 8 Zusammenfassung und Ausblick Zum Abschluss dieser Arbeit werden in diesem Kapitel die eingef hrten Technologien und Verfah rensweisen zusammengefasst und bewertet gt Kap 8 1 Dar ber hinaus wird der Einsatz in bereits existierenden Systemen diskutiert gt Kap 8 2 und es werden m gliche Weiterentwicklungen be schrieben gt Kap 8 3 Zuletzt wird mit surface computing ein Ausblick auf eine neue Art von Computersystemen gegeben die vom Einsatz der vorgestellten Resultate profitieren kann gt Kap 8 4 8 1 Zusammenfassung Im Rahmen einer Bestandsaufnahme wurden unterschiedliche Erg nzungen traditioneller Dateisys teme untersucht von einfachen Plug Ins gt Kap 2 6 ber Desktop Suchmaschinen gt Kap 2 10 bis hin zu komplexen Weiterentwicklungen gt Kap 2 7 Einige L sungen betten Dateien und ihre Applikationen dabei in eine objektorientierte Gesamtarchitektur ein Insbesondere die heute verbrei teten Desktop Suchmaschinen ver ndern jedoch nicht die Organisation des Dateisystems sondern erm glichen lediglich eine Suche nach Dateien ber Verzeichnisgrenzen hinweg Index Methoden gt Kap 3 die entweder als Wortindex das Herkunftsattribut nicht speichern oder aber eine unzu reichende Performanz haben vermindern die Leistungs
48. Attributen wenigen spezifizierten Attributen Nachbarschaft Alle Objekte die h chstens eine Entfernung e vom spezi fizierten Punkt haben Abb 3 3 1 Klassifizierung von multidimensionalen Operationen In der folgenden Abbildung werden existierende Indexstrukturen f r multi und hochdimensionale Datenr ume nach zwei wichtigen Kriterien klassifiziert n mlich der Eignung f r bestimmte Opera tionen aus gt Abb 3 3 1 und dem Typ der Suche Baum oder sequenzieller Scan 43 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Partial Match Operationen Partial Match Operationen effizient unterst tzt nicht effizient m glich Baum d B B Baume A Baum iDistance kd kdB Baum R R R Baum SS Baum X Baum Sequenzieller Scan Gridfiles Hashing Seq VA Datei d Anzahl der Dimensionen des Datenraums Abb 3 3 2 Klassifizierung von multidimensionalen Indexstrukturen Sak00 In Saa05 werden einige Techniken zur multi bzw hochdimensionalen Indexierung vorgestellt darunter auch das multidimensionale Hashen kd bzw kdB B ume Ben75 sowie R B ume Gut84 Insbesondere auf kd und R B umen basieren viele Derivate u a R Sel87 R Bec90 X Ber96 SS Whi96 und A B ume Sak00 3 3 1 Der Fluch der Dimensionen Die meisten der oben erw hnten Datenstrukturen zeigen bei hohen Dimensionszahlen d gt 10 gra vierende Geschwindigkeitsverluste Das gilt insbesondere f r Index
49. Bearbeiten Ansicht Lesezeichen Widgets Feeds Extras Hilfe CG N N A 3 hitp tisiennar 29 E Kacheln Liste Gro e Symbole EF Kleine Symbole Alle Dateien Favoriten Multimedia Audio Dateien Weitere Dateien aca st Sienna deskwork de Powered by r AMD Duron tm Processor 850 MHz Me AM 384 MB a t ROOT Version 9 0 Build 20102007 4 Abb 7 7 4 Nach Dateitypen gegliedertes Hauptverzeichnis Bei Bildern werden zun chst alle Dateien vom Typ dtDiashow gt Kap 6 2 1 pr sentiert da diese mehrere Bilder zusammenfassen und daher von besonderer Bedeutung sind Darunter k nnen alle Einzelbilder nach verschiedenen Attributen gruppiert gt Kap 7 4 abgerufen werden 119 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Sienna BILDER Opera Datei Bearbeiten Ansicht Lesezeichen Widgets Feeds Extras Hilfe z x 9 A 3 rttp sienna BILDER amp DISPLAY 4 Gro e Symbole E Kacheln iste Zur ck Diashows a 24 Geburtstag d Bowlen W David in Frankfurt Fees 24 Geburtstag W Jindras 25 Geburtstag W Saalbach 2004 d i Teamer Fahrt 2002 d 28 Geburtstag d Bramsche 2002 W Dissertation Vortrag 1 W Fees 25 Geburtstag a Ausflug nach Dusseldorf de Darias Abschied W Dissertation Vortrag 3 d i Abschlussvortrag Diplom v i Bramsche 2003 d Dissertation Vortrag 2 W Fees 27 Geburtstag W Korfu d Skifahrt 2003 i Umzug Fee W
50. Bildes also nur ein Symbol innerhalb des Word Dokuments erscheinen Das Paket wird also hnlich dargestellt wie eine an eine EMail angeh ngte Datei 2 5 Microsoft Indexerstellung 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 DIE Datei Bearbeiten Ansicht Wechseln zu Favoriten u ul Balalxsle Drucker Energieverwaltung Hardware Indexerstellung v 24 Objektfe Ej Arbeitsplatz Z Abb 2 5 1 Indexerstellung in der Systemsteuerung 2 Existierende L sungen Der erstellte Index wird von den Office Programmen Word Excel PowerPoint usw benutzt um beim ffnen von Dateien eine inhaltsbezogene Suche anzubieten Weitere Suche Suche Dateien die diesen Kriterien entsprechen Dateityp ist Alle Dateien Text oder Eigenschaft enh lt das Wort Memorysticks RB L schen Neue Suche Tl gro Kleinschreibung beachten Weitere Kriterien bestimmen Zur Liste hinzuf gen Und Eigenschaft Bedingung Wert Oder Dateiname D Jenthatt gt Suchen in fen z T Unterordner durchsuchen Abbrechen Suche speichern Suche ffnen Abb 2 5 2 Inhaltsbezogene Suche in Microsoft Word 97
51. Datei gel scht muss das entsprechende Tupel aus dem Master Index und dem betroffe nen Slave Index entfernt werden Das L schen von Tupeln ist potenziell gef hrlich bei naiver Im plementierung Kann die Sortierung zerst rt werden wie im folgenden Abschnitt demonstriert wird 5 1 5 1 L schen von Dateien naiv Aufgrund der uniformen Tupelgr e in den jeweiligen Indextabellen ist es naheliegend das L schen eines Tupels durch berschreiben mit dem letzten Tupel und Verk rzen der Datei zu imple gt EENEN Abb 5 1 6 L schen eines Tupels durch berschreiben mit dem letzten Tupel mentieren Das in diesem Abschnitt verwendete Beispiel liefert einen Fall bei dem die Sortierung dadurch zer st rt werden w rde Angenommen die MP3 Datei mit dem Schl ssel JK83ZZA_ soll gel scht wer den 74 Master Index Filekey Typ HEES Bild IA MPS LL9 ACX1 Bild GUIP7 D MP3 30_KUIXY Bild 5 Indexierung er a MP3 Index Filekey IT JGUIP7SD_ Bilder Index Filekey Z6_HG7E LL9 ACX1 30_KUIXY E zu l schende Eintr ge Abb 5 1 7 Vor dem L schen Die nachfolgende Abbildung zeigt dieselben Relationen nach dem L schen der Datei die betroffe nen Eintr ge wurden absichtlich durch das jeweils letzte Tupel der Heap Dateien berschrieben Master Index Filekey Typ 76 Ho7es Bild 30 KUY Bild LEH ACKT Bild Jsur
52. Durch die hohe Performanz und Skalierbarkeit kann Lucene f r beliebige Projektgr en und Anforderungen eingesetzt werden Wik06 darunter auch die Desktop Suchmaschinen Aduna AutoFocus Beagle Strigi und xfriend gt Kap 2 10 Luc07 3 1 1 Compound File System Lucene speichert den Index im sog Compound File System ab was im bertragenen Sinn ein begrenztes Gel nde meint Dieses Gel nde besteht aus den Dateien deletable SEGMENTS und dem eigentlichen Index mit der Endung CFS amp Index Datei Bearbeiten Ansicht Wechseln zu Favoriten e o Dan xEE Dateiname Gopcl Typ Ge ndertam BE 1462KB DateiCFS 26 06 06 04 36 a deletable IKB Datei 26 06 06 04 36 a SEGMENTS IKB Datei 26 06 06 04 36 4 Objekt e markiert D Arbeitsplatz Abb 3 1 1 Von xfriend angelegter Lucene Index 37 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Die CFS Datei enth lt eine Sammlung verschiedener Einzeldateien die unkomprimiert vorliegen Der Header enth lt eine Aufstellung aller enthaltenen Unterdateien mit Anzahl Offset und Name Gr n hervorgehoben Anzahl der Dateien im Compound File System Orange hervorgehoben Dateioffset als int64 Gelb hervorgehoben L ngenbyte vor Strings Rot hervorgehoben Dateinamen Abb 3 1 2 Dateiheader eines Compound File System von Aduna Autofocus gt Kap 2 10 Die im Compound File System enthaltenen Einzeldateien erf llen folgend
53. EE ege eege Eegen 71 34 3 EE use een 74 314 te kk ee er a E eee eect 74 Se 910a PRATA eelere eener RER 74 5 1 6 eege ee 76 3 2 PO Wannen 78 D GR Seeleute 79 3 2 2 Verifizierung aka asian 80 Inhaltsverzeichnis 6 Referenz Lihravv anne SI 6 1 e het eegen EE Ee EE Eege EE e 81 0 4 1 EE 82 6 1 2 Applikationen asus ee 83 0 13 RER E 85 6 2 Implementieruns ek ns 85 6 2 1 Namensraum cccannnnnenneennnennssnnnsnnnsnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnsnnnnnnnnnnnsnnnsnnnnnnnsnnnnennnnnn 85 6 2 2 Aelektton A 87 ES We egen E KE 89 6 3 e E 89 Le NEE 89 03 3 EE ee E ee 90 6 3 4 Moasteri loue Juder niia AEAEE ANAE EAA AAA AA AEEA ARAD 90 6 3 5 Komprimierter Mastenslave Inder 91 E DR ee en se aachen sebeduessabsiddesetecdadeensbidssedecdesscbsstassatecdslee Sea 92 6 4 1 Architektur c c cic ccccceeccneccneccnsccnsccnsccnsccnsccasccnsecusecsecasecasecasecasecusecasecuseesecuseeuseeues 92 O42 Implemenherung ue desse des dese ed dee dee 94 7 Amber akti Omics cccdiccscocssctesescesssssccascesesdeosssocesscoseuces eseccesdesea denen oscestessecoadesoscesesdsoccesesessessessecocsesede 95 SEH Delles Eegen 96 7 1 1 Moderne Shelly coscire aAA Aa 96 7 1 2 Anforderungen an eine Shell 98 K E EE 98 AET A 102 ER ee Vo in Sin u ONS EE 104 7 3 Benutzerdefimierte Filter u onenean a e ea a a aa 106 Peed Shell nietr E 106 VID EE 107 7 4 Automatische Ordner 107 Ee E EE 109 TIED EE 109 TS gt
54. EEIIIAA AAAAAAAAAAAASA S EREQOQUUYOU EAAOOOUUYOUOSO AANNAN gegen Fol OOM pee ae AIOUNN 10 ae AAAA S EE ee EE DEE See EEN SE Ee AAAAAAAAA A DBEER IIL 1 DDEEEIIII I AAAAAA AAAAAAA 6 6066 BBUUUYY 0S0000 B UUUYY ne eemeuienn lt aGesanyseeecaee Sosakecavececedss Abb 2 1 9 Wesentlicher Inhalt von MAGELLAN SYM 2 Existierende L sungen Das Layout der Tabellen orientiert sich am Standard Zeichensatz mit 256 Zeichen 8 Bit angeord net als 16x16 Matrix Die Tabelle SEPARATORS definiert f r jedes Zeichen welche Bedeutung es f r die Aufteilung der Daten in einzelne Begriffe besitzen soll Effekt auf die Indexierung Das Zeichen trennt ein Wort und wird als alleinstehendes Symbol indexiert Das Zeichen ist Teil eines Wortes 0 Das Zeichen ist Teil einer Zahl und wird als Nummer indexiert Das Zeichen trennt ein Wort wird aber nicht indexiert Abb 2 1 10 Wertebereich der SEPERATORS Tabelle Die CASE 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 SORT 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 2 2 SFS und MetaFS Unix Betriebssysteme k
55. FilePassword Filel ATA IMGL IMGH ID3Artist conn cmd ExecuteNonQuery cmd new SqlCommand CREATE NONCLUSTERED INDEX vid ON Test VIDL VIDH VIDVideoDecoder VIDAudioDecoder VIDCreationYear VIDCreationMonth VIDCreationDay VIDCompressedHeader VIDMultiStreams VIDArtist VIDComment VIDThema VIDVideoTitel VIDFirmware conn cmd ExecuteNonQuery cmd new SqlCommand CREATE NONCLUSTERED INDEX id3 ON Test ID3Artist D3Trackname ID3AlbumName ID3Comment D3Year D3Genre conn cmd ExecuteNonQuery cmd new SqlCommand CREATE NONCLUSTERED INDEX img ON Test IMGL IMGH IMGFarbmodus IMGCreationTime IMGCreationYear IMGCreationMonth IMGCreationDay IMGEquipment IMGBelichtung IMGFirmware IMGTitel IMGCopyright IMGArtist IMGComment IMGFocus IMGBlende conn cmd ExecuteNonQuery cmd new SqlCommand CREATE NONCLUSTERED INDEX aud ON Test e EE E CONN cmd ExecuteNonQuery 140 C Testprogramm Microsoft SQL Server 2005 cmd new SqlCommand CREATE NONCLUSTERED INDEX Ist ON Test LSTAnz1 LSTAnz2 LSTAnz3 LSTAnz4 LSTOptionen LSTCreationTime LSTCreationYear _LSTCreationMonth LSTCreationDay conn cmd ExecuteNonQuery StopWatch sw new StopWatch Metadaten laden sw Reset SQLXMLBulkLoad3Class objXBL new SQLXMLBulkLoad3Class objXBL ConnectionString Provider sqloledb server CARMIN SQLEXPRESS database Metadata integ
56. Generic Text 950 of 4063 files have been indexed Oz 20 407 607 807 Approximate time remaining 35 minute s Press Ctrl Break to stop the indexing Abb 2 1 7 Indexierung Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 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 Explore All files Concerning procedure gt 98 SYSTEM PAS 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 2 1 2 Steuerung der Indexierung Lotus Magellan setzt einen Volltext Index ein der vom Benutzer konfiguriert und an unterschiedli che Sprachen angepasst werden kann Die Konfigurationsdatei MAGELLAN SYM enth lt drei Tabel len SEPARATORS CASE und SORT welche die Indexierung wesentlich beeinflussen SEPARATORS CASE SORT ENER UOUGOG00UR ee Kain Eee AAAAAAAAAAAAAAA ABCDEFGHIUKLMNO www ee ee eee eee eee AAAAAAAAAAA A PORSTUVWXY 2s 0 s 2 eeae e awe ees AAAAAAAAAAAAAAA ABCDEFGHIJKLMNO ABCDEFGHIJKLMNO AAAAAAAAAAA PORSTUVWXYZ PORSTUVWXYZ UEAAAACERETTTAA CUEAAAACE
57. GetTypeFamilyld Links E GetTypeld Guid System Storage Audio de System Storage Calendar E W W C C Abb 2 9 4 WinFS Klasse System Storage GenericFile 28 2 Existierende L sungen Diese objektorientierte Typhierarchie erscheint als konsequente Weiterentwicklung von Rufus gt Kap 2 3 und vor allem Microsoft OLE gt Kap 2 4 Die Eigenschaften eines WinFS Items umfassen auch vielseitige Metadaten wie das Beispiel einer Videoaufzeichnung zeigt 2WinFS Type Browser M ATHLONG4 5 DefaultStore 4 0 Microsoft WinFS Bindings 30 System Storage 48 System Storage Audio Be System Storage Calendar BC System Storage Contacts System Storage Core G System Storage Documents System Storage mage System Storage Media i System Storage Messages System Storage Query i System Storage Rules System Storage Sync 3 System Storage Video a LC Inline Types 2 43 Items d VideoClip fa VideoRecord CC Links E gt Entity VideoRecord gt Document RecordedT gt VideoRecord Methods amp f Properties ET AudioQuality String Ef ChannelNumber Nullable lt Int32 gt ER ClosedCaptioning Nullable lt Boolean gt T Credits String ET EncodingToolName String EP EncodingT oolVersion String EP EpisodeTitle String ER IsFinale Nullable lt Boolean gt F IsLive Nullable lt Boolean gt EP IsPremiere Nullable lt Boolean gt ER IsSubtitled Nullable
58. Integration Indexierung und Interaktion hochdimensionaler Datenobjekte gt Kap 3 3 4 Als X seien die n Attribute bezeichnet die in allen k Objekt Schemata vertreten sind Y seien die brigen m Attribute aus Rj F r den Objektraum L gilt dann gt Kap 3 3 4 k common L NR j l k X common L QL Jdom X x xdom X xdom Y X x dom m j l 4 9 f Y R common L Die Attribute F und T sind damit immer Elemente von common L Eine Instanz l eines Library Schemas L ist nun eine Menge von Datenobjekten und eine Teilmenge von L KL 10 0 un ob 4 10 Jedes Datenobjekt o eines Objekt Schemas R L kann zum Element oa des globalen Datenraums Q L werden indem die Werte der im zugeh rigen Objekt Schema R nicht vorhandenen Attribute durch Nullmarken besetzt werden Verwendung von gt nach Zan82 oe Q R A Re L gt do e DL 0 20 4 11 Innerhalb einer Library L m ssen sich zwei beliebige Datenobjekte o und o aus Z die nicht identisch sind zumindest in ihren Attributwerten lt f t unterscheiden wodurch diese Attribute einen global g ltigen Superschl ssel bilden Vo 0 0 E L 0 E I L 0 0 gt Tp 7 0 Hp 7 Oy 4 12 Auf dem Library Modell k nnen alle Operationen der Relationen Algebra durchgef hrt werden so fern keine der oben dargestellten Vorschriften insbesondere 4 5 4 6 und 4 12 verletzt werden 4 2 Relationale Datenbanken
59. Kameras oder mit entsprechenden Zusatzger ten wer den die Koordinaten direkt im aufgenommenen Bild gespeichert und k nnen sp ter ausgewertet werden etwa durch Darstellung auf einer Weltkarte Diese Art des Geotaggings ist jedoch nur f r Bilddateien verf gbar und das Abspeichern der Aufnahmeposition ist nur mit hochwertigen Kame ras oder Zusatzger ten m glich Gro07 Dar ber hinaus ist die Suche nach Fotos anhand von L n gen und Breitenangaben unbefriedigend Dasselbe gilt f r Ortsnamen da diese sprachabh ngig und nicht eindeutig sind z B M nchen und Munich bzw mehrere Orte Neustadt Daher wird hier f r das Geotagging die Verwendung von IATA Flughafencodes IAT07 die Flug g sten von ihren Gep ckanh ngern engl baggage tag vertraut sind D U D DUSSELDURF HO osocrt E jr Abb 7 5 2 Gep ckanh nger mit IATA Codes Schon 1948 haben sich die in der IATA IAT07 zusammengeschlossenen gro en Fluggesellschaf ten darauf verst ndigt die flugrelevanten Abl ufe des Gesch fts zu standardisieren So kam es zum 3 Letter Code System Darin sind beispielsweise in der ersten Kategorie weltweit alle von Flugge sellschaften angeflogenen Flugh fen mit einer 3 Buchstabenkennung enthalten Versucht wurde die jeweiligen Kennungen so zu kreieren dass sie m glichst phonetisch an den dazugeh rigen Ort erin nern und der erste Buchstabe des Codes mit dem vollst ndigen Ortsnamen bereinstimmt FRA steht f
60. Layouts A Schriftarten 22 Spiele Highscores fal Texturen Wissenschaft R Fraktale Attraktoren oY Fraktale B ume A Fraktale Mengen 22 Gravitat ions S imulat ionen Chemische Molek le B Vokabeln Neue Dateien erstellen Dateien suchen gespeicherte Suchen Date isystien Statistik Vorhandene Dateien zeigen und ndern Neue Datei erstellen Dateien Goen gespeicherte Suchen CD Player G H Audin CD auslesen D DUD brennen aus gespeicherter Sitzung iamond Rio PMP an LPT1 intern SmartMedia Nullmoden Kabel an LPT2 Meister Sklave IF Verf gbarer Platz 59 160 920 064 Byte amp Dateien von DOS importieren Diskette 3 A formatieren Archiv einlesen Diskette 5 B formatieren Archiv einlesen 0 Adresse G Diashou fiir Bilder DI EMail lesen oder schreiben er be Ria SMS lesen oder schreiben Landschaft N f Lied i Metronom Kl ngdatei De Playlist fiir Audio Dateien A Si ibai Netzuerk Wissenschaftliche Anwendungen 2e sohre ban Pausenanimation Energiespar Modus Ternin Fx3D Demo Inferno L D Vu Seite 1S09668 Rescue Metronon Vorhandene Dateien ze igen ndern Dateien von DUS importieren Abb 7 1 14 Zirkul re Verweise auf andere Menuseiten 7 2 Join Operationen Eine Beispiel f r Suchfilter die programmgesteuert erzeugt werden sind Join Operationen Das Datenmodell einer Library gt Kap 4 1 bietet eine inh rente Unterst tzung f r Joins ber beliebige Attribute
61. OT gt C 2 METADATA XSD Das folgende Schema wird verwendet um die Metadaten aus der Data METADATA XML gt C mit SQLXML in die Datenbank zu importieren lt xml version 1 0 gt lt Schema xmlns urn schemas microsoft com xml data xmins dt urn schemas microsoft com xml datatypes xmins sql urn schemas microsoft com xml sql gt lt ElementType name FileTyp dt type int gt lt ElementType name FileBez dt type string gt lt ElementType name FileKey dt type string gt lt ElementType name FileSize dt type int gt lt ElementType name FileTime dt type string gt lt ElementType name FileNew dt type int gt lt ElementType name FilePassword dt type string gt lt ElementType name FilelATA dt type int gt lt ElementType name ROOT sql is constant 1 gt lt element type File gt lt ElementType gt lt ElementType name File sql relation Test gt lt element type FileTyp sql field FileTyp gt lt element type FileBez sql field FileBez gt lt element type FileKey sql field FileKey gt lt element type FileSize sql field FileSize gt lt element type FileTime sql field FileTime gt lt element type FileNew sql field FileNew gt lt element type FilePassword sql field FilePassword gt lt element type FilelATA sql field FilelATA gt lt ElementType gt lt Schema gt C 3 PROGRAM CS Die Datei PROGRAM CS ent
62. Rom Italien SZG Salzburg sterreich S Airbus A320 Enhanced TH City square Dynasmische Skins Maus WF Softwaretechnik M Yorp DPS Denpasar Bali Indonesien FLU New York Flushing USA LON London Gro britannien NYC New York USA SAY Siena Italien UWP Wuppertal Deutschland Anja Dissertation Vortrag 1 Keith Haring Sabine TH Sophia 3 Abb 7 7 6 BILDER IATA DTM Dortmund Deutschland FRA Frankfurt Deutschland MIL Mailand Italien PEG Perugia Italien Li SFO San Francisco Internati gt ZNB Hamm Deutschland Atoll Dissertation Vortrag 2 Logo TW Sandra S Starcraft II Powered by a Version 9 0 Build 20102007 7 Interaktion y Sienna AUDIO PUBDATE Opera Datei Bearbeiten Ansicht Lesezeichen Widgets Feeds Extras Hilfe v N P A d 3 http sienna AUDIOPUBDATE SDISPLAY 4 E Kacheln SS Liste E Gro e Symbole EE Kleine Symbole amp Zur ck Audio Dateien 2007 1 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996 1995 1994 1993 1992 1991 1990 1989 1937 1985 RED 1983 1982 1981 1980 1979 1977 1976 1974 1973 1969 1965 Ohne Angabe 19 2000 21st century digital boy amp Age of aquarius All need All or nothing All that she wants All the things I ve seen Anyplace anywhere anytime Bai
63. Schema enth lt ein ausge zeichnetes Attribut F mit Prim rschl sselfunktion 4 5 sowie ein Attribut T das den Typ aller Da tenobjekte eindeutig codiert 4 6 Zus tzlich enthalten sind d weitere Attribute A Ag mit d gt 0 R F T A A d gt 0 4 1 Ein Objekt Schema R erzeugt einen Datenraum Q der aus dem kartesischen Produkt der Wertebe reiche dom X R aller Attribute X von R besteht Q R dom R F x dom R T x dom R A x xdom R A 4 2 Ein Datenobjekt o wird als geordnetes Tupel von Attributwerten definiert das einem vorher defi nierten Schema R gen gt und daher in Q R enthalten ist oe Q R Oz ES fe dom R F Ate dom RT Aa dom R A A f t Nullmarke 4 3 58 4 Integration Datenobjekte sind oft hochdimensional da die Anzahl der Attribute eines Objekt Schemas in der Praxis sehr gro werden kann mehr als 50 Attribute sind durch g ngige Standards f r Metadaten leicht erreichbar EXI07 Nil05 Indexstrukturen gt Kap 3 gt Kap 6 werden bereits ab 10 At tributen als hochdimensional bezeichnet Web98 Eine Instanz r eines Schemas R ist eine Menge jedoch keine Multi Menge von Datenobjekten und damit eine Teilmenge von OR r R 01 0n E OUR 4 4 Innerhalb einer Instanz r R muss die Prim rschl sseleigenschaft von F hergestellt werden das hei t zwei beliebige nicht identische Datenobjekte o und o2 aus r R m ssen sich zumindest in ih ren Attributwerten f unterscheiden
64. Seinant sches Tagen serie 110 FOE EE 111 221 2 Bewertung von Dateien ee 113 E E On EE 115 716 A fsab n rientier ng een ee 115 7 0 1 tee deer ee ee ee een rer ee ee 117 Tl WEDSEL EE 117 7 7 1 Fancy fancy EE 119 EE TEE 121 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 8 Zusammenfassung und Ausblick ccccsssssssssssssscccsssssssssssssscccssssssssssssssccssssssssssssssesscees 123 Sl ZUSAnmenTassung zn enge 123 82 Integration In existierende Systeme ee 124 8 2 1 M ster Blave Inder 124 8 2 2 Erweiterung f r Dateisysteme u n aanscensinienennnnnennennnnennenn nenne nenne nennen en 124 E 125 8 3 Weiterentwicklungen ee esse 126 8 3 1 Masterislaveindex nne nn 126 EE 127 8 3 3 AllOMansehes EEN 127 8 3 4 Verbesserte Visualisierung u usa 128 S4 Aw nein 129 Anhang A GUOSS AP REEL ER cececacnesbacssdendadkuacecdusnacecduucscataxavevees 131 B Testprogramm zur Seek Geschwindigkeit scccccsssssssssssssscccssssssssssssscccccssssssssssscsssees 133 Bl EE NEE 133 e Areal 135 C Testprogramm Microsoft SQL Server 2005 ccssssssssssccccsssssssssssscccsccsssssssssssecssssssssees 137 C 1 MEIADATAXML see 137 C2 METADATA een 138 E PROGRAM e 138 D Testprogramin PostereSOL amp osccisecesccaceoasacasavececcaucncscazevarecankessacanevacncansuncavanevesecereeacseansoesents 143 D PROGRAM CS un 143 LEE E 147 Begriffe aus dem Glossar sind bei der ersten Verwendung kursi
65. Sektoren ab Sektor LBA an die durch Buf spezifi zierte Adresse zu laden Die entsprechende Funktion 42h arbeitet direkt mit LBA Adressen function Read Anz Byte LBA Longint Buf Pointer Boolean type ExtType record Size Anz Word P Pointer Adr Dummy Longlnt end var R Registers Ext ExtType Cyl Head Sec Word begin FillChar Ext SizeOf Ext 0 Ext Size 10 Ext Anz Anz Ext P Buf Ext Adr LBA R AH 42 R DL 80 R DS Seg Ext R SI Ofs Ext Intr 13 R ee and fCarry 0 eng 133 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Die Zeitmessung erfolgt durch Einklinken in den Zeit Interrupt IRQ 0 Interrupt 08h Dieser IRQ wird genau Seege also etwa 18 2 Mal pro Sekunde aufgerufen Tis94 var Oldint8 Pointer Clock LongInt procedure NewiInt8 assembler Asm PUSH AX PUSH DS MOV AX SEG DATA MOV DS AX INC DWORD PTR DS Clock PUSHF CALL DWORD PTR Oldint8 POP DS POP AX IRET end const MaxLBA 0 Gr e der Festplatte abz glich 2048 Sektoren hier eintragen var P Pointer Start LBA LongInt Durchlauf Chunk Word begin GetMem P 32768 GetIntVec 08 0ldInt8 SetIntVec 08 NewiInt8 Sequenziell Clock 0 for Durchlauf 1 to 10 do begin write 13 Sequenziell Durchlauf LBA Random MaxLBA for Chunk 1 to 32 do begin Read 64 LBA P Inc DA AAL end end writeln 13 Sequenziell Clock Ticks zu je 1 18 2s
66. US FRA 31 Lufthansa FRA DUS Lufthansa CityLine MUC DUS Air Berlin TXL CGN British Airways SFO MUC HEL FRA Muster CGN TXL Boeing 737 ZRH BOS Airbus A320 YYZ FRA Airbus A340 YVR YZ Canadair Regional Jet H K rzester Flu e e e NN N N G A ND Entfernung Operator ORD DUS Lufthansa American Airlines Aner ican Airlines Lufthansa Lufthansa Virgin America Southwest United Airlines Lufthansa Lufthansa Air France Air France Lufthansa Regional Lufthansa Lufthansa JetBlue Suiss Suiss Lufthansa Lufthansa Air Canada Abb 6 4 2 Darstellung eines Flugplans als Poster Zur Berechnung einer Bilddatei muss die Flugplan Applikation zun chst ein Hintergrundbild laden das in der Referenz Implementierung als Systemdatei vom Typ dtDigiFoto gt Kap 6 2 1 verf g bar ist Diesem Dateiformat ist die Applikation DatBild zugeordnet Diese Klasse enth lt u a die f fentlichen Methoden Scale Convert Save und GetBuffer zum Skalieren Konvertieren und Spei chern der Datei sowie zum Manipulieren der Bildinformationen Bei traditioneller Programmierung m sste die Flugplan Applikation das Hintergrundbild selbst ein lesen die Flugwege ber das Bild kopieren die entstandene Weltkarte mit eigenem Programmcode auf die vom Benutzer gew nschte Aufl sung skalieren und danach in einem bestimmten Format 93 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte z B wieder als JPEG Datei abspeichern Unter
67. a Jdom X x xdom X xdom Y e e dom 3 4 j l 50 3 Existierende Indexe 3 3 5 Performanz In den vorhergehenden Abschnitten wurde dargelegt welche theoretischen Schwierigkeiten beim Einsatz klassischer multidimensionaler Indexe zum Speichern von hochdimensionalen Dateiattribu ten zu erwarten sind 1 Degenerieren von Datenstrukturen die den Daten oder Objektraum partitionieren bei vielen Dimensionen Fluch der Dimensionen gt Kap 3 3 1 2 Keine Unterst tzung von Partial Match Operationen die gerade im Zusammenhang mit Dateiat tributen besonders h ufig vorkommen gt Kap 3 3 2 3 Ineffizienz von persistent gespeicherten B umen gt Kap 3 3 3 4 Keine Ausnutzung des partiell belegten Datenraums gt Kap 3 3 4 Um zu zeigen dass diese theoretischen berlegungen auch Auswirkungen in der Praxis haben wurde die Leistung derartiger Indexstrukturen anhand von zwei relationalen DBMS getestet dem Microsoft SQL Server 2005 gt Kap 3 3 5 1 und dem quelloffenen DBMS PostgreSQL gt Kap 3 3 5 2 Das Testsystem war mit einer AMD Athlon 64 X2 3800 dual core CPU 2000 MHz 2 GB DDR2 dual channel RAM 200 MHz Bustakt und einer 320 GB SATA Festplatte aus gestattet die als NTFS Dateisystem formatiert wurde Auf diesem System wurden die Bearbei tungszeiten von f nf Suchanfragen ermittelt die auf einem genau definierten Datenbestand mit 62 Dimensionen ausgef hrt wurden 1 Der erste Testfall sucht all
68. a auf die eigentlichen Daten nur vierfach indirekt zugegriffen werden kann impliziert dieser Vorgang einen erheblichen Zeit aufwand Erg nzend kommt hinzu dass die meisten Attribute nur wenige Byte gro sind die Archi tektur mit zus tzlichen I Nodes also sehr viel Speicherplatz verschwendet Gia99 Da ein I Node nur etwas mehr als 200 Byte belegt bleiben bei der minimalen Clustergr e von 1024 Byte 2 Sektoren knapp 800 Byte im I Node ungenutzt Daher wurde die Architektur so ab ge ndert dass kleine Attribute direkt innerhalb des I Nodes gespeichert werden Ein Attribut Verzeichnis wird nur bei gr eren Attributen ben tigt zum Beispiel f r das To Feld einer EMail mit vielen Empf ngern Gia99 3 2 1 Indexierung BeOS legt f r viele Attribute direkt im Dateisystem einen Index an um eine schnelle Suche zu un terst tzen Jeder Index verwaltet seine Eintr ge in einem B Baum so dass der Index als unsichtba res Verzeichnis auf der Festplatte abgelegt und der entsprechende Programmcode wieder verwendet werden kann Gia99 Das Dateisystem unterstiitzt Indexe fiir die Datentypen String bis 255 Zeichen Int 32 und 64 Bit Float und Double als Schl ssel Das Anlegen eines Index bzgl eines bestimmten Attributs wird ber eine API Funktion von einer Applikation veranlasst Das Dateisystem indexiert zudem von sich aus Dateiname gr e und das Datum der letzten nderung einer jeden Datei Gia99 3 2 2 Performanz Di
69. ach 1152 beispiels weise um Bilder mit einer bestimmten Mindestaufl sung zu finden 1152 Ergebnisse von Google Desktop Search Microsoft Internet Explorer iol x Datei Bearbeiten Ansicht Favoriten Extras Q zu ck SEI x B A Acesse E http localhost 4664 search amp s s28hJI8RmbkliyLoMdaodw 1Z5 1 q 11528ie UTF 8 Web Bilder Groups Yerzeichnis News Desktop Google hei Desktop Suche EattepEin tellungen Elemente entfernen Desktop Desktop Alle 0 E Mails 2 Dateien 0 Webprotokolle 0 Chats 1 2 von 2 0 045 Nach Relevanz sortieren Nach Datum sortiert H 276 BMP 768 x 1152 Pixel 2 5MB 276 C Eigene Dateien 276 BMP Ordner ffnen 21 06 D CiEigene Dateien 33 AVI Technical Information Video 00 00 29 00 Motion JPEG including Huffman Tables 1152 132 Kbit s 320x240 24 bit 290 frm 10 0000 frm s 3 x 4 1 500 eff bit per pixel 115213 eff bit per frame C Eigene Dateien 33 AVI Ordner ffnen 1 im Cache gespeichert 12 06 1152 Desktop Suche Google Desktop Search Startseite Privat Status Info 2005 Google L Lokales Intranet Abb 2 10 6 Suche mit Google Desktop nach 1152 34 2 Existierende L sungen Eine Suche nach dem Begriff 1152 findet nicht nur ein Bild mit dieser H he sondern auch eine AVI Videodatei mit einer Bitrate von 1152 132 kBit s Das Vorkommen in bestimmten Attributen etwa nur der Bildh he kann nicht abgefra
70. ache verzichtet Zur Selektion von Dateien wird auf den Attributen der Lib rary basierend eine Datenstruktur definiert die die Parameter einer Suchanfrage speichert und Fil ter genannt wird type FilterType record 1 Dateitypen Dateitypen Filetypes 2 Gemeinsame Attribute Volltextsuche String 31 F r Volltextsuche NameParam String 31 NameSuchmuster Byte 1 enth lt 2 ist 3 f ngt an mit 4 h rt auf mit DatumParam String 10 DatumSuchmuster Byte 1 neuer gleich 2 ist 3 lter gleich 4 Jahrestag FlagsParam Byte 1 Neu 2 System FlagsSuchmuster Byte 1 ist 2 ist nicht 3 Typabh ngige Metadaten Absender Empfaenger String 31 F r SMS und EMail Thema String 31 EMail AVI KuenstlerParam Titel String 31 MP3 AVI Erscheinungsjahr Album String 31 MP3 EquipmentFirmware String 31 JPEG AVI AufnahmeParam String 10 JPEG AVI AufnahmeSuchmuster Byte 1 neuer gleich 2 ist 3 alter gleich BreiteParam String 4 Bilder Videos Animationen HoeheParam String 4 Bilder Videos Animationen KuenstlerSuchmuster Byte 1 enthalt 2 ist end Damit eine Datei ins Suchergebnis aufgenommen wird m ssen alle aktiven Bedingungen der Fil terstruktur erf llt sein es handelt sich also um eine implizite AND Verkn pfung In Sektion 1 wird zun chst die Menge der erlaubten Dateitypen gt Kap 6 2 1 definiert Daran schlie en sich zwei Sektionen an die sich
71. ame document keywords cancel save Keywords Photography 5 University Final Project SOAT Abb 2 8 3 Speichern einer Datei mit kword bei installiertem DBFS Gor04 Als Erg nzung zum KDE Dateimanager dient das Programm kdbfs das in wesentlichen Teilen dem ffnen Dialog entspricht E Views Keywords fal Date Documents Meek AQ Ad e EI BI Cartoons amp Johnny Br ESE vr SpongeBob Angelina Jo Angelina Jo Angelina Jo Angelina Jo Beach Music i 5 Office 5 Photo Albums d ae GC RE D Paintball l s ECH applications Patio Beach Sun Beach Sun Bridget Ma Britney Sp Calm Ripple Tim Verja see IE m T 5 University i Abel Y ews amp Final Proj Dream Ho Fantasy Bird Gillian And Gillian And Gillian And Wallpapers i JL ent zwart wit voor 2000 A Stage e e tm EK EI mm F Website Gwyneth P Gwyneth P Lake Meatspace Meg Ryan black and w 5 cars e D RR Modulo26 Natalie Im Reflection Savanne Viper Inverted Mode Save View New Keyword Remove Keyword 25 files in view total size 3 MB Abb 2 8 4 kdbfs Gor04 Intern ben tigt DBFS die Unterst tzung einer SOL 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 Einga
72. ang der 1990er Jahre einen Siegeszug angetreten haben Saa05 Mit ihnen k nnen Bezie hungen dynamisch modelliert werden und zwar ohne eine externe Hierarchie Mar03 Dies wird auch beispielsweise von Microsoft im Rahmen einer data platform vision angestrebt Mic07 Durch das Erg nzen des relationalen Datenmodells um BLOBs und das Verwalten typspezifischer Datei Schemata in Dateisystemen k nnen beide Datenmodelle auf eine Library und dadurch auch auf das jeweils andere Datenmodell abgebildet werden BLOB relationale Datenbanken und se mantische Dateisysteme sind also gleich m chtig und in diesem Sinne als quivalent anzusehen Keine BLOBs Einheitliches Schema Abb 4 4 1 Beziehung zwischen Datenbanken und Dateisystemen 4 4 1 Zugriff In der Praxis ergeben sich aus den quivalenten Datenmodellen erhebliche Vorteile die u a zur L sung der von Shoens et al in Sho93 gefundenen Problematik beitragen Das in gt Abb 4 1 gezeigte EMail Postfach wird physikalisch in einer propriet ren Datenbank des zugeh rigen Programms gespeichert und ist daher f r die Suchfunktionen des Betriebssystems nicht erreichbar Es handelt sich bei der Datei EBAY MBX um eine BLOB relationale Datenbank je des Tupel enth lt Attribute wie Sender Empf nger Empfangsdatum und Titel der Nachricht Ein BLOB enth lt den Textk rper ggf werden weitere BLOBs f r angeh ngte Dateien hinzugef gt Betriebssysteme die die Integration von Datenbanken
73. ansen jesper funcom com PNG Images JPEG Translator X Read BW Gray images as truecolor BMP Images HSIRaw Translator Amigalcon Translator Register mimetype Released under the GPL c HSIRawTranslator Info 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 2 7 2 Postf cher Eine Besonderheit stellt auch der Umgang mit elektronischer Post dar W hrend herk mmliche Be triebssysteme das Speichern der EMails einer Zusatzsoftware berlassen gt 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 22 2 Existierende L sungen File Window Attributes name New Reaa Replied pratt Pending sent savea F n Vi Out amp UserTalk Abb 2 7 3 Postf cher Name Si
74. anten Attribut w chst bei geometrischer Betrachtung die Dimension des Referenzob jekts Bei voll spezifizierten Anfragen hat das Referenzobjekt 0 Dimensionen ist also ein Punkt Ist nur ein Attribut irrelevant so entsteht eine eindimensionale Referenzgerade bei 2 irrelevanten At tributen eine Referenzebene und so weiter Dies erh ht den Aufwand f r die Nachbarschaftssuche enorm was am Beispiel eines kd Baums Ben75 erl utert werden soll 47 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Ein kd Baum ist ein bin rer Baum dessen Ebenen innerer Knoten zyklisch durch alle Attribute ro tieren Ben75 Als Beispiel dient ein zweidimensionaler Ausschnitt des RGB Farbraums bei denen die Farben rot und blau die zwei Dimensionen bilden Zweidimensionaler Datenraum 50 Deckkraft 50 Deckkraft 50 Deckkraft 2 Dimension 1 Dimension Abb 3 3 6 Ausschnitt eines kd Baums tiber 2 Dimensionen rot und blau In gt Abb 3 3 6 wird auf der ersten Ebene des kd Baums die erste Dimension behandelt Alle Bl t ter die ber den linken Ast erreichbar sind haben weniger als 50 rote Farbdeckung alle ber den rechten Ast erreichbaren Farben haben mindestens 50 Rotanteil Auf der zweiten Ebene wird nun unabh ngig von der ersten Dimension ber den Farbwert der 2 Dimension blau entschieden Der jeweils links Ast f hrt zu Farben die weniger als 50 blauer Farbabdeckung aufweisen die jeweils rechten
75. asse der in gt Abb 6 1 2 dargestellten Vererbungshierarchie ist die abstrakte Klasse DDataAbstract die die grundlegenden Eigenschaften und Operationen aller Dateiformate model liert Neben den obligatorischen Attributen wie dem Prim rschl ssel F Filekey gt Kap 4 1 dem Typbezeichner T Typ gt Kap 4 1 einem Dateinamen Bez f r Bezeichnung und diversen Steuerbits Flags definiert diese Klasse eine Reihe von abstrakten Methoden Durch Aufruf dieser Methoden k nnen instanziierte Datenobjekte von au en manipuliert etwa umbenannt werden Die konkrete Realisierung insbesondere die Funktionsweise und das physikalische Format der beteilig ten Domains bleibt dem Aufrufer dabei verborgen 6 1 2 2 Domain Klassen Von der abstrakten Klasse DDataAbstract wird auf der n chsten Ebene der Programmcode aller Domains abgeleitet Domain Klassen implementieren Methoden f r den Dateizugriff etwa zum ffnen und Schlie en von Dateien Open und Close zum Verschieben des Dateizeigers Seek sowie zum Lesen und Schreiben von Daten an der aktuellen Position des Dateizeigers Read und Write Diese Operationen werden in geeigneter Weise gt Kap 6 1 1 auf das physikalische Datei system abgebildet und sind nur in der Domain Klasse selbst sowie allen abgeleiteten Klassen sicht bar protected Dar ber hinaus stellen Domain Klassen Methoden zum Umbenennen Rename und L schen Kill von Dateien bereit sowie eine Methode CreateList zur Dat
76. ateien sowohl generisch f r alle Dateien z B Kalenderansicht als auch typspezifisch z B Bilderball f r visuelle Inhalte ist zur Zeit Gegenstand einer an der Fachhochschule Dortmund durchgef hrten und vom Autor be treuten Projektarbeit mit daran anschlie ender Bachelor Thesis 8 4 Ausblick Die in dieser Arbeit vorgestellten Konzepte sind nicht nur f r vollwertige Betriebssysteme geeignet sondern auch f r den Einsatz in Umgebungen bei denen Eingaben durch den Benutzer nur einge schr nkt m glich sind Neben mobilen Ger ten insbesondere MP3 Playern und Smartphones stellt surface computing eine solche Plattform dar Bei Microsoft Surface Mic08b handelt es sich um einen Tisch mit ber hrungsempfindlicher Oberfl che die mehrere Ber hrungspunkte gleichzeitig registrieren kann Spezielle Applikationen sind f r den Einsatz in Bars Casinos Gesch ften und anderen Orten konzipiert Gerade wegen der innovativen Bedienung dieses Computersystems sind die Eingabem glichkeiten f r den Benutzer sehr beschr nkt eine Maus oder Tastatur ist nicht vorhanden und Menupunkte auf der Bildschirm oberfl che m ssen gro fl chig genug sein um durch eine Ber hrung sicher getroffen zu werden Abb 8 4 1 Surface Mic08b Abb 8 4 2 Foto Organisation mit Microsoft Surface Mic08b Die nach Meinung des Autors herausragendsten Anwendungen f r derartige Systeme ergeben sich im Zusammenspiel mit Ger ten die von der Oberfl che er
77. atement 6th USENIX Conference on File And Storage Techno logy San Jose 2008 http www usenix org event fast08 wips_posters koll wip pdf http www deskwork de DOWNLOAD DOCS FAST08 ZIP Stand 23 10 2008 Koll K A relational file system as an example for tailor made DMS Proceedings of the 2008 EDBT workshop on Software engineering for tailor made data management Nantes 2008 http portal acm org citation cfm id 1385489 Stand 23 10 2008 Koll K Indexing file attributes with the master slave index Postgraduate Symposium of the 2008 annual research conference of the South African institute of computer scientists and information technologists on Riding the wave of technology George Wilderness 2008 http www deskwork de DOWNLOAD DOCS SAICSIT8 PDF Stand 23 10 2008 Koll K Fancy fancy indexing ApacheCon US 2008 New Orleans 2008 http www deskwork de DOWNLOAD DOCS APACHEO08 ZIP Stand 23 10 2008 Kremp M Tagging im Trend Gemeinsam besser finden Spiegel Online http www spiegel de netzwelt web 0 1518 464902 00 html Stand 23 10 2008 151 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Les06 LHNO03 Lin05 Luc06 Luc07 Mal83 Mar03 152 Leser U et al Informationsintegration DPunkt Verlag 1 Auflage 2006 Von FRA iiber GRU nach GIG Lufthansa Newslink Ausgabe 24 Oktober 2003 http konzern lufthansa com de htmVpresse newsl
78. auf heterogene Datenquellen und Typsicherheit auch f r die Referenz Implementierung gel ten Die Referenz Library zeigt dar ber hinaus die praktische Funktionsf higkeit des Datenmodells Sowohl das Architekturmodell als auch die gew hlte Implementierung bieten au erdem noch weite re Vorteile 6 4 1 Architektur Die objektorientierte Architektur der Referenz Library bietet gegen ber anderen Systemen viele Vorteile Zun chst kann der Zugriff auf Dateiattribute kompakt durch Domain Klassen realisiert werden die zur Extraktion von Metadaten den Programmcode der Applikationen wiederverwenden k nnen Bei einer vollst ndige Neuindexierung wird f r jede Datei die Methode LoadMeta der zu geh rigen Applikation aufgerufen die alle Attributwerte der jeweiligen Datei als Datenstruktur zu r ckliefert Beim eigentlichen Zugriff auf Dateien wird ein Index eingesetzt Dar ber hinaus k nnen Applikationen anderen Modulen zus tzliche Methoden zur Manipulation ei ner geladenen Datei bereitstellen Das soll am Fallbeispiel einer Applikation erl utert werden die Flugpl ne speichert und alle absolvierten Fl ge auf einer Weltkarte darstellen kann Eine so erzeug te Weltkarte kann als Bilddatei gespeichert werden um beispielsweise in einem Fotolabor als Poster ausbelichtet zu werden 92 6 Referenz Library an AT chlie en Bus al CAE To S eichern EVA RACH nsicht P ster L ngster Flug SFO MUC 9 440 km 5 093 nm Routen Top Operator D
79. aums aus gew hlt werden welches dann als Bedingung zum Filter hinzugef gt wird Eventuell erforderliche Parameter dieser Bedingung k nnen danach eingestellt werden Mit den Schaltfl chen am rechten Rand des Fensters werden einzelne Bedingungen wieder entfernt Dar ber hinaus kann der Anwen der einen Suchbegriff zur Volltextsuche ber alle Attribute eingeben und Systemdateien vom Such ergebnis ausschlie en Suchbegr iff Durchsuchen Der K nstler enth lt Der Albunnane enth lt Freak of nature Abb 7 3 1 Datei suchen Dialog 7 3 1 Shell Integration Bei Suchfiltern handelt es sich um eine kompakte Datenstruktur gt Kap 6 2 2 die in einer Datei gespeichert werden kann Daher wurde in der Referenz Library ein neuer Dateityp dtSearch 42 de finiert gt Kap 6 2 1 Durch einen zus tzlichen Menupunkt in der Shell gt Abb 7 3 2 k nnen alle Dateien des Typs dtSearch im Datei Manager angezeigt werden Dateien dieses Typs werden beim Ausf hren vom Datei Manager als neuer Suchfilter gesetzt so dass sie dem Benutzer wie ein Un terverzeichnis erscheinen Das zugeh rige Applikations Objekt gt Kap 6 1 2 gestattet das Modifi zieren des Suchfilters k gt gt 4 R Abb 7 3 2 Gespeicherte Suchfilter in der Shell 106 7 Interaktion 7 3 2 Vorteile Benutzerdefinierte Filter bilden die intelligenten Wiedergabelisten und Alben der Applikationen iTunes bzw iPhoto nach was sich auch an den jew
80. aums und wird mit speziellen API Funktionen angesprochen Der Vorteil dieser Vorgehensweise liegt darin dass der Code der normalen Verzeichnisverwaltung f r Attribute wiederverwendet werden kann In einem ersten Entwurf von BeOS bestand eine Datei daher aus folgenden Komponenten Gia99 I Node Attribut Verzeichnis Abb 3 2 1 Datei mit Attributen Gia99 Diese Implementierung erscheint zun chst sehr elegant sie hat allerdings gravierende Nachteile F r den Zugriff auf ein bestimmtes Attribut muss ausgehend vom I Node der Datei der I Node des Attribut Verzeichnisses eingelesen werden Die dortige Variable data_stream verweist auf die Posi tion der Verzeichnisdaten auf der Festplatte bei BeFS ein B Baum Saa05 der die Nummern der I Nodes der einzelnen Attribute enth lt Ein solcher I Node enth lt wiederum eine Variable data_steam die dann die Position der eigentlichen Attribute auf der Festplatte speichert die zu sammen den B Baum bilden Der Zugriff auf ein Attribut ist also vierfach indirekt Gia99 41 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Da BeOS ein rein grafisches Betriebssystem ist sind neben den eigentlichen Metadaten aus den Da teien zugleich viele von der GUI erzeugte Attribute zu speichern etwa das anzuzeigende Symbol oder die Position im Fenster des Verzeichnisses Wird nun vom Benutzer ein Ordner ge ffnet so m ssen diese Angaben von allen Dateien im Ordner gelesen werden D
81. b 5 1 3 Startsituation Kol08c Die erste zu untersuchende Datei im Beispiel ist die Bilddatei mit dem Schl ssel Z6_HG7E Die typunabh ngigen Attribute stehen sofort durch Abfrage des Master Index zur Verf gung F r typ spezifische Attribute muss nun der entsprechende Eintrag im Index f r Bild Metadaten gesucht 72 5 Indexierung werden Dieses Suchen ist allerdings ein einfaches Finden in O 1 da der Merker im Bilder Index bereits auf den gew nschten Eintrag zeigt Danach werden die Zeiger im Master und Bilder Index um eine Position weiterbewegt gt Master Index Bilder Index MP3 Index Filekey _ Typ _ Filekey Filekey Z5_HG7ES ales TDAI 76 Hores Bild JKESZZA__ MPS gt Linacx Bild JGUIP7SD_ MPS JSUIP7SD gt EHS EC SEERES Abb 5 1 4 Nach Bearbeitung der ersten Datei Kol08c Analog zur ersten Datei wird nun die MP3 Datei mit dem Schl ssel JK83ZZA_ bearbeitet die sich im Master Index an der zweiten Stelle befindet Der Merker im MP3 Index zeigt sofort auf den kor rekten Eintrag so dass in O 1 auf die typspezifischen Metadaten zugegriffen werden kann Danach werden wieder alle betroffenen Zeiger also diejenigen im Master und MP3 Index auf das jeweils n chste Element bewegt em gt Master Index Bilder Index MP3 Index Filekey Typ _ ae Filekey Filekey zwee Dez
82. be von Schl sselworten durch den Benutzer gt Abb 2 8 3 Das DBFS erfordert also genauso wie Verzeichnisb ume die aktive Mithilfe des Benutzers der einen entsprechenden Aufwand betreiben muss Mil05 26 2 Existierende L sungen 2 9 Microsoft WinFS 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 Help View the WinFS help files Read the release notes Developer Information Software Developer Resources Wints H 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 gt Kap 3 3 5 1 in einer BLOB relationalen Datenbank gt 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 Abb 2 9 2 Integration von Min EA in Microsoft Windows Nach der Installation von WinFS erscheint im Arbeitsplatz Fenster das neue Symbol WinFS Stores Mic08c 27 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte P Arbeitsplatz d Arbeitsplatz Festplatten E Systeminformationen anzeig
83. bute F und 7 vor 4 1 die den Typ eines Datenobjekts global eindeutig codieren 7 4 6 bzw f r einen gegebenen Typ die Funktion eines Prim rschl ssels bernehmen F 4 5 Damit bilden die Attri butwerte f t aller Datenobjekte einen globalen Superschl ssel 4 12 In 4 7 wird gefordert dass dom F und dom T f r alle Objekt Schemata einer Library L identisch und somit vergleichbar sein m ssen In der Praxis kann der Wertebereich dom T beispielsweise ein dreibuchstabiger Code sein wo durch die blichen Namensendungen weiter benutzt werden k nnen Ebenso ist auch ein FourCC wie bei AVI Dateien Kol03 eine GUID RFC4122 oder ein MIME Typ RFC2045 denkbar Kol08b In der Referenz Library wurde f r dom T der Datentyp Byte gew hlt so dass jedes Da teiformat als 8 Bit gro e Zahl codiert wird Dadurch k nnen f r Operationen mit Dateitypen die Mengenfunktionen von Borland Pascal ausgenutzt werden Unter anderem sind in der Referenz Library gegenw rtig folgende Dateiformate definiert worden das Pr fix dt steht f r data type 85 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte const dtNone 0 Ung ltig bzw nicht initalisiertes Datenobjekt dtFolder 1 Ordner interne Verwendung im Datei Manager gt Aap 7 4 dtBild256 6 Unkomprimiertes Bild mit 256 Farben dtAdresse 9 Adresse dtTermin 11 Termin dtText 13 Textdatei dtHelp 14 Hilfetext dtTexture 15 3D Textur dtAudioCD
84. ch ist eine einfache Suche nach Dateien mit einem bestimmten Namen oder Namensteil m glich All files and folders und by Name gt 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 gt Abb 2 7 6 Eine Suche nach Dateien mit bestimmten Attributen by Attribute gt Abb 2 7 6 23 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte ist aber ebenso m glich Wird also beispielsweise nach Maildateien gesucht k nnen alle bei diesem Dateityp vorhandenen Metadaten in die Suchanfrage aufgenommen werden gt Abb 2 7 7 All files and folders by Name tar gz Query name Compressed Screens Include trash On All disks X More options Abb 2 7 5 Suche nach Dateien anhand des Namens bzw der Endung gt Ema on arase From contane D Abb 2 7 6 Suche nach Mails D by Attribute On Frome contains milly And When before yesterday And b Search Abb 2 7 7 Suche nach EMails anhand typspezifischer Attribute 2 8 DBFS 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 Zie
85. che Tupelgr en Reservierter Speicher I EM LO E Globale Attribute Cl Typspezifische Attribute Nicht belegter Speicher Abb 5 1 1 Suboptimale Datenstrukturen Daher wird der Master Slave Index als eine zweistufige Hierarchie implementiert die eine Genera lisierung bzw Spezialisierung abbildet Ein Master Index speichert alle Attribute die in allen un terst tzten Dateiformaten vorkommen z B Prim rschl ssel F Typ T Dateiname Gr e Zeitpunkt der letzten nderung Zugriffsrechte Dem Master Index werden zus tzliche Slave Indexe f r typ spezifische Attribute zur Seite gestellt wodurch der partiell belegte Datenraum gt Kap 3 3 4 ab gebildet wird Kol08c Die formale Definition der Struktur eines Master Slave Index basiert auf der Definition einer Libra ry gt Kap 4 1 Damit nicht die Dateien aller Formate indexiert werden m ssen gt Kap 6 1 1 wird zun chst basierend auf einem Library Schema L em Index Schema L definiert L R Rp CL k lt k 5 1 Da nur ausgew hlte Attribute aus glob L indexiert werden sollen also beispielsweise gro e Datei k rper vom Index ignoriert werden sollen wird jedes R aus L als Teilmenge eines R aus L defi niert Diese Teilmenge muss jedoch das Prim rschl sselattribut R F und das Typ Attribut R T enthalten VReL R CR R eL R FAR TER 5 2 Der Datenraum Q L und der Objektraum o weisen dieselbe Struktur wie Q L bzw L auf
86. chema Datenbank Library Dateisystem Store Gr n hervorgehoben im weiteren Verlauf eingesetzte Begriffe Abb 4 4 5 Terminologie f r Datenbanken Libraries und Dateisysteme 67 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Shoens bemerkt in Sho93 dass sich die Anwender schon vor langer Zeit f r Dateisysteme und ge gen Datenbanken zur Speicherung von Informationen entschieden haben ber 15 Jahre sp ter ist diese Aussage noch immer wahr und betrifft aufgrund der gro en Verbreitung digitaler Medien heute weitaus mehr Menschen als 1993 Zur besseren Lesbarkeit werden daher im Verlauf dieser Arbeit die in gt Abb 4 4 5 gr n hervorge hobenen Begriffe verwendet Eine Ausnahme stellen formale Betrachtungen oder der explizite Be zug auf Datenbanken bzw Dateisysteme dar Der Begriff Library wird bereits informell in diver sen Produkten etwa im Windows Media Player oder in Windows 7 verwendet Library v dd gt Music gt Library Songs 4 Playlists Album DJ Create Playlist Le Now Playing 4 Jd Library Recently Added A Artist Jazz Album 2006 Aaron Goldberg Worlds Aaron Goldberg AT Favorites Name Date modified Type E Desktop Recent Places Libran Documents 4 f Libraries Downloads ES Documents Librar Downloads Ai Music Music E Pictures gt Library H Videos Pictures a Computer en amp Local Disk C R Videos Libran Sr Network gn P
87. cmd ExecuteReader while r Read r Close Console WriteLine Case 5 sw Peek 10 0 ms conn Close Console WriteLine Ready Console ReadLine Literaturverweise Literaturverweise Apa07 App05 App08 Ben75 Ber96 Bor99 Apache Software Foundation HTTPD http httpd apache org Stand 23 10 2008 erste Referenzierung 22 10 2007 Apple Corporation Technology Brief Mac OS X Spotlight http images apple com macosx pdf MacOSX_Spotlight_TB pdf Stand 23 10 2008 erste Referenzierung 05 09 2005 Apple Corporation Mac OS X Spotlight Plugins http www apple com downloads macosx spotlight Stand 23 10 2008 Bentley J L Multidimensional binary search trees used for associative searching Communications of the ACM Volume 18 Ausgabe 9 1975 http portal acm org citation cfm id 361007 Stand 23 10 2008 Berchtold S et al The X tree An Index Structure for High Dimensional Data Proceedings of the 22nd VLDB Conference Mumbai 1996 http www vldb org conf 1996 P028 PDF Stand 23 10 2008 Borodin A et al Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems Proceedings of the 31st ACM Symposium on Theory of computing Atlanta 1999 http portal acm org citation cfm id 301330 Stand 23 10 2008 147 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Bri03 Cod70 Dou00
88. d 23 10 2008 Microsoft Corporation Microsoft WinFS Beta 1 Documentation Microsoft Corporation SQL Server 2008 Microsoft Data Platform Vision http www idea lab biz Resources SQL Server 2008 pdf Stand 23 10 2008 erste Referenzierung 09 12 2007 Microsoft Corporation An introduction to WinFS OPath http msdn microsoft com en us library aa480689 aspx Stand 23 10 2008 erste Referenzierung 27 07 2008 Microsoft Corporation Microsoft Surface http www microsoft com surface Stand 03 12 2008 erste Referenzierung 03 12 2008 Microsoft Corporation Create Namespace Extensions for Windows Explorer with the NET Framework http msdn microsoft com en us magazine cc188741 aspx Stand 04 12 2008 erste Referenzierung 04 12 2008 Microsoft Corporation Understanding XML Schema http msdn microsoft com en us library aa468557 aspx Stand 11 12 2008 erste Referenzierung 11 12 2008 153 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Mil00 Mil05 Nic06 Nil05 Nov05 OSC06 Reg02 RFC1094 154 Millstein T Query Containment for Data Integration Systems Proceedings of ACM Symposium on Principles of Database Systems PODS Dallas 2000 http www cs ucla edu todd research pods00 pdf Stand 23 10 2008 Mills B Metadata Driven Filesystem http bryanmills net uploads metafs bmills final pdf Stand 23 10 2008 erste Referenzier
89. den Ein DBMS kann mehrere Datenbanken verwalten und bietet Operationen auf diesen an F r Dateisysteme stellen Betriebs systeme und die Firmware von Multimedia Ger ten entsprechende Funktionen bereit 57 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Management Ebene DBMS Management Ebene Firmware Transaktionen API Transaktionen API Betriebssys ogische Ebene Logi gt e Datenbanksystem Datenbank Dateisystem Abb 4 2 Physikalische logische und Management Ebene verschiedener Speichersysteme Leider wird der Begriff Datenbank sowohl umgangssprachlich als auch in der Literatur oft stell vertretend f r Datenbanksystem und DBMS verwendet was jedoch im weiteren Verlauf zu Fehl schl ssen f hren w rde 4 1 Libraries In diesem Abschnitt wird das Datenmodell einer Library eingef hrt Basierend auf dem relationalen Datenmodell Cod70 wird zun chst ein Attribut A definiert Jedem Attribut A sind eine Bezeich nung welche die Bedeutung des Attributs beschreibt und mit dom A die Gesamtheit aller Werte die A enthalten kann zugeordnet blicherweise entspricht dom A einem atomaren Datentyp aber auch insbesondere beliebig lange Bytefolgen Dateik rper bzw BLOBs sind in Libraries m glich Sie werden hier ebenfalls als atomar angesehen Dar ber hinaus seien Nullmarken f r alle Wertebe reiche zul ssig Zan82 Ein Objekt Schema R wird als Menge von Attributen definiert Jedes
90. e die auf einer Partitionierung des Datenraums Q oder Objektraums basieren also u a auch f r kd B ume R B ume und ihre Derivate Die mathematische Grundlage f r diesen Effekt liegt in der exponentiellen Zunahme des Raumvolumens beim Hinzuf gen von Dimensionen Ber96 untersucht wie sich dieser Effekt auf R B ume auswirkt Bei gro en Dimensionszahlen weisen die umschreibenden Rechtecke einen gro en berlappungsgrad auf der sogar schon bei d 2 beobachtet werden kann Eix Fie Edit View Performance File Edit View Performance El el Abb 3 3 3 R Baum mit d 2 Bri03 Abb 3 3 4 R Baum Vergr erung Bri03 44 3 Existierende Indexe Bereits bei zehn Dimensionen wird eine berlappung von 100 erreicht was R B ume f r hoch dimensionale Anwendungen unbrauchbar macht Das ist ein Symptom eines grundlegenden Effekts der Fluch der Dimensionen genannt wird Von diesem Effekt sind alle Nachbarschafts Opera tionen betroffen bei denen sowohl der Datenraum als auch die Suchanfrage hochdimensional sind F r exakte Full Match Operationen hingegen eignen sich Gridfiles Saa05 die Suchanfragen in konstanter Zeit beantworten Full Match Operationen spielen f r Dateien jedoch keine wichtige Rolle da der Benutzer nicht alle Attributwerte einer Datei spezifizieren kann und eine gegebene Datei in der Regel auch nicht alle Attribute besit
91. e vollst ndige Adressdatei RFC2425 bzw einen Verweis auf eine solche Ein anderer Tag Typ kann f r Termindateien RFC2445 vorgesehen werden Auf diese Weise k n nen beliebige Dateien mit einem Terminplaner verkn pft werden um Dateien mit dem zugeh rigen Kalendereintrag zu verbinden oder um Dateien zur Wiedervorlage zu markieren 8 3 3 Automatisches Tagging Tagging erweitert die Objekt Schemata einer Library um zus tzliche Informationen nach denen Dateien gesucht und mittels automatischer Ordner gt Kap 7 4 auch gruppiert werden k nnen Diese Vorteile werden durch einen gewissen Aufwand des Benutzers erkauft der eigentlich ver 127 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte mieden werden soll gt Kap 1 Aus diesem Grund ist die Automatisierung des Taggings anzustre ben F r die beiden in Kap 7 5 vorgestellten Arten von Tags ist diese leicht durchf hrbar beispiels weise k nnen die von hochwertigen Kameras in Bilddateien gespeicherten GPS Koordinaten mit tels einer internen Tabelle um den n chstgelegenen IATA Code gt Kap 7 5 1 erg nzt werden F r die Bewertung von Dateien ist eine Vergabe anhand einer Aufrufstatistik m glich so dass bei spielsweise die 10 am h ufigsten ge ffneten Dateien automatisch mit 3 Punkten die n chsten 15 mit 2 Punkten und die folgenden 25 mit 1 Punkt angezeigt werden Auch f r weitere semantische Tags gt Kap 8 3 2 sind Automatisierun
92. e Dateien bei denen ein Bit f r Neue Datei gesetzt ist Auf den Testdaten findet diese Anfrage jedoch keine Dateien 2 Der zweite Fall soll alle Bilddateien finden Das Finden von Dateien eines bestimmten Typs ist eine grundlegende Funktion auf der alle Suchen nach typabh ngigen Metadaten basieren 3 Der dritte Testfall ist analog zum vorigen Fall konstruiert und soll alle Audio Dateien finden 4 Die vierte Suchanfrage erweitert den zweiten Testfall es sollen nicht mehr alle Bilddateien ge funden werden sondern nur noch diejenigen deren Breite 1024 Pixel ist Die Bildaufl sung ist bei allen Bilddateien am Dateianfang zu finden EXI07 5 Der f nfte Suchfilter erweitert den dritten Testfall es wird nun nur noch nach denjenigen Audio Dateien gesucht die in ihren Metadaten als K nstler Anastacia eingetragen haben Der ID3 Tag Nil05 befindet sich immer am Dateiende 3 3 5 1 Microsoft SQL Server 2005 Der Microsoft SQL Server 2005 ist als Standard L sung von besonderem Interesse da das Presti ge Produkt Microsoft WinFS gt Kap 2 9 dieses Datenbanksystem zum Speichern von Dateien einsetzt Um die Performanz des Microsoft SQL Servers zu testen wurde nach der Installation ber das Management Studio eine neue Datenbank mit dem Namen Metadata angelegt 51 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Ri Microsoft SQL Server Management Studio Express File Edit Wiew Tools Window Com
93. e Funktionen Luc06 Feldnamen gt Abb 3 1 4 Attribute werden nach der Position in der Namensliste durchnummeriert rq Worthaufigkeit frequency Enth lt zu jedem Wort die Dateien in denen es vorkommt einschl H ufigkeit prx N he zu anderen Worten proximity Enth lt die Position eines Wortes innerhalb des Dokuments Feldindex Enth lt f r alle Dokumente Zeiger auf die eigentlichen Metadaten falls vorhanden Felddaten Enth lt die eigentlichen Metadaten W rterbuch term infos Enth lt alle Worte die in den indexierten Dateien vorkommen Abb 3 1 3 Funktionen von Unterdateien im Compound File System Luc06 Damit ist offensichtlich dass Lucene einen Index in Form von invertierten Listen Kol07b aufbaut Am Anfang der Index Datei befindet sich eine Aufstellung aller vorkommenden Attribute Da xfriend vor allem auf Multimedia Dateiformate spezialisiert ist finden sich im Beispielindex u a gel ufige Metadaten wieder 38 ditor earbeiten 07 SF 7A 71 2E 01 05 01 OA 01 01 02 D1 04 HI 01 03 03 03 03 03 03 03 03 03 03 Ende Hilfe atei F _2Q 66 33 31 22 00 uchen OB 05 01 07 00 01 03 03 03 03 03 03 03 03 Speichern Alt P ools 08 00 03 03 03 03 03 03 03 03 03 Opt ionen Eygeggeeg Sggggggggggggeeg VVVVVVVVVVVVVVVY Schl ie en Gelb hervorgehoben L ngenbyte vor Strings Rot hervorgehoben Attributnamen Abb 3 1 4 Im xfriend Index enthaltene Attribut
94. e des Menus wurden zwei Sektionen f r die Verwaltung von Dateien eingerichtet Eigene Dateien enth lt 3 Punkte die Zugriff auf die Library bieten w hrend unter Externe Dateien Dateisysteme au erhalb der lokalen Library wie eingelegte Me dien und angeschlossene externe Datentr ger aufgef hrt sind I igene Dateien Vorhandene Dateien zeigen und ndern Neue Datei erstellen Dateien suchen gespeicherte Suchen Externe Dateien TOSHIBA MKZBB1MPL Ge DUD RAM im HL DT ST DVDRAM GSA 4167B of CD Player G H Audio CD auslesen Ge CD DVD brennen aus gespeicherter Sitzung Oi Diamond Rio PMP an LPT1 intern SmartMedia oY Nullmodem Kabel an LPT2 Meister Sklave Sei Dateien von DOS importieren Abb 7 1 8 Eigene Dateien 100 7 Interaktion Die beiden ersten Optionen gt Abb 7 1 8 verweisen auf Unterseiten w hrend Dateien suchen die Eingabe neuer Suchfilter durch den Benutzer erm glicht gt Kap 7 3 Gespeicherte Suchen zeigt alle benutzerdefinierten Filter an die f r eine sp tere Verwendung gespeichert wurden Die Menuseite Neue Dateien erstellen f hrt in den drei Sektionen B ro System und Wis senschaft Applikationen und Dateiformate auf verf gbarer Platz 59 160 920 064 Byte Abb 7 1 9 Untermenu Neue Datei erstellen Einige Menupunkte wie z B EMail schreiben sind hier aufgef hrt weil technisch betrachtet ei ne Datei vom Typ dtMail gt Ka
95. e oben dargestellte Realisierung eines Metadaten Indexes durch B Baume Saa05 ist aus Im plementierungssicht zwar elegant da bestehende Datenstrukturen und zugeh riger Programmcode benutzt werden k nnen allerdings merken die BeOS Entwickler selbst an dass B ume beim Ein satz in Dateisystemen Nachteile haben Early versions of BFS did in fact index the creation time of files but we deemed this index not to be worth the performance penalty it cost By eliminating the creation time index the file system received roughly a 20 speed boost in a file create and delete benchmark Abb 3 2 2 Performanz Einbu en durch Indexierung der Dateizeit Gia99 Es war daher nur konsequent kleine Attribute insbesondere solche nach denen nicht gesucht wird wie die Position des Icons im Fenster direkt im I Node der Datei unterzubringen Dies ist je 42 3 Existierende Indexe doch nur f r eine begrenzte Anzahl von Attributen m glich und sinnvoll Alle Attribute nach denen gesucht werden soll oder die nicht in den I Node passen m ssen weiterhin in einem B Baum un tergebracht werden auf dessen Bl tter von jedem I Node aus mittels Attribut Verzeichnis verwiesen wird Dies f hrt zu gravierenden Leistungseinbu en da bei zahlreichen Attributen eine entsprechend gro e Anzahl von Baumindexen notwendig wird die beim Anlegen Ver ndern und L schen einer Da tei in ihrer Gesamtheit aktualisiert werden m ssen Die Entwickler von BeOS habe
96. ee of 43 7 MB amp Local Disk D Storage Card ani Nee Volne E TRITT 4 WM 4 Application Data ConnMgr P Documents and Settings Lib My Documents Program Files wm Storage Card E Recycle Bin a Control Panel m 2 items Abb 8 2 1 Virtueller Namensraum unter Microsoft Windows Analog zu Microsoft WinFS kann dieser Mechanismus genutzt werden um die Dateien einer Libra ry f r existierende Software zug nglich zu machen 8 2 3 Applikationen Einige der in gt Kap 7 pr sentierten Verfahrensweisen k nnen unabh ngig vom Einsatz einer Lib rary bereits existierende Applikationen aufwerten So wird zur Zeit ein Modul f r den Apache HTTPD entwickelt der die bliche Indexierung von Verzeichnissen durch fancy fancy indexing 125 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte gt Kap 7 7 also einer CSS basierten Benutzeroberfl che ersetzen soll Kol08d Eine Web Applikation zur Abgabe und Bewertung von bungsaufgaben die ebenfalls diese Technologie nutzt befindet sich als Showcase Anwendung seit M rz 2008 an der Fachhochschule Dortmund im dauerhaften Einsatz gt Kap 7 7 2 Auch Datei Manager f r traditionelle Dateisysteme die ohne die Funktionalit t einer Library aus kommen m ssen k nnen von einigen Verbesserungen profitieren unter anderem k nnen automati sche Ordner anhand der vom Dateisystem verwalteten Attribute gebildet werden was in der Regel eine Kal
97. eichnisse abgebildet Besondere Sektionen der Webseite enthal ten Ubersichtstabellen und Eingabeformulare f r nderungen Kol08d 121 SmartAssign NG Opera Datei Bearbeiten Ansicht Lesezeichen Widgets Extras Hille 8 9 8 S A http jjlocalhost SmartAssignNGlindex php DISPLAY Aktuelles Semester 88 2008 es Einf Informatik 1 Lern und Arbeitstechniken Neue Vorlesung erstellen Vergangene Semester WS 2007 08 ame Test Doz Dozent Login TestDoz01 er 88 2008 on SmartAssign 2 0 1 University of Applied Sciences and Arts Abb 7 7 8 Hauptseite SmartAssign NG Opera loxi Datei Bearbeiten Ansicht Lesezeichen Widgets Extras Hilfe Jax H a L P http jflocahost SmartAssignNGjindexAufgabe php7ENTITY 18DISPLAY 2 PS Logout E Kacheln Zur ck Einf Informatik Einstellungen zu dieser bungsaufgabe Name der Aufgabe FOR Schleifen Laufende Nummer innerhalb der Vorlesung Einf Informatik 1 E Maximalpunkte f r diese Aufgabe Abgabe bis 01 03 2008 3 59 Uhr Einstellungen ndern nderungen werden sofort sichtbar bersicht ber alle Abgaben Abgaben gesamt 6 Abgaben digital Einf Informatik 1 88 2008 FOR Schlelfen ne University of Applied Sciences and Arts Abb 7 7 10 Aufgabe erstellen Formular 122 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte SmartAss
98. eiger nur der urspr ngliche Dateik rper sichtbar ist Kol08b Ein weiterer Grund f r die Einf hrung von Domains sind Benutzerkonten die bei Multiuser Betriebssystemen verwendet werden Zu keinem Zeitpunkt sind hier alle Dateien verf gbar ledig lich die Dateien des jeweils angemeldeten Benutzers werden gemountet au erdem sind bestimmte Systemdateien etwa Schriftarten freigegeben Daher verf gt jeder Benutzer der Referenz Implementierung ber eigene Domains die zusammen etwa dem Heimverzeichnis in traditionellen Systemen entsprechen Zus tzlich werden Domains f r Systemdateien angelegt die f r alle Benut zerkonten verf gbar sind 6 1 2 Applikationen Das Referenz Modell muss keine R cksicht auf bestehende Applikationen und die durch den Ver lust der Kompatibilit t entstehenden Probleme nehmen Daher wird ein ganzheitlicher objektorien tierter Ansatz eingef hrt bei dem Applikationen durch Vererbung zum Teil der Library werden DDataAbstract Bez String Filekey String Typ Byte Flags Byte DatBild Load I I LoadMeta Open Load Run Seek LoadMeta RunToView Read Run Rename Write GetBuffer Kill Close Scale Rename Convert Kill Save CreateList Open Seek Registry Read Close CreateList Abb 6 1 2 Einbindung von Applikationen 83 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 6 1 2 1 Datei Klasse Oberste Kl
99. eiligen Dialogfenstern zeigt Smart Playlist M Match the following rule Podcast L i is true E Limit to 25 songs L i selected by random Match only checked songs E Live updating Cancel ED Abb 7 3 3 Intelligente Wiedergabeliste in Apple iTunes Die benutzerdefinierten Filter der Referenz Library gehen jedoch ber Wiedergabelisten hinaus Durch die Einbindung der Library ins Betriebssystem gt Kap 6 k nnen benutzerdefinierte Filter f r beliebige Dateien definiert werden und nicht nur f r die Dateiformate einer bestimmten Appli kation Derartige Suchfilter sind also universell einsetzbar Da sie beim ffnen eine Suchanfrage an die Library ausl sen ist das von ihnen repr sentierte Suchergebnis dar ber hinaus stets aktuell 7 4 Automatische Ordner Suchfilter sind im Idealfall so formuliert dass alle relevanten Dateien gefunden werden recall aber keine unerw nschten Elemente enthalten sind precision Das erfordert einen genau formu lierten Suchfilter was f r den Benutzer sehr aufw ndig oder aufgrund der verf gbaren Attribute gar unm glich ist Nic06 und Mal83 zeigen nun dass ein Unterschied zwischen Suchen in den Bedeutungen von browse und search existiert Demnach ist f r den Menschen das Durchsuchen von bereits dar gestellten Dateien wesentlich einfacher als das Erinnern an Eigenschaften Es ist somit unabdingbar Suchergebnisse im Datei Manager sin
100. eisuche Diese Methode bekommt eine Suchanfrage gt Kap 6 2 2 bergeben und liefert eine Liste aller enthaltenen Dateien zur ck die den Bedingungen der Suchanfrage gen gen Die konkrete Implementierung kann variieren bei spielsweise durch die Verwendung eines Indexes gt Kap 5 Ein solcher Index kann ohne Beteili gung von Applikationen verwaltet werden da der Zugriff auf Dateien ausschlie lich ber die von der Domain bereitgestellten Methoden durchgef hrt wird Auf diese Weise kann etwa bei jedem Aufruf von Close nach vorhergehenden Schreiboperationen automatisch eine Aktualisierung des In dexes vorgenommen werden 6 1 2 3 Applikations Klassen Formatspezifische Methoden etwa zum Einlesen einer Datei Load oder zur Extraktion der Meta daten LoadMeta bleiben in Domain Klassen weiterhin abstrakt Sie werden erst in den eigentli chen Applikations Klassen implementiert Die Objekte von Applikations Klassen repr sentieren damit eine konkrete Datei die nach dem Aufruf von Load in aller Regel in den Arbeitsspeicher ein gelesen wurde und zur Benutzung bereitsteht Alternativ kann ein solches Datei Objekt auch von einem Domain Objekt erzeugt worden sein um z B bei einer Neuindexierung durch Aufruf der Methode LoadMeta nur die Attributwerte einzulesen und danach in einem Index zu speichern 84 6 Referenz Library F r Applikationen die Dateien aus mehreren Domains verarbeiten sollen ergibt sich hier bei kon sequenter Umsetzu
101. en die physikalische Dateisysteme durchf h ren k nnen auf die Relationenalgebra zur ckf hren da diese auch auf das Library Modell anwend bar ist So entspricht das Ausgeben aller Dateien in einem bestimmten Verzeichnis und mit einem bestimmten Namen etwa durch DIR DOC bzw LS DOC einer Selektion o Abb 4 4 2 Selektion in einem physikalischen Dateisystem Je nach eingesetztem Betriebssystem k nnen durch zus tzliche Parameter unterschiedliche Attribute f r jede Datei ausgegeben werden In diesem Beispiel gibt B nur die Dateinamen ohne weitere An gaben aus es handelt sich dabei also um eine Selektion o mit anschlie ender Projektion 7 auf die ses eine Attribut Abb 4 4 3 Selektion und Projektion in einem physikalischen Dateisystem 4 4 3 Typsicherheit Traditionell identifizieren Betriebssysteme und Applikationen den Typ einer Datei durch eine Er weiterung des Dateinamens wie etwa av c jpg mp3 und so weiter Dieses Verfahren hat den 66 4 Integration gro en Nachteil dass ein Anwender beim Umbenennen einer Datei die Erweiterung und damit den Dateityp ndern kann was die Datei unbrauchbar macht sie w rde z B beim ffnen gar nicht oder mit einem falschen Programm gestartet Katharina mp3 xi Wenn Sie die Dateinamenerweiterung ndern wird die Datei m glicherweise unbrauchbar M chten Sie sie trotzdem ndern Abb 4 4 4 Warnung beim Ver ndern der Dateinamenerweiterung Im Gegensatz
102. en a Le JP System C et Daten D T Software EI ystem C KE a aten D gt Eine Einstellung ndern Ger te mit Wechselmedien Si Netzwerkumgebung u 314 Diskette A DVD RAM Laufwerk E t Q Eigene Dateien D Gemeinsame Dokumente D _ DYD Laufwerk X E Systemsteuerung gt Arbeitsplatz Sn Systemordner KI NOMAD Explorer WinFS Stores 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 2 9 1 WinFS Type Browser Jede in WinFS gespeicherte Datei Item genannt gt Kap 4 4 4 entspricht einem vorher definier ten Schema das von Anwendungen durch Vererbung erweitert werden kann WinFS Type Browser Refresh stores I Bac wee d 7 Lol System Storage GenericFile type hierarchy 8 a ATHLONG4 hy DefaultStore 2 8 System Storage e Cl Inline Types e CC Item Extensions Item Fragments 2 43 Items Pa Folder Fi ltem Aa a Methods fa Share So dhe e A Storelnfo RK Q
103. enderansicht gt Kap 7 4 erm glicht 8 3 Weiterentwicklungen Die in dieser Arbeit eingef hrten Technologien bieten ein erhebliches Anwendungspotential In die sem Abschnitt werden daher zuk nftige Entwicklungsschritte pr sentiert deren Umsetzung in naher Zukunft realistisch erscheint 8 3 1 Master Slave Index Der in gt Kap 5 eingef hrte Master Slave Index kann als zus tzliche Methode in bereits existieren de DBMS integriert werden Kap 8 2 1 Um den Anforderungen kommerzieller Datenbanksys teme gerecht zu werden m ssen die Algorithmen die auf einem Master Slave Index operieren um die F higkeit der nebenl ufigen Ausf hrung concurrent access erweitert werden Da Suchvorg nge keine Ver nderungen am Index vornehmen gt Kap 5 1 2 k nnen diese bereits jetzt nebenl ufig durchgef hrt werden Das Hinzuf gen von Tupeln muss serialisiert werden da neue Daten immer ans Ende der Indextabellen angeh ngt werden gt Kap 5 1 3 m glicherweise gleichzeitig ablaufende Suchvorg nge m ssen am alten Dateiende angehalten oder beendet werden bis das Hinzuf gen abgeschlossen ist Sollen Eintr ge ge ndert oder gel scht werden m ssen Suchvorg nge unter Umst nden neu gestartet werden damit keine inkonsistenten Suchergebnisse an den Aufrufer bermittelt werden Dar ber hinaus bleibt zu untersuchen ob andere Datenstrukturen als Slave Indexe eingesetzt wer den k nnen und auch sinnvoll sind Denkbar ist beispie
104. entsprechenden Ordner Dar ber hinaus stellen automatische Ordner kein starres Ordnungsschema f r Dateien dar denn die Gruppierung ndert sich sofort wenn ein anderes Sortierkriterium ausgew hlt wird Es handelt sich also in der Terminologie von Mal83 gt Kap 1 bei automatischen Ordnern um piles die sich selbst ordnen bzw neu zusammensetzen und so zu files werden ein Vorgang der bei Papierak ten undenkbar ist Zusammen mit einem Attribut das das letzte Aufrufdatum einer Datei oder die 109 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Anzahl der Aufrufe in einem bestimmten Zeitraum enth lt k nnen aktuelle oder wichtige Da teien schnell aufgefunden werden Hiervon profitiert die in gt Kap 7 1 vorgestellte Shell die auf der Startseite u a alle f lligen Termi ne an prominenter Stelle anzeigt Wird im Datei Manager die Kalenderdarstellung auf Adressen oder Termine angewandt so werden einschl gige Programme wie Terminplaner oder Adressverwal tungen mit Hilfe automatischer Ordner ersetzt 7 5 Semantisches Tagging In vielen Systemen darunter DBFS gt Kap 2 8 k nnen Dateien mit Schlagworten versehen wer den nach denen dann auch gesucht werden kann Schlagworte stellen zur Zeit die beliebteste Form des Taggings dar Kre07 Die folgende Abbildung zeigt als weiteres Beispiel ein Foto innerhalb des Bilderdienstes Flickr Fli07 das mit den Tags shdh shdh15 jpf und nick
105. er H he besitzt w rde dieses 88 6 Referenz Library Element also aus Dateitypen entfernt Optimierte Filter betreffen m glicherweise nicht alle Do mains so dass sie von einem Master Slave Index schneller bearbeitet werden k nnen gt Kap 5 1 2 In der Referenz Implementierung wird daher jede Suchanfrage vor ihrer Abarbei tung wie folgt eingegrenzt Suchtypen Filter Dateitypen Kopie um Struktur des Aufrufers nicht zu ver ndern Suchtypen bereinigen Typen entfernen denen geforderte Metadaten fehlen with Filter do begin if Absender lt gt or Empfaenger lt gt then Suchtypen Suchtypen dtSMS dtMail if Thema lt gt then Suchtypen Suchtypen dtMail dtVideoAVI if Kuenstler lt gt or Titel lt gt then Suchtypen Suchtypen dtMP3 dtVideoAVI if Erscheinungsjahr lt gt or Album lt gt then Suchtypen Suchtypen dtMP3 if EquipmentFirmware lt gt then Suchtypen Suchtypen dtDigiFoto dtVideoAVI if AufnahmeSuchmuster gt 1 then Suchtypen Suchtypen dtDigiFoto dtVideoAVI if BreiteParam lt gt or HoeheParam lt gt then Suchtypen Suchtypen dtFlic dtXAnim dtVideoMPEG dtVideoAVI dtQuickTime dtBild True dtBild256 dtBildAnsi dtDigiFoto dtTexture dtVideoSMJPEG end 6 3 Performanz Im Rahmen der Referenz Implementierung wurde der Master Slave Index aus gt Kap 5 einem Per formanztest unterzogen Die Messergebnisse unterstreichen die theoretische Leistungsf higkeit der Indexstru
106. erenzierung 10 09 2006 Gopal B et al Integrating Content based Access Mechanisms with Hierarchical File Systems Proceedings of the 3rd USENIX Symposium on Operating Systems Design and Implementation New Orleans 1999 http www usenix org events osdi99 full_papers gopal gopal pdf Stand 23 10 2008 Gorter O Database File System An Alternative to Hierarchy Based File Systems Master s thesis University of Twente 2004 http dbfs sourceforge net Stand 23 10 2008 erste Referenzierung 05 09 2005 Grobe T et al Geodaten f r Fotos Magazin f r Computertechnik c t Special Digitale Fotografie Heise Verlag 2007 Guttman A R Trees A Dynamic Index Structure for Spatial Searching Proceedings of the ACM SIGMOD Conference Boston 1984 http www sai msu su megera postgres gist papers gutman rtree pdf Stand 23 10 2008 Hacker S et al The BeOS Bible Addison Wesley Verlag 1 Auflage 1999 http www birdhouse org beos bible exc_data html Stand 23 10 2008 HardwareEcke de BeOS http www hardwareecke de berichte grundlagen beos php Stand 23 10 2008 erste Referenzierung 04 09 2005 149 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte IAT07 Imf02 Jag05 KDE06 Ker03 Kol03 Kol07a 150 International Air Transport Association http www iata org Stand 23 10 2008 erste Referenzierung 11 06 2007 Imfeld A
107. ern von Metadaten und zur Bearbeitung von Suchanfragen Indexe nehmen daher eine zentrale Rolle ein die ber die Performanz der Gesamtl sung entscheidet Im folgenden Kapitel werden drei Ans tze f r einen Index vorgestellt die Lucene Bibliothek gt Kap 3 1 die von vielen Desktop Suchmaschinen eingesetzt wird ein ins Dateisystem integrierter Index gt Kap 3 2 und multidi mensionale Indexe gt Kap 3 3 Aufgrund der Integration von semantischen Dateisystemen und relationalen Datenbanken gt Kap 4 ist der letzte Ansatz besonders interessant so dass die Ursa chen f r die dort auftretenden Performanz Probleme ausf hrlich dargelegt werden Die gewonnenen Erkenntnisse gt Kap 3 4 finden beim Master Slave Index gt Kap 5 Anwendung 3 1 Lucene Lucene ist eine Open Source Java Bibliothek zum Erzeugen und Durchsuchen von Indexen sie ist Teil der Apache Software Foundation Mit Hilfe dieser plattformunabh ngigen Bibliothek lassen sich in kurzer Zeit Volltextindexe f r beliebige Inhalte erzeugen Die Bibliothek setzt sich aus zwei Hauptbestandteilen zusammen eine Komponente erzeugt den Index wobei diesem beliebige typi sierte Dokumente hinzugef gt werden Eine Query Engine durchsucht den Index schlie lich Ne ben diesen grundlegenden Eigenschaften verf gt Lucene ber eine reichhaltige Auswahl zus tzli cher Funktionen und Tools welche durch die Open Source Community aktiv und umfangreich wei terentwickelt werden
108. ers besteht aus einem Fenster mit dem Titel Arbeitsplatz das einen vom Speicherort abh ngigen Einstieg ins Dateisystem bietet dies ist besonders sinnvoll da der Da teiname mit Pfad den Prim rschl ssel eines traditionellen Dateisystems darstellt und somit ein wichtiges Ordnungskriterium ist Es sei darauf hingewiesen dass die in gt Abb 7 1 3 am linken Fensterrand untergebrachten Favo rite Links nicht etwa eine typspezifische Suche oder Filterung aktivieren sondern lediglich die von Windows bei der Installation angelegten Verzeichnisse Documents in der deutschen Version Eigene Dateien genannt Documents My Pictures Eigene Dateien Eigene Bilder bzw Documents My Music Eigene Dateien Eigene Musik ffnen unabh ngig von ihrem tats chlichen Inhalt 97 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Name Type 2 Total Size Free Space E Documents Hard Disk Drives 4 E Pictures BR Music More ww Sy GZ Folders MU Desktop a C Drive C D Drive D E Drive E Ip N ADI PC Workgroup KHD A VistaPC Processor Intel R Pentium R D CPU 3 40GHz Memory 3 00 GB Abb 7 1 3 Computer Fenster von Windows Vista 7 1 2 Anforderungen an eine Shell Soll eine Library zur Datenspeicherung benutzt werden so erscheint die Pr sentation von Verzeich nissen als Einstieg ins Dateisystem unzureichend da eine derartige Hierarchie nicht mehr angebo ten wird AuBerdem stehen bel
109. f higkeit dieser L sungen Zur grundlegenden Verbesserung der Organisationsstrukturen wurde das Datenmodell einer Library pr sentiert gt Kap 4 1 das m chtig genug ist um sowohl die Tupel relationaler Datenbanken als auch Dateien zu beschreiben beide werden als gleichwertige Datenobjekte mit beliebigen Attribu ten gesehen und so integriert Damit die Attributwerte aller Datenobjekte schnell zur Verf gung ste hen sollten sie indexiert werden Zur Indexierung partiell belegter Datenr ume gt Kap 3 3 4 die durch Tupel heterogener Schemata gebildet werden eignet sich ein Master Slave Index gt Kap 5 Er unterst tzt Partial Match Operationen gt Kap 3 3 2 und ist immun gegen ber degenerativen Effekten hochdimensionaler Datenr ume gt Kap 3 3 1 Auch bei Anwendung des Library Modells k nnen Dateien und Applikationen in eine objektorien tierte Architektur eingebettet werden Die in gt Kap 6 vorgestellte Referenz Architektur und ihre Implementierung liefern daf r eine Vorlage welche die praktische Funktionsf higkeit des Library Modells nachweist Die Referenz Library wird au erdem eingesetzt um die Performanz eines Mas ter Slave Indexes zu messen gt Kap 6 3 Diese Indexierungsmethode ist anderen Ans tzen ber legen und bietet auch bez glich des absoluten Zeitbedarfs eine ausreichende Leistung Eine Library integriert verschiedene Datenquellen insbesondere relationale Datenbanken und klas sische Dateis
110. form Resource Identifier URI Generic Syntax http www ietf org rfc rfc3986 txt Stand 23 10 2008 RFC 4122 A Universally Unique Identifier UUID URN Namespace http www ietf org rfe rfc4122 txt Stand 23 10 2008 Robbins A UNIX in a nutshell O Reilly Verlag 3 Ausgabe 1999 Saake G et al Datenbanken Implementierungstechniken mitp Verlag 2 Auflage 2005 Sakurai Y et al The A tree An Index Structure for High Dimensional Spaces Using Relative Approximation Proceedings of the 26nd VLDB Conference Kairo 2000 http www vldb org conf 2000 P516 pdf Stand 23 10 2008 155 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Sel87 She96 Sho93 Stu07 Tag08 Tan02 Web98 Whi96 156 Sellis T K et al The R Tree A Dynamic Index for Multi Dimensional Objects Proceedings of the 13th VLDB Conference Brighton 1987 Shemitz J Using RDTSC for benchmarking Visual Developer Magazine Juni 1996 http www midnightbeach com rdtsc html Stand 23 10 2008 Shoens K et al The Rufus System Information Organization for Semi Structured Data Proceedings of the 19th VLDB Conference Dublin 1993 http www vldb org conf 1993 P097 PDF Stand 23 10 2008 StudiVZ http www studivz net Stand 23 10 2008 erste Referenzierung 09 07 2007 Tag Galaxy http www taggalaxy de Stand 03 12 2008 erste Referenzierung 03 12 2008 Tanenbau
111. gen Werkzeuge Hilfe G il EA VAR Objektbrowser Eigenschaften Statistiken Abh ngigkeiten Abh ngige H d po emp 1 reg Tabele Engsf gte Tupel Aktualisierte Tupel Gel schte Tupel Gr e D Aggregate 0 H H H Konversionen 0 S Dom nen 0 Funktionen 0 P Triggerfunktionen 0 N Prozeduren 0 Operatoren 0 Operatorklassen 0 D Sequenzen 0 Tabellen 1 H E test D Typen 1 E Sichten 0 SQL Feld Replikation 0 Tabellen wird aufgefrischt Fertig Abb 3 3 12 Gr e einer Datenbank f r 92 288 Dateien Analog zu gt Kap 3 3 5 1 wurden die Laufzeiten f r dieselben f nf Suchanfragen ermittelt Indexe in Form von B B umen f r jedes Attribut boten dabei keinen oder keinen nennenswerten Vorteil Ohne Index Indexiert B B ume 10000 ms 10000 ms 1000 ms 1000 ms 100 ms 100 ms 10 ms 10 ms 1 10 100 Dateien in Tausend Dateien in Tausend 1102 3 4 45 1102 3 4 a5 Abb 3 3 13 Leistungsf higkeit von PostgreSQL Kol08c Der marginale Zeitvorteil wird jedoch durch eine deutlich geringere Performanz beim Hinzufiigen von neuen Tupeln zum Index erkauft Das ist insbesondere beim Einsatz in Dateisystemen ein Prob lem so dass die theoretischen berlegungen und Aussagen gt Kap 3 2 1 der Entwickler des BeOS File System gt Kap 2 7 durch diese Messungen noch einmal best tigt werden 54 3 Existierende Indexe 10000 s 1000 s 100s Le Ge 10s 4 0 10
112. gen durchf hrbar so k n nen mittels bilderkennender Verfahren und in Adressdateien gespeicherter Referenzbilder automa tisch Personen in Bildern erkannt und getaggt werden Beim Erstellen oder Speichern von Dateien k nnen Termindateien automatisch als Tag hinzugef gt werden wenn der Zeitpunkt des Speicherns in den Zeitraum des Termins f llt Auch ein Join gt Kap 7 2 ber die Dateizeit ist denkbar 8 3 4 Verbesserte Visualisierung Traditionelle Datei Manager stellen die Dateien eines Verzeichnisses bzw eines Suchergebnisses als Liste mit mehr oder weniger Angaben je Datei dar Durch automatische Ordner gt Kap 7 4 die Dateien anhand eines vorher gew hlten Attributs gruppieren wird eine Darstellung als Kalender erm glicht gt Abb 7 4 4 Dar ber hinaus sind weitere Varianten zur Visualisierung von Dateien denkbar die allerdings auf grund der beschr nkten M glichkeiten der zur Implementierung genutzten Plattform nicht realisiert werden konnten Ein Beispiel hierf r liefert die Website Tag Galaxy Tag08 die anhand eines eingegebenen Begriffs Fotos vom Bilderdienst Flickr Fli07 l dt und als Ball darstellt Dieser Ball eignet sich um schnell einen berblick ber eine gr ere Anzahl Bilder oder auch Videos zu bekommen er kann mit der Maus beliebig gedreht werden Abb 8 3 2 Bilderball Tag08 128 8 Zusammenfassung und Ausblick Eine umfassende Bestandsaufnahme ber Visualisierungsmethoden f r D
113. gt werden Diese Schw che des verwendeten Indexes ist besonders rgerlich weil die Internet Suchmaschine durch Eingabe besonderer Parameter gesteuert werden kann filetype pdf liefert nur Dateien mit dieser Endung zur ck und site www deskwork de findet nur Dokumente dieses WWW Servers Die Steuerung der Desktop Suche durch Parameter wie width 1024 minheight 1152 oder artist Anastacia w rde eine deutlich genauere Suche erm g lichen was allerdings vom eingesetzten Wortindex nicht unterst tzt wird 2 10 4 Yahoo Desktop Ein direktes Konkurrenzprodukt zu Google Desktop ist Yahoo Desktop das ebenfalls von einem gro en Betreiber einer WWW Suchmaschine entwickelt wurde Im Gegensatz zu Google Desktop benutzt Yahoo Desktop jedoch keinen WWW Browser zur Darstellung der Suchergebnisse sondern ist eine eigenst ndige Applikation An dieser Desktop Suchmaschine fallen die M glichkeiten zur Steuerung der Indexierung beson ders positiv auf F r jeden Teilbaum der Verzeichnishierarchie kann eingestellt werden ob die dort enthaltenen Dateien vollst ndig gar nicht oder nur mit ausgew hlten Attributen indexiert werden sollen Ei Indexing Options x Choose A Folder Indexing Options for 0 c eigene deeler Eigene Dateien 29 Screenshots und Indexe Everything all files x Software C File names and sizes plus content for specified 4 20 System Volume Information extensions doc ppt etc EI winfsbeta File names and sizes o
114. h lt das eigentliche Testprogramm Die Klasse Program greift auf eine nicht abgebildete Klasse StopWatch zu deren Objekte die Zeit mit einer Genauigkeit von 0 1 ms messen k nnen Intern greift das NET Framework dabei auf den RDTSC Befehl She96 zur ck 138 C Testprogramm Microsoft SQL Server 2005 using SALXMLBULKLOADLiIb using System using System Data using System Data Sql using System Data SqlClient using System Collections Generic using System Text namespace ConsoleApplication1 class Program Nur ein Thread SQLXML ist nicht thread safe STAThread static void Main string args SqlConnection conn new System Data SqlClient SqlConnection conn ConnectionString integrated security SSPI data source CARMIN SQLEXPRESS persist security info False Inn catalog Metadata Console Write Connecting conn Open Console WriteLine done Alte Tabelle entfernen SqlCommand cmd new SqlCommand DROP TABLE Test conn try cmd ExecuteNonQuery catch Neue Tabelle erstellen cmd new SqlCommand CREATE TABLE Test FileTyp int FileBez varchar 31 FileKey varchar 8 FileSize int FileTime varchar 20 FileNew int FilePassword varchar 15 FilelATA int VIDFourCC varchar 4 VIDL int VIDH int VIDVideoDecoder int VIDAudioDecoder int VIDCreationYear int VIDCreationMonth int
115. heorie verlorene Schlacht zu schlagen wird in gt Kap 5 mit dem Master Slave Index eine Indexstuktur auf Basis einer se quenziellen Suche beschrieben die au erdem den partiell belegten Datenraum gt Kap 3 3 4 aus nutzt 56 4 Integration 4 Integration Im Rahmen dieses Kapitels wird gezeigt dass sich die Datenmodelle von BLOB relationalen Da tenbanken gt Kap 4 2 1 und semantischen Dateisystemen gt Kap 4 3 1 auf das Library Modell gt Kap 4 1 abbilden lassen und sich umgekehrt das Modell einer Library auf beide Da tenmodelle abbilden l sst Es wird gezeigt wie Abbildungsvorschriften konstruiert werden k nnen durch die keine Informationen verloren gehen Dadurch k nnen BLOB relationale Datenbanken und semantische Dateisysteme als gleich m chtig und in diesem Sinne quivalent angesehen wer den Mittels der Integration beider Datenmodelle wird ein Problem gel st auf das Shoens et al bereits 1993 in Sho93 hingewiesen haben da die M glichkeiten traditioneller Dateisysteme begrenzt sind implementieren viele Applikationen propriet re Datenbanken um ihre Nutzdaten dort abzu speichern Diese Datenbanksysteme und damit die zugeh rigen Applikationen nehmen die Daten jedoch in Besitz d h sie sind f r andere Programme ber das Dateisystem nicht mehr zug ng lich Ein Beispiel f r diesen Sachverhalt sind EMail Programme die neben dem eigentlichen Text k rper auch Attribute wie Absender Datu
116. hfilter der Shell nicht ausreichen In gt Kap 7 3 wird daher ein Dialogfenster zur Eingabe von Suchfiltern vorgestellt 4 Ebenso wichtig ist die Darstellung von Dateilisten etwa eines Suchergebnisses f r den Anwen der Hier ergeben sich durch die einer Library inh renten Semantik diverse Vorteile und Verbes serungen unter anderem automatische Ordner gt Kap 7 4 Anzeigen von Aufgaben gt Kap 7 6 und verbesserte Webserver gt Kap 7 7 Da die in diesem Kapitel vorgestellten Verbesserungen zum Teil v llig unterschiedliche Problem stellungen bearbeiten und daher nicht vergleichbar sind werden ihre Vorteile nicht am Ende dieses Kapitels zusammengefasst sondern am Ende der jeweiligen Abschnitte 95 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 7 1 Shell Der Begriff Shell stammt von Unix Betriebssystemen und bezeichnet die dort verwendeten Kommandointerpreter Da unter Unix Shells gew hnliche Programme ohne besondere Rechte sind entstanden viele gleichberechtigt nebeneinander stehende Shells die sich teilweise erheblich in Syntax und Funktionsumfang unterscheiden Rob99 Auch bei ausschlie lich grafisch orientierten Betriebssystemen existiert eine Shell Sie interpretiert dort jedoch keine eingegebenen Kommandos sondern ist in der Regel das Anwendungsprogramm das nach dem Booten als erstes gestartet wird Welches Programm als Shell fungieren soll l sst sich bei vielen Betriebssystemen eins
117. hr Datenmodell ber eine zus tzliche Schnittstelle erreichbar ist OSC06 Uber diesen Weg k nnen beliebige Anwendungsprogramme auf die Metadaten zugreifen die aufgrund der Be schr nkungen physikalischer Dateisysteme innerhalb eines Dateik rpers gespeichert werden m s sen Sie werden von semantischen Dateisystemen gleichberechtigt ins Datei Schema integriert u M Semantisches Dateisystem Dateiname Ge ndert am Gr e Dateik rper se az scr oe U Weitere Metadaten innerhalb des Dateik rpers Abb 4 3 2 Beispieldatei eines semantischen Dateisystems Durch Abbildung aller R aus SDS l sst sich analog zu 4 16 das Datenmodell eines semantischen Dateisystems in das einer Library berf hren ohne dass Informationen verloren gehen 63 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte F r semantische Dateisysteme ist auch der umgekehrte Weg m glich da sowohl ein Library Sche ma als auch das Schema eines semantischen Dateisystems aus mehreren Objekt bzw Datei Schemata bestehen kann eine Library in ein semantisches Dateisystem berf hrt werden wenn dies auch f r jedes Objekt Schema gilt Alle Attribute A eines Objekt Schemas R mit dom A BLOB werden auf Dateik rper K eines Da tei Schemas R abgebildet Alle anderen Attribute werden auf Metadaten Attribute des Datei Schemas abgebildet die ggf transparent in einem der Dateik rper gespeichert werden Das Prim r
118. hriften 4 3 4 5 4 6 4 7 und 4 12 hinzugef gt werden so dass gilt R R U F T F T A Ays Kr Kan 4 16 In den meisten Dateisystemen bt der Dateiname die Funktion eines Prim rschl ssels aus zumin dest innerhalb eines Verzeichnisses Liegen alle Dateinamen einschlie lich des Pfades vor gilt diese 62 4 Integration Schl sseleigenschaft ber das gesamte Dateisystem In diesem Fall kann das Attribut des Dateina mens direkt auf F abgebildet werden 4 3 2 Semantische Dateisysteme Imfeld stellt in Imf02 fest dass semantische Informationen zu Dateien also Metadaten grund s tzlich schon in den Dateien selbst vorhanden sind und prinzipiell auch extrahiert werden k nnen Da das Datenmodell DS blicher Dateisysteme allen Dateien dasselbe Datei Schema aufzwingt ist der Zugang zu diesen Informationen einzig ber die entsprechenden Applikationen m glich wo durch die Sicht auf Metadaten eingeschr nkt wird und ihre globale Verf gbarkeit verliert Imf02 Semantische Dateisysteme stellen eine Weiterentwicklung physikalischer Dateisysteme zur Verbes serung dieser Situation dar Ihr Schema SDS unterscheidet sich von dem traditioneller Dateisysteme DS dadurch dass f r alle Dateiformate individuelle Datei Schemata und damit Attribute bzw Me tadaten verwaltet werden k nnen SDS Ri Bu 4 17 Oft sind semantische Dateisysteme so konzipiert dass sie auf ein traditionelles Dateisystem aufbau en und i
119. i einer Nachbarschaftssuche ein bestimmter Cluster C von l Clus tern insgesamt betrachtet werden muss und somit die entsprechenden Sektoren mit den Attributen geladen werden ist proportional zum Volumen den C im Suchraum einnimmt VM x Vol MSum x Einn Ues 2 1 I pm mbr C 3 1 avg P visit Es VM x bezeichnet das Volumen von Cluster x das durch die Minkowski Summe Funktion MSum ES um die erwartete Entfernung E nn des n chsten Nachbarn von x vergr ert wird begrenzt vom Datenraum Q Das Volumen eines Bereichs C kann nach unten begrenzt werden d h es kann ein 46 3 Existierende Indexe Mindestvolumen angegeben werden da die mbr eines jeden Bereichs konvex ist verl sst eine Hilf slinie zwischen zwei beliebigen Elementen x und y eines Bereichs C die mbr nicht so dass gilt Web98 Xi Vi C VM mbr C gt VM line x y 3 2 Damit kann auch die durchschnittliche Wahrscheinlichkeit f r den Zugriff auf C nach unten be grenzt werden Die von Weber durchgef hrten und in Web98 beschriebenen Simulationen zeigen nun dass bei 10 Elementen im Suchraum Q ab 1500 Dimensionen nahezu alle Cluster betrachtet werden m ssen Ausgehend davon dass ein sequenzielles Lesen des Indexes im Vergleich zu wahl freiem Zugriff auf moderner Hardware nur einen Bruchteil der Zeit ben tigt gt Kap 3 3 3 1 erge ben sich folgende Schlussfolgerungen Web98 1 F r jeden Partitions oder Cl
120. ictures Date modified 11 2 2008 4 14 PM Library Abb 4 4 7 Verwendung des Begriffs Library in Microsoft Windows 7 68 5 Indexierung o Indexierung In diesem Kapitel wird eine neuartige Indexstruktur der Master Slave Index Kol07a Kol08c eingef hrt Diese Datenstruktur kann insbesondere eingesetzt werden um die Attribute von Dateien zu indexieren und eine hohe Performanz f r die Dateisuche gt Kap 6 2 2 sicherzustellen Der Master Slave Index wird in einer Referenz Library gt Kap 6 eingesetzt die gleichzeitig der Durchf hrung praktischer Performanzmessungen dient gt Kap 6 3 5 1 Master Slave Index Die Grundidee des Master Slave Index besteht darin die Attributwerte aller Dateien hintereinander in einer Heap Datei Saa05 zu speichern Suchanfragen werden bearbeitet indem diese Datei se quenziell gelesen wird und die Attributwerte jeder Datei mit einem Suchfilter gt Kap 6 2 2 abge glichen werden Diese Vorgehensweise ist immun gegen den Fluch der Dimensionen gt Kap 3 3 1 denn die Laufzeit einer Indexabfrage ist ausschlie lich von der Indexgr e und der Geschwindigkeit des Da tentr gers abh ngig Dadurch ist die Performanz auch unabh ngig von der Anzahl der Dimensionen des Datenraums denn das Einlesen einer Zeichenkette mit 256 Byte L nge hat denselben Aufwand wie das Einlesen von 256 8 Bit Zahlen Au erdem werden Partial Match Abfragen bei denen nur wenige Attribute spezifizie
121. ie besten Voraussetzungen bieten Unix Betriebssysteme da der globale Namensraum f r Dateien ber Mountpoints gt Kap 2 2 oh nehin aus mehreren Dateisystemen zusammengesetzt wird ber einen solchen Mountpoint k nnen die in einer Library gespeicherten Dateien ins Unix Dateisystem eingebunden und f r Applikatio nen welche die Programmierschnittstelle der Library nicht nutzen zug nglich gemacht werden Dar ber hinaus k nnen bei vielen Desktop Managern darunter KDE KDE06 die Standard Dialoge zum ffnen und Speichern von Dateien ersetzt werden gt Kap 2 8 so dass auch Legacy Software die M glichkeiten einer Library eingeschr nkt nutzen kann Ein hnlicher Mechanismus ist auch f r die Windows Plattform verf gbar und wird beispielsweise von Microsoft WinFS gt Kap 2 9 und von Ger tetreibern gt Abb 8 2 1 genutzt Mittels Explo rer Namespace Extensions k nnen innerhalb der Verzeichnishierarchie Mountpoints erstellt wer den deren weitere Unterverzeichnisse und Dateien von Plug Ins ins Dateisystem abgebildet werden Mic08c Auf diese Weise integriert Microsoft WinFS seine Stores ins Dateisystem gt Abb 2 9 3 aber auch die Treiber von mobilen Ger ten erm glichen dem Benutzer auf diese Weise den Zugriff auf die dort abgespeicherten Informationen COO Computer WM my Organize Views Folders Name Type Total Size Free Space BE Desktop a p 5 4 Computer Local Disk CH 22 4 MB fr
122. iebige Suchfilter bereit die jedoch nicht genutzt werden Daher las sen sich aus den oben beschriebenen Eigenschaften und Unzul nglichkeiten aktueller grafischer Shells Anforderungen an verbesserte Shell Generationen herleiten 1 Verbesserte Menuf hrung um auch viele Befehle und Applikationen bersichtlich und mit Hilfe texten bzw Hinweisen darzustellen 2 Unterst tzung einer Library durch verbesserten Aufruf des Datei Managers 3 Exponierte Darstellung von besonders wichtigen Menupunkten Hinweisen und Alarmen um Widgets zu ersetzen 7 1 3 Hypertext Menus Die oben gestellten Anforderungen implizieren eine flexiblere Darstellung f r einzelne Befehle die ber das uniforme Layout eines Menus hinausgehen Komplexere Layouts sind den meisten An wendern bereits durch WWW Seiten vertraut Die Grundidee zur Verbesserung grafischer Shells besteht deshalb darin Befehle und Anwendungen als Link in Hypertext Seiten einzubetten Da die meisten Betriebssysteme ber Webbrowser verf gen und derartige Seiten anzeigen k nnen erscheint es sinnvoll die Darstellungsm glichkeiten von HTML um propriet re Strukturen zu erweitern die dann innerhalb f r Menuseiten verwendet und vom Browser verstanden werden k nnen 98 7 Interaktion Angaben zum Verk ufer Verk ufer konstantinkoll 430 de E Bewertungen 99 1 Positiv Mitglied seit 15 07 00 in Deutschland Angemeldet als privater Verk ufer Bewertungskommentare lesen Frage an de
123. ieser Umstand f llt besonders auf wenn sehr viele Dateien betroffen sind sog batch rename bzw batch delete Li OO T Commands Edit View Options Help Mask C x P Include subdirectories J Manual mode New name OriginalN ame gt Replace Search for x D Replace with D gt IV Case sensitive I Whole words I Exclude extension IV Onlyonceineachname I Regular expression Change case File name Dont change S Extension Don t change he P Include path part Preview 1 file and 2 directories Original Name NewName Seel Datel Timel CU checksum checksum DIR 31 8 2004 14 11 52 blesk altap Sala C 7zip Zap DIR 31 8 2004 14 11 52 blesk altap Sala fa plugins ver plugins ver 1 8 6 2004 20 14 28 blesk altap Sala Abb 5 1 10 Batch rename Im Folgenden soll das Massenl schen von Dateien n her untersucht werden Der naive Ansatz f r alle m Dateien die L schfunktion des Betriebssystems mit dem jeweiligen Schl ssel aufzurufen ist von Nachteil Viel effizienter ist es dem Betriebssystem selbst eine Liste der zu l schenden Dateien zu bergeben die dann direkt abgearbeitet wird 76 5 Indexierung Dass die zweite Variante effizienter ist berrascht denn in beiden F llen ergibt sich theoretisch eine Laufzeit von O n m Dabei wird jedoch vernachl ssigt dass die Liste der zu l schenden Dateien zumeist im schnellen Arbeitsspeicher vorliegt w
124. ig igno riert denn Magellan dient ja gerade dem Auffinden von Dateien mit unbekanntem Pfad Lotus Magellan Explore All files AUTOEXEC BAT Lotus Magellan Release 2 0 All files Company Please Wait Abb 2 1 3 Programmstart Abb 2 1 4 Suchen nach einem Begriff 2 Existierende L sungen Beim ersten Programmstart kann die Suchanfrage allerdings noch nicht bearbeitet werden da Ma gellan noch keine Dateien indexiert hat Magellan could not open the index file with the IX2 extension a If the index resides on a network another user may be updating or rebuilding it Use Index Alt F5 Update to update the index and try the search again Consider the possibility of a disk error Press Esc to continue Abb 2 1 5 Fehlender Index Vor dem Indexieren k nnen bestimmte Dateiendungen angegeben werden 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 Index Setup Description All files Index file name ALLFILES Filespec eie 8 exe com SUS H Calm Enter or edit descriptive name of index type to highlight the character that follows it 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 Now indexing DW 3 ARJ Using viewer
125. ign NG Opera lolxi 7 Datei Bearbeiten Ansicht Lesezeichen Widgets Extras Hilfe x at a Gi e Q 5 N A http iiocaihost SmartAssignNG indexvorlesung phprenTITY 28015PLA 2 PS Logout Zur ck Zur Hauptseite bungsaufgaben 2 IF ELSE 311 3 59 Uhr 3 SunSpot to Rudi V ller Proj 0 Abgaben 17 02 1976 16 00 Uh F r diese Vorlesung wurden bereits bungsaufgaben ver ffentlicht Die Vorlesung kann daher nicht mehr gel scht werden Neue bungsaufgabe erstellen Dozenten und Tutoren E 1 A 3 Gesamt Tutor l schen Konstantin Koll 2 1 0 3 nicht m glich Mark Krannich 0 D z l schen Test Doz 0 1 nicht m glich Neuen Tutor hinzuf gen Punktestand _ I H T i 2 Ze rlesung Einf Informatik 1 S SS 2008 Tutoren 2 Abgaben 8 University of Applied Sciences and Arts 1 Abb 7 7 9 Vorlesung mit Tabellen SmartAssign NG Opera Datei Bearbeiten Ansicht Lesezeichen Widgets Extras Hilfe RK CO S o LA ge A http iocaihost SmartAssignNG indexAufgabe phprenTITY 18D15PLAY 2 PE stellungen andern nderungen werden sofort sichtbar bersicht ber alle Abgaben Abgaben gesamt 6 Abgaben digital 4 Tutoren Abgaben je Tutor Korregieren Unkorregierte digitale Abgaben 1234 7044005 Konstantin Koll 12345677 test test Korregierte digitale Abgaben 5678000 Horst M ller
126. in Baum pro Attribut modifiziert werden Aus diesem Grund indexiert das BeFS nicht alle Attribute gt Kap 3 2 1 Die Performanz ver schlechtert sich weiter da durch die nicht sequenziellen Zugriffe auf Baumstrukturen das eingesetz te Speichermedium zu gro en Geschwindigkeitsverlusten f hren kann gt Kap 3 3 3 Partial Match Operationen werden auch von den meisten multidimensionalen Indexstrukturen gt Kap 3 3 die alle Attribute in einer Datenstruktur zusammenfassen nicht effizient unterst tzt 55 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte da diese vor allem f r Nachbarschaftssuchen entwickelt wurden Somit ist insbesondere der Einsatz von kd und kdB B umen gt Kap 3 3 2 sowie von Gridfiles Saa05 und iDistance Jag05 aus geschlossen rechte Spalte in gt Abb 3 3 2 Multidimensionale Indexe die den Datenraum Q oder den Objektraum partitionieren degenerieren dar ber hinaus aufgrund des Fluchs der Dimensio nen beim Einsatz auf hochdimensionalen Daten Web98 Als Konsequenz besteht das Problem eines nicht sequenziellen Zugriffs auch bei den meisten multidimensionale Indexstrukturen wo durch sogar der Geschwindigkeitsgewinn von iDistance gt Kap 3 3 1 auf nicht gleichverteilten Daten wieder vernichtet wird Als einziges Verfahren bleibt f r das Indexieren der Attribute somit nur das sequenzielle Lesen aller Attributwerte aus einer geeigneten Datei Statt eine bereits in der T
127. inem oder mehreren Dateik rpern K Ka be steht und zus tzlich weitere Attribute A Ay enth lt R A AysKu K d gt 0Ad gt 0 4 14 bliche Attribute sind beispielsweise der Dateiname der Zeitpunkt der letzten nderung und die Gr e des Dateik rpers Die meisten Dateisysteme k nnen f r jede Datei nur einen einzigen Datei k rper abspeichern moderne Dateisysteme wie z B NTFS gestatten jedoch auch das Speichern be liebig vieler sog Forks f r jede Datei Kol07b Das Schema traditioneller Dateisysteme enth lt nur ein einziges Datei Schema dem alle Dateien unabh ngig von ihrem Format entsprechen m ssen so dass gilt DS R 4 15 Die folgende Abbildung zeigt ein Beispiel f r eine Datei die einen Dateik rper enth lt und dem Datei Schema R Dateiname Ge ndert am Gr e Dateik rper gen gt Dateiname Ge ndert am Gr e Dateik rper Abb 4 3 1 Beispieldatei 4 3 1 Abbildungsvorschrift Um ein Dateisystem auf eine Library abzubilden gen gt es analog zu gt Kap 4 2 zu zeigen dass sich ein Datei Schema R auf ein Objekt Schema R abbilden l sst Ein Datei Schema R ist genau wie ein Objekt Schema R eine Menge von Attributen so dass die allgemeinen Attribute A bis Aq sowie alle d Dateik rper problemlos abgebildet werden k nnen Dar ber hinaus m ssen das Schl sselattribut F und ein Typ Attribut T von einer geeigneten Abbildungsvorschrift unter Beach tung der Vorsc
128. ini 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 gt Kap 6 Der Master Slave Index gt Kap 5 und seine Leistungs f higkeit gt Kap 6 3 wird ausf hrlich in Kol08c beschrieben Zuletzt waren Verbesserungen an Webserver Applikationen gt Kap 7 7 Gegenstand eines Vortrages Kol08d Dar ber hinaus wurde 2007 der Master Slave Index gt 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 2 Existierende L sungen 2 Existierende L sungen 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 gt 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 gt Kap 2 1 In diesem Kapitel werden verschiedene Ans tze untersucht dokumentiert und bewertet gt Kap 2 11 Neben Desktop Suchmaschinen werden auch relevante Entwicklungen aus dem akademischen Bereich und Techniken die
129. ink archiv_2003 newslink_2003_10 index html Stand 23 10 2008 linuxlog de Beagle Search Tool http linuxlog archiv usr local bin de beaglesearchtool html Stand 23 10 2008 erste Referenzierung 07 09 2005 Lucene Index File Formats http lucene apache org java 1_9 O fileformats html Stand 23 10 2008 erste Referenzierung 12 07 2006 Lucene PoweredBy http wiki apache org jakarta lucene PoweredBy Stand 23 10 2008 erste Referenzierung 03 12 2007 Malone T W How Do People Organize Their Desks Implications for the Design of Office Infoma tion Systems ACM Transactions on Office Information Systems Vol 1 No 1 Januar 1983 http portal acm org citation cfm id 357430 Stand 23 10 2008 Marsden G Improving the usability of the hierarchical file system ACM International Conference Proceeding Series Vol 47 Proceedings of the 2003 annual research conference of the South African institute of computer scientists and information technologists on Enablement through technology Fourways 2003 http portal acm org citation cfm id 954027 Stand 23 10 2008 Mic93 Mic00 Mic05 Mic07 Mic08a Mic08b Mic08c Mic08d Literaturverweise Microsoft Corporation Verkniipfen und Einbetten von Objekten Benutzerhandbuch Microsoft Windows for Workgroups 1993 Microsoft Corporation How to disable the Find Fast indexer http support microsoft com kb 158705 EN US Stan
130. intr ge Abb 5 1 12 Nach dem Markieren der ersten Datei 77 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Da alle n Dateien aus dem Master Index mit den m Eintr gen in der L schliste verglichen werden m ssen ergibt sich eine Ordnung von O n m Gegen ber dem Durchlaufen des Indexes der auf der Festplatte gespeichert ist f llt das Durchsuchen der L schliste im Arbeitsspeicher allerdings kaum ins Gewicht Liegt die L schliste sortiert vor Kann beim Suchen der aktuellen Datei sogar ei ne bin re Suche eingesetzt werden so dass sich die Ordnung zu O n log m verbessert Dies ist bei der naiven Variante nicht m glich da die Sortierung der L schliste dort irrelevant ist Nach der ers ten Phase sind alle Dateien der L schliste aufgefunden und die zugeh rigen Eintr ge in allen In dexen markiert gt gt Master Index Bilder Index MP3 Index L schliste Filekey Typ Filekey Z6HG7ES Bild Z6HGT7ES JK83ZZA_ MP3 amp LL9 ACX1 30_KUIXY_ Ze Xe LL9ACXI Bild_ JGUIP7 D_ MP3 30_KUIXY_ Bild 1 E zum L schen markierte Eintr ge Abb 5 1 13 Nach dem Markieren aller Dateien der L schliste In einer zweiten Phase m ssen nun alle markierten bzw invalidierten Datens tze endg ltig aus der Datei entfernt werden Dieser Schritt muss jedoch nicht sofort durchgef hrt werden sondern kann auch beispielsweise bis zum Logout des Benutze
131. ionaler Datenobjekte Eigenschaften von videomodes txt my zx bernehmen 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 Eigenschaften von Geb Einladung FR ppt _ Eigenschaften von IMPOSSIB AVI ei bernehmen ct Abb 2 6 2 Powerpoint Datei Abb 2 6 3 AVI Video Diese Plug Ins sind als eine Erweiterung von Microsoft OLE gt Kap 2 4 anzusehen da sie f r be stimmte Dateitypen wie z B PowerPoint Pr sentationen oder AVI Videos in die Registry Datei gt Kap 2 4 2 eingetragen wurden 20 2 Existierende L sungen 2 7 BeFS 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 al
132. ird abh ngig vom erkannten Ger t f r das dort eingebaute Dateisystem ein Library Schema verwaltet oder bertragen Der Zugriff auf beliebige Attribute und Metadaten unterst tzt die Visualisierung von Datenobjekten wie Audio Inhalten gt Abb 8 4 4 insbesondere da eine hohe Geschwindigkeit durch den Einsatz eines Master Slave Indexes gew hr leistet werden kann Dadurch treten durch das Anzeigen der enthaltenen Dateien keine sp rbaren Verz gerungen beim Platzieren eines Ger ts auf der Oberfl che auf Dar ber hinaus gestatten es die flexiblen Objekt Schemata oberfl chenspezifische Attribute zu ein zelnen Dateien zu speichern etwa Position und Zustand nach der letzten Benutzung Dies verein facht die Bedienung da Einstellungen etwa die Gr e und Lage eines Bildes schnell und automa tisch wiederhergestellt werden k nnen 130 Anhang A Glossar BLOB DBMS ext2 Domain FAT Filter Finder I Node Leerlauf Prozess Library Mountpoint NTFS A Glossar Abk rzung f r Binary Large Object ein Wertebereich f r Attribute zur Speicherung von Dateien in relationalen Datenbanken Abk rzung f r Datenbank Management System Wichtiges Dateisystem f r Linux das auf Nodes basiert und Verzeich niseintr ge in B umen abspeichert Kol07b Speicherort gt Kap 6 1 1 Mit DOS eingef hrtes Dateisystem das zur Kompatibilit t f r nahezu alle externen Flash Speicherkarten und USB Sticks ve
133. jedoch nicht gegeben da Dateiformate nur bestimmte Metadaten enthalten so hat eine MP3 Datei beispielsweise keine Breite oder H he Nil05 w hrend der Exif Standard kei nen Albumnamen und kein Genre kennt EXI07 Es existieren also in der Praxis keine Dateien die alle dem Dateisystem bekannten Metadaten Attribute mit Werten belegen in den entsprechenden Regionen eines Datenraums k nnen also keine Dateien enthalten sein sparsity Der Objektraum hat somit nicht die Form des Hyperquaders Q Kol08b Kol08c dom X dom Y dom Y Abb 3 3 7 Objektraum o f r zwei Dateiformate mit je zwei Attributen blau In gt Abb 3 3 7 wird der Datenraum Q Hyperquader dargestellt Dateiformat 1 liefere die Attribute X und Y Dateiformat 2 die beiden Attribute X und Y2 Ausgehend von diskreten Wertebereichen f r alle Attribute l sst sich der Hyperquader als Q dom X x dom Y x dom Y2 beschreiben Der Ob jektraum ist in diesen Hyperquader eingebettet und besteht nur aus den zwei blau eingef rbten Fl chen Kol08b Kol08c a dom X xdom Y U dom X x dom 3 3 Der Objektraum kann auch allgemein fiir mehr als zwei Dateiformate und beliebige Attributmengen f r jedes Format definiert werden Es seien k Dateitypen definiert die zus tzlich zu den n Attributen X bis X die in allen Formaten vorkommen jeweils m weitere Attribute haben die von Y bis Yin durchnummeriert werden Dann gilt Kol08b Kol08c k
134. jeweiligen Sprache benutzt werden M nchen Deutschland bzw Munich Germany 112 7 Interaktion Bielefeld Deutschland Korfu Griechenland Denpasar Bali Indonesien Dortmund Deutschland D sseldorf Deutschland Neuark USA Neu York Flushing USA ep Sie Dass ES E GER Hannover Deutschland Jog jakarta Indonesien Klagenfurt sterreich London Gro br itannien Mailand Italien Nordrhe in Hestfalen Deu N rnberg Deutschland Neu York USA Perugia Italien San Francisco USA Ron Italien Siena Italien San Francisco Internat i San Jose USA Salzburg sterreich Huppertal Deutschland Hann Deutschland Osnabr ck Deutschland Abb 7 5 4 Nach Orten gebildete automatische Ordner Die Relation IATACodes wird nach Code sortiert gespeichert und enth lt etwa 9 300 Eintr ge Da die automatischen Ordner anhand dieses Attributs sortiert werden k nnen die dreibuchstabigen Ordnernamen durch einen Merge Join in linearer Zeit mit Ortsnamen versehen werden Die Lauf zeit f r das Erzeugen automatischer Ordner f r 3 Letter Codes ist also O n IATACodes 7 5 2 Bewertung von Dateien Ein weiterer Tag Typ der Referenz Library gt Kap 6 hat als Wertebereich die Zahlen 1 2 und 3 und wird als Bewertung interpretiert Ist der entsprechende Attributwert einer Datei null so wird 0 bzw unbewertet angenommen Mittels dieses Attributs wird z B der Zugriff auf die Lieblings musik oder gern ge
135. kannt und ber WLAN oder Bluetooth ins System eingebunden werden k nnen gt Abb 8 4 3 gt Abb 8 4 4 Gerade hier bietet eine Lib rary aufgrund der Vielzahl m glicher Dateiattribute gro e Vorteile gegen ber herk mmlichen Da teisystemen 129 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Als Beispiel sollen hier wiederum Mobiltelefone und MP3 Player angef hrt werden Wird ein sol ches Ger t vom Surface System erkannt wird ein Kreis um das Ger t dargestellt Zus tzlich er scheinen einige der auf dem Ger t gespeicherten Bilder oder Musikst cke letztere dargestellt durch eine Art Karteikarte mit Titelbild Bewertung und Zusatzinformationen gt Abb 8 4 4 Der Benut zer kann nun ber ein einfaches Menu Fotos versenden etwa an einen Onlinedienst oder beliebige Dateien mit einer Fingerbewegung in den Kreis eines anderen Ger ts ziehen und dadurch bertra gen Dateien die in einen zus tzlich dargestellten Bereich bewegt werden speichert das jeweilige Surface System dauerhaft ab Abb 8 4 3 Foto Applikation Mic08b Abb 8 4 4 Interaktion mit Ger ten Mic08b In diesem Szenario kann das Library Modell seine St rken voll ausspielen Ein grundlegender Vor teil ist die inh rente Typsicherheit f r Dateien so dass beim Datentransfer von und zu Ger ten nur unterst tzte Dateiformate insbesondere f r weniger standardisierte Anwendungen wie Navigations systeme bertragen werden Hierzu w
136. ktur im Zusammenspiel mit der Referenz Implementierung deren Praxistauglichkeit da durch nachgewiesen wird 6 3 1 Testumgebung Zum Einsatz kamen wieder die Testdaten und das Testsystem aus Abschnitt gt Kap 3 4 Das Test system war mit einer CPU vom Typ AMD Athlon 64 X2 3800 dual core 2000 MHz 2 GB DDR2 dual channel RAM 200 MHz Bustakt und einer 320 GB SATA Festplatte ausgestattet die als NTFS Dateisystem formatiert wurde Zeitmessungen wurden mit dem RDTSC Befehl She96 durchgef hrt 6 3 2 GREP F r einen ersten Geschwindigkeitstest wurde der Befehl GREP benutzt der Dateien nach bestimm ten Zeichenketten durchsucht GREP verf gt ber keine Informationen zu den einzelnen Dateifor maten sondern ffnet jede Datei und durchsucht den gesamten Dateik rper Das impliziert eine enorme Zeitverschwendung bei gro en Multimedia Dateien die Metadaten nur in kleinen Berei chen am Anfang oder Ende der Datei enthalten EXI07 Nil05 89 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Bei 1442 Dateien ben tigte GREP 955 3 Sekunden also mehr als 15 Minuten f r Testfall 5 alle MP3 Dateien von einer bestimmten K nstlerin Da solche Laufzeiten in der Praxis unbrauchbar sind wurde auf weitere Tests mit gr erem Datenbestand verzichtet Kol08c 6 3 3 Ohne Index Im n chsten Test wurden alle f nf Testf lle mit der Referenz Library bearbeitet allerdings ohne ei nen Index Die Laufzeit ist gegen be
137. l die berwindung der klassischen hierarchischen 24 2 Existierende L sungen 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 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 Views E Keywords rl Date L l 3 ef Documents Keywords N Q rm 5 E gt Cartoons nai g d Johnny Br i i EF Images I cker Database File Sys Usability Testing e Office HEEN Photo Albums aaa aaa Den Haag r nn dbfs paper dbfs screen gt mu ie invite 2 invite Photography vi University IA practical file sys reportFunbrowsing be Final Proj i allpapers SOAT 5 Zwart wit voor 2000 eng reportLinearDelays test Wallpaper Website testest black and w cars people X Show only Application Type opening Cancel Abb 2 8 2 ffnen einer Datei mit kword bei installiertem DBFS Gor04 25 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte KWord lt 2 gt N
138. lando Beds are burning Believer Big big girl Big trip to Portland Black coffee Bombtrack Bongo bong Book of days Break on through Broken home California dreaming amp Calling Elvis amp Cantaloop amp Car wash Catch me zi _Celehratian ceneration of Celehration s Cham ot foolz of Charmed theme sana ime Audio Dateien Powered by teien 212 Mm e 873 829 351 Byte 0 inisse 34 Version 9 0 Build 20102007 4 Abb 7 7 7 AUDIO PUBDATE Die obige Abbildung zeigt analog zu gt Abb 7 7 6 alle Audio Dateien geordnet nach Erschei nungsjahr Die untere Sektion pr sentiert alle Dateien ohne entsprechende Angabe 7 7 2 Vorteile Mit fancy fancy indexing k nnen Webserver Applikationen f r das automatische Indexieren von Dateien eine zeitgem e CSS basierte Oberfl che anbieten Mittels einer virtuellen Verzeichnis struktur kann dabei auf den erweiterten Funktionsumfang einer Library zugegriffen werden In einer weiteren Ausbaustufe kann das fancy fancy indexing zur Einbindung von strukturierten Daten und Formularen genutzt werden was die Erstellung von Web Applikationen vereinfacht Als Fallbeispiel dient ein System zur Verwaltung von bungsaufgaben den zugeh rigen L sungsvor schl gen von Studenten sowie den Bewertungen durch Dozenten Die Hierarchie der einzelnen Da tenobjekte Vorlesungen enthalten bungen die wiederum Abgaben von Studenten enthalten wird in diesem System auf virtuelle Verz
139. 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 gt Kap 2 3 und Mic rosoft OLE gt Kap 2 4 begonnen und wurde mit moderneren Systemen wie Microsoft WinFS gt Kap 2 9 fortgesetzt Andererseits wird versucht die eingangs erw hnten Schw chen physikali scher Dateisysteme gt Kap 1 durch Weiterentwicklungen oder Zusatzsoftware zu beheben Das Rufus Projekt BeFS gt Kap 2 7 und Microsoft WinFS lassen sich beiden Kategorien zuordnen 2 1 Lotus Magellan 1990 wurde von der Firma Lotus das DOS Programm Magellan als eine der ersten Desktop Suchmaschinen ver ffentlicht Moderne Desktop Suchmaschinen gt Kap 2 10 basieren noch im mer auf dem Architekturmodell das mit Magellan eingef hrt wurde Abb 2 1 1 Architektur einer Desktop Suchmaschine Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Desktop Suchmaschinen sind normale Applikationen die ber das Bet
140. llt und kann auch ausgedruckt werden Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Microsoft Word Dokument Datei Bearbeiten Ansicht Einf gen Format Extras Tabelle Fenster eee Ie oI se Abb 2 4 6 Eingebettetes Formel Objekt Ware der Formel Editor getrennt gestartet und die Formel als Datei gespeichert worden hatte die Datei als verkn pftes Objekt ins Zieldokument eingef gt werden k nnen gt Abb 2 4 4 2 4 2 Registry 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 gt Kap 2 3 1 sondern verwaltet in der Datei REG DAT im WINDOWS Verzeichnis eine Registrie rung in die sich OLE kompatible Programme w hrend der Installation eintragen Registrier Editor BE Datei Bearbeiten Hilfe Microsoft Formel E ditor 2 0 Abb 2 4 7 Registry unter Windows 3 11 2 Existierende L sungen Zu jedem Datentyp werden wichtige Informationen gespeichert vor allem m gliche Befehle print und open in der Gruppe shell sowie die zust ndige Programmdatei EQNEDIT EXE Registrier Editor Datei Bearbeiten Suchen Hilfe 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 REGEDIT EXE bearbeitet werden
141. lsweise ein Wortindex auf Basis von inver tierten Listen f r Textdokumente um ihren Inhalt zu indexieren Ein derartiger Index k nnte auch zus tzlich zu einem regul ren Slave Index f r strukturierte Attribute eingesetzt werden so dass sich die Informationen von Textdateien auf drei Indexe verteilen 126 8 Zusammenfassung und Ausblick 8 3 2 Semantisches Tagging Durch semantisches Tagging werden statt einer Liste mit Schl sselworten unterschiedliche Typen von Tags verwaltet implementiert wurden bisher Ortsangaben gt Kap 7 5 1 und eine Bewertung von Dateien gt Kap 7 5 2 Dar ber hinaus sind weitere Tags denkbar die teilweise sogar schon in anderen Umgebungen verf gbar sind Ein Beispiel ist das Taggen von Bilddateien mit Informatio nen ber dargestellte Personen wie es etwa die Community Website StudiVZ Stu07 anbietet Foto 7 von 7 Zur ck zum Album Zu Konstantin Kolls Profil Zu Konstantin Kolls Fotoalben vorheriges Foto Markierte Personen auf diesem Bild Konstantin Koll Abb 8 3 1 Tagging mit Personendaten Stu07 Ein Personen Tag bei StudiVZ besitzt mehrere Attribute u a den Namen und die Hochschule der Person und da hier nur Bilder getaggt werden k nnen auch eine X und Y Koordinate innerhalb des Bildes Die Informationen die zur Person selbst gespeichert werden k nnen um beliebige Attribute wie beispielsweise Anschrift oder Geburtsdatum erg nzt werden und enthalten im Extremfall ein
142. lt Boolean gt EP IsTapeDelay Nullable lt Boolean gt ET NetworkAffiliation String T DriginalBroadcastD ateTime Nullable lt C oF RecordingRequestld Nullable lt Guid gt ET Repeat Nullable lt Boolean gt EP Sap Nullable lt Boolean gt ER Serviceld String T StationCallSign String EP StationName String oF VideoQuality String Abb 2 9 5 WinFS Klasse System Storage Video RecordedTV 2 9 2 StoreSpy 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 29 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte StoreSpy BOCES BO 2 Allltems Documents Messages Meetings Contacts Photos Other Save Syne Photos secs I Date Taken Include subfolders E Sathlon64 DefaultStore 2 8 7 09375 Canon Powers 2 8 7 09375 Canon Powersh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon Powersh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon Powe
143. m A S Moderne Betriebssysteme Pearson Education 2 Auflage 2002 Weber R et al A Quantitative Analysis and Performance Study for Similarity Search Methods in High Dimensional Spaces Proceedings of the 24nd VLDB Conference New York 1998 http www vldb org conf 1998 p194 pdf Stand 23 10 2008 White D A et al Similarity Indexing with the SS tree Proceedings of the 12th IEEE International Conference on Data Engineering 1996 http portal acm org citation cfm id 655573 Stand 29 01 2009 Literaturverweise Wik05 Wik06 Zan82 Wikipedia WinFS http en wikipedia org wiki WinFS Stand 23 10 2008 erste Referenzierung 29 06 2005 Wikipedia Lucene http de wikipedia org wiki Lucene Stand 23 10 2008 erste Referenzierung 12 07 2006 Zaniolo C et al Database relations with null values Proceedings of the 1st ACM SIGACT SIGMOD Symposium on Principles of Databa se Systems Los Angeles 1982 http portal acm org citation cfm id 588117 Stand 13 11 2008 157
144. m Dateik rper selbst gesucht wird Ein derartiger Suchfilter ist mit SQL gar nicht bzw nur umst ndlich oder mittels propriet rer Erweiterungen zu formulieren Die Manipulation des Datenbestandes wird im Referenz Modell weder ber einen Filter noch mit tels einer Befehlssprache durchgef hrt sondern durch den Aufruf von Methoden die Domains bzw Applikationen bereitstellen gt Kap 6 1 2 6 2 2 1 Query containment Vor der eigentlichen Durchf hrung einer Dateisuche kann die Filterstruktur optimiert werden in dem Dateiformate aus der Menge Dateitypen entfernt werden die ohnehin keine Suchergebnisse liefern Diese Optimierung wird als query containment bezeichnet Mil00 also als Eingrenzen der Suche Folgender Filter verdeutlicht das Prinzip ResetFilter Setzt den gesamten Filter zur ck with Filter do begin Dateitypen dtMP3 dtVideoAVI dtQuicktime BreiteParam 640 Breite gr er oder gleich 640 Pixel HoeheParam 480 H he gr er oder gleich 480 Pixel KuenstlerParam Anastacia KuenstlerSuchmuster 2 ist end Retrieve Startet die Suche Es ist offensichtlich dass diese Suche niemals MP3s liefern wird da dieses Format als reine Audio Datei nicht ber eine Breite oder H he verf gt gt Kap 3 3 4 Daher muss f r jede im Filter gefor derte Bedingung die Menge Dateitypen mit der Menge der Formate geschnitten werden die das entsprechende Attribut berhaupt besitzen da dtMP3 keine Breite od
145. m bezeichne die Projektion der Relationenalgebra Vo 0 0er R Ao er R A0 0 gt 7Rr 0 7 0 4 5 In 4 1 wurde gefordert dass 7 den Typ aller Datenobjekte eindeutig codiert Da der Typ nach 4 2 und 4 3 durch das Objekt Schema R vorgegeben wird m ssen alle Datenobjekte aus r R densel ben Attributwert f r 7 besitzen der zus tzlich als Typbezeichner f r R angesehen werden kann Vo 0 0 E r R 0 E r R gt 7 0 7 0 4 6 Ein Library Schema L wird definiert als Menge von k Objekt Schemata R Ry deren jeweilige Attribute F und T denselben Wertebereich dom F bzw dom T umfassen Lo Book Der Datenraum Q ZL eines Library Schemas L wird durch das kartesische Produkt aller Attribute gebildet Da die Attribute F und T aber auch andere Attribute in mehreren Objekt Schemata vor kommen k nnen gt Kap 3 3 4 wird mit glob L zun chst die globale Menge aller verf gbaren dom R F SN dom R T dom R T 4 7 Attribute als Vereinigung der Objekt Schemata gebildet Jedes dieser Attribute bildet eine Dimensi on des Datenraums AL k glob L JR j l DL dom g X X dom g nc 4 8 Mit common L sei die Menge aller Attribute bezeichnet die in allen R aus L enthalten sind Diese Menge ist somit die Schnittmenge aller Rj und enth lt aufgrund 4 1 insbesondere F und T Daten objekte k nnen in Q L nur in ausgew hlten Regionen existieren partiell belegter Datenraum 59
146. m und Thema der EMail verwalten m ssen ge Eudora eBay loj x 7 File Edit Mailbox Message Transfer Special Tools Window Help 4 x I BY AB am 3 eBay 11 23 30 12 05 Sie haben den folgenden Artikel bei eBay geka eBay 17 29 04 01 06 Sie haben den folgenden Artikel bei eBay gekau eBay 16 20 05 01 06 Sie haben den folgenden Artikel bei eBay gekau serice paypal de 16 05 06 01 06 Best tigung Ihrer Zahlung eBay 01 26 09 01 06 Sie haben den folgenden Artik info tradekontor24 01 59 09 01 06 Kaufabwicklung erfolgreich abgeschlossen eBay Mitglied limo 16 21 09 01 06 lhr eBay Artikel wurde verschickt mercarimus 21 27 09 01 06 Mercarimus Best tigung des Zahlungseingang eBay 10 46 11 01 06 Verkaufter eBay Artikel Microsoft Word 97 eBay Mitglied weis 10 55 11 01 06 Ich werde die Bezahlung f r den eBay 10 43K 0K For Help press F1 Abb 4 1 Qualcomm Eudora mit ge ffnetem Postfach Wird nun mit herk mmlichen Mitteln nach Dateien mit einem bestimmten Schlagwort gesucht so w rde lediglich der Name der Datenbank Datei im Suchergebnis erscheinen in gt Abb 4 1 also die Datei EBAY MBX nicht jedoch ein individuelles Datenobjekt wie z B eine bestimmte EMail Die Begriffe Datenbank und Dateisystem werden hier angelehnt an die ANSI SPARC Archi tektur Saa05 im Sinne von gt Abb 4 2 eingesetzt eine Datenbank bzw ein Dateisystem sind logi sche Strukturen die auf einer physikalischen Ebene umgesetzt wer
147. munity Help STEE E gt Da BS te Object Explorer Ss ummary aag CARMINSSGLEXPRESS SQL Server 9 0 3042 9 Datab Seii ig Databases 59 Server Objects CARMIN SGLEXPRESS Databases 2 Item s E Replication H O Management CE System Databases Metadata Abb 3 3 8 Angelegte Datenbank Metadata Innerhalb einer Datenbank k nnen mehrere Tabellen Indexe Logs usw abgespeichert werden Der weitere Zugriff insbesondere das Anlegen einer geeigneten Tabelle und das Erstellen von Indexen wurde durch das Testprogramm in gt Kap C durchgef hrt Besonders problematisch ist die geringe Konfigurierbarkeit der Indexe Ein Index kann h chstens 16 Attribute umfassen so dass keine wirk lich hochdimensionalen Indexe gt Kap 3 3 angelegt werden k nnen New Inder EI Adding the selected columns will result in an index key with 62 columns The maximum permissible number of index key columns is 16 Abb 3 3 9 Begrenzte Indexierung max 16 Attribute Statt dessen wurden mehrere Indexe mit den jeweils maximal 16 zul ssigen Dimensionen erstellt Ein Index wurde als clustered index angelegt Prim rindex der die physikalische Sortierung be einflusst alle anderen Indexe waren unclustered In dieser Konfiguration wurde die Ausf h rungszeit f r die f nf Suchanfragen durch ein Testprogramm ermittelt Als Hauptaussage ist dabei zu treffen dass eine Suche mit Index l nger dauert als ohne
148. n 6 3 5 Komprimierter Master Slave Index Da die Performanz des Master Slave Index vor allem von der Geschwindigkeit des Datentr gerzu griffs abh ngt kann die Leistung durch Verringern der zu lesenden Datenmenge gesteigert werden In diesem Zusammenhang ist die verlustfreie Kompression der Indexdateien besonders interessant Die Index Tabellen eines Master Slave Index werden ausschlie lich sequenziell verarbeitet so dass der Dateizeiger niemals neu positioniert werden muss Dadurch k nnen die Datenstr me transparent vor der Verarbeitung dekomprimiert und bei nderungen wieder komprimiert werden Eine Komprimierung mit PKZIP Deflate Methode basierend auf dem LZ77 Algorithmus und Huffman Codierung erzielt einen Kompressionsfaktor von 16 1 was einer Steigerung der Ge schwindigkeit um Faktor 10 entspricht Der Zeitverbrauch f r das Bearbeiten eines komprimierten Master Slave Indexes w chst nach wie vor linear mit der Dateigr e zus tzlich hat das Initalisieren des Dekomprimierers einen konstanten Zeitbedarf 91 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 10000 ms 1 10 100 Dateien in Tausend 1102 3 4 5 Abb 6 3 5 Laufzeiten mit komprimiertem Master Slave Index Kol08c 6 4 Vorteile Die hier vorgestellte Referenz Library basiert auf dem Datenmodell einer Library gt Kap 4 bzw implementiert dieses wodurch alle in Abschnitt gt Kap 4 4 genannten Vorteile wie einheitlicher Zugriff
149. n Verkaufer Zu meinen bevorzugten Verk ufern hinzuf gen Andere Artikel des Verk ufers Sicher kaufen 1 Sehen Sie sich das Bewertungsprofil des Verk ufers an Bewertungspunkte 430 99 1 Positiv Bewertungskommentare lesen 2 Informieren Sie sich ber den K uferschutz Kostenloser K uferschutz Paypal Wenn Sie PayPal verwenden sind Ihre K ufe bei erg eBay bis zu 500 EUR abgesichert Mehr zum Thema Abb 7 1 4 WWW Seite mit flexiblem Layout f r einzelne Befehle Die Darstellung von Programmen und Dateien als Link innerhalb einer Menuseite ist einfach zu realisieren F r lokale Dateien definiert HTML das URL Schema RFC3986 file so l sst sich eine Applikation durch Verlinkung der ausf hrbaren Bin rdatei einbinden lt A HREF file C Programme Picture Publisher PP50 EXE gt Picture Publisher lt A gt starten Abb 7 1 5 Darstellung eines Programms als HTML Link F r Optionen die nicht mit einer lokalen Datei verbunden werden k nnen kann ein propriet res URL Schema wie menu eingef hrt werden das f r den Anwender unsichtbar bleibt und nur vom systemeigenen Browser im Shell Modus verstanden wird Um die bersicht einer Menuseite weiter zu erh hen wurde in der Referenz Shell ein Mechanis mus implementiert der Menupunkte gruppiert und zu Sektionen zusammenfasst Wird HTML zur Definition des Menus verwendet k nnen Sektionen auch au erhalb von Menuseiten in anderen Dokumenten durch Einf
150. n besonderen Verzeichnissen wie Eigene Dateien Eigene Bilder aktiv und das auch nur innerhalb des Explorers 115 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Keine Markierung Systemaufgaben Systeminformationen anzeigen T Software D Eine Einstellung ndern Andere Orte SJ Netzwerkumgebung CO Eigene Dateien KH Gemeinsame Dokumente amp Systemsteuerung Details Arbeitsplatz Systemordner Abb 7 6 1 Systemaufgaben von Windows XP Keine Markierung Yideoaufgaben D Ale wiedergeben Li Alle Elemente auf CD kopieren Datei und Ordneraufgaben J Neuen Ordner erstellen Ordner im Web ver ffentlichen Ki Ordner freigeben Andere Orte Gemeinsame Dokumente E Eigene videos d Arbeitsplatz SJ Netzwerkumgebung Details Gemeinsame Videos Dateiordner Ge ndert am Samstag 19 August 2006 08 43 Abb 7 6 3 Videoaufgaben von Windows XP 116 Verzeichnis markiert Videodatei markiert Datei und Ordneraufgaben C Neuen Ordner erstellen Ordner im Web ver ffentlichen KI Ordner freigeben Andere Orte d Arbeitsplatz CO Eigene Dateien O Gemeinsame Dokumente Si Netzwerkumgebung Details Dateien von Besitzer Dateiordner Ge ndert am Heute 23 September 2006 10 16 Yideoaufgaben gt Alle wiedergeben Auf CD kopieren Datei und Ordneraufgaben Datei umbenennen L Datei verschieben Datei kopieren Datei im web ver ffentlichen
151. n versucht diesen Effekt zu minimieren indem nicht alle Attribute indexiert werden gt Abb 3 2 2 Zus tzlich dege neriert die Zugriffsgeschwindigkeit von Baumstrukturen wenn sie auf mechanischen Festplatten gespeichert werden da hier der Zugriff auf verteilt gespeicherte Datenbl cke besonders zeitauf w ndig ist gt Kap 3 3 3 Dieser Effekt hat Benoit Schillings einer der Entwickler von BeFS in einem Interview zu folgender Aussage veranlasst And didn t use B Trees thought B Trees were evil and still do Reading them is slow and super expensive Reading big blocks is actually more efficient than using B Trees on modern hardware Abb 3 2 3 Windows on a database sliced and diced by BeOS vets Reg02 3 3 Multidimensionale Indexierung Ein zentrales Problem relationaler Datenbanksysteme ist das multidimensionale Indexieren also das Indexieren mehrerer Attribute in einer einzigen Datenstruktur Dieses Problem betrifft auch Datei systeme da Metadaten aus zahlreichen Attributen bestehen bei vollst ndiger Implementierung des Exif EXI07 und ID3 Standards Nil05 wird ein Datenraum mit mehr als hundert Dimensionen erzeugt der damit nicht nur multi sondern sogar hochdimensional ist Auf derartig beschaffene Daten und zugeh rigen Indexen k nnen im Sinne der Datenbanktechnik verschiedene Klassen von Operationen in der Regel Suchanfragen angewandt werden Partial Match FullMatch nee Beer Werten in allen
152. namen 3 Existierende Indexe Weitere Informationen zu den einzelnen Attributen folgen in der entsprechenden Unterdatei En dung fdt direkt aufeinander Eine Trennung ist nicht erforderlich da der Feldindex Endung fdx f r jede Datei Zeiger auf die entsprechenden Daten verwaltet earbeiten Hilfe Speichern Alt P Opt ionen ec6ble82 04bb 1 1db 944b 61589b3 fcb2dt filed v npr gt 3 9zicinyfrObim gt 001 BMP 001 DN PA IC Eigene Da Te len DR 4 C Eigene Dateie nf 921 ciny9dgdyo 21 06 20060 1536 g E31 efile N filet filety pel Sfilet file typet tbmpT Jif il e picturel Mi let picturet b np bf ile inde xdateN tf ilet i ndexdatet 20061 filet indexda te 2006 061 If ilet indexdat et 20061 061 261 filet date Schl ie en Gelb hervorgehoben L ngenbyte vor Zeichenketten Rot hervorgehoben MIME Typ Dateil nge und Aufl sung Abb 3 1 5 Felddaten einer Bilddatei 39 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 3 1 2 Performanz Invertierte Listen wie sie Lucene verwaltet sind problematisch f r den Einsatz in Desktop Suchmaschinen da nderungen am Dateisystem sehr umfangreiche Aktualisierungen des Indexes implizieren Saa05 Besonders zeitaufw ndig ist die komplette Neuindexierung des Dateisystems Beagle implementiert den Indexer daher als Leerlauf Prozess wodurch sich das System zwar nicht verlangsamt eine volls
153. ng des Modells das Problem der Mehrfachvererbung die von vielen Program miersprachen nicht unterst tzt wird Da aber zu jedem Zeitpunkt h chstens eine Datei pro Applika tions Objekt aktiv ist ist auch nur der Zugriff auf die Methoden eines einzigen Domain Objekts er forderlich Daher kann die Mehrfachvererbung durch dynamisches Linken realisiert werden 6 1 3 Registry Die eigentliche Referenz Implementierung verwaltet eine begrenzte Anzahl vorher definierter Da teiformate gt Kap 6 2 1 sie ist also statisch Im Gegensatz dazu muss f r praktische Anwen dungen die Erweiterbarkeit sichergestellt werden es m ssen also nachtr glich neue Datentypen Domains und Applikationen hinzugef gt werden k nnen Aus diesem Grund ist in der Architektur eine Registry vorgesehen die analog zur Registry von Microsoft OLE gt Kap 2 4 2 funktioniert Neben einer Liste aller Dateiformate enth lt die Registry f r jeden Dateityp eine Liste mit Domains die das jeweilige Dateiformat enthalten k nnen Dar ber hinaus werden f r alle Dateiformate die Applikationen die das jeweilige Format ffnen k nnen registriert 6 2 Implementierung In diesem Abschnitt werden zwei wichtige Teilbereiche der Referenz Implementierung pr sentiert der Namensraum gt Kap 6 2 1 und die Suche nach Dateien mit bestimmten Eigenschaften gt Kap 6 2 2 6 2 1 Namensraum Das Datenmodell einer Library gt Kap 4 1 schreibt f r jedes Objekt Schema R die Attri
154. nly Dale X Recycle Bin x C Nothing do not index Maximum file size for content indexing Generally excludes large graphical files also applies to attachments EY gt Megabvtecs D Specify Extensions OK Cancel Abb 2 10 7 Indexierungs Optionen bei Yahoo Desktop 35 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 2 11 Fazit Die Analyse verschiedener Systeme in diesem Kapitel dokumentiert die Anstrengungen die zur Verbesserung physikalischer Dateisysteme unternommen wurden Sie lassen sich soweit zutreffend bez glich der Einbindung von Applikationen den Verbesserungen an der Organisation des Datei systems sowie anhand der eingesetzten Indexe bewerten Einige L sungen versuchen Dateien zusammen mit den zugeh rigen Applikationen in eine objekt orientierte Gesamtarchitektur einzubinden gt Kap 2 3 wozu als Grundlage alle Dateiformate mit ihren spezifischen Eigenschaften vom Betriebssystem registriert gt Kap 2 4 werden m ssen Da heterogene Dateiformate unterschiedliche Attribute und Operationen unterst tzen muss der Typ ei ner Datei sicher festgestellt werden k nnen Hierzu sind Dateiendungen nur bedingt geeignet da sie vom Benutzer ge ndert werden k nnen gt Abb 4 4 4 Ebenso ungeeignet sind die Klassifizierer des Rufus Projekts gt Abb 2 3 1 da sie den Typ einer Datei nicht sicher ermitteln K nnen Die Microsoft Indexerstellung gt Kap 2 5 zeigt als Bes
155. nvermeidlichen Leistungseinbu en den Speichermedien bei wahlfreiem Zugriff im Gegensatz zu sequenziellem Zugriff haben verringert auch das verwendete physikalische Datei system die Zugriffsgeschwindigkeit je nach Typ drastisch Wird zum Beispiel ein B Baum innerhalb einer Datei gespeichert h ngt die Traversierungsge schwindigkeit zus tzlich davon ab mit welchem Zeitaufwand der Dateizeiger auf eine neue Stelle der Indexdatei bewegt werden muss ltere Dateisysteme wie FAT die Datenbl cke linear verket ten verlangsamen das Traversieren eines Baums um O n auf O n log n w hrend bei ext2 ein Da teizeiger durch eine mehrstufige Blockadressierung Kol07b in konstanter Zeit positioniert werden kann Diese Abh ngigkeit von der Leistung des physikalischen Dateisystems stellt schon seit l ngerer Zeit ein Problem dar Datenbanksysteme operieren daher oft auf unformatierten Speichermedien ohne Dateisystem wodurch ein wahlfreier Zugriff auf beliebige Sektoren nur vom verwendeten Daten tr ger abh ngt gt Kap 3 3 3 1 49 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 3 3 4 Partiell belegter Datenraum Eine besonders n tzliche Eigenschaft des Datenraums den Dateiattribute bilden wird von multidi mensionalen Indexstrukturen bisher nicht explizit unterst tzt sie gehen in der Regel davon aus dass sich ein Objekt an jedem Punkt im Datenraum Q befinden kann Speziell bei der Metadaten Indexierung ist dies
156. nvoll aufzubereiten In einem ersten Schritt kann der Anwender eine Sortierreihenfolge f r die dargestellten Dateien w hlen beispielsweise alphabetisch oder auf bzw absteigend nach Dateizeit oder Dateigr e Da durch werden beispielsweise aktuell in Arbeit befindliche Dateien weit oben gezeigt und damit schnell gefunden Hat der Benutzer eine Sortierung ausgew hlt wird deshalb die Checkbox Ord ner bilden aktiv 107 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte GEBE Ansicht Bilder 118 58 Standard benutzen bbrechen FF GG Sort ieren Angaben Nicht sortieren ET Alte zuerst gt Ruf nahme Fa Neue zuerst Kurze zuerst t Gr e E Longe zuerst K nstler Ort Ordner bilden Attribut WS nzeige Liste Dateityp E Kacheln bk Details WS Relatives Datum i K nstler Fe Liste Titelleiste u Ob jekt ID Ei Abb 7 4 1 Fenster Ansicht des Datei Managers Mit ihr werden in einem zweiten Schritt Dateien bez glich des gew hlten Sortierkriteriums grup piert und als Unterverzeichnis dargestellt gt Abb 7 4 3 2 Bilder und Texturen Benutzerdateien Korfu 32 187 12 08 2003 21 Dynasnische Skins Korfu Ka 12 08 2003 21 CG Fee 626 83 04 2005 17 58 Korfu 5 12 08 2003 21 D Fees 24 Geburtstag Korfu R Sg 12 08 2003 21 Fees 25 Geburtstag Korfu d s 12 08 2003 21 E ineare Chips R d 29 03 2005 01 33 Korfu SEN 12 08 2003 21 Korfu Ge CH S
157. oft tee Gegebenheeten 13 Zah DEP none se E es len see 14 24 2 EE 16 2 4 3 Objekt MAng g t u 17 25 Microsoft Tockert sauna ee 18 2 6 Microsoft Windows Explorer nee ee 19 e SE 21 2 7 1 BersetzeT E 21 E EE 22 2 43 Suchfunktion anenierienie 23 2 DEIN ser lernen 24 2 9 Microso 14 Ee 27 ES WinFS EE 28 KE 29 2 10 Moderne Desktop Suchmaschinen u a aa 31 2 10 1 Linux Beagle u 31 EE E E ARE een 32 2 102 Google EEN 34 2 40 4 Geet 35 PR TBB Cid EE 36 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 3 Existierende Indlexe en rsneineienne EI EEE EEE EN Eee 37 S e EE 37 34 4 Compound File System rer 37 3412 Perfomanzu au 40 32 Een 40 Sled E 42 3 22 DEI EE 42 3 3 Multidimensionale Indexierune uuensesse a a a 43 3 3 1 Der Fluch der Dimensionene uud ai 44 3 3 2 Partial E 47 3 3 3 Ineffizienz von persistent gespeicherten B umten 48 3 3 4 Partiell ee EES 50 33 9 VEER 5I SE E 55 WW dassos asi v ras ssrt ESSO Vo SEET VES SEVES SE T SEO sisses aE sks ESt 57 BN EE 58 4 2 ENEE EN een ee 60 4 2 1 BLOB relationale Datenbanken sense anne 61 Ze Zu alii 2 01 ane eee NENNE Poem ECE SEHWEHEREFUFENER EETLEEEEPEEENEERLLTUELNENPERLT NERTEENEEEHELUEENERTEREEHENUERDESERREER 62 43 1 Abbodungsvorschnit energie heise 62 4 3 2 Semantische EN 63 I e E 64 BAT E 65 442 e 66 44 3 Typsicherheit EE 66 44 4 e 67 KEE TE 69 e NI EE 69 5 1 1 ee EE Eege geet eebe 69 Dudek
158. orf Boulen Bramsche 2002 Bramsche 2003 City square Dar ias Abschied David in Frankfurt Dissertation Vortrag 1 Dissertation Vortrag 2 Dynasnische Skins Fee Fees 24 Geburtstag Fees 25 Geburtstag Fees 27 Geburtstag Jindra Jindra in Dortmund Jindras 25 Geburtstag Jindras 25 Geburtstag Jindras Selbstprasentat ion Jindras Selbstprasentat ion Keith Haring Keith Haring An ja Atoll Ausflug nach D sseldorf Boulen Bramsche 2002 Bramsche 2003 City square Dar ias Abschied David in Frankfurt Dissertation Vortrag 1 Dissertation Vortrag 2 Dynasnische Skins Fee Fees 24 Geburtstag Fees 25 Geburtstag Fees 27 Geburtstag Jindra Jindra in Dortmund A NIE EEE OOU ES ES EI Abb 7 6 5 Typspezifische Dateibefehle 7 6 1 Vorteile Durch die Aufgabenorientierung werden dem Benutzer nur diejenigen Befehle gezeigt die auf die gerade markierten Dateien anwendbar sind Da in der Referenz Library die f r den Benutzer rele vanten ffentlichen Methoden f r alle Dateien bekannt sind l sst sich die Aufgabenorientierung leichter umsetzen und zwar einheitlich in allen Anwendungsprogrammen 7 7 Webserver Die Verwendung einer Library als Speichersystem impliziert Verbesserungen an anderen Program men die dies zun chst nicht vermuten lassen Ein Beispiel hierf r sind Webserver also diejeni gen Programme die eingehende HTTP Anf
159. orhanden 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 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Microsoft OLE greift nicht tief ins Betriebssystem ein sondern stellt f r OLE kompatible Anwen dungen lediglich eine Registrierung aller anderen OLE Anwendungen gt Kap 2 4 2 und ein ent sprechendes API zur Verf gung Mit dem Objekt Manager gt Kap 2 4 3 steht au erdem ein Hilfsprogramm zur Verf gung Abb 2 4 1 OLE Architektur 2 4 1 Beispiel Als Zieldatei soll ein einfaches Word Dokument dienen Microsoft Word verf gt nat rlich ber OLE F higkeiten Microsoft Word Dokument Datei Bearbeiten Ansicht Einf gen Format Extras Tabelle Fenster te ar euren Word TextT 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
160. ovider PostgreSQL Data Source localhost password E61534S User ID ROOT location Metadata conn Open Console WriteLine done Alte Tabelle entfernen OleDbCommand cmd new OleDbCommand DROP TABLE Test conn try cmd ExecuteNonQuery catch 143 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 144 Neue Tabelle erstellen cmd new OleDbCommand CREATE TABLE Test FileTyp int FileBez varchar 31 FileKey varchar 8 FileSize int FileTime varchar 20 FileNew int FilePassword varchar 15 FilelATA int VIDFourCC varchar 4 VIDL int VIDH int VIDVideoDecoder int VIDAudioDecoder int VIDCreationYear int VIDCreationMonth int VIDCreationDay int VIDCompressedHeader int VIDMultiStreams int VIDArtist varchar 31 VIDComment varchar 31 VIDThema varchar 31 VIDVideoTitel varchar 31 VIDFirmware varchar 31 ID3Artist varchar 30 ID3Trackname varchar 30 ID3Albumname varchar 30 ID3Comment varchar 30 ID3Year varchar 4 ID3Genre int IMGL int IMGH int IMGFarbmodus int IMGCreationTime varchar 5 IMGCreationYear int IMGCreationMonth int IMGCreationDay int IMGEquipment varchar 127 IMGBelichtung varchar 127 IMGFirmware varchar 127 IMGTitel varchar 127 IMGCop
161. p 6 2 1 erzeugt wird der Benutzer kann also erwarten dass die entsprechende Applikation auf dieser Unterseite aufgef hrt wird Gleichzeitig ist das Verfassen von EMails eine wichtige Funktion heutiger Computersysteme so dass diese Option noch einmal auf der Hauptseite in der Sektion Nachrichten angeboten wird gt Abb 7 1 11 Die drei Sektionen B ro System und Wissenschaft werden auf gleiche Weise auf der Menu seite Vorhandene Dateien zeigen ndern gt Abb 7 1 10 benutzt typbasierte Filter stellen also die prim re Zugriffsm glichkeit auf die Library dar Dieses Vorgehen erscheint besonders sinnvoll da sich der Benutzer fast immer an den Typ einer gesuchten Datei wie Audio Datei oder Bild erinnert Auf der Menuseite Vorhandene Dateien zeigen ndern sind auch Dateitypen aufgef hrt die nicht vom Benutzer erzeugt sondern vom Betriebssystem automatisch verwaltet werden Darunter fallen z B Hilfethemen der Online Hilfe oder Spiele Highscores 101 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte ur ck oru rts nfang DESKWORK 8 1 ROOT Sienna ee Willkommen Vorhandene Dateien zeigen ndern m Adressen Audio Dateien LP Playlists Bilder E Diashous B Dokumente DI EMails h B SMS OC Termine Videos Systen Archive of Audio CDs og CD DVD Sitzungen oY DOS Programne 2 Hilfethemen B Layouts Dy Schriftarten 2 Spiele Highscores pall
162. peters versehen wurde Talking outside on Flickr Photo Sharing Opera 5 x Datei Bearbeiten Ansicht Lesezeichen Widgets Feeds Extras Hilfe CH r H GO P A A eo http flickr comphotos progrium 3862951 30 2 E jas 100 L flickr arent signe Sign In Help Home The Tour Sign Up Explore Search everyone s photos 1 Search Talking outside Uploaded on February 10 2007 by progrium progrium s photostream nickpeters Additional Information akel Canon PowerShot SD550 More properties aken on February 3 2007 Would you like to comment k publik Sign up for a free account or sign in if you re already a member Abb 7 5 1 Bild mit Schl sselworten bei Flickr Fli07 Das Datenmodell einer Library gt Kap 4 1 gestattet beliebige Attribute innerhalb eines Objekt Schemas so dass Tagging durch Hinzuf gen eines geeigneten Attributs zu allen Objekt Schemata f r alle Dateiformate unterst tzt werden kann Ebenso k nnen auch mehrere Attribute mit unter schiedlichen Bedeutungen und Wertebereichen eingef hrt werden wodurch im Gegensatz zur ein fachen Auflistung von Schlagworten ein semantisches Tagging implementiert wird In diesem Abschnitt werden zwei in der Referenz Library gt Kap 6 implementierte Tag Typen vorgestellt 110 7 Interaktion 7 5 1 Geotagging Der Exif Standard EXIO07 f r die Einbettung von Metadaten in Bilddateien definiert zwei Attribu te f r GPS Koordinaten Von hochwertigen
163. prsp_ MP3 Rot hervorgehoben ungleiche Reihenfolge Gr K g A Bilder Index MP3 Index Filekey Filekey Z6 HG7E Lee JGUIP7 D LL9 ACX1 30 KUY Abb 5 1 8 Nach dem L schen Die in gt Abb 5 1 8 rot hinterlegten Eintr ge befinden sich nun in ihren jeweiligen Relationen nicht mehr in derselben Reihenfolge zueinander so dass ein Merge Join die falschen Tupel verbinden w rde Im Master Index hat der Eintrag mit dem Schl ssel 30_KUIXY den Eintrag f r LL9 ACX1 berholt was im Slave Index nicht erfolgt ist die Merge Eigenschaft ist f r diese beiden Tupel nicht mehr erf llt 5 1 5 2 L schen von Dateien korrekt Um die Merge Eigenschaft zu erhalten m ssen Tupel durch Aufr cken der Nachfolger aus den In dex Relationen gel scht werden 75 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte gt EENEN Abb 5 1 9 L schen eines Tupels durch Verschieben Die Laufzeit einer korrekten L schoperation betr gt immer O n da alle nachfolgenden Tupel ver schoben werden m ssen 5 1 6 Massen Operationen Der Master Slave Index hat bei nderungs und L sch Operationen lineare Laufzeit was beim Ein satz eines effizienten Dateisystems wie z B ext2 eine partielle Verschlechterung bedeutet gt Abb 5 2 2 Das Ver ndern von Attributwerten und L schen einer Datei ist in diesem Fall nicht mehr in O log n sondern nur noch in O n m glich D
164. pt 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 2 3 1 Klassifizierer 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 2 Existierende L sungen 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 2 3 2 Objekte 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
165. r Domain ge speichert Der einer Domain zugeordnete Programmcode gt Kap 6 1 2 2 realisiert den Dateizu griff f r Applikationen indem das physikalische Dateisystem virtualisiert und f r das Datenmodell der Library aufbereitet wird Kol08b Viele Dateiformate etwa f r Adressen RFC2425 oder Termine RFC2445 bestehen nur aus we nigen Attributen und weisen oft keinen Dateik rper auf Datenobjekte dieser Formate sind kleine Tupel uniformer Gr e Die Referenz Library sieht f r derartige Dateien Domains vor die alle Tu pel eines Typs in einer einzigen Heap Datei im physikalischen Dateisystem zusammenfassen je nach Dateiformat beispielsweise ADRESSEN DAT oder TERMINE DAT Der Zugriff auf einzelne Datenobjekte wird vom zugeh rigen Programmcode gt Kap 6 1 2 2 transparent auf die jeweilige Heap Datei abgebildet Kol08b Auf diese Weise wird kein Speicherplatz in Dateisystemen ver schwendet die zur Verbesserung der Schreib und Leseperformanz gro e Zuordnungseinheiten ein setzen sollten Kol08a Datenobjekte mit Dateik rper werden in anderen Domains direkt auf Dateien des physikalischen Dateisystems abgebildet Attribute die weder das physikalische Dateisystem noch das jeweilige Da teiformat im Dateik rper als Metadaten deklarieren werden in Headern gespeichert die jeder Datei 82 6 Referenz Library vorangestellt werden Dies geschieht transparent da f r Applikationen durch Addition der Header gr e zum Dateiz
166. r GREP gt Kap 6 3 2 deutlich geringer da die Referenz Library die jeweiligen Dateiformate korrekt parsen kann und nur diejenigen Bereiche einliest die tats chlich relevante Metadaten enthalten Auf diese Weise ergibt sich eine etwa hundertfache Ge schwindigkeitssteigerung gegen ber GREP 1000 s 100s Dateien in Tausend 11 82 3 4 5 Abb 6 3 3 Laufzeiten ohne Indexierung Kol08c Die Laufzeit ist im Wesentlichen von der Anzahl der Dateien abh ngig so dass die Testf lle linear skalieren Da die Verzeichniseintr ge von NTFS in einem B Baum gespeichert werden ist theore tisch eine Laufzeit von O n log n zu erwarten Die Verzeichniseintr ge werden aufgrund des h ufi gen Zugriffs jedoch im RAM gecacht so dass hier kaum Bl cke von der Festplatte gelesen werden 6 3 4 Master Slave Index Im n chsten Schritt wurde die Referenz Library um einen Master Slave Index erweitert Wiederum wurden alle f nf Suchanfragen auf verschieden gro en Datenbest nden bearbeitet Gegen ber einer Implementierung ohne Indexierung ist eine deutliche Steigerung der Geschwindigkeit messbar wiederum etwa um Faktor 100 90 6 Referenz Library 1 10 100 Dateien in Tausend 1102 3 EE Abb 6 3 4 Laufzeiten mit Master Slave Index Kol08c Das Bearbeiten des ersten Testfalls hat einen besonders geringen Zeitaufwand da das zu pr fende Attribut im Master Index gespeichert wird und daher keine Slave Indexe bearbeitet werden m s se
167. r Nutzer seine Fotos einsortiert 3 5 Diskette I GH Fotos C Geburtstage Anton I Berta I Christian CI Doris LC Emil CT Urlaub Spanien I Ibiza I Mallorca C Teneriffa GC T rkei I Antalya Bodrum 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 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 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 ode
168. r noch der urspr nglich mit Lotus Magellan eingef hrten Architektur gt Abb 2 1 1 obwohl mittlerweile fast 20 Jahre vergangen sind Viele dieser L sungen stehen f r diverse Be triebssysteme Mac OS X Linux Windows zum kostenfreien Download bereit oder sind sogar quelloffen e Aduna Autofocus e diskMETA Pro http aduna biz products autofocus http www diskmeta com e Apple Spotlight gt 2 10 2 e Google Desktop gt 2 10 3 http www apple com macosx features spotlight http desktop google com e Ask Desktop e Microsoft MSN Toolbar http sp ask com docs desktop http toolbar msn com e Beagle gt 2 10 1 e Strigi http beagle project org http strigi sourceforge net e Copernicus Desktop Search e xfriend http www copernic com http www x friend de e dtSearch Desktop e Yahoo Desktop gt 2 10 4 http www dtsearch com http desktop yahoo com Da sich Desktop Suchmaschinen sehr gleichen werden in den folgenden Abschnitten nur die Be sonderheiten einiger Suchmaschinen exemplarisch vorgestellt 2 10 1 Linux Beagle Mit dem Beagle Projekt steht auch fiir Linux eine leistungsfahige Desktop Suchmaschine auf Open Source Basis zur Verf gung Beagle arbeitet wie blich mit einem Index der automatisch ak tualisiert wird wenn der Linux Kernel so compiliert wurde dass er die Funktion inotify unterst tzt Benachrichtigung wenn nderungen am Dateisystem vorgenommen wurden
169. r 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 1 1 Zielsetzung und berblick 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 gt Kap 1 1 1 Indexierung gt Kap 1 1 2 und Interaktion gt 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 Referenz Library gt 6 Integration von Datenbarken und Verbesserte Interaktion gt 7 Indexierung durch Master Slave oos Leer Joins Benutzerdef Automatische Semantisches Aufgaben Fancy fancy Suenfilter Ordn ner Tagging ern indexing S ne 4 SIA E ins E AE 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
170. rSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon Power h 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon PowerSh 2 8 7 09375 Canon Power h 2 8 7 09375 Canon Powersh LastModiicationTime 21 09 2004 23 18 32 CG 1 CreationTime 13 09 2005 21 09 41 Be ENS e Itemid 11f23bb2 9524 da11 3454 001121891239 2 8 7 09375 Canon PowerSh NamespaceName 105_0634 JPG j ShelPath VE DEER 2 8 7 09375 Canon PowerSh ItemSize 2 8 7 09375 Canon PowerSh beienee 2 8 7 09375 Canon PowerSh MediaCatalogNumber 2 8 7 09375 Canon PowerSh MediaClassSecondar MediaClassPrimaryld 2 8 7 09375 Canon PowerSh ProtectedType I T Protected 4 9 21 3125 Canon PowerSh OriginalPhysicalld 4 9 21 3125 Canon PowerSh MetadataProviderName null T T T MetadataProviderCop null 2 8 7 09375 Canon PowerSh Period null 2 8 7 09375 Canon PowerSh Abb 2 9 6 StoreSpy Die Liste der angezeigten Dateien wird dabei ohne R cksicht auf m gliche Unterverzeichnisse er zeugt und auch Metadaten werden angezeigt Das Ergebnis kann nach Typgruppen Documents Photos weiter gefiltert werden Das Besondere an WinFS liegt
171. ragen beantworten Die Verbesserungen an diesen An wendungen werden in diesem Abschnitt u a anhand des sehr verbreiteten Apache HTTPD Apa07 gezeigt Wird ber das HTTP Protokoll eine URL angefordert die keine Datei bezeichnet sondern ein Unterverzeichnis so wird im einfachsten Fall vom HTTPD eine Fehlermeldung zur ckgesendet 117 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 1403 Forbidden Opera Datei Bearbeiten Ansicht Lesezeichen Widgets Feeds Extras Hilfe N es A http Awww deskwork de STUFF Forbidden You don t have permission to access STUFF on this server Additionally a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request Apachell 3 Server at www deskwork de Port 80 Abb 7 7 1 Zugriff auf ein Verzeichnis ohne Indexierung durch den Webserver Wenn der Administrator den HTTPD entsprechend konfiguriert hat so wird gleichsam als beson derer Service vom Webserver in Echtzeit eine Liste aller im entsprechenden Ordner vorhandener Dateien und Unterverzeichnisse erzeugt und ausgeliefert Index of STUFF Opera Datei Bearbeiten Ansicht Lesezeichen Widgets Feeds Extras Hilfe z e o N A Je http www deskwork de STUFF Index of STUFF e Parent Directo e IATA TXT e Yellowstone gif Apache l 3 Server at www deskwork de Port 80 Abb 7 7 2 Zugriff auf ein Verzeichnis mit einfacher Indexierung durch den
172. rated security SSPI objXBL ErrorLogFile SQLXML3Books errlog objXBL Keepldentity false objXBL Execute J Dokumente und Einstellungen ROOT Eigene Dateien DISS SRC METADATA XSD J Dokumente und Einstellungen ROOT Eigene Dateien DISS SRC METADATA XML Console WriteLine Load sw Peek 10 0 ms Testfall 1 sw Reset cmd new SqlCommand SELECT FROM Test WHERE FileNew 1 conn SqlDataReader r cmd ExecuteReader r Read r Close Console WriteLine Case 1 sw Peek 10 0 ms Testfall 2 sw Reset cmd new SqlCommand SELECT FROM Test WHERE FileTyp 6 OR FileTyp 15 OR FileTyp 26 OR FileTyp 34 conn r cmd ExecuteReader while r Read r Close Console WriteLine Case 2 sw Peek 10 0 ms Testfall 3 sw Reset cmd new SqlCommand SELECT FROM Test WHERE FileTyp 5 OR FileTyp 7 OR FileTyp 23 OR FileTyp 32 conn r cmd ExecuteReader while r Read r Close Console WriteLine Case 3 sw Peek 10 0 ms Testfall 4 sw Reset cmd new SqlCommand SELECT FROM Test WHERE FileTyp 6 OR FileTyp 15 OR FileTyp 26 OR FileTyp 34 AND IMGL gt 1024 conn r cmd ExecuteReader mas r Read r Close Console WriteLine Case 4 sw Peek 10 0 ms 141 Integration Indexierung und Interaktion hochdimen
173. riebssystem 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 e Ascii Text e Lotus Agenda e Microsoft Word e Quicken e CompuServe e Lotus Manuscript e Multiplan e Quattro Pro e dBase e Lotus Symphony e Paradox e WordPerfect e GIF e LotusWorks e PCX e Wordstar e Lotus 1 2 3 e Microsoft Excel e Quark Express 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 gt Kap 2 10 veranschauli chen die ausnahmslos nach demselben Prinzip arbeiten 2 1 1 Arbeitsweise 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 nd
174. rithmus zu existieren der sowohl die Laufzeit auf poly d und den Speicherbedarf auf poly nd begrenzt Dieses Ph nomen ist als Fluch der Dimensionen be kannt Bor99 3 3 1 2 Partitionierung des Daten bzw Objektraums Durch die Wichtigkeit hochdimensionaler Datenr ume f r praktische Anwendungen wurde in der Vergangenheit intensiv nach Datenstrukturen und Algorithmen geforscht die die Vorteile der beiden Extreml sungen vereinen sollen Dabei f llt auf dass vor allem das sequenzielle Scannen aller Ob jekte bei geschickter Implementierung eine berraschend gute Performanz bietet und unter be stimmten Voraussetzungen sogar optimal f r gro e d ist Web98 45 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Indexstrukturen die den Daten bzw Objektraum partitionieren degenerieren mit zunehmender Dimensionszahl so dass die Partitionen zunehmend gro e Volumina enthalten und sich daher stark berlappen Dadurch m ssen sehr viele Objekte betrachtet werden so dass die Partitionen letztlich doch sequenziell gescannt werden zus tzlich zum Aufwand der durch die Partitionierung verur sacht wird etwa das Traversieren eines Baums Ber96 schl gt daher einen modifizierten R Baum vor den X Baum extended node tree bei dem derartig degenerierte Baumknoten absichtlich durch lineare Listen supernodes ersetzt und dann sequenziell durchsucht werden The X tree may be seen as a hybrid of a linear
175. rkumgebung Details Beispielmusik Dateiordner Ge ndert am Dienstag 1 August 2006 17 09 Audiodatei markiert Musikaufgaben gt Alle wiedergeben Musik online kaufen Auf Audio CD kopieren Datei und Ordneraufgaben m Datei umbenennen L i Datei verschieben IDN Datei kopieren Q Datei in E Mail versenden X Datei l schen Andere Orte CN Gemeinsame Musik a Eigene Musik d Arbeitsplatz 2 Netzwerkumgebung Details A New Stories Highway Blues wma Gr e 742 KB Windows Media TM Audio Interpret Marc Seales composer New Stories Ernie Watts saxophone Albumtitel Speakin Out Jahr 1999 Titelnummer 1 Dauer 00 01 33 Abb 7 6 4 Musikaufgaben von Windows XP 7 Interaktion Der Datei Manager der Referenz Library fragt die ffentlichen Methoden f r alle markierten Datei formate ab und stellt die Schnittmenge der Befehlsmengen als Schaltfl chen dar In gt Abb 7 6 5 zeigt die linke Spalte die Befehle ffnen und Bearbeiten die f r einen automatischen Ordner gt Kap 7 4 verf gbar sind Besteht die Auswahl aus Bildern kommen weitere Befehle hinzu Diashow ist beispielsweise nur f r Bilder verf gbar und erzeugt mit dem entsprechenden Prog ramm automatisch eine Pr sentation aus allen markierten Bilddateien 24 Geburtstag 28 Geburtstag 24 Geburtstag 28 Geburtstag Abschlussvortrag Diplom Airbus A320 Enhanced An ja Atoll Ausflug nach D sseld
176. rogramm gt Kap B auf verschiedenen Datentr gern mechanischen Festplatten und Flash Speichern unter sucht F r beide Zugriffsarten wurden jeweils 10 Durchl ufe pro Datentr ger ausgef hrt bei jedem Durchlauf wurden 1024 KB also 2048 Sektoren eingelesen F r den sequenziellen Zugriff wurde bei jedem Durchlauf ein zuf lliger Startblock ausgew hlt also 10 Mal beim randomisierten Zu griff f r jeden einzelnen Sektor also 20480 Mal Bei allen getesteten Speichermedien war der sequenzielle Zugriff deutlich schneller maximal bis etwa Faktor 300 gt Kap B 2 Dies gilt sogar f r den Flash Speicher da hier beim randomisierten Lesen f r jeden Sektor neue Adressen an den Speicher Controller bertragen werden m ssen Dieser Effekt impliziert einen Geschwindigkeitsnachteil f r Baumstrukturen da beispielsweise beim Verfolgen eines Pfades durch einen B Baum f r jeden Knoten ein neuer Sektor vom Datentr ger eingelesen werden muss und dieser in der Regel nicht unmittelbar hinter dem Vorg nger liegt In der Praxis werden dabei allerdings nie Einbu en um einen so hohen Faktor erlitten da sich die meisten Sektoren der Indexstruktur zumindest im selben Gebiet der Plattenoberfl che befinden und nicht v llig zuf llig verteilt sind Aber selbst dann bzw sogar bei Flash Speicher ohne mechanische Teile bietet das sequenzielle Lesen einen Geschwindigkeitsvorteil 3 3 3 2 Zeitkomplexit t durch das Dateisystem Zus tzlich zu den u
177. rs verschoben werden Das Entfernen der Daten s tze hat pro Tabelle eine Laufzeit von O n wenn jeder Index sequenziell verarbeitet wird und nicht markierte Eintr ge an eine neue Heap Datei angeh ngt werden Diese neue Datei ersetzt schlie lich die urspr ngliche Datei so dass alle zu l schenden Tupel endg ltig aus dem Index ent fernt sind 5 2 Performanz Die Tabelle in gt Abb 5 2 2 stellt f r die Dateisysteme FAT und ext2 die Dauer verschiedener Ope rationen ohne und mit Master Slave Index dar Das FAT Dateisystem speichert Verzeichniseintr ge in einer Liste ab w hrend ext2 daf r einen B Baum einsetzt Das Suchen einer bestimmten Datei anhand ihres Dateinamens ist also in O n bzw O log n durchf hrbar Wenn eine Liste mit allen Dateien vorliegt ist eine auf Metadaten gest tzte Suche beim Einsatz des FAT Dateisystems in O n m glich jede der n Dateien muss ge ffnet und durchsucht werden wo 78 5 Indexierung bei das ffnen jeweils O n zum Suchen des Verzeichniseintrags ben tigt F r ext2 ergibt sich ent sprechend O n log n ee Filekey FindFirst 75 HG7E Kae Va O Header gt Kap 6 1 1 ffnen der Datei CT Weitere Metadaten Dateik rper Abb 5 2 1 Ablauf eines Suchvorgangs ohne Index Das Modifizieren eines Verzeichnisses Hinzuf gen oder L schen von Dateien bzw Modifizieren des Verzeichniseintrags setzt das Finden des jeweiligen Eintrags voraus so
178. rt sind Kap 3 3 2 problemlos unterst tzt Das sequenzielle Lesen der Indexdatei hat dar ber hinaus den Vorteil dass kein zus tzlicher Leis tungsverlust durch das eingesetzte Dateisystem auftritt gt Kap 3 3 3 2 Auf diese Weise kann ein Master Slave Index problemlos innerhalb eines Dateisystems abgespeichert werden Da bei un fragmentierten Dateien gro e Teile in zusammenh ngenden Bl cken auf dem Datentr ger gespei chert sind k nnen diese Bereiche sequenziell gelesen und im Arbeitsspeicher gepuffert werden Somit werden Verz gerungen durch langsamen wahlfreien Zugriff gt Kap 3 3 3 1 vermieden 5 1 1 Generalisierung Spezialisierung Durch die unterschiedlichen Formate der einzelnen Dateien entsteht ein partiell belegter Datenraum gt Kap 3 3 4 Um heterogene Tupel in einer Heap Datei abzuspeichern gibt es prinzipiell zwei M glichkeiten entweder m ssen unterschiedliche Tupelgr en in Kauf genommen werden die die Implementierung erschweren und ineffizienter werden lassen da kein wahlfreier Zugriff anhand der Tupelnummer mehr m glich ist oder jedes Tupel wird auf eine Maximalgr e verl ngert wodurch die Gesamtgr e des Indexes zunimmt Beide Varianten sind nicht akzeptabel zumal letztere die Einf hrung neuer Dateiformate mit weiteren Attributen erschwert wenn nicht ausreichend Platz in den Tupeln reserviert wurde 69 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Unterschiedli
179. rt um einige Aspekte eines semantischen Dateisystems gt Kap 2 7 2 Hier wird vor allem die Verwaltung der Metadaten gt Kap 2 7 3 diskutiert Weiterf hrende Informationen hierzu sind in Gia99 zu finden BeFS speichert Attribute als Paar von Schl sselwort und Wert ab in Analogie zu relationalen Da tenbanken Die F higkeit beliebig viele Attribute anzulegen gestattet das einfache Abspeichern von Metadaten die auch automatisch indexiert werden k nnen BeFS benutzt einen Node um wichti ge Informationen ber eine Datei abzuspeichern Die Struktur hei t bfs_inode und hat folgenden Aufbau Gia99 40 3 Existierende Indexe typedef struct bfs_inode int32 magic inode_addr mode num int32 uid int32 gid int32 mode int32 flags bigtime_t create_time bigtime_t last_modified_time inode adr parent inode_addr attributes unit32 type int32 inode_size binode_etc etc data_ stream data int32 pad 4 int32 small_data 1 bfs_inode Besonders auff llig sind die Eintr ge vom Typ inode_addr sie verweisen auf andere I Nodes Da bei ist inode_num ein Verweis auf sich selbst und parent zeigt auf den I Node des Ordners in dem sich die Datei bzw das Verzeichnis befindet Besonders wichtig fiir die Verwaltung von Metadaten ist die Variable attributes welche auf den I Node eines versteckten Ordners zeigt der alle Attribute speichert Dieses Verzeichnis befindet sich au erhalb des normalen Verzeichnisb
180. rwendet wird Da tenbl cke einer Datei werden als verkettete Liste gespeichert wodurch ein Dateizeiger in O n bewegt werden kann Kol07b Datenstuktur die in der Referenz Library gt Kap 6 die Parameter ei ner Suchanfrage enth lt gt Kap 6 2 2 Shell von Mac OS Information Node enth lt in vielen Unix Dateisystemen wie z B ext2 alle Informationen zu einer Datei einschlie lich der von ihr belegten Bl cke auf dem Datentr ger ein Verschieben des Dateizeigers ist in O 1 m glich Kol07b Prozess der nur ausgef hrt wird wenn kein anderer Prozess CPU Zeit beansprucht Datenspeicher auf den sowohl relationale Datenbanken als auch Datei systeme abgebildet werden k nnen gt Kap 4 Spezielles Verzeichnis der Unix Verzeichnishierarchie das mit dem Hauptverzeichnis eines Dateisystems zusammenf llt alle untergeordne ten Verzeichnisse geh ren nicht mehr zum Root Dateisystem Standard Dateisystem von Microsoft Windows kann f r eine Datei mehrere Dateik rper Forks verwalten Kol07b 131 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Query containment Registry Semantisches Dateisystem Shell SQL Tagging Widget 132 Eingrenzen von Suchanfragen gt Kap 5 2 2 gt Kap 6 2 2 1 Konfigurationsdatei von Microsoft Windows wird heute auch zum Speichern von Programmeinstellungen benutzt gt Kap 2 4 2 Ein semantisches Dateisystem arbeitet typabh ngig
181. s 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 Abb 2 7 1 Integrierte Architektur von BeOS In diesem Abschnitt wird auf die besonderen F hgkeiten von BeFS eingegangen auf bersetzer gt Kap 2 7 1 Postf cher gt Kap 2 7 2 und auf die Suchfunktion gt Kap 2 7 3 2 7 1 bersetzer 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 21 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 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 TIFF Images HSIRaw Translator Targa Images a StyledEdit Translator HSI Raw image translator v0 9 0 Oct 24 1999 PPM Images 99 by Jesper H
182. s hin zu Highend Systemen eingesetzt werden Die Library wird dadurch zum integralen Be standteil des Betriebssystems so dass Applikationen die bereitgestellte Funktionalit t voraussetzen k nnen Abb 6 1 Integration ins Betriebssystem 6 1 Architektur In diesem Abschnitt wird zun chst die Architektur der Referenz Library eingef hrt bevor in gt Kap 6 2 konkrete Details zur Implementierung pr sentiert werden Die Referenz Library setzt sich aus mehreren Domains gt Kap 6 1 1 zusammen die entweder auf einem physikalischen Dateisystem aufbauen oder als virtuelle Domain in gt Abb 6 1 1 ganz rechts andere Informationen in die Library integrieren Applikationen gt Kap 6 1 2 greifen nicht mehr direkt auf das physikalische Dateisystem zu sondern werden durch die Library in ein objekt orientiertes Gesamtkonzept eingebunden Kol08b In einer Registry gt Kap 6 1 3 werden alle aktiven Komponenten verwaltet 81 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Pr ve Library Registry Physikalisches en 7 Domain Applikation me P ua e e Dateiformat Dateiformat Dateiformate Dateiformat Abb 6 1 1 Architektur bersicht Kol08b 6 1 1 Domains Eine Domain OSC06 wird hier als weitgehend unabh ngiger Speicherort f r Datenobjekte defi niert Die Library wird durch Domains partitioniert jede Datei ist also in genau eine
183. schen 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 EX107 Dar ber hinaus enth lt MetaFS zus tzliche Befehle zur Manipulation der verschiedenen Attribute 2 2 2 Performanz 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 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
184. schl ssel Attribut F eines Objekt Schemas kann beispielsweise durch Umformung und Einbezie hung des Typ Attributs T in Form eines Namenssuffix auf den Dateinamen abgebildet werden Eine solche Abbildungsvorschrift kann im allgemeinen Fall nur ein Element eines semantischen Da teisystems SDS zum Ziel haben da das uniforme Datei Schema physikalischer Dateisysteme DS h chstens einem Objekt Schema entsprechen kann Damit gilt analog zu gt Kap 4 2 dass sich die Datenmodelle von physikalischen und semantischen Dateisystemen in ein Library Schema berf h ren lassen das Datenmodell einer Library sich hingegen nur auf ein semantisches Dateisystem ab bilden l sst Einheitliches Schema Abb 4 3 3 Physikalisches Dateisystem semantisches Dateisystem und Library 4 4 Vorteile Marsden stellt in Mar03 fest dass Datenbanken urspr nglich in hierarchielosen Dateien gespei chert wurden Da so keine Beziehungen zwischen den gespeicherten Daten modelliert werden konn ten wurden hierarchische Datenbanken eingef hrt die die Darstellung von 1 n Beziehungen er laubten Hierarchische Datenbanken sind jedoch nicht geeignet um alle Beziehungen zwischen En tit ten zu modellieren weshalb die Hierarchie mittels Links durchbrochen werden konnte An genau diesem Entwicklungspunkt befinden sich Dateisysteme heute Mar03 64 4 Integration Die Datenbanktechnik hat sich jedoch zu relationalen Datenbanken Cod70 weiterentwickelt die seit Anf
185. sehene Filme enorm vereinfacht In einem ersten Schritt wurden entsprechende Suchfilter in die Shell gt Kap 7 1 eingebunden gt Abb 7 5 5 und der Datei Manager um die wahlweise Anzeige der Bewertung erweitert gt Abb 7 5 6 Da das Bewertungsattribut durch die Aufnahme in den Suchfilter gt Kap 6 2 2 systemweit zur Verf gung steht profitieren davon auch andere Applikationen wie etwa ein Mediacenter Programm In einer Kategorie Favoriten er scheinen auch die von der Library bereitgestellten virtuellen Abspiellisten die automatisch alle MP3 Dateien mit mindestens einem zwei oder drei Punkten enthalten und einfach angew hlt wer den k nnen gt Abb 7 5 7 Favoriten mit Mindestbeuertung Abb 7 5 5 Suchfilter f r die Anzeige von Favoriten 113 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 21st century digital boy Bad religion A little less conversat ion Elvis Presley Ab auf die Piste Buddy Age of aquarius Fifth dimension Ain t talking bout Dub Apol loFourForty All about us Tatu All I need Air All the things she said Tatu Apache Incredible Bongo Band Asere je Las Ketchup Aya benzer Mustafa Sandal Bai lando Loona Big big trouble Die happy Big trip to Portland Mary Black Bonbtrack Boon Anastacia Boten Anna Basshunter Break my stride Blue lagoon Break on through The doors Bring me to live Evanescense Butterfly Crazy toun Calling Elvis h Dire Straits Can t
186. sionaler Datenobjekte Testfall 5 sw Reset cmd new SqlCommand SELECT FROM Test WHERE FileTyp 5 OR FileTyp 7 OR FileTyp 23 OR FileTyp 32 AND ID3Artist Anastacia conn r cmd ExecuteReader mn r Read r Close Console WriteLine Case 5 sw Peek 10 0 ms conn Close Console WriteLine Ready Console ReadLine 142 D Testprogramm PostgreSQL Anhang D Testprogramm PostgreSQL Um in gt Kap 3 3 5 2 die Leistung der Datenbank PostgreSQL zu messen wurde ein Testprog ramm in C entwickelt Das Programm gt Kap D kann mit Microsoft Visual Studio f r die NET Umgebung compiliert werden Zur korrekten Ausf hrung ist neben einem installierten Micro soft SQL Server ein passender ODBC Treiber fiir PostgreSQL erforderlich D 1 PROGRAM CS Die Datei PROGRAM CS enth lt das eigentliche Testprogramm Die Klasse Program greift auf eine nicht abgebildete Klasse StopWatch zu deren Objekte die Zeit mit einer Genauigkeit von 0 1 ms messen k nnen Intern greift das NET Framework dabei auf den RDTSC Befehl She96 zur ck using System using System Data using System Data OleDb using System Collections Generic using System Text namespace ConsoleApplication1 class Program Nur ein Thread OleDb ist nicht thread safe STAThread static void Main string args Console Write Connecting OleDbConnection conn new OleDbConnection Pr
187. so dass Applikationen in unterschiedlichen Dateien gespeicherte Informationen verbinden k nnen Diese Technik wertet Applikationen auf indem etwa beim Betrachten eines Bildes Befehle zum Anzeigen anderer Bilder mit hnlichen Eigenschaften z B Aufnahmedatum oder Belichtung an geboten werden oder beim Abspielen von Musikdateien weitere St cke desselben K nstlers zur Auswahl stehen Als Fallbeispiel dient eine gespeicherte SMS die neben dem eigentlichen Nach richtentext auch die Telefonnummer der Absenderin enth lt 104 7 Interaktion ge Tina Geburtstag 185 52 Von 491737064555 24 08 2002 21 25 Uhr Nee Hola geburtstagskind Wollte dir noch mal rucken einen sch nen abend mit den kollegen aus S eichern dortnund winschen LaB dich ordentlich S nden feiern Und danke f r gestern Tina Abb 7 2 1 SMS mit Telefonnummer der Absenderin Die Referenz Library kennt ein Dateiformat f r Adressdateien gt Kap 6 2 1 die bei der Darstel lung von SMS zur Aufl sung der Telefonnummer benutzt werden In gt Abb 7 2 1 kann die Tele fonnummer der Absenderin jedoch nicht aufgel st werden da der Join von SMS Dateien und Adressen ber die Attribute Von und Mobiltelefon keine Dateien liefern Nun wird eine Adressdatei erstellt in der die Telefonnummer die in der obigen SMS enthalten ist als Mobiltelefon eingetragen wird Sy a E eruerfen Mier Geburtsdatun S eichern Tina 0 ii Benutzen Stra e q Ort hee
188. ss 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 1 1 2 Indexierung 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 gt Kap 3 3 1 Ebenfalls negativ wirkt sich aus dass der Index in der Regel innerhalb eines physi kalischen Dateisystems gespeichert wird gt 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 gt 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 1 1 3 Interaktion Basierend auf der Integration und Indexierung wird als letztes Teilziel die Interaktion mit gro en Datenmengen durch die Realisierung for
189. stop Red Hot Chili Peppers Candyman Christina Aguilera Cantaloop US3 Car wash Rose Royce Celebration generat ion Hestban Chain of foolz Aretha Franklin Chori chori Aneela feat Arash Chor javon Nato Conplicated Avril Lavigne Connected Stereo MCs B Alle MP3s ab LA Zuf llige Reihenfolge Alle MP3s ab mn Einzelne Dateien W 21st century digital b Eigene Dateien Laufwerk G Laufwerk H Abb 7 5 7 Virtuelle Abspiellisten im Medienzentrum 114 7 Interaktion 7 5 3 Vorteile Tagging erweitert die Metadaten die von diversen Dateiformaten geliefert werden um eine global g ltige Kennzeichnung Durch semantisches Tagging k nnen Dateien nicht nur anhand von Schlagworten sondern durch bestimmten Eigenschaften gesucht und kategorisiert werden Tagging wird vom Library Modell gt Kap 4 1 unterst tzt und steht daher systemweit f r alle Dateiforma te zur Verf gung Speziell f r das Geotagging bieten die von der IATA IAT07 eingef hrten 3 Buchstaben Codes Vorteile Gegen ber GPS Koordinaten sind sie leicht zu merken da sie kurz sind und sich an nat r liche Ortsnamen anlehnen Dies gilt umso mehr wenn die entsprechenden Orte tats chlich besucht wurden etwa beim Tagging von Urlaubsfotos und videos und das Tag vom Benutzer selbst verge ben wurde Dar ber hinaus sind sie genormt und dadurch eindeutig Sie k nnen bei der Bearbeitung einer Suchanfrage leicht verarbeitet werden und sind vielen Menschen a
190. t ber die Reihenfolge der Tupel in ihren jeweiligen Heap Dateien berechnet wird Um Speicherplatz zu sparen kann daher durch Anpassung von 5 6 auf das Wiederholen des Schl sselattributs in den Slave Indexen verzichtet werden Wird von dieser Optimierung kein Gebrauch gemacht so kann w hrend des Merge Joins berpr ft werden ob sich an der aktuellen Stelle eines Slave Indexes auch tats chlich das angeforderte Tupel befindet Ist dies nicht der Fall so ist der Index inkonsistent und muss neu aufgebaut werden 80 6 Referenz Library 6 Referenz Library Dieses Kapitel stellt die Architektur gt Kap 6 1 und Implementierung gt Kap 6 2 einer Refe renz Library vor Auf diesem System basierend kann schlie lich die Interaktion mit Dateien gt Kap 7 verbessert werden insbesondere wird hier der vollst ndige Zugriff auf beliebige Meta daten realisiert so dass eine starre Verzeichnisstruktur obsolet wird Zur Sicherstellung einer hohen Leistung wird zur Indexierung ein Master Slave Index gt Kap 5 eingesetzt und erprobt gt Kap 6 3 Im Rahmen dieser Arbeit soll auf bestehenden Dateisystemen aufgebaut werden indem diese um zus tzliche Funktionen erweitert werden Dabei soll die Architektur skalierbar sein also auf nahezu beliebige Dateisysteme aufgesetzt werden k nnen Konkrete von diesem Modell abgeleitete Libra ries k nnen so von Flash Speicherkarten die blicherweise mit dem FAT Dateisystem formatiert sind bi
191. t ndige Indexierung aber besonders viel Zeit beansprucht Obwohl es sich noch um Alphaware handelt macht das Tool einen soliden Ein druck Einzig die Installation und die erste Indexerstellung sind etwas problema tisch Die Indexerstellung hat bei mir 50 GB Home circa 48h gedauert wo bei die Systembelastung nicht weiter ins Gewicht fiel ich konnte normal wei terarbeiten Abb 3 1 6 Private WWW Seite unter Lin05 Dieses Verhalten ist jedoch tats chlich problematisch denn nach der Installation sollte ein Pro grammpaket m glichst sofort einsatzbereit sein jedenfalls nicht erst nach zwei Tagen Laufzeit Die se Nachteile sind jedoch nicht Lucene anzulasten da die Bibliothek als universeller Textindex f r eine Vielzahl von Einsatzzwecken entwickelt wurde Vielmehr sind es die Hersteller von Desktop Suchmaschinen die f r ihre Projekte geeignetere Alternativen zu Lucene einsetzen sollten etwa einen Master Slave Index 5 Dar ber hinaus f llt auf dass alle Attributwerte einer Datei als Zeichenkette gespeichert werden die Aufl sung der Bilddatei gt Abb 3 1 5 ist als 1536 und 2048 enthalten und nicht als Bin r zahl Dies ist effizient f r die Suche durch Schlagworte wie sie Internet Suchmaschinen verwen den erschwert allerdings Vergleiche mit den Operatoren gr er oder kleiner 3 2 BeFS Die Funktionsweise von BeFS hnelt der anderer Unix Dateisysteme wie beispielsweise ext2 er weite
192. tandteil des Office Pakets dass ein Bedarf an besseren Organisationsformen f r Dateien besteht Eine Vielzahl von weiteren Systemen wie z B Desktop Suchmaschinen gt Kap 2 10 realisieren die Suche von Dateien ber Verzeichnis grenzen hinweg ohne allerdings die eigentliche Organisation des Dateisystems zu verbessern Die se Systeme sind also h chstens als Provisorium zu bezeichnen Die vorgestellten L sungen die eine Dateisuche erm glichen indexieren die Attribute des Datei systems sowie Metadaten und ggf Suchbegriffe aus dem Dateik rper Der eingesetzte Index sollte dabei nicht nur das Vorkommen von bestimmten Attributwerten indexieren sondern auch das Ur sprungsattribut selbst so dass gezielt nach Dateien mit bestimmten Eigenschaften gesucht werden kann Ein Volltext Index wie er beispielsweise von Google Desktop eingesetzt wird vermag dies nicht zu leisten wodurch derartige Produkte nur eine eingeschr nkte Funktionalit t bieten k nnen gt Kap 2 10 3 Indexe welche auch das Herkunftsattribut katalogisieren werden im folgenden Kapitel gt 3 vorge stellt Aufgrund der Rahmenbedingungen von Dateisystemen bieten diese Indexe die urspr nglich f r andere Einsatzgebiete entwickelt wurden nur eine eingeschr nkte Leistung Dies reduziert auch die Performanz des Gesamtsystems 36 3 Existierende Indexe 3 Existierende Indexe Viele L sungen die in gt Kap 2 vorgestellt wurden verwenden einen Index zum Abspeich
193. technische universit t dortmund Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Dissertation zur Erlangung des Grades eines Doktors der Naturwissenschaften der Technischen Universit t Dortmund an der Fakult t Informatik von Konstantin Koll Dortmund 2009 Tag der m ndlichen Pr fung 18 Februar 2009 Dekan Prof Dr Peter Buchholz Gutachter Prof Dr Gisbert Dittrich Prof Dr Heinrich M ller Ich bedanke mich bei Prof Dr Dittrich und Prof Dr M ller von der Technischen Universit t Dortmund f r die Betreuung meiner Promotion ebenso bei Prof Dr Spinczyk f r seine Unterst tzung Besonderer Dank gilt Judith Ahrens Lars Heide Diether Koll Felix Kaiser Felizitas Ottemeier Ingo Olaf Schumacher Jindra Siekmann Sandra Teusner und Vasilis Vasaitis f r viele Verbesserungsvorschl ge Inhaltsverzeichnis Inhaltsverzeichnis 1 ET 1 1 1 Zielsetzung und berblick nennen 2 LIF Des an essen ee 2 LAD EN 3 LIS EE 3 12 Res ltate usa eu 4 L3 SP eV UC MEISE E 4 2 Existierende L sungen siaceceeacecesivecerncsvesscesivasvversvannunssvecnvecivnnsuensterevn vs vovsuandunverasivexeincdeonstacewneveens 5 2 1 Lotus Mare lan een een 5 E WEE 6 2 1 2 Steuerung der TNICXICTHNG une iaiia 8 22 SFS und Metaf Senen E E EE 9 22d WEIIereHntmack lungen euere 11 2 22 Perfor MANZ rir a E E E EE EEEE EE E 11 EC Me 12 23 1 Klassifizierer ns 12 23 2 ODER eine EE AA EE AE AaS 13 24 Micros
194. tellen In diesem Abschnitt wird eine Shell entworfen welche die erweiterten M glichkeiten einer Library unterst tzt Zun chst wird in gt Kap 7 1 1 der Funktionsumfang moderner Shells vorgestellt bevor in gt Kap 7 1 2 Anforderungen an eine Shell auf Library Basis formuliert werden In gt Kap 7 1 3 werden Mechanismen zur Erf llung dieser Anforderungen eingef hrt 7 1 1 Moderne Shells Sehr h ufig verwendete grafische Shells sind der Explorer gt Kap 2 6 der seit Microsoft Win dows 95 Bestandteil des Betriebssystems ist und der Finder als Shell von Mac OS F r Unix ste hen neben den Kommandozeilen Shells verschiedene grafische Shells als Teil von Desktop Managern wie KDE KDE06 oder Gnome Gno06 zur Verf gung Zum Funktionsumfang moder ner Shells geh rt in der Regel ein Menu zum Starten von Programmen und Funktionen das neuer dings durch auf dem Desktop platzierte Widgets erg nzt wird sowie ein Datei Manager 7 1 1 1 Start Menu und Widgets Die Shell Komponente die zur Auswahl von Befehlen und Programmen dient ist in den meisten Betriebssystemen als hnlich aufgebautes Menu angelegt das in der Regel durch Klick auf eine be sondere Schaltfl che z B Start in der linken unteren Bildschirmecke ge ffnet wird YES Unterhaltungsmedien l CD Wiedergabe 3 abcAYI Tag Editor E Systemprogramme gt E Lautst rkeregelung E Adobe Premiere 6 0 I Editor Li ADSLWatch E Microsoft PowerPoint Viewer 9
195. ten Microsoft SQL Server die Bibliothek SQLXML erforderlich die vor dem Compilieren des Programms in das Projekt eingebunden werden muss Verweis hinzuf gen NET COM Projekte Durchsuchen Aktuell Microsoft Scriptlet Library Microsoft Sdpblb 1 0 Type Library Microsoft Shell Controls And Automation Microsoft Smart Tags 2 0 Type Library Microsoft Soap Type Library Microsoft Speech Object Library Microsoft SQL Distribution Control 9 0 Microsoft SQL Merge Control 9 0 Microsoft SQL Replication Conflict Resolver Library JAWINDOWS system32 scrobj dll J AWINDOWS system32 sdpblb dll J AWINDOWS system32 S HELL32 dll J Programme Gemeinsame Dateien Microsoft Sh J Programme Gemeinsame Dateien MSSoap Bi J Programme Gemeinsame Dateien Microsoft Sh Programme Microsoft SQL Server S0 COM sql Programme Microsoft SQL Server SO COM sql Programme Microsoft SQL Server 90 COM repl Microsoft SQL Replication Errors 9 0 Programme Microsoft SQL Server S0 COM repl Microsoft SQL Virtual Directory Control 3 0 Type Library J Programme Gemeinsame Dateien System Dle Microsoft SQLDMO Object Library 8 SProgramme Microsoft SQL Server 80 T ools bin Microsoft SULSML BulkLoad 3 0 Type Library 3 0 J Programme Gemeinsame Dateien Ole Microsoft Tablet PC Type Library version 1 0 i J Programme Gemeinsame Dateien M Microsoft TAPI 3 0 Type Library d JNWINDOWS spstem32 tapi3 dil Microsoft Terminal Ser
196. teraktion von Daten pr sentiert die sich aus dem Einsatz einer Library als Speichersystem ergeben Als Beispiel wird dabei die Referenz Library gt Kap 6 eingesetzt Die Interaktion mit einer Library l sst sich all gemein auf vier Pfade aufteilen AA Programm erstellt Programm benutzt einen Suchfilter Suchergebnis intern Darstellung f r den Benutzer Benutzer formuliert eine Suchanfrage Abb 7 1 Interaktion mit einer Library 1 Suchanfragen k nnen intern von einem Programm gestellt werden ohne dass der Benutzer dazu einen Suchfilter gt Kap 6 2 1 spezifizieren muss Beispiele hierf r sind eine speziell entwi ckelte Shell gt Kap 7 1 die u a nach neuen Dateien und f lligen Terminen sucht und Join Operationen innerhalb von Applikationen gt Kap 7 2 2 Manche Programme zeigen das Suchergebnis nicht als Dateiliste an sondern verarbeiten es in tern weiter Die in gt Kap 7 1 pr sentierte Shell dient auch hier als Beispiel da die gefundenen Dateien nur gez hlt nicht aber aufgelistet werden werden Weitere Programme die von Pfad 2 Gebrauch machen k nnten Hilfsprogramme sein die in regelm igen Abst nden alte bereits gelesene EMails l schen bzw archivieren sowie Programme zum Massenl schen oder umbe nennen von Dateien gt Kap 5 1 6 3 Neben den vordefinierten Suchfiltern sollen Benutzer auch selbst Suchabfragen formulieren k nnen wenn die vordefinierten Suc
197. ts path Abb 2 10 3 Integration von Spotlight in den Finder App05 Genau wie die meisten anderen Systeme ben tigt die Spotlight Engine Zusatzmodule zur Bearbei tung diverser Dateiformate Apple bietet zus tzliche Plug Ins zum Download an um Spotlight den Zugriff auf weitere Formate zu erm glichen App08 Creator Erika Mustermann Original Date 2004 10 18 21 19 12 Digitized Date 2004 10 18 21 19 12 Camera Maker Canon Camera Model Canon Digital EOS Exposure 1 60 sec Aperture f 2 8 Exposure Bias 1 00 Metering Pattern x ISO 100 Adobe Abb 2 10 4 Verarbeitung von Metadaten mit Apple Spotlight App05 33 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Anfrage Suchergebnis Abb 2 10 5 Schematische Darstellung einer Suchanfrage mit Apple Spotlight App05 2 10 3 Google Desktop Die Desktop Suchmaschine Google Desktop wurde vom gleichnamigen Betreiber einer beliebten Internet Suchmaschine entwickelt Google Desktop integriert sich nahtlos in den Microsoft Internet Explorer und erweitert dort die Internet Suchmaschine desselben Herstellers durch lokale Sucher gebnisse und eine explizite Desktop Suche Google Desktop nutzt zur Indexierung einen Wortindex der lediglich Begriffe nicht aber deren Herkunftsattribut indexiert Das ist ein gro er Nachteil denn es kann nicht nach bestimmten Eigen schaften gesucht werden Folgende Abbildung zeigt als Beispiel die Suche n
198. tschrittlicher 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 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 1 2 Resultate Im Rahmen dieser Arbeit wurden folgende Resultate mit Neuheitswert erzielt e 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 gt Kap 2 Im Zuge dieser Be standsaufnahme wurden auch eingesetzte Indexe untersucht gt Kap 3 e Das Datenmodell f r Libraries auf das sich die Modelle von relationalen Datenbanken und Da teisystemen abbilden lassen wird eingef hrt gt Kap 4 e Der Master Slave Index wird als neue Datenstruktur zur Indexierung eingef hrt gt Kap 5 e Zum Nachweis der praktischen Funktionsf higkeit des Library Modells wird eine Referenz Library vorgestellt gt Kap 6 e 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 gt Kap 7 1 3 Ver ffentlichungen Die Resultate dieser Arbeit gt Kap 1 2 st tzen sich auf diverse Ver ffentlichungen deren alle
199. ttribut 7 in ein Relations Schema aufgenommen werden In diesem Zusammenhang ist es problematisch dass f r die Attribute von Objekt Schemata BLOBs als Wertebereich explizit zugelassen sind Eine Library behandelt diese zwar als atomar das klassi sche relationale Datenmodell hingegen gestattet keine BLOBs da diese in Wirklichkeit eben nicht atomar sind In der Praxis entstand jedoch schon fr h der Wunsch auch Bin rdaten in einer Relation abzuspei chern Als Beispiel k nnen Fotos in einer Relation mit Personen dienen oder eingescannte Titel bl tter in einer Relation f r Zeitschriften Moderne Datenbanksysteme gestatten daher auch das Speichern von BLOBs und sehen diese ebenfalls als atomar an Aus diesem Grund kann eine Trennung zwischen relationalen Datenbanken ohne und mit Unterst t zung f r BLOBs gezogen werden Letztere werden hier BLOB relational genannt Damit lassen sich alle relationalen Datenbanken auf eine Library abbilden Libraries hingegen k nnen allgemein nur auf BLOB relationale Datenbanken abgebildet werden Abb 4 2 1 Relationale Datenbank BLOB relationale Datenbank und Library 61 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte 4 3 Dateisysteme In diesem Abschnitt wird gezeigt dass das Datenmodell von Dateisystemen ohne Verlust von In formationen auf das Datenmodell einer Library abgebildet werden kann Ein Datei Schema R ist eine Menge die abh ngig vom Dateisystem aus e
200. uch au erhalb der Luft fahrt Branche vertraut aen C State province NRW Postal code 44227 Country Germany Airport DUS If you are or might become an ApacheCon speaker please enter the 3 letter abbreviation of the airport from which you would most likely be flying Abb 7 5 8 Anmeldeformular f r eine Konferenz Ausschnitt Werden Tags manuell durch den Benutzer vergeben so impliziert dies einen Aufwand der mit dem Anlegen von Verzeichnissen vergleichbar ist wobei allerdings eine Datei mehrere Tags erhalten kann Semantisches Tagging kann jedoch auch automatisch durchgef hrt werden etwa durch Pro tokollieren aller Dateiaufrufe zur Ermittlung besonders h ufig benutzter Dateien gt 8 3 3 7 6 Aufgabenorientierung Die einzelnen Objekt Schemata der Referenz Library gt Kap 6 wurden um ein zus tzliches Attri but erweitert das alle f r den Benutzer relevanten Methoden der jeweiligen Applikations Klassen gt Kap 6 1 2 speichert etwa Weiterleiten bei EMails Auf diese Weise kann der Datei Manager in Abh ngigkeit von den gerade angezeigten bzw markierten Dateien Befehle typspezi fisch bereitstellen Dou00 Die nachfolgenden Abbildungen zeigen die sog task pane von Microsoft Windows XP Hier wer den unter dem Stichwort Aufgaben in Abh ngigkeit von den markierten Dateien etwa Bilder oder Videodateien unterschiedliche Befehle angezeigt Leider sind diese Befehle bei Windows XP lediglich i
201. und sogar die Angaben ber Dateiformate und OLE kompatible Programme sind noch vorhanden e Registrierungseditor Registrierung Bearbeiten Ansicht CG CC Microsoft Name Wert Active Setup ab Standard wert nicht gesetzt E ActiveMovie CAPROGRAMME GEMEINSAME DATEIEN MICROSOFT SHAREDSEQUATION CG Advanced INF Setup E ComplexScripts 5 Cryptography E Direct3D E Directinput DIRECTPLAY FE lb DirectX Diagnostic Tool Eot a Equation Editor A 30 a Options Directories Fonts General Sizes Spacing E windows gt Arbeitsplatz HKEY_CURRENT_USER Software Microsoft E quation Editor3 0 Options Directories Abb 2 4 9 Registrierungs Editor ab Windows 95 2 4 3 Objekt Manager 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 PACKAGER EXE Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Objekt Manager Paket BE Datei Bearbeiten Hilfe RIES Abb 2 4 10 Poker Erstellung mit dem Objekt Manager Das erstellte Paket kann danach in ein Zieldokument eingebettet werden Verkn pfungen sind nicht m glich Im obigen Beispiel gt Kap 2 4 1 w rde statt des eigentlichen
202. ung 25 11 2005 Nickell S A Cognitive Defense of Associative Interfaces for Object Reference http www gnome org seth storage associative interfaces pdf Stand 23 10 2008 erste Referenzierung 14 02 2006 Nillson M http www id3 org Stand 23 10 2008 erste Referenzierung 14 07 2005 Novell SUSE Linux Professional 93 http www novell com de de products linuxprofessional beagle html Stand 23 10 2008 erste Referenzierung 07 09 2005 Object Services and Consulting Inc Semantic File Systems http www objs com survey OFSExt htm Stand 23 10 2008 erste Referenzierung 14 01 2006 The Register Windows on a database sliced and diced by BeOS vets http www theregister co uk 2002 03 29 windows_on_a database_sliced Stand 23 10 2008 RFC 1094 NFS Network File System Protocol Specification http www ietf org rfc rfc1094 txt Stand 23 10 2008 RFC2045 RFC2425 RFC2445 RFC3986 RFC4122 Rob99 Saa05 Sak00 Literaturverweise RFC 2045 Multipurpose Internet Mail Extensions MIME Part One Format of Internet Message Bodies http www ietf org rfc rfc2045 txt Stand 23 10 2008 RFC 2425 A MIME Content Type for Directory Information http www ietf org rfc rfc2425 txt Stand 23 10 2008 RFC 2445 Internet Calendaring and Scheduling Core Object Specification iCalendar http www ietf org rfc rfc2445 txt Stand 23 10 2008 RFC3986 Uni
203. upels mit dem Prim rschl sselwert f in der Relation r 5 7 71 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte Ist diese Eigenschaft erf llt so k nnen alle Index Relationen parallel sequenziell durchlaufen wer den was in O n m glich ist und einem Merge Join Saa05 entspricht 5 1 2 1 Beispiel Das folgende Beispiel zeigt einen Master Slave Index der die Attributwerte einiger Bilder und MP3 Dateien enth lt Das Attribut F wird als Filekey bezeichnet das Attribut T als Typ Dar ber hinaus besitzt der Beispiel Index die oben definierte Merge Eigenschaft 5 7 gt e Master Index Slave Index f r Bilder Slave Index f r MP3s Filekey Typ Filekey Filekey Album Z6_HG7E Bild Z6_HG7E 1024 JK83ZZA_ Texas The Hush JK83ZZA_ MP3 LLmAcK 64 JGUIP7 D d Laun Bild 30_KUIKXY 2048 JGUIP7 D_ MP3 30 KUY Bild Abb 5 1 2 Master Slave Index Kol08c Zur Bearbeitung von Suchanfragen wird jeder Index mit einem Zeiger auf das n chste zu bearbei tende Element versehen Anfangs zeigen alle Merker auf das erste Element ihres Index gt e p Master Index Bilder Index MP3 Index Filekey Typ Filekey Filekey Z _HG7ES Bild gt Z6HG7ES gt JKB3ZZA_ JK83ZZA__ MP3 ILLNACK LL9ACX1 Bild JGUIP7 D 30_KUIXY JGUIP7 D_ MP3 30_KUIXY Bild Ab
204. usterindex existiert eine Dimensionszahl d ab der ein sequenzieller Suchlauf schneller ist In der Praxis ist d dabei deutlich kleiner als 610 2 Die Zeitkomplexit t jedes Partitions oder Clusterindex konvergiert bei gro en d gegen O n 3 F r jeden multidimensionalen Partitions oder Clusterindex gibt es eine Dimensionszahl d bei deren berschreiten alle Sektoren des Index gelesen werden m ssen Die berlegenheit des sequenziellen Scannens bei Gleichverteilung wird von Jag05 experimentell best tigt Als Konsequenz aus den theoretischen berlegungen wird in Web98 eine Indexstuktur namens VA Datei entwickelt die approximierte Attributwerte abspeichert und sequenziell scannt F r alle im Idealfall wenige Objekte bei denen die approximierten Werte in der Nachbarschaft des Referenzpunktes liegen wird dann der tats chliche Abstand zu p berechnet Liegt keine Gleichverteilung vor so existieren Indexstrukturen wie iDistance Jag05 die bei Nachbarschaftssuchen effizienter sind als VA Dateien Der Geschwindigkeitsgewinn gegen ber se quenziellen Verfahren wie VA Dateien ist jedoch nur etwa Faktor 10 Jag05 was beim Einsatz in Dateisystemen durch andere Faktoren gt 3 3 3 kompensiert wird 3 3 2 Partial Match Operationen Da fast alle multidimensionalen Indexstrukturen f r die Nachbarschaftssuche entwickelt wurden werden keine Operationen mit nur wenigen spezifizierten Attributwerten unterst tzt denn mit je dem irrelev
205. v gedruckt iv 1 Einleitung 1 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 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 fiktive
206. vices Active Client 1 0 Type Libr 1 JAWINDOWS system32 mstscax dll OK Abbrechen Abb C 1 Verweis auf die Bibliothek SQLXML in Microsoft Visual Studio 1 1 1 1 1 5 1 1 9 1 3 C 1 METADATA XML Alle Attribute der Testdateien wurden in einer XML Datei gespeichert Dieses Dateiformat kann von vielen Applikationen durch die Bibliothek SQLXML auch vom Microsoft SQL Server impor tiert werden lt ROOT gt lt File gt lt FileTyp gt 34 lt FileTyp gt lt FileBez gt Sabine 1 lt FileBez gt lt FileKey gt 1P L_8S lt FileKey gt lt FileSize gt 632690 lt FileSize gt lt FileTime gt 18 07 2005 18 03 58 lt FileTime gt lt FileNew gt 0 lt FileNew gt lt FilelATA gt 9313 lt FilelATA gt lt IMGL gt 1200 lt IMGL gt lt IMGH gt 1600 lt IMGH gt lt IMGFarbmodus gt 1 lt IMGFarbmodus gt lt IMGCreationTime gt 1 7 56 lt IMGCreationTime gt lt IMGCreationYear gt 2005 lt IMGCreationYear gt lt IMGCreationMonth gt 7 lt IMGCreationMonth gt lt IMGCreationDay gt 17 lt IMGCreationDay gt 137 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte lt IMGEquipment gt Minolta Co Ltd DIMAGE X20 lt IMGEquipment gt lt IMGBelichtung gt 1 180 Sekunde lt IMGBelichtung gt lt IMGFirmware gt Ver 1 00 lt IMGFirmware gt lt IMGTitel gt MINOLTA DIGITAL CAMERA lt IMGTitel gt lt IMGFocus gt 4 80mm lt IMGFocus gt lt IMGBlende gt f 28 lt IMGBlende gt lt File gt lt RO
207. weiligen Anwendungsprogrammen die Wahl durch eine geeignete SQL Erweiterung z B CREATE MASTERSLAVE INDEX idx ON table Auf diese Weise kann eine Vielzahl von Anwendungen und Produkten die entsprechend ausger ste te DBMS einsetzen profitieren Darunter befinden sich nicht nur Desktop Suchmaschinen und Sys teme wie Microsoft WinFS gt Kap 2 9 das auf dem Microsoft SQL Server gt Kap 3 3 5 1 ba siert sondern beispielsweise auch Data Warehouses Dar ber hinaus lassen sich die Operationen auf dem Master Slave Index ressourcenschonend im plementieren was die Datenstruktur auch f r mobile Systeme etwa Smartphones und MP3 Player geeignet macht 8 2 2 Erweiterung f r Dateisysteme Weitaus komplexer als die Integration des Master Slave Indexes in Datenbanksysteme ist die Integ ration des Library Modells gt Kap 4 1 in traditionelle Datei und Betriebssysteme hnlich wie bei der Referenz Library gt Kap 6 kann das bereits vorhandene Dateisystem als Grundlage f r eine Library dienen die parallel zum eigentlichen Dateisystem das Speichern von Dateien erm g licht Ein zus tzlicher Datei Manager und speziell ausgestattete Applikationen k nnen dann ber eine zus tzliche Programmierschnittstelle auf die Library zugreifen 124 8 Zusammenfassung und Ausblick Dies ist jedoch unbefriedigend da die Library ins normale Dateisystem integriert werden soll Dazu existieren je nach Plattform unterschiedliche M glichkeiten D
208. yright varchar 127 IMGArtist varchar 127 IMGComment varchar 127 IMGFocus varchar 15 IMGBlende varchar 15 IMGChip varchar 11 AUDMin int AUDSec int AUDHund int AUDChannels int AUDBits int AUDSamples int AUDSampleRate int LSTAnz 1 int LSTAnz2 int LSTAnz3 int LSTAnz4 int LSTOptionen int LSTCreationTime varchar 5 LSTCreationYear int D Testprogramm PostgreSQL LSTCreationMonth int LSTCreationDay int conn cmd ExecuteNonQuery StopWatch sw new StopWatch Metadaten laden DataSet ds new DataSet ds ReadXml J Dokumente und Einstellungen ROOT Eigene Dateien DISS SRC METADATA XML String prefix INSERT INTO Test int cols ds Tables 0 Columns Count Indexe erstellen int a 0 a lt cols a cmd new OleDbCommand CREATE INDEX idx a ToString ON Test USING btree ds Tables 0 Columns a ToString conn cmd ExecuteNonQuery for int a 0 a lt cols a prefix prefix ds Tables 0 Columns a ToString 4 a lt cols 1 prefix prefix sw Reset ee DataRow f in ds Tables 0 Rows String st prefix VALUES for int a 0 a lt cols a String v flal ToString Replace _ if v v 0 st st v if a lt cols 1 st st st st
209. ysteme und verwaltet daher beliebige Attribute und Metadaten der jeweiligen Daten objekte Auf Basis eines derartigen Speichersystems konnte die Benutzerschnittstelle mittels diver 123 Integration Indexierung und Interaktion hochdimensionaler Datenobjekte ser Techniken etwa Join Operationen gt Kap 7 2 oder automatischer Ordner gt Kap 7 4 ver bessert werden Dadurch wird das urspr ngliche Ziel den Zugriff auf Dateien zu optimieren gt Kap 1 erreicht 8 2 Integration in existierende Systeme Die in dieser Arbeit beschriebenen Verbesserungen lassen sich zum Teil in bereits bestehende Sys teme integrieren Dies gilt vor allem f r den Master Slave Index gt Kap 8 2 1 aber auch f r die Erweiterung vorhandener Dateisysteme gt Kap 8 2 2 und Applikationen gt Kap 8 2 3 8 2 1 Master Slave Index Am besten geeignet f r den Einbau in existierende Systeme ist der Master Slave Index gt Kap 5 DBMS bieten h ufig mehrere Datenstrukturen zur Indexierung an gt Kap 3 3 so dass ein Mas ter Slave Index ggf in einer fortschrittlicheren Variante gt Kap 8 3 1 als zus tzliche Methode hinzugef gt werden kann Das DBMS wird dadurch in die Lage versetzt hochdimensionale Daten objekte mit heterogenen Schemata effizient zu indexieren Ein entsprechend ausger stetes DBMS kann f r alle Indexe ber mehr als d Attribute automatisch einen Master Slave Index als Daten struktur ausw hlen oder berl sst den je
210. ze test Thu Jan 01 1970 12 00 AM New sy Modified Where can we BoxtoAAPR Thu Jan 01 1970 12 00 AM E New Br Created Re Running a F ning right away Thu Jan 01 1970 12 00 AM gt Read All Kind Re Netscape bug correction Thu Jan 01 1970 12 00 AM ez New Ma Path Running a FGGI ning right away Thu Jan 01 1970 12 00 AM Read Ve tter I June 18 1997 Fri Jun 13 1997 09 39 PM gt Read Linda Ackerman Subject Install Guide Thu Jan 01 1970 12 00 AM amp New ONSALE_Ma onsale To eals and Deals tm Thu Jan 01 1970 12 00 AM gt New David T Pierson Cc r Filespec Question Thu Jan 01 1970 12 00 AM E New ron be com Ron Th Erom bug confirmed Thu Jan 01 1970 12 00 AM D Cen Mowe Heltzel Riek E Reply To Thu Jan 011970 12 00 AM N 1zitems Status z Priority v When 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 2 7 3 Suchfunktion Da BeFS die besonderen Attribute einiger Dateiformate einbindet ist es einfach eine inhaltsbezo gene Suche ber diese Attribute zu implementieren Nat rli
211. zt gt Kap 3 3 4 um einen genauen Referenz punkt im globalen Datenraum Q zu definieren Dennoch werden im Folgenden Indexstrukturen f r diese Operationen untersucht da auf diese Weise wertvolle Erkenntnisse f r die Indexierung von Dateien gewonnen werden 3 3 1 1 Triviale Extreme Die Nachbarschaftssuche in einem d dimensionalen Datenraum beinhaltet das Spezifizieren eines Punktes p und die Suche nach dem Datenobjekt das den geringsten Abstand zu p aufweist Eine Erweiterung die k Nachbarschaftssuche soll die k n chstgelegenen Objekte liefern Bor99 F r diese Probleme existieren zwei triviale Algorithmen die entweder die Suchzeit oder den Spei cherbedarf minimieren Zum einen kann f r alle Objekte der Abstand zu p ausgerechnet werden wobei das Objekt mit dem kleinsten Abstand gespeichert und zur ckgeliefert wird Die Ausf h rungszeit betr gt O n der zus tzliche Speicherbedarf ist konstant Der andere Extremfall existiert nur wenn eine endliche Anzahl von Suchanfragen m glich ist dann kann das Ergebnis f r jede denkbare Anfrage im Voraus berechnet und gespeichert werden Suchanfragen k nnen dann in O d beantwortet werden allerdings wird dies mit einem exponentiellen Speicherbedarf erkauft Bor99 Das eigentliche Problem der Nachbarschaftssuche besteht nun darin gleichzeitig die Laufzeit und den Speicherbedarf zu minimieren F r sinnvolle Umgebungen z B euklidischer Datenraum und beliebige n und d scheint kein Algo

Integration, Indexierung und Interaktion

Contents

Download Pdf Manuals

Related Search

Related Contents