Serialisierbarkeit (Datenbanken)

Serialisierbarkeit (Datenbanken)

Definitionen #

Operationen einer Transaktion serialisierbarkeit_datenbanken_c76727dd2f7610df6caf965c086720928bd4252e.svg

  • serialisierbarkeit_datenbanken_dbc8e5b559016af117d4f7e1630fba07ac99acdc.svg lesen von serialisierbarkeit_datenbanken_874a462690fc792889fb3f5d5ac1fd10c61ca248.svg
  • serialisierbarkeit_datenbanken_a889f1e6e999d77952b5bcb400b34f0cd9997969.svg schreiben von serialisierbarkeit_datenbanken_874a462690fc792889fb3f5d5ac1fd10c61ca248.svg
  • serialisierbarkeit_datenbanken_7c4dfc2cd157dbe29e21023deead14e3bfc23b46.svg abort
  • serialisierbarkeit_datenbanken_46e437a724681d09ed917fcdcf308b6610368934.svg commit
  • serialisierbarkeit_datenbanken_138f5e977ac800082770e7494155d37ab8db1f87.svg “happend before relationship”

Konsistenzanforderungen #

Alle Operationen müssen vor einem abort oder commit durchgeführt werden.

  • serialisierbarkeit_datenbanken_1eebecae20ef3fe8622d75cb3778ccce2d7e0845.svg
  • oder
  • serialisierbarkeit_datenbanken_176501c7d72ca41ea41bcbbe2d081728cf38016e.svg

Reads und writes haben eine Reihenfolge

  • serialisierbarkeit_datenbanken_fe5e820549157c3a0f94304b1b19a44ec897e118.svg
  • oder
  • serialisierbarkeit_datenbanken_af5f443b5a2eb75aaad40cf7567532f1916468c2.svg

Historie #

  • serialisierbarkeit_datenbanken_6811e172f559294b8034f8e05a23944df7e265f7.svg - serialisierbarkeit_datenbanken_5dd5bfd771ed183ed63489cf5a1a7b54415940bc.svg ist die Union aller Transaktionen
  • serialisierbarkeit_datenbanken_3b970fbfdef2e2da4f0c72b144dca936492a4326.svg - serialisierbarkeit_datenbanken_805abf6247cdb8a1612a817bca054077dfd82a54.svg enthält alle "happened before relationships" aller Transaktionen einzeln und eventuell noch ein paar mehr zwischen den Transaktionen (die zum gleichen Ergebnis führen würden)

Konfliktoperationen #

Zwischen reads und writes zweier Transaktionen serialisierbarkeit_datenbanken_c76727dd2f7610df6caf965c086720928bd4252e.svg und serialisierbarkeit_datenbanken_ac9c30301be78d55d392eeb81e6952ee03e6e56a.svg treten in folgenden Fällen Konflikte auf:

  • serialisierbarkeit_datenbanken_dbc8e5b559016af117d4f7e1630fba07ac99acdc.svg und serialisierbarkeit_datenbanken_758c23d7b1cee019a1f9bb21c08e34b3e1600ce3.svg: Die Reihenfolge ist entscheident
  • serialisierbarkeit_datenbanken_a889f1e6e999d77952b5bcb400b34f0cd9997969.svg und serialisierbarkeit_datenbanken_758c23d7b1cee019a1f9bb21c08e34b3e1600ce3.svg: Auch hier ist die Reihenfolge entscheident

Für zwei Konfliktoperationen serialisierbarkeit_datenbanken_1e07f5ea8054cbe9e33803f209e513c65026fcf2.svg und serialisierbarkeit_datenbanken_d1ac3adad050d6764cc1738b2dbafdbb97477619.svg gilt daher etweder:

  • serialisierbarkeit_datenbanken_dd4e0cfc4644ade7cff2458e5b05536e0e70a572.svg
  • oder
  • serialisierbarkeit_datenbanken_eb96b25fd4a28aa919b97a3558365000ee12d790.svg

Serialisierbar #

Eine Historie serialisierbarkeit_datenbanken_5dd5bfd771ed183ed63489cf5a1a7b54415940bc.svg ist serialisierbar, wenn sie äquivalent zu einer seriellen Historie ist.

Das ist der Fall wenn der Serialisierbarkeitsgraph kreisfrei ist.

Serialisierbarkeitsgraph #

  • Ein Graph mit den Transaktionen als Knoten.
  • Kanten (serialisierbarkeit_datenbanken_4d55f163463a5e8b813ff60082cc1278d44120d4.svg) werden gebildet aus:
    • serialisierbarkeit_datenbanken_75c2521e13c58df364dfccf58553e34001356031.svg
    • serialisierbarkeit_datenbanken_83f35fbba4721bdb512d02c5dedb888668f178d7.svg
    • serialisierbarkeit_datenbanken_579dd1efaa58d4ffcf609377797a0a5f7cab7d52.svg

    • Konfliktoperationen in der Historie führen zu einer Kante

Beispiel #

führt zu

“Liest von” Beziehung #

serialisierbarkeit_datenbanken_c76727dd2f7610df6caf965c086720928bd4252e.svg liest von serialisierbarkeit_datenbanken_ac9c30301be78d55d392eeb81e6952ee03e6e56a.svg in serialisierbarkeit_datenbanken_5dd5bfd771ed183ed63489cf5a1a7b54415940bc.svg wenn gilt:

  • serialisierbarkeit_datenbanken_d5c5cab07ac422c8df040871f29fa5e02e07c3c9.svg

  • UND serialisierbarkeit_datenbanken_ac9c30301be78d55d392eeb81e6952ee03e6e56a.svg wird vor dem read nicht aborted:

    serialisierbarkeit_datenbanken_783dd2801abc5cf6e54af6771eaefdc13477d6c4.svg

  • UND alle writes die zwischendrin auf serialisierbarkeit_datenbanken_874a462690fc792889fb3f5d5ac1fd10c61ca248.svg passiert sind wurden bis zum read aborted.

    serialisierbarkeit_datenbanken_b3b137a36285477f29b0691252568a24bf04954d.svg

Beispiel serialisierbar #

Kann serialisiert werden zu:

Beispiel nicht serialisierbar #

Eigenschaften von Historien #

Rücksetzbar (RC) #

Alle Transaktionen serialisierbarkeit_datenbanken_ac9c30301be78d55d392eeb81e6952ee03e6e56a.svg von denen gelesen wurde, wurden committed bevor wir (serialisierbarkeit_datenbanken_c76727dd2f7610df6caf965c086720928bd4252e.svg) comitten dürfen.

serialisierbarkeit_datenbanken_711e91e9eefb32231a5e5711598458cf8d75d62d.svg

Einfaches Kriterium, kann aber zu cascading aborts führen, da lesende Transaktionen vor dem Commit merken, dass die schreibenden TAs aborted wurden.

Avoiding Cascading Abort (ACA) #

Wenn

serialisierbarkeit_datenbanken_36c450d94220bb2d9fdbd305cac65cd5cacd0737.svg

ist sichergestellt, dass es keine cascading aborts gibt, da die Daten schon committet sind. serialisierbarkeit_datenbanken_3ac3b48cbb74153cdfc209a2e4a9e62d27ced5e0.svg Es gibt keine dirty reads.

Strikte Historien (ST) #

Wenn

serialisierbarkeit_datenbanken_81cdacdb1d821f26f46ec45ec174f782580c758f.svg

für irgendwelche operationen serialisierbarkeit_datenbanken_97cf90974e268a07fea3e3c0199b5d1dca6fa353.svg, dann wurde serialisierbarkeit_datenbanken_ac9c30301be78d55d392eeb81e6952ee03e6e56a.svg davor committet oder abortet.

  • serialisierbarkeit_datenbanken_cf8d7297fd50c3ced42bc36ecab9912883372876.svg
  • ODER
  • serialisierbarkeit_datenbanken_2f4352b6b9a74779a89f66825b15b3d466752403.svg

Serialisierbar (SR) #

siehe oben

Calendar July 20, 2022 (Updated October 22, 2023)