Skip to content

Instantly share code, notes, and snippets.

@theaspect

theaspect/acid.sql

Last active December 12, 2021 20:06
Download ZIP

Revisions

  1. theaspect revised this gist Nov 21, 2020. 1 changed file with 361 additions and 5 deletions.
    366 changes: 361 additions & 5 deletions acid.sql
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,24 @@
    -- Транзакция - связанный набор операций
    --
    -- Atomicity Атомарность, выполняется либо целиком, либо целиком откатывается/отменяется
    -- Вася Петя
    -- 20 10
    -- 20-10
    -- СБОЙ СИСТЕМЫ
    -- 10+10

    -- Consistency Консистентность, после завершения транзакции система должна оказаться в непротиворечивом состоянии
    -- Граф A <-> B
    -- NodeID (not null), ParentId (not null, FK NodeId)
    -- BEGIN
    -- A Null (Запрещено ключами)
    -- B A
    -- UPDATE table SET ParentID = B where NodeID = A
    -- COMMIT

    -- Isolated Изолированность - Транзации происходящие одновременно с текущей не должны влиять
    -- Durable Надежность – Как только произошел коммит, никакой сбой произошедший после коммита не должен на него повлиять

    -- Atomicity транзакция выполняется либо полностью либо откатывается целиком
    -- Consistency если база данных находится в консистентном состоянии (все инварианты выполнены),
    -- то после транзакции база останется в консистентном состоянии
    @@ -60,7 +81,7 @@ select * from account;
    BEGIN;
    UPDATE account set balance = balance + 10 where client = 'petya';
    select * from account;
    UPDATE account set balance = balance - 1 where client = 'vasya';
    UPDATE account set balance = balance - 10 where client = 'vasya';
    select * from account;
    COMMIT;

    @@ -69,7 +90,7 @@ select * from account;
    BEGIN;
    UPDATE account set balance = balance - 10 where client = 'vasya';
    select * from account;
    UPDATE account set balance = balance + 1 where client = 'petya';
    UPDATE account set balance = balance + 10 where client = 'petya';
    COMMIT;
    -- Одновременно во втором коннекте КОНЕЦ

    @@ -90,8 +111,8 @@ COMMIT;
    -- rollback T2:
    -- unlock(v)
    -- блокировка v успешна
    -- read(p)
    -- write(p)
    -- read(v)
    -- write(v)
    -- commit:
    -- unlock(v)
    -- unlock(p)
    @@ -105,4 +126,339 @@ COMMIT;

    -- Процесс поиска блокировок периодически строит граф и ищет в нём циклы

    -- stale/fair
    -- Read-Write lock
    -- R W
    -- R + -
    -- W - -

    -- CAP-theorem consistency/availability/partition-tolerance
    -- BASE - Basically Available, Soft state, Eventually Consistent
    -- stale/fair

    use se;
    show schemas;
    show tables;

    # Cycle
    drop table if exists graph;
    create table graph(
    id INT primary key,
    parent_id INT not null,
    FOREIGN KEY (parent_id) references graph(id)
    );
    select * from graph;

    # 1, 2
    # 2, 1

    insert into graph values (1, 2);
    insert into graph values (2, 1);

    insert into graph values
    (1, 2),
    (2, 1);

    insert into graph values (1, NULL);
    insert into graph values (2, 1);
    UPDATE graph set parent_id = 2 where id = 1;

    insert into graph values (1, 1);
    insert into graph values (2, 1);
    UPDATE graph set parent_id = 2 where id = 1;
    select * from graph;

    -- mysql not support deferred checks
    set foreign_key_checks = 0;
    BEGIN;
    insert into graph values (1, 2);
    insert into graph values (2, 1);
    COMMIT;
    set foreign_key_checks = 1;

    -- copy from console 2
    # use se;
    # SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
    # BEGIN;
    # select * from t;
    # ROLLBACK;
    #
    # SET SESSION TRANSACTION ISOLATION LEVEL READ COMMITTED;
    # BEGIN;
    # UPDATE t set b = b + 1 WHERE a = 1;
    # COMMIT;
    #
    # SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ;
    # BEGIN;
    # insert into t values (3, 3);
    # select * from t;
    # COMMIT;
    #
    # SET SESSION TRANSACTION ISOLATION LEVEL SERIALIZABLE;
    # BEGIN;
    # insert into t values (4, 4);
    # select * from t;
    # COMMIT;

    show schemas;
    create schema if not exists se;
    use se;

    drop table if exists t;
    create table t (a int primary key, b int);
    insert into t values (1, 1), (2, 2);
    select * from t;


    -- READ UNCOMMITTED
    -- READ COMMITTED
    -- REPEATABLE READ
    -- SERIALIZABLE

    -- Isolation Level Dirty Read Nonrepeatable Read Phantom Read Serialization Anomaly
    -- Read uncommitted Allowed, but not in PG Possible Possible Possible
    -- Read committed Not possible Possible Possible Possible
    -- Repeatable read Not possible Not possible Allowed, but not in PG Possible
    -- Serializable Not possible Not possible Not possible Not possible

    -- Lost Update (невозможен)
    -- T1 T2
    -- BEING
    -- b = b + 1 where a = 1 BEGIN
    -- b = b + 2 where a = 1
    -- COMMIT
    -- COMMIT

    -- Первый пользователь попытался купить билет
    -- Второй пользователь в этот момент увидел что билет куплен
    -- У первого пользователя не хватило денег и он отказался

    -- Dirty Read
    -- T1 T2
    -- b = b + 1 where a = 1
    -- select b
    -- rollback

    SET SESSION TRANSACTION ISOLATION LEVEL READ UNCOMMITTED;
    BEGIN;
    UPDATE t set b = b + 1 WHERE a = 1;
    select * from t;
    ROLLBACK;

    show processlist;
    kill connection 19;
    kill query 19;

    -- Non repeatable read
    -- T1 T2
    -- select b
    -- b = b + 1 where a = 1
    -- select b
    -- rollback

    SET SESSION TRANSACTION ISOLATION LEVEL READ COMMITTED;
    BEGIN;
    select * from t;
    -- update in t2
    select * from t;
    ROLLBACK;

    -- Phantom read
    -- T1 T2
    -- select b
    -- insert b (3, 3)
    -- select b
    -- rollback

    SET SESSION TRANSACTION ISOLATION LEVEL REPEATABLE READ;
    BEGIN;
    -- select * from t;
    -- insert in t2
    -- select * from t;
    -- mysql does not allow phantom reads, but allow phantom writes
    select * from t;
    -- insert in t2
    update t set b = 10 where a = 3;
    select * from t;
    COMMIT;

    -- Самая строгая изоляция
    SET SESSION TRANSACTION ISOLATION LEVEL SERIALIZABLE;
    BEGIN;
    select * from t;
    update t set b = 3 where a = 3;
    select * from t;
    COMMIT;

    -- Нормальные формы
    -- Дублирование
    -- Аномалии DML
    -- Неконсистентность

    -- 1НФ
    -- Нет повторений
    -- Все значения скалярны
    drop table if exists cars;
    create table cars (brand varchar(100), model varchar(100));
    insert into cars values ('BMW', 'X5, X7'), ('NISSAN', 'GT-R'), ('NISSAN', 'GT-R');
    select * from cars;

    drop table if exists cars;
    create table cars (brand varchar(100), model varchar(100), primary key (brand, model));
    insert into cars values
    ('BMW', 'X5'),
    ('BMW', 'X7'),
    # ('NISSAN', 'GT-R'),
    ('NISSAN', 'GT-R');
    select * from cars;


    -- 2НФ
    -- 1НФ +
    -- Каждый неключевой атрибут неприводимо зависит от каждого потенциального кллюча
    -- (схемы с простыми ключами всегда во 2НФ)
    -- Аномалии:
    -- Избыточность
    -- Нельзя создать склад без деталей
    -- Удаление детали приводит к потере склада
    drop table if exists store;
    create table store (
    store varchar(100),
    detail varchar(100),
    count int,
    address varchar(100),
    primary key (store, detail));
    insert into store values
    ('main', 'monitor', 10, 'bakinsky 15'),
    ('main', 'laptop', 10, 'bakinsky 15'),
    ('aux', 'mouse', 1, 'kuznetsky 18');
    select * from store;

    -- Разбиваем составной ключ

    drop table if exists stores;
    create table stores (
    store varchar(100) primary key,
    address varchar(100));
    insert into stores values
    ('main', 'bakinsky 15'),
    ('aux', 'kuznetsky 18');

    drop table if exists details;
    create table details(
    store varchar(100),
    detail varchar(100),
    count int,
    primary key (store, detail),
    foreign key (store) references stores(store)
    );
    insert into details values
    ('main', 'monitor', 10),
    ('main', 'laptop', 10),
    ('aux', 'mouse', 1);

    select * from stores;
    select * from details;

    select * from stores s join details d on s.store = d.store;

    -- 3НФ
    -- 2НФ +
    -- Ни один неключевой отрибут не находится в зависимости от потенциального ключа
    -- (Есть транзитивные зависимости между атрибутами)
    drop table if exists employee;
    create table employee (name varchar(100) primary key, department varchar(100), phone varchar(100));
    insert into employee values
    ('vasya@example.com', 'development', '101'),
    ('petya@example.com', 'development', '101'),
    ('kolya@example.com', 'qa', '103');
    select * from employee;

    -- НФБК 3+НФ Бойс Кодд
    -- Более строгая 3НФ
    -- Каждая нетривиальная неприводимая слева функциональная зависимость
    -- имеет в качестве своего детерминанта некоторый потенциальный ключ
    -- (Нет зависимостей внутри ключа)
    drop table if exists supplier;
    create table supplier(
    code int,
    supplier varchar(100),
    detail varchar(100),
    count int,
    primary key (code, supplier, detail));
    insert into supplier values
    (1, 'gl', 'internet', 100),
    (1, 'gl', 'tv', 10),
    (2, 'papa', 'pizza', 5);
    select * from supplier;

    -- 4НФ
    -- НФБК +
    -- Все нетривиальные многозначные зависимости фактически являются функциональными зависимостями от потенциальных ключей
    -- Аномалии:
    -- При добавлении пиццы или района необходимо добавить все районы/пиццы/рестораны
    -- При удалении теряется информация от районах/пиццах
    drop table if exists pizza;
    create table pizza (
    restraunt varchar(100),
    pizza varchar(100),
    district varchar(100),
    primary key (restraunt, pizza, district));
    insert into pizza values
    ('sovetsky', 'pepperoni', 'central'),
    ('sovetsky', 'margarita', 'central'),
    ('raduga', 'margarita', 'kirovsky'),
    ('raduga', 'margarita', 'rudnichny');
    select * from pizza;

    -- Пиццы
    -- Рестораны
    -- delivery, rest_district Ресторан -> Районы доставки
    -- assort Ресторан -> Пиццы

    -- order (delivery_id, assort_id, 10)

    -- 5НФ
    -- 4НФ +
    -- Отсутствуют сложные соединения между атррибутами
    -- Аномалии:
    -- Продавец имеет право торговать только с определенными фирамами
    -- данное отношение не может исключать ситуации когода отношение нарушается
    drop table if exists seller;
    create table seller (
    seller varchar(100),
    supplier varchar(100),
    product varchar(100),
    primary key (seller, supplier, product));
    insert into seller values
    ('ya', 'bosch', 'refrigerator'),
    ('ya', 'bosch', 'cooker'),
    ('ya', 'lg', 'vacuum'),
    ('promenad', 'bosch', 'washing machine'),
    ('promenad', 'lg', 'vacuum');
    select * from seller;
    -- Необхоимо разбить на три отношения


    -- ДКНФ
    -- Каждое наложенное ограничение является логическим следствием ограничений доменов и
    -- ограничений ключей наложенных на данную переменную отношения
    -- По-сути задание перечня допустимых значений для каждого типа

    -- 6НФ
    -- 5НФ +
    -- Переменная отношения находится в 6НФ тогда и только тогда когда удовлетворяет всем нетривиальными зависимостям соединения
    -- Декомпозиция 6НФ невозможна без потерь
    -- Применяется во временных рядах
    --
    -- id клиента
    -- Интервал дат
    -- Улица |
    -- Город |
    -- Штат | - Каждое из полей может изменяться независимоб что приводит к дублированию данных
    -- Индекс |
    -- Телефон |

    -- Можно разбить на отдельные отношения, но из-за того что интервалы могут не пересекаться сложно джойнить
    -- circular inclusion constraint требует при наличии хотя бы одной строки из (улицы, города, штата, индекса)
    -- все остальные тоже должны существовать. Это требование невозможно выполнить в современных БД,
    -- поэтому ограничения выносятся в слой приложения
  2. theaspect created this gist Apr 4, 2020.
    108 changes: 108 additions & 0 deletions acid.sql
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,108 @@
    -- Atomicity транзакция выполняется либо полностью либо откатывается целиком
    -- Consistency если база данных находится в консистентном состоянии (все инварианты выполнены),
    -- то после транзакции база останется в консистентном состоянии
    -- внутри транзакции консистентность может нарушаться
    -- Isolation эффекты одних транзакций не должны влиять на другие транзакции
    -- Durability эффекты от завершенной транзакции должны быть устойчивыми

    -- Transaction последовательность операций либо выполняется либо отклонояется


    -- Инварианты:
    -- Суммарный баланс не должен меняться
    -- Баланс >= 0
    drop table if exists account;
    create table account(client varchar(100) primary key, balance int);
    insert into account values
    ('vasya', 100),
    ('petya', 200);
    select * from account;

    -- do check in application petya's balance >= 100
    -- BEGIN;
    update account set balance = balance - 100 where client = 'petya';
    update account set balance = balance + 100 where client = 'vasya';
    -- COMMIT;
    -- ROLLBACK;
    select * from account;


    -- Race Condition (Lost Update)

    -- Connect1 Connect2
    -- read petya read petya
    -- check petya balance check petya balance
    -- petya -100
    -- write 100
    -- petya -200
    -- write 0

    BEGIN;
    select * from account;
    UPDATE account set balance = balance + 10 where client = 'petya';
    select * from account;
    ROLLBACK;

    -- Одновременно во втором коннекте НАЧАЛО
    BEGIN;
    select * from account;
    UPDATE account set balance = balance + 20 where client = 'petya';
    select * from account;
    COMMIT;
    -- Одновременно во втором коннекте КОНЕЦ

    -- Option 1 прервать
    -- Option 2 перезапустить

    -- Deadlock

    select * from account;
    BEGIN;
    UPDATE account set balance = balance + 10 where client = 'petya';
    select * from account;
    UPDATE account set balance = balance - 1 where client = 'vasya';
    select * from account;
    COMMIT;

    -- Одновременно во втором коннекте НАЧАЛО
    select * from account;
    BEGIN;
    UPDATE account set balance = balance - 10 where client = 'vasya';
    select * from account;
    UPDATE account set balance = balance + 1 where client = 'petya';
    COMMIT;
    -- Одновременно во втором коннекте КОНЕЦ

    -- Lock, Unlock, Read, Write
    -- p == petya
    -- v == vasya

    -- T1 T2
    -- lock(p)
    -- lock(v)
    -- read(p)
    -- read(v)
    -- write(p)
    -- write(v)
    -- lock(v) <- Ждём T2
    -- lock(p) <- Ждём Т1
    -- обнаружена блокировка
    -- rollback T2:
    -- unlock(v)
    -- блокировка v успешна
    -- read(p)
    -- write(p)
    -- commit:
    -- unlock(v)
    -- unlock(p)

    -- Список Блокировок
    -- T1: p
    -- T2: v

    -- Граф ожидания
    -- T1 <-> T2 (цикл в графе)

    -- Процесс поиска блокировок периодически строит граф и ищет в нём циклы

    -- stale/fair