Processing math: 100%

Wiki

A universe of ideas

User Tools

Site Tools


uni:8:dbs2:zusammenfassung

Differences

This shows you the differences between two versions of the page.

Link to this comparison view

Both sides previous revisionPrevious revision
Next revision
Previous revision
uni:8:dbs2:zusammenfassung [2015-07-17 18:13] skrupellosuni:8:dbs2:zusammenfassung [2020-11-18 18:11] (current) – external edit 127.0.0.1
Line 1: Line 1:
 ====== Zusammenfassung ====== ====== Zusammenfassung ======
 +Die Mega-Übersicht
 +<code>
 +Synchronisation
 + Pessimistische Synchronisation mit Sperren
 + Sperrprotokolle
 + 2PL [deadlocks]
 + Konservatives 2PL
 + Striktes 2PL [deadlocks]
 + Konservatives + Striktes 2PL
 + Sperrverfahren
 + RX
 + RUX
 + RAX
 + RIX
 + RAC
 + Deadlocks
 + Vermeiden [konservatives 2PL/precaiming]
 + Erkennen
 + Wartegraph
 + Time-Out
 + wound-wait
 + wait-die
 + Pessimistische Synchronisation mit Zeitstempeln
 + Optimistische Synchronisation mit Zeitstempeln
 + BOCC
 + BOCC+
 + FOCC
 +</code>
 +
 +  * [[Synchronisation]]
 +
 ===== Grundbegriffe ===== ===== Grundbegriffe =====
 ==== Anforderungen (Codd) ==== ==== Anforderungen (Codd) ====
Line 25: Line 56:
   * Durability (Abgeschlossene Transaktionen sind von dauer)   * Durability (Abgeschlossene Transaktionen sind von dauer)
  
-===== Synchronisation =====+
 ==== Serialisierungs-Graph ==== ==== Serialisierungs-Graph ====
 ^ x ^ y ^ z | <- Attribute | ^ x ^ y ^ z | <- Attribute |
Line 66: Line 97:
 | konfliktäquivalent | Gleiche Abhängigkeitsmengen | | konfliktäquivalent | Gleiche Abhängigkeitsmengen |
  
-===== Locking ===== +===== Integrität ===== 
-==== Verfahren ==== +  * Schlüssel-~ 
-=== (Voll) === +  * Referenzielle ~ 
-^    ^     ^ +  * Multiplititäten Constraints 
-  (-)  |+  * Allgemeine Constraints 
 + 
 +===== Datenschutz ===== 
 +==== Discretionary Access Controll (DAC==== 
 +Explizite Autorisierung: 
 +<blockquote>//Subjekt// bekommt //Zugriffsrecht// auf //Objekt//</blockquote> 
 +  grant ... on ... to ... 
 +   
 +==== Verfeinertes DAC ==== 
 +Implizite Autorisierung: 
 +  * //starke// Autorisierung überschreibt //schwache// Autorisierung 
 +  * Es gibt //positive// und //negative// Autorisierung 
 +  * Subjekte, Objekte und Operationen haben eine Hierarchie 
 + 
 + 
 +  * Implizite Weitergabe positiver Autorisierung in die eine Richtung 
 +  * Implizite Weitergabe negativer Autorisierung in die andere Richtung 
 + 
 +==== Mandatory Access Control (MAC) ==== 
 +  * Sicherheitsklassen für //Subjekte// und //Objekte// 
 +  * Objekte hochstufen (V) 
 +  * Objekte runter stufen (X
 +  * Zugriff wenn ''class(S>= class(O)'' 
 +  * Angelegte Objekte ''class(S) =< class(O)'' 
 + 
 +===== HW ===== 
 +B+ 
 +  * Directory/Index Seiten 
 +  * Datenseiten 
 + 
 +  * **Sequenziell** \\ tscan=tseek+fttransfer+fcpuffertlat 
 +  * **Wahlfrei** \\ trandom=(tseek+cindexttransfer+tlat)a 
 + 
 +===== Anfrageoptimierung ===== 
 +==== Arten ==== 
 +  * **Logische Anfrageoptimierung** \\ Auswertungsplan umbauen 
 +  * **Physische Anfrageoptimierung** \\ Algorithmen auswählen 
 + 
 +==== Logische Anfrageoptimierung ==== 
 +=== Umformungsregeln === 
 +  * RS=SS 
 +  * RS=SR 
 +  * RS=SR 
 +  * R×S=S×R 
 +  * (RS)T=R(ST) 
 +  * (RS)T=R(ST) 
 +  * (RS)T=R(ST) 
 +  * (R×S)×T=R×(S×T) 
 +  * σA(σB(R))=σB(σA(R)) 
 +  * σAB(R)=σA(σB(R)) 
 +  * πA(πB(R))=πA(R) mit AB 
 +  * πA(σB(R))=σB(πA(R)) mit attr(B)A 
 +  * σB(RS)=σB(R)S mit attr(B) attr(R) 
 +  * σB(R×S)=σB(R)×S mit attr(B) attr(R) 
 +  * σB(RS)=σB(R)σB(S) 
 +  * σB(RS)=σB(R)σB(S) 
 +  * σB(RS)=σB(R)σB(S) 
 +  * πB(RS)=πB(R)πB(S) 
 +  * σA=B(R×S)=RA=BS 
 + 
 +=== Algo === 
 +  - σ splitten 
 +  - σ nach unten 
 +  - σ und × =>  
 +  - π einfügen, um auf minimum beschränken 
 +  - π nach unten 
 +  - σ mergen 
 + 
 +===== Big Data ===== 
 +  * high-**volume** 
 +  * high-**velocity** 
 +  * high-**variety** 
 + 
 +==== Map-Reduce ==== 
 +  - **Map** \\ Data => KV-Pair 
 +  - **Shuffle** \\ Same key to same node 
 +  - **Reduce** \\ Marge Values per Key 
 + 
 +==== Zählanfrage auf unsicheren Daten ==== 
 +F=(1P(A)+xP(A)) 
 + 
 +==== Data Warehouse ==== 
 +OLTP                          | OLAP                         | 
 +| Online Transaction Processing | Online Analytical Processing | 
 +| Detail                        | Nur relevante                | 
 +| Aktuelle                      | Historische                  | 
 +| Ist eine quelle               | Hat viele quellen            | 
 +| Veränderbar                   | Nur hinzufügen               | 
 + 
 +<blockquote>//Fakten// in //hierachischen// //Dimensionen//</blockquote> 
 + 
 +=== Relationales mapping === 
 +Faktentabelle in der Mitte 
 +== Snowflake == 
 +Eine Tabelle pro Hierachieebene pro Dimension 
 + 
 +== Star == 
 +Eine Tabelle pro Dimension 
  
-=== RX === +===== Recovery ===== 
-   ^         ^ +==== Fehlerarten ==== 
- R |  (+)  |  (-)  | +  * Transaktionsfehler => Rücksetzen 
- X |  (-)  |  (-)  |+    * Lokales UNDO 
 +  * Systemfehler => Warmstart 
 +    * Globales UNDO 
 +    * Globales REDO 
 +  * Medienfehler => Geräte-Recovery 
 +    * Globales REDO
  
-=== RUX === +==== Logging ==== 
-  * U: update/lesen +  * Physisch [Bit-Blöcke] 
-   ^             ^ +    * Übergangslogging [XOR] 
-^  R |  (+)  |  (-)  |  (-)  | +    * Zustandslogging [Volle ...] 
- U |  (+)  |  (-)  |  (-)  | +      * Seiten-Logging [... Seiten] 
- X |  (-)  |  (-)  |  (-)  |+      * Eintrags-Logging [... Einträge] 
 +  * Logisches Logging [Befehle/Parameter loggen] 
 +  * Physiologisches Logging [Befehle/Parameter pro Seite]
  
-Übergänge: +=== Aufbau Log-File === 
-  * -> X: Möchte jetzt schreiben+Ringbuffer 
 +  * LSN (Fortlaufende Nummer) 
 +  * TA-ID (Welche Transaktion) 
 +  * Page-ID (Welche Seite) 
 +  * REDO 
 +  * UNDO 
 +  * PrevLSN
  
-=== RAX === +Log-Granularität $<=$ Sperrgranularität
-  * A: = U (update/lesen)+
  
-^    ^             ^ +=== Einbringungsstrategie (wo in DB=== 
-^  R |  (+  (+)  |  (-)  | +  * Direkt (NonAtomic, Update in-place=> UNDO nötig 
-^  A |  (+)  |  (-)   (-)  | +  * Indirektes Einbringen (Atomic["Daneben ablegen"] => Kein UNDO nötig
-^  X |  (-  (-)  |  (-)  |+
  
-Übergänge: +=== Verdrängungsstrategien (wann frühestens Puffer -> DB) === 
-  * A -> X: Möchte jetzt schreiben +  * No-Steal [Nach COMMIT] => Kein UNDO 
-=== RIX === +  * Steal [egal] => UNDO
-Auf oberer Ebene (Tabelle): +
-^      ^           IR  ^   IX  ^  RIX  ^ +
-^    R |  (+)  |  (-)  |  (+)  |  (-)  |  (-)  | +
-^    X |  (-)  |  (-)  |  (-)  |  (-)  |  (-)  | +
-^   IR |  (+)  |  (-)  |  (+)  ^  (+)  ^  (+)  | +
-^   IX |  (-)  |  (-)  ^  (+)  ^  (+)  |  (-)  | +
-^  RIX |  (-)  |  (-)  ^  (+)  |  (-)  |  (-)  |+
  
-^ Überprüfung auf unterer Ebene nötig  ^+WAL-Prinzip: UNDO muss vor Änderungen an DB im Log stehen
  
-  * Obere Ebene hat ... +=== Ausschreibungsstrategie (wann spätestens Puffer -> DB) === 
-    * **R** +  * Force [Vor COMMIT] => Kein REDO 
-    * **X** +  No-Force [egal] => REDO
-  * Untere Ebene hat ... +
-    * R => **IR** +
-    => **IX** +
-  * Obere Ebene hat //R//, untere Ebene hat //X// ... +
-    * **RIX** (mix aus //R// und //IX//)+
  
 +COMMIT-Regel: REDO muss vor COMMIT im Log stehen
  
-Auf unterer Ebene (Tupel): RX/RUX/RAX +==== Sicherungen ==== 
-=== RAC === +=== Arten === 
-  * **A** Änderung Vneu im cache +  * TOC: Sicherung //einer// TA (entspricht Force) 
-  * **C** Valt wird noch von alten Lesern gelesen+  TCC: Alle Änderungen raus schreiben, derweil keine //TA//. 
 +  * ACC: Alle Änderungen raus schreiben, derweil keine //Operation//.
  
-^    ^   R           ^ +=== Ablauf === 
-^  R  (+)   (+)   (+)  +| 1. Analyse   | Gewinner/Verlierer Bestimmen                    || 
-^  A  (+)   (-  (-)  | +2. REDO      Vollständiges REDO          Gewinner REDO      
-^  C  (+)   (-)   (-)  |+3. UNDO      UNDO (damalslaufender TAs UNDO verlierer TA  | 
 +4. Abschluss Sicherungspunkt erstellen                       ||
  
-Übergänge: +  * Gewinner => COMMIT im log 
-  * A -C: Bei commit +  * Verlierer =Rest
-==== Eigenschaften ==== +
-^ Verfahren ^ Kein Verhungern ^ Deadlockfrei \\ selbes Obj.  ^ Deadlockfrei \\ anderes Obj.  ^ Schedule ^ Bemerkung ^ +
-|   RX | (X) | (X) |  (X) | kaskadierte freies rücksetzen | Parallele Leser | +
-|  RUX | (V) | (V) |  (X) |  | Parallele Leser | +
-|  RAX | (X) | (V) |  (X) |  | Zwar nach kein verklemmen, dafür verhungern für mehr Parallelität  |+
uni/8/dbs2/zusammenfassung.1437149606.txt.gz · Last modified: 2020-11-18 18:10 (external edit)