Informatik Forsch. Entw. (2007) 21: 125–126 DOI 10.1007/s00450-007-0026-0

EDITORIAL

Editorial zum Themenheft: ,,Datenbanksysteme“ Theo H¨arder

Online ver¨offentlicht: 31 Mai 2007 © Springer-Verlag 2007

Die BTW ist die gr¨oßte deutsche Tagung zu allen Themen in den Bereichen Datenbanken und Informationssysteme. Sie versteht sich als das zentrale Forum der deutschen Datenbankgemeinde, bei dem Wissenschaftler, Praktiker und Anwender im zweij¨ahrigen Turnus u¨ ber ihre Forschungs- und Entwicklungsergebnisse vortragen. Die BTW begann 1985 als Tagungsreihe ,,Datenbanksysteme f¨ur B¨uro, Technik und Wissenschaft“; das Akronym BTW wurde vor einigen Jahren umgedeutet und steht heute f¨ur ,,Datenbanksysteme f¨ur Business, Technologie und Web“. Vom 7. bis 9. M¨arz 2007 fand die 12. BTW-Tagung der Gesellschaft f¨ur Informatik (GI) an der RheinischWestf¨alischen Technischen Hochschule (RWTH) Aachen statt. Nach u¨ ber 20 Jahren ist das Gebiet der Datenbanksysteme sowohl seitens der Forschung als auch seitens der Anwendungen etabliert und allgemein akzeptiert als ein Gebiet, welches nach wie vor wichtige Beitr¨age zum Fortschritt der Informationstechnik leistet. Heute gilt die Datenbanktechnologie als der wichtigste St¨utzpfeiler der Softwarebranche. Datenbanksysteme sind als Standardsoftware auf s¨amtlichen Rechnerplattformen vorhanden; Datenbanken sind zentrales Fundament vieler Anwendungen und Anwendersysteme. Datenbanktechnologie ist nicht nur unverzichtbar f¨ur große und skalierbare Web-Anwendungen und Service-orientierte Architekturen, sondern ist bereits auch integrierter Bestandteil vieler eingebetteter Technologien. Sie erlaubt die Realisierung umfassender digitaler Bibliotheken und die zunehmend genauere Datenanalyse mithilfe von Data-Warehouseund Data- Mining-Ans¨atzen. Trotzdem zeichnen sich noch viele neue Herausforderungen ab, etwa bei der Informationsintegration von heterogenen, verteilten Datenquellen, beim Grid Computing oder beim Web 2.0. Die BTW 2007 sollte Datenbank-Kernthemen (Technologie) und -Anwendungen (Business und Web) gleichrangig reflektieren. Dazu wurden Einreichungen zur Da-

tenbanktechnik und zu ihrem Zusammenspiel mit anderen Techniken und Anwendungen erbeten. Von den etwa 60 eingereichten Aufs¨atzen wurden 12 Lang- und 12 Kurzbeitr¨age angenommen und zusammen mit drei eingeladenen Beitr¨agen in einem Tagungsband der GI-Edition (Lecture Notes in Informatics, Volume P-103) publiziert. Erg¨anzt wurde dieser Tagungsband mit Kurzdarstellungen von zwei Arbeiten, die mit Preisen f¨ur hervorragende Dissertationen im Datenbankbereich ausgezeichnet wurden, sowie weiteren Beitr¨agen im Industrie- und im Demonstrationsprogramm. Die f¨unf am besten bewerteten Beitr¨age des wissenschaftlichen Programms wurden f¨ur eine Ver¨offentlichung in diesem Themenheft ausgew¨ahlt. Dazu wurden die Autoren aufgefordert, verbesserte und erweiterte Versionen ihrer Aufs¨atze zu erstellen, die erneut begutachtet wurden. Der erste Beitrag, Master-detail clustering using merged indexes von G¨otz Graefe (HP Labs Palo Alto, CA, USA), beschreibt spezielle B-B¨aume, die mehrere herk¨ommliche Indexe vereinigen und ihre Eintr¨age in einer gemeinsamen Sortierreihenfolge speichern. Auf diese Weise l¨asst sich in relationalen Datenbanken eine hierarchische Clusterbildung zusammengeh¨origer S¨atze erzielen und somit die Denormalisierung von der logischen Ebene der Tabellen und Zeilen auf die physische Ebene der Indexe und S¨atze verlagern. Dazu werden viele zugeh¨orige Implementierungsaspekte wie Mehrbenutzersynchronisation und Recovery, Kontrolle relationaler Integrit¨atsbedingungen, spezielle Aktualisierungsoperationen und Vorkehrungen f¨ur die Anfrageverarbeitung usw. diskutiert. Schließlich wird gezeigt, dass insbesondere durch die Clusterbildung im Vergleich zum Einsatz herk¨ommlicher Indexe die E/A-Kosten f¨ur den Verbund in Beziehung stehender Tabellen auf einen Bruchteil gesenkt werden k¨onnen, wobei zus¨atzlich Spareffekte bei der Puffernutzung erreicht werden.

13

126

Ebenso die Verbesserung der Anfrageverarbeitung betreffend befasst sich im zweiten Beitrag, Extending a tuplebased XPath algebra to enhance evaluation flexibility, Christian Mathis (Technische Universit¨at Kaiserslautern) vertieft mit der algebraischen Behandlung der XML-Anfragesprache XPath. Bisher konnten viele leistungsstarke Auswertungsalgorithmen auf physischen XML-Dokumenten wie beispielsweise der ,,Holistic Twig Join“ nicht in den ¨ Ubersetzungsund Optimierungsprozess einbezogen werden. Durch Einf¨uhrung eines logischen strukturellen Verbundes erweitert er eine herk¨ommliche logische XMLAlgebra, so dass damit XPath-Ausdr¨ucke in eine physische Algebra u¨ bersetzt und dabei diese fehlenden Auswertungsalgorithmen integriert werden k¨onnen. Der an der TU Kaiserslautern entwickelte XML Transaction Coordinator erlaubte empirische Leistungsanalysen, die Effizienzsteigerungen von einer Gr¨oßenordnung nachwiesen. Skyline-Anfragen unterst¨utzen eine besonders intuitive Form der Anfragestellung, da der Benutzer das gew¨unschte Anfrageergebnis nur qualitativ u¨ ber Pr¨aferenzen spezifizieren muss. Der dritte Beitrag, Restricting skyline sizes using weak pareto dominance von Wolf- Tilo Balke, Ulrich G¨untzer und Wolf Siberski (Forschungszentrum L3S, Hannover und Universit¨at T¨ubingen) untersucht die Ableitung interessanter Teilmengen der Pareto Skyline, die f¨ur interaktive Aufgaben wie Anfrageverfeinerung oder RelevanzFeedback genutzt werden k¨onnen. Solche Teilmengen m¨ussen klein, effizient zu berechnen, f¨ur hochdimensionale Anfragen geeignet und m¨oglichst repr¨asentativ sein. Das vorgeschlagene Verfahren l¨asst nicht nur die Gr¨oße der Ergebnismengen deutlich schrumpfen, sondern verbessert auch die Auswertungszeit um etwa zwei Gr¨oßenordnungen. Beim Problem der Reverse k-Nearest Neighbors (RkNN) ist es das Ziel, alle Objekte in einer Datenbank zu finden, in deren k-n¨achster Nachbarumgebung ein gegebenes Anfrageobjekt enthalten ist. Viele Anwendungen erfordern nur eine n¨aherungsweise Antwort auf RkNN-Anfragen, wobei es besonders wichtig ist, schnell eine Antwort mit hohem Recall zur¨uckzuliefern. Im vierten Beitrag dieses Themenheftes, Efficient reverse k-nearest neighbor estima-

13

H¨arder

tion, schlagen die Autoren Elke Achtert, Christian B¨ohm, Peer Kr¨oger, Peter Kunath, Alexey Pryakhin und Matthias Renz (Ludwig-Maximillians-Universit¨at M¨unchen) einen Ansatz f¨ur eine effiziente, n¨aherungsweise RkNN-Suche in beliebigen metrischen R¨aumen vor, wobei der Wert von k erst zur Anfragezeit spezifiziert wird. Das Verfahren nutzt existierende metrische Indexstrukturen und verwendet eine Absch¨atzung der N¨achsten-Nachbar-Distanzen, um den Suchraum zu beschr¨anken. Durch empirische Analysen wird gezeigt, dass die vorgeschlagene L¨osung signifikant besser skaliert als existierende nicht-approximative Verfahren und die Antwortmenge einen hohen Recall aufweist. Der f¨unfte Beitrag, Algebraic query optimization for distributed top-k queries stammt von Thomas Neumann und Sebastian Michel (Max-Planck-Institut f¨ur Informatik, Saarbr¨ucken). Da die Daten auf verschiedenen Rechnern verteilt sind, muss bei der Optimierung der Anfrageauswertung neben der lokalen Rechnerleistung insbesondere die Netzwerklast ber¨ucksichtigt werden. Die Anfrageoptimierung erfolgt mithilfe der dynamischen Programmierung, wobei f¨ur die Absch¨atzung bestimmter Kosten spezielle Annahmen getroffen werden. Der optimierte Anfrageplan wird hierarchisch ausgewertet, wobei nur eine kleine und fest vorgegebene Anzahl von Kommunikationsschritten ausgef¨uhrt wird. Der Erfolg dieser Optimierung in Form einer beachtlichen Reduktion von Netzwerklast und Antwortzeit wird durch eine Vielzahl an Experimenten mit realen Daten belegt. Ich m¨ochte mich bei den Autoren f¨ur die z¨ugige und stets reibungslose Kooperation bei der Erstellung dieses Themenheftes bedanken. Sie haben ihre Konferenzbeitr¨age f¨ur dieses Themenheft erweitert und sich einem erneuten Begutachtungsprozess unterworfen. Dazu mussten sie den teilweise engen Zeitrahmen einhalten und kurzfristig Verbesserungen und Erg¨anzungen in ihre Beitr¨age einarbeiten. Den Gutachtern danke ich daf¨ur, dass sie in kurzer Zeit diese Beitr¨age ausf¨uhrlich bewertet und kommentiert haben. Theo H¨arder, Technische Universit¨at Kaiserslautern