Speicherung von XML-Dokumenten

 Datenbank

 194 views
of 113
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Description
XML und Datenbanken Speicherungsmethoden Meike Klettke meike@informatik.uni-rostock.de www.xml-und-datenbanken.de 1 Inhalt  Anforderungen an die Speicherung…
Share
Transcript
XML und Datenbanken Speicherungsmethoden Meike Klettke meike@informatik.uni-rostock.de www.xml-und-datenbanken.de 1 Inhalt  Anforderungen an die Speicherung  Motivation der Existenz verschiedener Varianten  Vorstellung verschiedener Speicherungsverfahren – Speicherung und Indizierung – Speicherung der Graphstruktur – strukturierte Speicherung in Datenbanken  Hybride Verfahren  Weiterführende Literatur Meike Klettke 2 Anforderungen an die Speicherung von XML-Dokumenten Nach (Fiebig, Kanne, Moerkotte)  Effektive Speicherung  Effizienter Zugriff auf XML-Dokumente oder Teile davon – Transaktionsverwaltung – Unterstützung von XPath und XQuery – Unterstützung von SAX und DOM für Anwendungen  Wiederherstellbarkeit der Dokumente (oder der Informationen aus den Dokumenten) Meike Klettke 3 Unterteilung von XML- Dokumenten Datenzentrierte Dokumente Meyer strukturiert, regulär 1-234-56789-0 2 Beispiele: Produktkataloge, Bestellungen, 30.00 Rechnungen Dokumentzentrierte Dokumente XML builds on the principles of two existing unstrukturiert, irregulär languages, HTML and SGML to create a simple Beispiele: wissenschaftliche Artikel, mechanism .. The generalized markup concept .. Bücher, E-Mails, Webseiten Semistrukturierte Dokumente Neil Bradley datenzentrierte und dokumentzentrierte XML companion 1-234-56789-0 Anteile XML builds on the principles of two existing Beispiele: Veröffentlichungen, Amazon languages, HTML and .. Meike Klettke 4 Speicherungsmethoden  Vorstellung von verschiedenen Methoden – Grundprinzip der Speicherung – Eigenschaften – Anfragemöglichkeiten  Dabei Klassifikation bekannter Methoden Meike Klettke 5 Speicherung von XML-Dokumenten strukturierte Speicherung Speicherung der Speicherung als Ganzes Dokumentstruktur in Datenbanken Volltext- und Volltextindex XML-Index Information Retrieval Suchmaschinen Text Extender - Oracle Text - DB2 Text Extender - Informix Text Data Blades Meike Klettke 6 Exkurs: Information Retrieval  Volltextindizierung = grundlegende Technologie im Information Retrieval  Eingesetzt bei der Verarbeitung von – Textdokumenten – Universitätskatalogen oder in – Suchmaschinen – überall hinter solchen Feldern: Meike Klettke 7 Gewünschte Suchfunktionalität  „wo findet man Informationen über objektrelationale Datenbanken?“  „wo ist der Begriff Information Retrieval definiert?“  „wo ist der Zusammenhang zwischen Datenbanken und Information Retrieval erläutert?“  „was sind Biomembranen?“  die Verarbeitung solcher Informationen: Inhalt des Gebietes Information Retrieval (nach Norbert Fuhr: = inhaltsbasierte Suche in Texten)  beachten muss man Effizienz, in der Regel liegen große Textmengen zugrunde  Anwendung in Suchmaschinen, spezielle Anforderungen dabei Meike Klettke 8 Typische Suchfunktionalität: google Meike Klettke 9 Suchfunktionalität: Bibliothek Meike Klettke 10 man sucht also ein Dokument..  zum Beispiel html, pdf, ps, in dem die in der Suche angegebenen HTML-Dokument: Begriffe auftauchen  Computer „versteht“ die Texte nicht, man kann also nur danach ... suchen, welche Wörter in den Information Retrieval Texten vorkommen, wie oft, in ... Datenbanken welchem Zusammenhang ... ... Information ... Web ... Datenbank Meike Klettke 11 Überblick über die Dokumentverarbeitung /1 „Such doch mal im Internet danach ...“ Notwendigkeit eines Indexes:  damit Anfragen effizient ausgeführt werden können Inhaltsbasierte Suche in Volltexten  Deskribierung  Recherche  Ergebnispräsentation Meike Klettke 12 2. Überblick über die Dokumentenverarbeitung Recherche Suche von Textdokumenten nach Vorgabe von Dokumentdeskriptoren Index Bewertung Ordnung der gefundenen Dokumente nach ihrer Güte Deskribierung Ranking, Relevance Feedback manuelle und automatische Verfahren zur Anreicherung des strukturierten Textes mit Deskriptoren Meike Klettke 13 Indexbildung /1  Suchmaschinen für das WWW realisieren eine Indexbildung über Webseiten  Übrigens: Information-Retrieval-Systeme und Datenbanksysteme führen ebenfalls eine Indexbildung nach der Speicherung von Dokumenten durch  Bei Indexbildung muss bereits feststehen, welche Arten von Informationen angefragt werden und wie die Anfragen aussehen  Anfragen sind zeitkritisch, Indexbildung nicht ! Meike Klettke 14 Deskribierung Recherche Suche von Textdokumenten nach Vorgabe von Dokumentdeskriptoren Index Bewertung Ordnung der gefundenen Dokumente nach ihrer Güte Deskribierung Ranking, Relevance Feedback manuelle und automatische Verfahren zur Anreicherung des strukturierten Textes mit Deskriptoren Meike Klettke 15 Indexbildung /2  aus den Dokumenten werden die relevanten Stichworte extrahiert, diese fließen in den Index ein ... Information Retrieval Datenbank ... Datenbanken Datenbanken ... Information Information, 2* ... Web Retrieval ... Datenbank Web Meike Klettke 16 Implementierung als invertierte Liste Term i d3 (15) d2(25,30) d4(50) d1(300) Term j d2(45) Dokumente d1..dn Term k d2(335) d1(435) • verschiedene Optimierungen dieser Indexstrukturen • Anfragen sind zeitkritisch, die Indexbildung nicht, Ziel sind also effiziente Zugriffe Meike Klettke 17 Übersicht über Verfahren zur Deskribierung  statistische, wortbasierte Verfahren – Häufigkeit von Wörtern auswerten  linguistische Verfahren – Stammwortreduktion – Erkennen von Satzzusammen- Deskribierung Index hängen  wissensbasierte Verfahren – Klassifikationen, Thesauren, Ontologien Meike Klettke 18 Häufigkeit der Terme auswerten / 1  Stoppwortliste eliminiert sehr häufige Worte – (diese würden sehr viele Einträge im Index bewirken, sind aber für die Recherche ungeeignet) – Beispiele – 10 häufigste Begriffe im Deutschen: • der, die, und, in, den, von, zu, das, mit, sich  sehr seltene Begriffe werden gestrichen – (haben zwar die höchste Selektivität, würden die Anzahl der Begriffe im Index stark erhöhen und sind für die Recherche zu speziell) – Beispiele (aus Heuer, Saake, 2000): • BadHilfskraft • Datenbankimplmentierung Meike Klettke 19 Häufigkeit der Terme auswerten / 2 Häufig- keit Zipf´sches Gesetz (nach George Kingsley Zipf, 1902-1950) die Verteilung der Worte in einem Dokument richtet sich nach der Übersicht Rang* * Sortierung der Terme nach abfallender Häufigkeit Diskrimi- zu seltene Terme nations- kraft der Terme Salton, McGill, 1983 zur Suche eignen sich Begriffe mit mittlerer Häufigkeit am besten abnehmende Worthäufigkeit Stoppwortliste Eliminierung seltener Begriffe Meike Klettke 20 Bildung eines linguistischen Indexes / 1  Motivation: Suche nach dem Begriff soll auch Deklinationen bzw. Konjugationen einbeziehen Beispiele: – bei Eingabe des Suchbegriffes „Datenbank“ sollen auch Dokumente mit dem Begriff „Datenbanken“ gefunden werden – bei der Suche nach „fehlschlagen“ soll auch „fehlschlug“ und „fehlgeschlagen“ gefunden werden  Verfahren: statt der exakten Begriffe wird die Grundform der Terme im Dokument gespeichert  Verfahren verkleinert die invertierten Listen und führt sprachlich zusammengehörige Terme zu einem Eintrag zusammen Meike Klettke 21 Vorgehensweise bei der Bildung eines linguistischen Indexes / 2 – Wortnormalisierung (Groß- und Kleinschreibung, Umlaute) – Wortdekomposition (nur für deutsche Sprache) • Komposita (zusammengesetzte Begriffe) werden auseinandergenommen, • Beispiele: – West-mole, Ost-mole – Einzel-zimmer, Doppel-zimmer, Zweibett-zimmer, Vierbett-zimmer – Stammformreduktion, Verfahren zur Bestimmung der Grundformen durch: • Regeln (für die englische Sprache sind zahlreiche Verfahren bekannt) oder • Wörterbücher (besonders für die deutsche Sprache aufgrund vieler Unregelmäßigkeiten erforderlich) Meike Klettke 22 Recherche Recherche Suche von Textdokumenten nach Vorgabe Index von Dokumentdeskriptoren Bewertung Ordnung der gefundenen Dokumente nach ihrer Güte Deskribierung Ranking, Relevance Feedback manuelle und automatische Verfahren zur Anreicherung des strukturierten Textes mit Deskriptoren Meike Klettke 23 Verfahren zur Recherche Häufigste Retrievalmodelle - Boolesches Retrieval Recherche - Vektorraummodell Index - probabilistisches Modell Deskribierung und Recherche müssen mit den gleichen Methoden erfolgen (Stammwortreduktion, Stoppwortliste) Meike Klettke 24 Boolesches Retrieval / 1  Grundbaustein: Attribut - Attributwert - Paar  verknüpft durch: and, or, not  Nachteile: relativ geringe Möglichkeiten, Anfragen zu formulieren  oft können Benutzer die Verarbeitung der Anfrage nicht einschätzen  z.B. wurden bei Suchmaschinen Statistiken erhoben, dass die Anfragen durchschnittlich 1.7 Wörter enthalten Meike Klettke 25 Boolesches Retrieval / 2 Meike Klettke 26 Boolesches Retrieval auf invertierten Listen Term i d3 (15) d2(25,30) d4(50) Term j d2(45) d1(300) Dokumente d1..dn Term k d2(335) d1(435) • Beispielanfragen: •k • i or j • i and k • i and k and not j Meike Klettke 27 Vektorraummodell  Dokumente und Anfragen werden als Vektoren betrachtet  mit einem Ähnlichkeitsmaß (Abstandsfunktion) werden zu einer Anfrage die Ergebnisdokumente ermittelt  es gibt zahlreiche Ähnlichkeitsmaße  Ergebnis der Ähnlichkeitsfunktion kann für das Ranking verwendet werden Meike Klettke 28 Probabilistisches Modell  Terme der Anfrage können gewichtet werden, damit hat der Benutzer die Möglichkeit, wichtigere und unwichtigere Teile einer Anfrage zu spezifizieren  Terme des Dokumentes werden ebenfalls gewichtet – manuelle Verfahren: für Indizierende stellt die Angabe solcher Wahrscheinlichkeiten eine schwierige Aufgabe dar – automatische Verfahren: verwenden Termhäufigkeiten, Dokumentgröße, Position des Terms im Dokument, ..  Ähnlichkeitsfunktion liefert ebenfalls ein Ranking Meike Klettke 29 Arten von Anfragen  Boolesche Anfragen  Stammformsuche  Phrasensuche  Proximity-Suche – maximaler Wortabstand, im gleichen Satz mit, Wortreihenfolge  Phonetische Suche – Suche nach ähnlich klingenden Wörtern  fehlertolerante Suche – Zulassen von x Fehlern  Berücksichtigung der Dokumentstruktur  Wichtungsfaktoren Meike Klettke 30 Bewertung Recherche Suche von Textdokumenten nach Vorgabe von Dokumentdeskriptoren Bewertung Ordnung der gefundenen Dokumente Deskribierung nach ihrer Güte manuelle und automatische Index Ranking, Relevance Feedback Verfahren zur Anreicherung des strukturierten Textes mit Deskriptoren Meike Klettke 31 Verfahren zur Bewertung Recherche Index Bewertung  Ranking Bestimmung, in welcher Reihenfolge die ermittelten Ergebnisse präsentiert werden  Relevance Feedback Dialog mit dem Benutzer, bei dem eine neue Ergebnisermittlung aufgrund von relevanter und nicht relevanter Dokumenten ermittelt wird Meike Klettke 32 Ranking  Aufgabe: Reihenfolge für die Ausgabe der relevanten Dokumente wird gesucht  Grundlegende Maße – Häufigkeit des Suchterms im Dokument – Anzahl der verschiedenen Suchterme eines Dokumentes – Anzahl der Dokumente, in denen der Suchterm auftritt – Dokumentgröße – ... – Aus Kombinationen dieser Maße ergeben sich Rankingfunktionen  Boolesches Retrieval erlaubt kein Ranking (Ergebnis 0 oder 1), dieses wird oft nachträglich als 2. Schritt über der Menge der relevanten Dokumente ermittelt. Meike Klettke 33 Ende des Exkurses Vorgestellt wurden:  Techniken zur Textverarbeitung Jetzt folgt:  Anwendung für XML-Dokumente Meike Klettke 34 Grundprinzip der invertierten Liste Dokumente Stichworte Stichworte Dokumente A D F A 1 3 1 B 2 C 2 3 2 B C D D 1 2 3 E 3 3 A C D E F 1 Invertierte Speicherung: Bestimmung der Stichworte Speicherung der Stichworte und der Dokumente der zugehörigen Dokumente Meike Klettke 35 Volltext-Index Hotel Hübner Begriff Verweis hotel 18119 Warnemünde Warnemünde Seestraße Rostock 12 ort anreisebeschreibung Aus Richtung Rostock kommend ... - bekannte Methode (älter als relationale Datenbanken) - Verfahren aus dem Bereich der Dokumentverarbeitung Meike Klettke 36 Weiteres Beispiel Term Element nachricht autor nachname Fürst Fürst Christian dpa vorname fuerst@dpa.de Christian inhalt Mozartjahr 2006 ueberschrift … Vermarktungsfest Ein Vermarktungsfest text Wolfgang Als Wolfgang Amadeus Mozart im Alter von 35 Jahren starb, .. … Meike Klettke 37 Volltext-Index Nicht nur Suche nach exaktem Auftreten der Begriffe möglich, Verwendung von  Statistischen wortbasierten Verfahren – (Stoppwortlisten, Streichen von selten vorkommenden Begriffen)  Linguistischen Verfahren – Wortnormalisierung – (Groß-, Kleinschreibung, Getrennt- und Zusammenschreibung, Umlaute), – Wortdekomposition durch Regeln (engl.) oder Wörterbücher (dt.) – Stammwortreduktion  Wissensbasierten Verfahren – (Einsatz von Ontologien und Thesauren zur Suche nach Synonymen sowie Über- und Unterbegriffen) Meike Klettke 38 Anfragen /1  boolesches Retrieval Kombination von Anfrageteilen mit AND, OR oder NOT Beispiele: – Hotel AND Warnemünde – (Hotel OR Pension) AND (Warnemünde OR Rostock)  linguistische Anfragen – Stammwortsuche, phonetische Suche, Ähnlichkeitssuche usw. Meike Klettke 39 Anfragen /2  Position der Stichworte im Index erlaubt weitere Anfragen Beispiele: – Suchbegriff 'Datenbanken' tritt vor 'XML' im Dokument auf – der Begriff 'Information' folgt unmittelbar auf 'Retrieval‚ – 'XML' und 'Datenbanken' treten mit einem Abstand von höchstens 5 Wörtern auf  Ergebnis der Anfragen ist in der Regel das vollständige Dokument  Die Anfragen sind also Suchfunktionen  Nicht realisierbar ist jedoch: • //hotel[adresse/ort/text()=“Warnemuende“] • Nur: hotel and adresse and ort and Warnemuende Meike Klettke 40 Eigenschaften des Volltext-Indexes Schemabeschreibung Nicht erforderlich Dokumentrekonstruktion XML-Dokumente bleiben im Original erhalten Anfragen Anfragen des Information Retrieval Updates Austausch der XML- Dokumente erforderlich Weitere Besonderheiten Volltextfunktionen (SQL-MM) keine Auswertung des XML- Markups Anwendung dokumentzentrierte XML- Anwendungen Meike Klettke 41 Systeme /1 Suchmaschinen  fast alle herkömmlichen Suchmaschinen verwenden invertierte Listen zur Indexbildung IBM DB2 Text Extender  Text Extender, ermöglicht die Speicherung von Volltextdokumenten innerhalb eines Datenbanksystems  vier verschiedene Arten von Indizes können gebildet werden,  Mögliche Suchanfragen: – Stammwortreduktion, – exakte Suche, – phonetische Suche, – Ähnlichkeitssuche – … Meike Klettke 42 Systeme /2 Oracle Text  Verarbeitung von Volltext-Datentypen  Information-Retrieval-Anfragen in Form von speziellen SQL-Anweisungen  Mögliche Anfragen – Stammwortreduktion – Verwendung von Wildcards – Ähnlichkeits- und Phrasensuche  Ranking der Ergebnisse erfolgt  Relevance Feedback durch den Anwender ist möglich Meike Klettke 43 Speicherung von XML-Dokumenten strukturierte Speicherung Speicherung der Speicherung als Ganzes Dokumentstruktur in Datenbanken Volltext- und Volltextindex XML-Index DB2 Text Extender Oracle Text Informix Verity Text Search Data Blade XML-Suchmaschinen Meike Klettke 44 Volltext- und XML-Index - XML - Struktur kann in Anfragen ausgewertet werden Meike Klettke 45 Weiteres Beispiel Term Verweis Element Fürst Christian Mozartjahr Fürst Vermarktungsfest Christian Wolfgang dpa fuerst@dpa.de Mozartjahr 2006 … Element Verweis Ordnung Vorgänger Ein Vermarktungsfest nachricht 1 autor 1 Als Wolfgang Amadeus Mozart im Alter von 35 Jahren starb, .. nachname 1 vorname 2 inhalt 3 ueberschrift 1 text 2 Meike Klettke 46 Volltext- und XML-Index  Strukturinformationen müssen aus dem Index erkennbar und wiederherstellbar sein,  Zuordnung: Inhalten zum Markup sowie  Hierarchische Schachtelung und Anordnung des Markup Meike Klettke 47 Anfragen /1  boolesches Retrieval – Hotel AND Warnemünde  linguistische Anfragen – Stammwortsuche, phonetische Suche, Ähnlichkeitssuche usw.  Position der Stichworte im Index erlaubt weitere Anfragen – Suchbegriff 'Datenbanken' tritt vor 'XML' im Dokument auf – der Begriff 'Information' folgt unmittelbar auf 'Retrieval‚  Durch das Anlegen eines Strukturindexes lässt sich das Markup auswerten: • /unterkuenfte/hotel[adresse/ort/text()=“Warnemuende“ or adresse/ort/text()=“Rostock”] • /unterkuenfte/hotel[contains(name/text(),”Strand”] Meike Klettke 48 Anfragen /2  Einsatz von XPath und XQuery ist dadurch möglich  Anfragen, die das gesamte Dokument als Ergebnis liefern, lassen sich einfach realisieren,  Anderenfalls muss das Dokument geparst werden und das Ergebnis daraus generiert werden. Meike Klettke 49 Eigenschaften des Volltext- und XML-Indexes Schemabeschreibung Nicht erforderlich Dokumentrekonstruktion XML-Dokumente bleiben im Original erhalten Anfragen Anfragen des Information Retrieval Auswertung des Markups in den Anfragen XML-Anfragen möglich Updates Austausch der XML-Dokumente erforderlich Weitere Besonderheiten Volltextfunktionen (SQL-MM) Anwendung dokumentzentrierte und semistrukturierte XML-Anwendungen Meike Klettke 50 Systeme DB2 Text Extender  Speicherung von Volltextdokumenten innerhalb eines Datenbanksystems  Auswertung von Markup ist möglich  Dadurch Kombination von Volltextanfragen mit Auswertung von XML-Markup möglich Oracle Text  XML-Unterstützung durch Auswertung von XML-Strukturen  bewirkt, dass Volltextanfragen und Anfragen zur Struktur der Dokumente kombiniert werden können. Meike Klettke 51 Speicherung von XML-Dokumenten strukturierte Speicherung Speicherung der Speicherung als Ganzes Dokumentstruktur in Datenbanken (einfache) Speicherung der Abbildung der Informationen Graphstruktur des DOM Neil Bradley Florescu/Kossmann Shimura/Yoshikawa/Uemura Meike Klettke 52 Speicherung der Graphstruktur / 1 Elements: Element Type Value Order Vorgänger hotel 1 adresse 2 plz int 18119 1 ort string Warnemünde 2 strasse string Seestrasse 3 Attributes: Element Attribute Type Value url string www... autor string Müller • generische Speicherung der Struktur des XML-Dokumentes • werden mehrere XML-Dokumente in der Relation gespeichert, muss noch eine ID des XML-Dokumentes in der Relation ergänzt werden Meike Klettke 53 Weiteres Beispiel ID Element Wert Ordnung Vorgänger n001 nachricht 1 - n002 autor 1 n001 Fürst Christian n003 nachname Fürst 1 n002 dpa fuerst@dpa.de n004 vorname Christian 2 n002 n005 agentur dpa 3 n002 Mozartjahr 2006 … n006 e-mail fuerst@dpa.d 4 n002 e Ein Vermarktungsfest Als Wolfgang Amadeus Mozart im Alter von 35 Jahren starb, .. Element Attribut Typ Wert n001 id xs:ID ID0001 n001 bedeutung xs:int 4 n002 autor_id xs:ID A0001 Meike Klettke 54 Speicherung der Graphstruktur /2  Verwendung von Relationen zur Speicherung von Elementen und Attributen  Elemente: DocID Elementname Typ Wert Ordnung Verweis auf Vorgänger  Attribute: Attributname Typ Wert Verweis auf Element  Damit ist die Zuordnung von Inhalten zur Struktur, sowie die vollständige Wiederherstellung der Struktur möglich Meike Klettke 55 Speicherung der Graphstruktur /3  DTD nicht erforderlich  für einfache Anfragen verwendbar  Durch Erweiteru
Related Search
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks