| Autor(en): |
Armin Roth |
Titel: |
Efficient query answering in peer data management systems |
| Gutachter: |
Ulf Leser; Felix Naumann; Kai-Uwe Sattler |
| Erscheinungsdatum: |
12.03.2012 |
| Volltext: |
pdf
(urn:nbn:de:kobv:11-100200575)
|
| Fachgebiet(e): |
Informatik |
| Schlagwörter (ger): |
Kosten, Anfragebearbeitung, Peer-Daten-Management-Systeme, Vollständigkeit |
| Schlagwörter (eng): |
Peer data management systems, Query answering, Completeness, Cost |
| Einrichtung: |
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II |
| Lizenz: |
|
| Zitationshinweis: |
Roth, Armin:
Efficient query answering in peer data management systems;
Dissertation,
Humboldt-Universität zu Berlin, Mathematisch-Naturwissenschaftliche Fakultät II , publiziert am 12.03.2012, urn:nbn:de:kobv:11-100200575
|
Metadatenexport:
 Um
den gesamten Metadatensatz im Endnote- oder
Bibtex-Format zu speichern,
klicken Sie bitte auf den entsprechenden Link.
|
Endnote
Bibtex
|
| print on demand:
Wenn
Sie auf dieses Icon klicken, können Sie
ein Druckexemplar dieser Publikation bestellen.
|
|
| Diese Seite taggen:
Diese
Icons führen auf so genannte Social-Bookmark-Systeme, auf denen Sie
Lesezeichen anlegen, persönliche Tags vergeben und Lesezeichen anderer Nutzer
ansehen können.
|
|
| Abstract (ger): |
| Peer-Daten-Management-Systeme (PDMS) bestehen aus einer hochdynamischen
Menge heterogener, autonomer Peers. Die Peers beantworten Anfragen einerseits
gegen lokal gespeicherte Daten und reichen sie andererseits nach einer Umschreibung
anhand von Schema-Mappings an benachbarte Peers weiter.
Solche aufgrund fehlender zentraler Komponenten eigentlich hoch-
flexiblen Systeme leiden bei zunehmender Anzahl von Peers unter erheblichen Effi-
zienzproblemen. Die Gründe hierfür liegen in der massiven Redundanz der Pfade im
Netzwerk der Peers und im Informationsverlust aufgrund von Projektionen entlang
von Mapping-Pfaden.
Anwender akzeptieren in hochskalierten Umgebungen zum Datenaustausch in vielen
Anwendungsszenarien Konzessionen an die Vollständigkeit der Anfrageergebnisse.
Unser Ansatz sieht in der Vollständigkeit ein Optimierungsziel und verfolgt einen
Kompromiß zwischen Nutzen und Kosten der Anfragebearbeitung. Hierzu schlagen
wir mehrere Strategien für Peers vor, um zu entscheiden, an welche Nachbar-Peers
Anfragen weitergeleitet werden. Peers schließen dabei Mappings von der Anfragebearbeitung
aus, von denen sie ein geringes Verhältnis von Ergebnisgröße zu Kosten,
also geringe Effizienz erwarten.
Als Basis dieser Schätzungen wenden wir selbstadaptive Histogramme über die
Ergebniskardinalität an und weisen nach, daß diese in dieser hochdynamischen Umgebung
ausreichende Genauigkeit aufweisen. Wir schlagen einen Kompromiß zwischen
der Nutzung von Anfrageergebnissen zur Anpassung dieser Metadaten-Statistiken
und der Beschneidung von Anfrageplänen vor, um den entsprechenden Zielkonflikt
aufzulösen. Für eine Optimierungsstrategie, die das für die Anfragebearbeitung verwendete
Zeit-Budget limitiert, untersuchen wir mehrere Varianten hinsichtlich des
Effizienzsteigerungspotentials. Darüber hinaus nutzen wir mehrdimensionale Histogramme
über die Überlappung zweier Datenquellen zur gezielten Verminderung der
Redundanz in der Anfragebearbeitung.
|
| Abstract (eng): |
| Peer data management systems (PDMS) consist of a highly dynamic set of autonomous,
heterogeneous peers connected with schema mappings. Queries submitted
at a peer are answered with data residing at that peer and by passing the queries
to neighboring peers. PDMS are the most general architecture for distributed integrated
information systems. With no need for central coordination, PDMS are highly
flexible. However, due to the typical massive redundancy in mapping paths, PDMS
tend to be very inefficient in computing the complete query result as the number
of peers increases. Additionally, information loss is cumulated along mapping paths
due to selections and projections in the mappings.
Users usually accept concessions on the completeness of query answers in large-scale
data sharing settings. Our approach turns completeness into an optimization
goal and thus trades off benefit and cost of query answering. To this end, we propose
several strategies that guide peers in their decision to which neighbors rewritten
queries should be sent. In effect, the peers prune mappings that are expected to
contribute few data. We propose a query optimization strategy that limits resource
consumption and show that it can drastically increase efficiency while still yielding
satisfying completeness of the query result.
To estimate the potential data contribution of mappings, we adopted self-tuning
histograms for cardinality estimation. We developed techniques that ensure sufficient
query feedback to adapt these statistics to massive changes in a PDMS. Additionally,
histograms can serve to maintain statistics on data overlap between alternative
mapping paths. Building on them, redundant query processing is reduced by
avoiding overlapping areas of the multi-dimensional data space. |
Zugriffsstatistik:
Die Daten für die Zugriffsstatistik der einzelnen Dokumente
wurden aus den durch AWStats aggregierten Webserver-Logs erstellt.
Sie beziehen sich auf den monatlichen Zugriff auf den Volltext sowie
auf die Startseite. Die Zugriffsstatistik wird nicht standardisiert erfasst und kann maschinelle Zugriffe enthalten.
Bei Formatversionen eines Dokuments, die aus mehreren Dateien bestehen
(insbesondere HTML), wird jeweils der monatlich höchste Zugriffswert
auf eine der Dateien (Kapitel) des Dokuments angezeigt.
Um die detaillierten Zugriffszahlen zu sehen,
fahren Sie bitte mit dem Mauszeiger
über die einzelnen Balken des Diagramms.
|
 | |  | | | | | | | | | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 |
| Monat | Apr
12 | May
12 | Jun
12 | Jul
12 | Aug
12 | Sep
12 | Oct
12 | Nov
12 | Dec
12 | Jan
13 | Apr
13 | | Startseite | | | 7 | 6 | 8 | | | | | 1 | | | PDF | 5 | 7 | 5 | 3 | 6 | 10 | 12 | 3 | 14 | 18 | 24 |
Gesamtzahl der Zugriffe seit Apr 2012: - Startseite – 22 (2.44 pro Monat)
- PDF – 107 (9.73 pro Monat)
|
