| 书目名称 | Intervall-Indexstrukturen in Datenbanksystemen | | 编辑 | Gabriele Blankenagel | | 视频video | | | 丛书名称 | Informatik-Fachberichte | | 图书封面 |  | | 出版日期 | Book 1992 | | 关键词 | Datenbank; Datenbanksystem; Datenbanksysteme; Intervall-Indexstrukturen; algorithmische Geometrie | | 版次 | 1 | | doi | https://doi.org/10.1007/978-3-642-77590-1 | | isbn_softcover | 978-3-540-55591-9 | | isbn_ebook | 978-3-642-77590-1Series ISSN 0343-3005 | | issn_series | 0343-3005 | | copyright | Springer-Verlag Berlin Heidelberg 1992 |
| 1 |
Front Matter |
|
|
Abstract
|
| 2 |
,Einleitung, |
Gabriele Blankenagel |
|
Abstract
Datenbanksysteme wurden in der Vergangenheit vorwiegend für spezielle betriebswirtschaftliche Anwendungen, sogenannte “Standard” Anwendungen, entwickelt und viele Jahre erfolgreich eingesetzt. In den letzten Jahren hat sich das Interesse dagegen in wachsendem Maße auf die Datenbankunterstützung technisch wissenschaftlicher Anwendungen, sogenannter “Nicht-Standard” Anwendungen konzentriert, für die herkömmliche Datenbanksysteme, beispielsweise hinsichtlich der Datenmodelle und der Effizienz, ungeeignet sind. Zu diesen . zählen z.B. temporale Datenbanksysteme und geometrische Datenbanksysteme.
|
| 3 |
,Grundlagen, |
Gabriele Blankenagel |
|
Abstract
In diesem Kapitel fassen wir einige Grundlagen zusammen. Nach der Einführung einiger globaler Definitionen und Bezeichnungen erläutert der Abschnitt 2.1, wie das Points-In-Regions Mengenproblem im Kontext von Datenbanken auftritt; es folgen einige Vorbemerkungen zum Points-in-Regions Mengenproblem. In Abschnitt 2.2 wird das Speicher- und Berechnungsmodell skizziert, das wir bei der Untersuchung der internen und externen Algorithmen sowie der internen und externen Datenstrukturen zugrunde legen. In den Abschnitten 2.3 bis 2.5 wiederholen wir die Konzepte der internen Strukturen des Priority Search Tree, des Segment Tree und des Interval Tree, weil sie die Grundlage der von uns entwickelten Strukturen des externen Priority Search Tree, des externen Segment Tree und des externen Interval Tree bilden.
|
| 4 |
,Interne und externe Lösungen des Points-in-Regions Mengenproblems, |
Gabriele Blankenagel |
|
Abstract
Das . sei folgendermaßen formuliert: ..
|
| 5 |
,Der XP-Baum, |
Gabriele Blankenagel |
|
Abstract
Der . ist eine externe Struktur, die eine über einem Gitter G definierte Menge P von zweidimensionalen Punkten auf einer Menge S von externen Knoten (Seiten) darstellt und . unterstützt, die mit einem an einem Gitterrand verankerten Rechteck nach allen Punkten suchen, die in diesem Suchbereich liegen. ., die mit einem rechteckigen Suchbereich in beliebiger Lage nach allen in ihm liegenden Punkten suchen, können — weniger effizient — ebenfalls durchgeführt werden. Über einem Raster definierte Intervalle können ebenfalls in einem XP-Baum verwaltet werden, wenn sie anhand ihrer beiden Endpunkte in zweidimensionale Punkte transformiert werden. ., die mit einem Suchwert nach allen Intervallen suchen, die diesen Suchwert einschließen, und ., die mit einem Suchintervall nach allen geschnittenen Intervallen suchen, lassen sich beispielsweise in Halbbereichs-Suchen auf Punkten transformieren, so daß der XP-Baum auch diese Suchen auf Intervallen unterstützt. Daneben können auf XP-Bäumen alle anderen interessanten Suchen auf Intervallen durchgeführt werden. — Die Ergebnisse dieses Kapitels wurden bereits in [BlG90b] veröffentlicht.
|
| 6 |
,Der EST, |
Gabriele Blankenagel |
|
Abstract
Der . ist eine dynamisch balancierte externe Intervallstruktur, die eine über einem Raster definierte Menge I von Intervallen beliebiger Dichte als eindimensionale ausgedehnte Objekte auf einer Menge S von Seiten darstellt. Wie im internen Fall unterstützt der EST ., die mit einem Suchwert nach allen Intervallen suchen, die diesen Wert einschließen. — Die Ergebnisse dieses Kapitels wurden bereits in [BlG90c] veröffentlicht.
|
| 7 |
,Der EIT, |
Gabriele Blankenagel |
|
Abstract
Der . ist eine weitere dynamisch balancierte externe Intervallstruktur, die eine über einem Raster definierte Menge I von Intervallen beliebiger Dichte als eindimensionale ausgedehnte Objekte auf einer Menge S von Seiten darstellt. Wie im internen Fall unterstützt der EIT nicht nur ., sondern auch .; daneben können auf einem, leicht modifizierten, EIT alle anderen interessanten Suchen auf Intervallen durchgeführt werden.
|
| 8 |
,Vergleich von XP-Baum, EST und EIT, |
Gabriele Blankenagel |
|
Abstract
In diesem Kapitel vergleichen wir die in den letzten drei Kapiteln vorgestellten externen Strukturen miteinander. Dieses geschieht, indem zunächst Charakteristika der drei Strukturen zusammengefaßt, einander gegenübergestellt und erläutert werden. Anschließend vergleichen wir den EST und den EIT als externe Strukturen zur Verwaltung von Intervallmengen detaillierter miteinander in bezug auf Gemeinsamkeiten und Unterschiede. Schließlich werden der XP-Baum, der EST und der EIT kurz unter dem Aspekt des Einsatzes als Intervall-Indexstrukturen in Datenbanksystemen betrachtet. Abschließend schlagen wir einige Empfehlungen vor, unter welchen Umständen welche der drei Strukturen zur Unterstützung von Suchen auf einer Menge von Intervallen einzusetzen ist.
|
| 9 |
,Indexstrukturen für ausgedehnte geometrische Objekte, |
Gabriele Blankenagel |
|
Abstract
Ein wichtiges Problem, das in Nicht-Standard-Datenbanksystemen, insbesondere in geometrischen Datenbanksystemen, auftritt, besteht darin, eine große Menge von ausgedehnten geometrischen Objekten so auf Hintergrundspeichern zu verwalten, daß Schnitt-Suchen mit Suchbereichen und, als Spezialfall hiervon, Punkteinschluß-Suchen effizient unterstützt werden; eine Unterstützung von Updates ist ebenfalls wünschenswert und in manchen Anwendungen erforderlich. Zur Lösung dieses Problems erfolgten gerade in den letzten Jahren rege Forschungsaktivitäten, die zur Entwicklung zahlreicher Indexstrukturen für zwei-und mehrdimensionale ausgedehnte geometrische Objekte führten.
|
| 10 |
,Zusammenfassung und abschließende Bemerkungen, |
Gabriele Blankenagel |
|
Abstract
In diesem letzten Abschnitt fassen wir die geleistete Arbeit zusammen und zeigen Anwendungen für die entwickelten externen Algorithmen und die Intervall-Indexstrukturen auf; wir versuchen dabei, ihre Bedeutung einzuschätzen und weisen auf einige offene Punkte hin.
|
| 11 |
Back Matter |
|
|
Abstract
|
|
|
发表于 2025-3-21 17:43:04
