Teil I Motivation und Grundlagen · 2020. 4. 14. · bersetzung, Zug riffspfadw ahl, Zug...

Teil I

Motivation und Grundlagen

Überblick

1. Aufgaben und Komponenten eines DBMS

2. Relationale vs. nicht-relationale DBMS

3. OLTP, OLAP und HTAP

4. Disk- vs. Main-Memory-Systeme

5. Klassische 5-Schichtenarchitektur

6. Neue Entwicklungen

Sattler/Saake | VL Datenbank-Implementierungstechniken | April 2019 1–1

Aufgaben und Komponenten einesDBMS

Prinzipien: Die neun Codd’schen Regeln

1. Integration: einheitliche, nichtredundante Datenverwaltung2. Operationen: Speichern, Suchen, Ändern3. Katalog: Zugriffe auf Datenbankbeschreibungen im Data

Dictionary4. Benutzersichten5. Integritätssicherung: Korrektheit des Datenbankinhalts6. Datenschutz: Ausschluss unauthorisierter Zugriffe7. Transaktionen: mehrere DB-Operationen als Funktionseinheit8. Synchronisation: parallele Transaktionen koordinieren9. Datensicherung: Wiederherstellung von Daten nach

Systemfehlern

Betrachtete Fragestellungen

Data Dictionary

Optimierer Auswertung PlattenzugriffAnfragen

Updates

SichtdefinitionDatendefinition

Datei-organisation

DB-Operationen

Einbettung

Masken

Externe Ebene Konzeptuelle Ebene Interne Ebene

Zentrale Komponenten

• Anfrageverarbeitung: Planung, Optimierung und Ausführungdeklarativer Anfragen

• Transaktionsverwaltung: Koordination und Synchronisationvon Transaktionen, Durchführung von Änderungen, Sicherungder ACID-Eigenschaften

• Speichersystem: Organisation der Daten im Hauptspeicherund auf dem Externspeicher für effizienten Zugriff undPersistenz

Klassische DB-Landschaft

Database

Application Application „Banking,SAP, …“

„Server“

„Disk“

Relationale vs. nicht-relationaleDBMS

Relationale DBMS

• Basis: Relationenmodell = Daten in Tabellen strukturiert• Beziehungen über Werte (= Fremdschlüssel),

Integritätsbedingungen• SQL als standardisierte Anfragesprache• kommerziell erfolgreichstes Datenmodell: Oracle, IBM DB2,

MS SQL Server, SAP HANA, …

WEINE WeinID Name Farbe Jahrgang Weingut

1042 La Rose Grand Cru Rot 1998 Château ...2168 Creek Shiraz Rot 2003 Creek3456 Zinfandel Rot 2004 Helena2171 Pinot Noir Rot 2001 Creek3478 Pinot Noir Rot 1999 Helena4711 Riesling Reserve Weiß 1999 Müller4961 Chardonnay Weiß 2002 Bighorn

Kritik an RDBMS / SQL

• nicht skalierbar• Normalisierung von Relationen, viele Integritätsbedingungen zu

prüfen• kann man in RDBMS auch vermeiden!

• starre Tabellen nicht flexibel genug• schwach typisierte Tabellen (Tupel weichen in den tatsächlich

genutzten Attributen ab)• viele Nullwerte wenn alle potentiellen Attribute definiert• alternativ Aufspaltung auf viele Tabellen• Schema-Evolution mit alter table unflexibel

• tatsächlich in vielen Anwendungen ein Problem• Integration von spezifischen Operationen (Graphtraversierung,

Datenanalyse-Primitive) mit Stored Procedures zwar möglichführt aber oft zu schwer interpretierbarem Code

NoSQL-Systeme

• Datenmodelle• KV-Stores• Wide Column Stores• Dokumenten-orientierte Datenhaltung• Graph-Speicher• …

• Anfragesprache ⇝ unterschiedliche Ansätze:• einfache funktionale API• Programmiermodell für parallele Funktionen• angelehnt an SQL-Syntax• …

NoSQL-Systeme: Beispiele

• dokumentenorientierte Datenbanksysteme: MongoDB• semistrukturierte Dokumente in JSON- bzw. BSON-Format• Anfragen: CRUD erweitert um dokumentspezifische Suche

• Graph-Datenbanksysteme: Neo4j• Property Graphen als Datenmodell: Knoten und Kanten mit

Eigenschaften• Anfragesprache Cypher• Muster der Form ”Knoten → Kante → Knoten …“

OLTP, OLAP und HTAP

OLTP vs. OLAP

• Online Transactional Processing (OLTP)→ Klassische operative Informationssysteme• Erfassung und Verwaltung von Daten• Verarbeitung unter Verantwortung der jeweiligen Abteilung• Transaktionale Verarbeitung: kurze Lese-/ Schreibzugriffe auf

wenigen Datensätzen• ACID-Eigenschaften

• Online Analytical Processing (OLAP)→ Data Warehouse• Analyse im Mittelpunkt = entscheidungsunterstützende

Systeme• Langandauernde Lesetransaktionen auf vielen Datensätzen• Integration, Konsolidierung und Aggregation der Daten

OLTP: Beispiel

BEGIN;SELECT KundenNr INTO KNr

FROM Kunden WHERE email = '...';INSERT INTO BESTELLUNG VALUES (KNr, BestNr, 1);UPDATE Artikel SET Bestand = Bestand-1

WHERE ArtNr = BestNr;COMMIT TRANSACTION;

OLAP: Beispiel

SELECT DISTINCT ROW Zeit.Dimension AS Jahr,Produkt.Dimension AS Artikel,AVG(Fact.Umsatz) AS Umsatzdurchschnitt,Ort.Dimension AS Verkaufsgebiet

FROM (Produktgruppe INNER JOIN Produkt ON Produktgruppe.[Gruppen-Nr] = Produkt.[Gruppen-ID]) INNER JOIN((((Produkt INNER JOIN [Fact.Umsatz] ON Produkt.[Artikel-Nr]= [Fact.Umsatz].[Artikel-Nr]) INNER JOIN Order ON[Fact.Umsatz].[Bestell-Nr]= Order.[Order-ID]) INNER JOINZeit.Dimension ON Orders.[Order-ID] =Zeit.Dimension.[Order-ID]) INNER JOIN Ort.Dimension ONOrder.[Order-ID] = Ort.Dimension.[Order-ID]) ONProduktgruppe.[Gruppen-Nr] = Produkt.[Gruppen-ID]

GROUP BY Produkt.Dimension.Gruppenname, Ort.Dimension.Bundesland,Zeit.Dimension.Jahr;

Abgrenzung OLTP – OLAP: Anfragen

OLTP OLAPFokus Lesen, Schreiben, Modi-

fizieren, LöschenLesen, periodisches Hin-zufügen

Transaktionsdauerund -typ

kurze Lese- / Schreib-transaktionen

langandauernde Lese-transaktionen

Anfragestruktur einfach strukturiert komplexDatenvolumeneiner Anfrage

wenige Datensätze viele Datensätze

Datenmodell anfrageflexibel analysebezogenAntwortzeit msecs …secs secs …min

Abgrenzung OLTP – OLAP: Daten

OLTP OLAPDatenquellen meist eine mehrereEigenschaften nicht abgeleitet, zeitak-

tuell, autonom, dyna-misch

abgeleitet / konsolidiert,historisiert, integriert, stabil

Datenvolumen MByte …GByte GByte …TByte …PByteZugriffe Einzeltupelzugriff Tabellenzugriff (spaltenwei-

• HTAP = Hybrid Transactional and Analytics Processing• Ziel: schnellere Geschäftsentscheidungen durch

”Echtzeit“-Verarbeitung• OLAP und OLTP auf der gleichen Datenbank: naheliegend,

aber große technische Herausforderung• sehr unterschiedliche Workloads (Anfrage- und Lastprofile)• Transaktionsverwaltung: gegenseitige Beeinflussung von

Änderungs- und Leseoperationen reduzieren• unterschiedliche Datenorganisation (physisch, logisch)

HTAP: Herausforderungen

OLAP OLTP

Analytical (OLAP) und Transactional processing (OLTP):

• verschiedene Zugriffscharakterisiken• verschiedene Performance-Ziele (Latenz vs. Durchsatz)

=⇒ Unterschiedliche Optimierungen notwendig

Disk- vs. Main-Memory-Systeme

Traditionelle Annahmen

• Daten sollen dauerhauft aufbewahrt werden• Datenbank ≫ Hauptspeicher• Disk ≫ Hauptspeicher• Hauptspeicher = flüchtiger (volatiler) Speicher• Disk-IO dominiert Kosten

Traditionelle Annahmen /2

Quelle [1]

Knapper Hauptspeicher

Quelle [2]

Disk-basierte Systeme

Speicherhierarchie

Hauptspeicher

Optische Platten

Magnetbänder

Festplatten, Solid-State-Disk

Primärspeicher

Sekundärspeicher

Tertiärspeicher

Eigenschaften von Speichermedien

Primär Sekundär TertiärGeschwindigkeit schnell langsam sehr langsamPreis teuer preiswert billigStabilität flüchtig stabil stabilGröße klein groß sehr großGranulate fein grob grob

Speichermedien

• Primärspeicher• Primärspeicher: Cache und Hauptspeicher• sehr schnell, Zugriff auf Daten fein granular: theoretisch jedes

Byte adressierbar (Cachelines)• Sekundärspeicher

• Sekundärspeicher oder Online-Speicher• meist Plattenspeicher, nicht-flüchtig• Granularität des Zugriffs gröber: Blöcke, oft 512 Bytes• Zugriffslücke: Faktor 105 langsamerer Zugriff

• Tertiärspeicher• Zur langfristigen Datensicherung (Archivierung) oder

kurzfristigen Protokollierung (Journale)• üblich: optische Platten, Magnetbänder• ”Offline-Speicher“ meist Wechselmedium• Nachteil: Zugriffslücke extrem groß

Transferraten HDD vs. SSD

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192

Blockgröße in KB

HDD randomSSD random

HDD seqSSD seq

Konsequenz für disk-basierte Systeme

• blockbasierter Zugriff mit typischen Blockgrößen ≥ 4 KB• speziell für Magnetplatten Optimierung auf sequentielle

Zugriffe• Disklayout: Organisation der Daten auf der Disk =

fortlaufende Folge von Blöcken• sequentielles Lesen und Schreiben

• Zugriffslücke zwischen Hauptspeicher und Disk durch Cachingverbergen (Lokalität von Zugriffen ausnutzen)

Main-Memory-Datenbanken

• klassische Annahmen nicht mehr zutreffend:• Systeme mit Hauptspeicher im TB-Bereich verfügbar• Datenbank kann komplett im Hauptspeicher gehalten werden

(muss aber dennoch persistent sein)

• Main-Memory- oder Hauptspeicher-Datenbanken:Ausnutzung der großen Hauptspeicher undMulticore-Architekturen• Beispiele: SAP HANA, Oracle TimesTen, SQL Server Hekaton,

Hyper, MemSQL, …• Besonderheiten: hauptspeicheroptimierte Datenstrukturen

(Main-Memory-Scans), Persistenz trotz volatilem Speicher,Datenkompression, Nebenläufigkeitskontrolle

Klassische 5-Schichtenarchitektur

Fünf-Schichtenarchitektur

• Architektur für klassische DBMS• basierend auf Idee von Senko 1973• Weiterentwicklung von Härder 1987• Umsetzung im Rahmen des IBM-Prototyps System R• genauere Beschreibung der Transformationskomponenten

• schrittweise Transformation von Anfragen/Änderungen bis hinzu Zugriffen auf Speichermedien

• Definition der Schnittstellen zwischen Komponenten

5-Schichtenarchitektur: Funktionen

Datensystem

Zugriffssystem

Speichersystem

Pufferverwaltung

Betriebssystem

MengenorientierteSchnittstelle

SatzorientierteSchnittstelle

InterneSatzschnittstelle

Systempuffer-schnittstelle

Datei-schnittstelle

Geräteschnittstelle

Externspeicher

Übersetzung, Zugriffspfadwahl,Zugriffskontrolle, Integritätskontrolle

Data Dictionary, Currency Pointer,Sortierung, Transaktionsverwaltung

Record Manager, Zugriffs-pfadverwaltung, Sperr-verwaltung, Logging, Recovery

Systempufferverwaltung, Seitenersetzung, Seitenzuordnung

Externspeicherverwaltung,Speicherzuordnung

5-Schichtenarchitektur: Objekte

Datensystem

Zugriffssystem

Speichersystem

Pufferverwaltung

Betriebssystem

RelationenSichten MOS

Externe SätzeIndexstrukturenScans

Interne SätzeBäumeHashtabellen

SegmenteSeiten

DateienBlöcke

ZylinderSpuren

Lies Block kSchreibe Block k

Bereitstellen Seite jFreigeben Seite j

FIND NEXT satzSTORE satz

SELECT ...FROM ... WHERE ...

LOOKUP im B-BaumINSERT in B-Baum

Erläuterungen

• mengenorientierte Schnittstelle MOS:• deklarative Datenmanipulationssprache auf Tabellen und

Sichten (etwa SQL)

• durch Datensystem auf satzorientierte Schnittstelle SOSumgesetzt:• navigierender Zugriff auf interner Darstellung der Relationen• manipulierte Objekte: typisierte Datensätze und interne

Relationen sowie logische Zugriffspfade (Indexe)• Aufgaben des Datensystems: Übersetzung und Optimierung

von SQL-Anfragen

Erläuterungen /2

• durch Zugriffssystem auf interne Satzschnittstelle ISSumgesetzt:• interne Tupel einheitlich verwalten, ohne Typisierung• Speicherstrukturen der Zugriffspfade (konkrete Operationen

auf B+-Bäumen und Hashtabellen), Mehrbenutzerbetrieb mitTransaktionen

Erläuterungen /3

• durch Speichersystem Datenstrukturen und Operationen derISS auf interne Seiten eines virtuellen linearen Adressraumsumsetzen• Manipulation des Adressraums durch Operationen der

Systempufferschnittstelle SPS• Typische Objekte: interne Seiten, Seitenadressen• Typische Operationen: Freigeben und Bereitstellen von Seiten,

Seitenwechselstrategien, Sperrverwaltung, Schreiben des Logs

• durch Pufferverwaltung interne Seiten auf Blöcke derDateischnittstelle DS abbilden• Umsetzung der DS-Operationen auf Geräteschnittstelle erfolgt

durch BS

Neue Entwicklungen

Anforderungen aus neuen Anwendungen

• Nicht-Standard-Datenmodelle (siehe NoSQL-Systeme)• flexibler Umgang mit Datenstrukturen (JSON, Schema on

Read, …)• beschränkte (Lookups) vs. erweiterte (z.B. Graphoperationen,

Datenanalysen) Anfragefunktionalität• Skalierbarkeit zu Big Data (massiv parallele/verteilte

Systeme)• dynamische Daten / Datenströme• …

Aktuelle Anwendungen / Themen

Entwicklungen im Hardware-Bereich

Picture adapted from [1]

Großer HauptspeicherQuelle [3]

Multi-core CPUs

Quelle [4]

Solid State DisksQuelle [5]

Co-ProzessorenSattler/Saake | VL Datenbank-Implementierungstechniken | April 2019 1–34

Entwicklungen im Hardware-Bereich /2

• Multicore- und Manycore-Prozessoren: 64+ Cores• Nutzung erfordert Parallelisierungstechniken und

Nebenläufigkeitskontrolle

• Memory Wall: Hauptspeicherzugriff als Flaschenhals• RAM-Zugriff 60 ns, L1-Cache: 4 CPU-Zyklen ⇝

Cache-optimierte Strukturen

• Datenbank-Accelerators• Hardware-unterstütztes Datenmanagement: FPGA, GPU als

Coprozessoren, Highspeed-Netzwerk, SSDs als zusätzlicheCache-Ebene, …

• Persistenter Memory: nicht-volatiler Speicher• Instant Restart / Recovery von Main-Memory-Datenbanken

Übungsprojekt

ToyDB: Überblick

• Sammlung von Java-Modulen zur Implementierung vonKernfunktionen eines DBMS

• Single-Process-Modell in Anlehnung an5-Schichten-Architektur

• Organisation des Externspeichers in Dateien mit Seiten festerGröße (4KByte)

• B+-Baum- und R-Baum-Indexe• Anfrageoperatoren für relationale Algebra• rudimentärer Support für Transaktionen

ToyDB: Systemarchitektur und Module

Paged File Managerdbis.toydb.pf

Record Managerdbis.toydb.rm

Index Managerdbis.toydb.ix.

Query Execution Plan Operators

dbis.toydb.qep

Statistics Managerdbis.toydb.statistics

Transaction & Lock Manager

dbis.toydb.tx

Query Processor (Rewriting & Optimization)dbis.toydb.qp

Buffer Pool Managerdbis.toydb.bp

System Managerdbis.

toydb.sm

SQL Parserdbis.toydb.parser

Command Line Processordbis.toydb.CmdLine

Zusammenfassung

• Datenmanagementfunktionalitäten in vielenSoftwaresystemen erforderlich

• nicht auf Implementierung kompletter DBMS beschränkt,sondern für nahezu alle datenintensiven Systeme: auch inSuchmaschinen, Datenanalyseanwendungen, eingebettetenSystemen, Visualisierungssystemen, Steuerungssystemen,Entwicklungsumgebungen, …

• gemeinsame Aufgaben / Komponenten: Datenorganisationund -verwaltung (Indexstrukturen), Transaktionsverwaltung /Nebenläufigkeitskontrolle / Recovery, Anfrageverarbeitung

• betrifft Datenstrukturen und Algorithmen

Web-Quellen

[1] http://commons.wikimedia.org/wiki/File:RAM_module_SDRAM_1GiB.jpg

[2] http://commons.wikimedia.org/wiki/File:Hard_disks.jpg

[3] http://www.flickr.com/photos/25757823@N07/2719552544

[4] http://commons.wikimedia.org/wiki/File:Super_Talent_2.5in_SATA_SSD_SAM64GM25S.jpg

[5] http://commons.wikimedia.org/wiki/File:Gtx260.jpg

[6] http://commons.wikimedia.org/wiki/File:Travis_Race_car.jpg

[7] http://www.flickr.com/photos/denieseclariz/7412854696

Teil I Motivation und Grundlagen · 2020. 4. 14. · bersetzung, Zug riffspfadw ahl, Zug...

Documents

KoMPressoren · steuerunGen drucKLuftAufbereitunG ... · • Kompressor mit angebautem/integ-riertem Kältetrockner, • mit oder ohne Behälter sowie • mit oder ohne Druckluftaufbereitung

Welcome! 1. Übersicht Bilingualer Zug in der Orientierungsstufe Bilingualer Zug in der Mittelstufe Fahrtenkonzept Bilingualer Zug in der Oberstufe Erwartungen

Männerrunde im Zug Frauenrunde im Zug Unterkunft De Watermann

Ost Feld Zug

ESAF 2019 Zug - panathlonzug.ch · Sportanlass mit Volksfestcharakter ESAF 2019 Zug 2019 in Zug Das „Eidgenössische“ ist das grösste wiederkehrende Sportereignis und eines der

Der zug des_lebens

Report No. 85830-TR Evaluation of the EU - TURKEY€¦ · Evaluation of the EU-Turkey Customs Union CURRENCY AND EQUIVALENT UNITS CURRENCY EQUIVALENTS (Exchange Rate Effective February

Steuerrecht des Kantons Zug · Steuerrecht des Kantons Zug Stand per 1. Januar 2020 Tax Law of the Canton of Zug Status as of 1 January 2020

Wahlen Spezial Zug

Waldgesellschaften des Kantons Zug

Projekt Zug 13302

Welcome!. Übersicht Bilingualer Zug in der Orientierungsstufe Bilingualer Zug in der Mittelstufe Fahrtenkonzept Bilingualer Zug in der Oberstufe Erwartungen

2020/05/07 · PAK'n'SAVE $70m 60m 50m New Wor d $52m Countdown $59m $51rn 2018 $62m $51m $23m 2019 Source N'elsen Currency converter: Amount: From this currency: Zealand Dollars

PUBLIC EXPENDITURE AND FINANCIAL ACCOUNTABILITY · 2016. 7. 12. · Philippines Public Financial Management Performance Review-October 2007 - - 2 Currency Equivalents Currency Unit

Zug des lebens

REPORT - Hauptseite · PDF fileMilutina Milankovića 27 · 11000 Beograd ... hangfassadensystem mit integ - ... (BLoK Architekt: B edau B rouwe architecten,

Parkhotel Zug Smokers Lounge

Wohlfühlen im Zug

Macro and Currency Outlook Highlights Q1 2018 · 2020. 1. 30. · Macro and Currency Outlook Highlights Q1 2018 Claire Dissaux Managing Director Global Economics & Strategy cdissaux@millenniumglobal.com

Der Zug des Lebens