Why Sybase/SQL Server/DB2 SERIALIZABLE is not serializable

[vc]

vc, it is obvious to me that we have another misunderstanding here. There is no contradiction with either formal or informal definition of ACID transaction. The schedule that subsequently fails is not serializable - that's precisely why one of the transactions has to die - simply because serializable isolation level makes sure that invalid schedules never materialize. And they don't. Exactly as promised.

The schedule may be not serializable not because some scheduler decides to fail it. There is a definition(s) of a serializable schedule that you no doubt are familiar with.

In this specific case ("insert select max()'), the failure can be interpreted in two ways:

1. Arguably, the strict 2PL protocol cannot assure serializibility in a dynamic database, a database with inserts/deletes. Therefore, the SERIALIZABLE IL does not quite make it.

2. Some claim that the Strict 2PL can handle the phantoms thanks to the implicit 'control information'/index locking associated with a table. If so, then a reasonable representation for our statement, in terms of read/writes, would be:

write(control); read(y=max(X)); write(y); write(control); commit;

... which makes possible only serial schedules for transactions of this kind.

The conclusion might be that it's not the original statement which is defective but rather that the SERIALIZABLE implementation is broken and is unable to handle the SQL unless augmented with updlock. If the implementation is indeed broken, then, again, it does not quite deserve the 'true' adjective.

3. I may be missing something obvious and the statement is indeed not serializable. If so, please show me the loop in the serializability graph.


Thanks.

VC

[tengiz]

vc,

Давайте начнём с самого начала и пока оставим в стороне графы сериализации, так как это всего лишь одна из возможных техник анализа выполнения транзакций. Итак, транзакция - это :

a) последовательность шагов, которая либо выполняется целиком, либо не выполняется вовсе;
б) результат выполнения любой транзакции таков, как если бы вселенная оказалась заморожена на момент начала этой транзакции, поэтому суммарный эффект выполнения многих транзакций должен соответствовать какому-либо строго последовательному порядку их выполнения.
в) если в результате выполнения транзакций условия (а) или (б) невозможно выполнить, одна или более транзакций аварийно завершаются и любые именения сделанные такими транзакциями бесследно исчезают.

Наш пример - <insert into t (id) select 1 + max (id) from t> - упрощённо состоит из двух шагов:

1) R - прочитать максимальное значение id: max_id
2) W - добавить в таблицу строку где id = 1 + max_id

Пусть мы имеем две транзкции 1 и 2. Рассмотрим следующие варианты их параллельного выполнения в предположении, что изначально в таблице была одна строка с id = 0. Число после шагов – максимальное значение id после выполнения обеих транзакций:

1. R1, W1, R2, W2 - 2
2. R2, W2, R1, W1 - 2
3. R1, R2, W1, W2 - 1
4. R1, R2, W2, W1 - 1
5. R2, R1, W1, W2 - 1
6. R2, R1, W2, W1 - 1

Заметим, что строго последовательное выполнение тразнакций вне зависимости от их порядка должно в результате оставить состояние базы данных, где в таблице имеется три строки и максимальное значение id должно быть 2.

Следовательно, сценарии 1 и 2 соответствуют нашему определению транзакции, а сценарии 3..6, очевидно, нет. Т.е. чтобы не вызвать противоречий СУБД не должна позволить сценариям 3..6 материализоваться, как бы она не была устроена, блокировочник, версионник, гибрид, сертификатор, etc.

Блокировочник никогда не даст сценариям 3..6 успешно завершиться, как Вы знаете, эти, и только эти сценарии обязательно закончатся дедлоками. И не потому, что дедлок здесь – это досадный недостаток блокировочников, а потому, что этим сценариям просто нельзя дать успешно завершиться согласно приведённым выше определениям.

[vc]

vc,

Давайте начнём с самого начала и пока оставим в стороне графы сериализации, так как это всего лишь одна из возможных техник анализа выполнения транзакций. .

No let's use some definitions we agree on. Such as that a conflict-serializable schedule is a history whose precedence graph does not contain loops. Obviously, any mixture of operations inside the transaction pattern we are discussing satisfies the serializability requirement.

Another, simpler example would be :

Table t1(age) contains (20, 30, 40)

Transactions:

TR1: select max(age) from t1; select max(age) from t1;
TR2: insert into t1(age) values(70);

According to your definition, a 2PL locker without predicate/index locking is unable to handle (r1,w2,r1) and therefore this schedule is not serializable.
If you think, it is serializable, explain why and how its different from

TR1: read(max); write;
TR2; read(max) write;

VC

PS. My next response may come in a week as I'll be away.

[tengiz]

No let's use some definitions we agree on. Such as that a conflict-serializable schedule is a history whose precedence graph does not contain loops. Obviously, any mixture of operations inside the transaction pattern we are discussing satisfies the serializability requirement.

Нет, так не годится. Дайте правило, как Вы строите граф, а потом будем рассуждать. Кроме того, я впервые слышу о графе, построенном на precedence в контексте изоляции транзакци. Я знаю wait-for графы, depends-on графы, reads-from графы, same-write-positioning графы, serialization графы. Но всё это - всего лишь техники для описания явления и все эти методы имеют ограничения в области применения. Фундаментом же всегда является определение транзакции. Да, действительно, из определения транзакции следуют некие свойства графов (например, для wait-for графа отсутствие циклов), которым они должны удовлетворять. Но отказываясь рассуждать в самых базовых терминах, Вы заведомо сужаете область приложения рассуждений.

И даже если согласиться на Ваше ограничение и попытаться представить, как бы я строил precedence граф, то случаи 3..6 из моего примера очевидно имеют цикл. Догадайтесь сами какой.

[vc]

И даже если согласиться на Ваше ограничение и попытаться представить, как бы я строил precedence граф, то случаи 3..6 из моего примера очевидно имеют цикл. Догадайтесь сами какой.

Actually, I agree that there is a loop even though your notation is a bit misleading since it skips an important piece of information.

One might have understood, say, history 3 as:

3. R1(X), R2(X), insert1(Y), insert2(Y) -> 1,1

... where X is the max and Y = max + 1.
For this history, there would be no loop because there would be no conflicts between any of the operations under strict 2PL.

However, here the vanilla 2PL is in fact re-enforced with a sort of predicate locking (key range or table locking) and the actual schedule is more like:

3. R1(X)-with-predicate-lock; R2(X)-with-predicate-lock; insert1(Y1), insert2(Y2)

... where insert1 conflicts with R2(X) and insert2 with R1(x) which leads to a T1 <--> T2 loop in the precedence graph and a dead-lock during runtime.


So yes you are right, schedule 3 (and similarly 4,5,6) would not be serializable even if a full-blown predicate locking were available. Deadlock here is a logical outcome. I take back my words about serializable not being serializable ;)

VC

[tengiz]

vc, welcome back.

Возможно, я опять туманно выразился, но сценарии, который я перечислял, не имеют в виду никакой конкретный способ обеспечения изоляции - ни блокировки, ни версии, ни любая другая техология "тасования" операций не ограничивают рассматриваемые варианты. Это просто в чистом виде операции и все возможные их перестановки - с целью выяснить, являются ли результирующие последовательности операций сериализованными или нет.

Я исходил из того, что для мы строим графы по следующим правилам (имея в виду, что мы строим precedence графы, как Вы и предлагали, хотя обычно в литературе это делается несколько иначе):

1. Если операция транзакции T2 прочитала значение, записанное операцией транзакции T1, то очевидно, что T2 произошла после T1.
2. Если операция транзакции T2 записала поверх значения прочитанного операцией транзакции T1, либо поверх множества, которое пыталась прочитать T1, то очевидно, что транзакция T2 произошла после T1
3. Транзакция T1 и T2 либо происходят одна после другой (т.е. или T1 после T2 или T2 после T1), либо они вообще независимы (не пересекаются по данным).

Если в результате построения нарушается правило (3), то последовательность операций не является сериализуемой.

[vc]

vc, welcome back.

Thank you, I beat you on the vacation front didn't I ;)

Возможно, я опять туманно выразился, но сценарии, который я перечислял, не имеют в виду никакой конкретный способ обеспечения изоляции

Neither did I. Maybe I used outdated terminology but I was thinking, traditionally, in terms of conflicting operations: two operations conflict if both handle the same data item and at least one of them is 'write'. Now, two histories are conflict equivalent if they order conflicting operations in the same way and, further, a history is conflict serializable (or simply serializable) if its conflicting operations are ordered in the same way as those of some serial history. The precedence graph (alias serialization graph alias dependency graph) is a directed graph whose vertices are transactions and the edges are all T(i)->T(j) where one of T(i) operations precedes and *conflicts* with one of T(j)'s operations. It can be proven that a history is serializable if its precedence graph is acyclical.

Also, it can be shown that the strict two-phase locking protocol (S2PL) used in the major locking schedulers permits only the histories whose precedence graph is acyclical. So far so good, but the traditional serializability theory assumes, surprisingly, only static databases (in other words the 'write' operation in a history means only 'update'). As soon as 'inserts'/'deletes' are introduced, S2PL fails miserably ('phantoms').

In order to ensure 'true' serializabilty for dynamic databases, S2PL has to be augmented with some additional mechanism that prevents phantoms. The mechanism can be for example predicate locking or, its weak form, key range locking or table locking. With some form of predicate locking in place, it can be trivially shown (as I did in my previous message) that the precedence graph for some 'insert select max()+1' histories would contain loops. In the absence of the phantom-prevention mechanism, S2PL will permit non-serializable histories simply because inserts would not conflict with reads since they would operate on different data items.

[tengiz]

vc,

1. "Традиционная" теория появилась в семидесятые годы, примерно тогда же и было сформулировано понятие well-formed операций, которые обязательно учитывают предикаты, поэтому "традиционная" теория практически с самого начала была "правильной". Перечисленная в заголовке тройка "традиционных блокировочников" с самого начала работает именно так - поэтому они умеют 100% правильно сериализовать транзакции.

2. Настёт "динамических" и "статических" баз - даже если запретить insert/delete и только разрешить update, то 2PL без предикатных блокировок не обеспечивает сериализуемости (я думаю Вам не составит труда придумать тривиальный пример,) так что дело не в "статичности" или "динамичности" баз данных.

3. Да, Вы правы - ЛЮБОЙ механизм изоляции транзакций обязан учитывать предикаты тем или иным способом. Иначе не будет сериализуемости. Пример с max + 1 не будет правильно работать ни на одном известном мне версионнике. Генераторы последовательностей снимают только одну проблему (причём, несериализуемым способом - ситуацию спасает, правда, тот факт, что генератор - это суррогатный ключ). Что касается массы других сценариев, где нужен точный учёт предикатов - ничего другого кроме как блокировка целых таблиц версионники предложить не могут.

И именно поэтому хорошо сделанный гибрид побъёт всех.

[Dmitry67]

Да. Пример из практики: бухгалтерия нде некоторые виды документов являются так называемыми 'документами строгой отчетности' и дырки в нумерации не допустимы.

[vc]

...

2. Настёт "динамических" и "статических" баз - даже если запретить insert/delete и только разрешить update, то 2PL без предикатных блокировок не обеспечивает сериализуемости (я думаю Вам не составит труда придумать тривиальный пример,) так что дело не в "статичности" или "динамичности" баз данных.

I apologize for being dense but cannot think of any at the moment, always have thought that S2PL allows only serializable schedules in the absence of delets/insers. Please give an example.

3. Да, Вы правы - ЛЮБОЙ механизм изоляции транзакций обязан учитывать предикаты тем или иным способом. Иначе не будет сериализуемости. Пример с max + 1 не будет правильно работать ни на одном известном мне версионнике. Генераторы последовательностей снимают только одну проблему (причём, несериализуемым способом - ситуацию спасает, правда, тот факт, что генератор - это суррогатный ключ). Что касается массы других сценариев, где нужен точный учёт предикатов - ничего другого кроме как блокировка целых таблиц версионники предложить не могут.

Actually some can albeit at the application level (dbms_lock), but in general yes you are right.

[vc]

Да. Пример из практики: бухгалтерия нде некоторые виды документов являются так называемыми 'документами строгой отчетности' и дырки в нумерации не допустимы.

A 'gapless' sequence is most frequently a frivolous requirement affecting concurrency in a negative way both in MV and locking schedulers. You can have either concurrency or 'gapless' sequences but not both at the same time.

I do realize that sometimes it's impossible to change business 'logic' due to many factors having nothing to do with real logic or common sense.

[tengiz]

...always have thought that S2PL allows only serializable schedules in the absence of delets/insers. Please give an example.

Любой сценарий в котором транзакция T1 пытается прочитать данные, которые транзакцией T2 меняются так, что начинают удовлетворять условию, наложенному T1, создаёт проблемы с сериализуемостью.

Пусть исходно в t одна строка с col = 1 и одна строка с col = 2. Пусть транзакции T1 и T2 должны сделать следующее:

T1. update t set col = -col where col = 1 and not exist (select * from t where col < 0)
T2. update t set col = -col where col = 2 and not exist (select * from t where col < 0)

Понятно, что параллельное выполнение таких транзакций будет правильным только в том случае, если после их выполнения в талбице будет только одна строка с col < 0. Любой другой исход не будет соответствовать никакому варианту последовательного выполнения транзакций.

Гарантировать правильность выполнения такого сценария можно только при учёте предикатов, одними реально тронутыми данными здесь не обойтись.

[tengiz]

Actually some can albeit at the application level (dbms_lock), but in general yes you are right.

vс - я исхожу из того, что предлагается системой обработки транзакций по умолчанию. Т.е. насколько эта система в состоянии справиться с абстрактно "правильно" написанными программами, написанными без учёта её особенностей. Или другими словами - если мои программы выдают "правильный" результат (возможно, не самым эффективным образом) когда они работают по одиночке, то система должна гарантировать что при параллельном выполнении произвольного количества "правильных" программ неправильного результата никогда не будет. Причём это не должно зависеть ни от наличия индексов, ни от эффективности модели данных, ни от того, является ли система реляционной, сетевой, иерархической, etc. Bottom line - для каждой программы создаются условия, в которых она работает так, как если бы она была единственной программой в системе. Без всяческих усилий со стороны авторов программ. В этом и есть суть изоляции.

[vc]

...always have thought that S2PL allows only serializable schedules in the absence of delets/insers. Please give an example.

Любой сценарий в котором транзакция T1 пытается прочитать данные, которые транзакцией T2 меняются так, что начинают удовлетворять условию, наложенному T1, создаёт проблемы с сериализуемостью.

Пусть исходно в t одна строка с col = 1 и одна строка с col = 2. Пусть транзакции T1 и T2 должны сделать следующее:

T1. update t set col = -col where col = 1 and not exist (select * from t where col < 0)
T2. update t set col = -col where col = 2 and not exist (select * from t where col < 0)

Понятно, что параллельное выполнение таких транзакций будет правильным только в том случае, если после их выполнения в талбице будет только одна строка с col < 0. Любой другой исход не будет соответствовать никакому варианту последовательного выполнения транзакций.

Гарантировать правильность выполнения такого сценария можно только при учёте предикатов, одними реально тронутыми данными здесь не обойтись.

Well, I disagree here:

The SQLs can be interpreted as follows:

T1: read(X); read(xi | xi=1); write(xi); c;
T2: read(X); read(xj | xj=2); write(xj); c;

... where read(X) means reading the whole table (thanks to the 'not exists' predicate which selects the entire table in order to ensure that the subquery is indeed empty ).

A history with any permutation of all the reads preceding the writes would deadlock, therefore, for your example, 2PL alone would be sufficient. In other words, locking the existing data is enough to ensure serializability which is a subtle but crucial difference from the phantom inserts/deletes as in the latter case there is nothing to lock yet and in order to solve the phantom problem predicate locking would have to lock *potential* not real rows.

[tengiz]

vc - во-первых, я полагаю, что Ваше возражение не по существу. Исходные транзакции можно переписать иначе, например вот так:

if (select count (*) from t1 where col < 0) = 0 then update t set col = -col where col = 1

Во-вторых, я думаю что Вы несколько необычно понимаете предикатную блокировку. Предикатная блокировка не зависит от наличия или отсутствия реальных данных. Поэтому "predicate locking would have to lock *potential* not real rows" - это тавтология. Предикатная блокировка по определениею блокирует предикат, на основе которого делается доступ к данным вне зависимости от наличия или отсутствия удовлетворяющих предикату данных. Другое дело, что конкретные техники обеспечения предикатных блокировок используемых в реальных системах могут зависеть от наличия или отсутствия данных, но это уже детали реализации.

A history with any permutation of all the reads preceding the writes would deadlock, therefore, for your example, 2PL alone would be sufficient. In other words, locking the existing data is enough to ensure serializability which is a subtle but crucial difference from the phantom inserts/deletes...

Нет, неверно. Ровно та же самая техника (блокировка целой таблицы) позволяет избежать фантомов в случае insert/delete. В любом случае нужно как-то учитывать данные, которые не удовлетворяют условиям отбора сейчас, но могут удовлетворять позже. Поэтому если мы разрешаем использовать табличные блокировки (а они по сути нужны только тогда, когда нет предикатных блокировок реализованных любым способом), то никакой разницы между insert/delete или update нет.

[vc]

vc - во-первых, я полагаю, что Ваше возражение не по существу. Исходные транзакции можно переписать иначе, например вот так:

if (select count (*) from t1 where col < 0) = 0 then update t set col = -col where col = 1

But the re-write does not change the fact that every row (the entire table) would have to be inspected and threfore locked without any need for an additional mechanism such as predicate locking. Your new SQL is fully equivalent to the original one in terms of transaction history conflicts.

Предикатная блокировка не зависит от наличия или отсутствия реальных данных. Поэтому "predicate locking would have to lock *potential* not real rows" - это тавтология. Предикатная блокировка по определениею блокирует предикат, на основе которого делается доступ к данным вне зависимости от наличия или отсутствия удовлетворяющих предикату данных.

I fully agree with the above. My point (which you are disputing) is that predicate locking is not needed *if* the database is static, 2PL with its locking *existing* data woud be enough. Predicate locking was 'invented' precisely to handle insert/delete phantoms.

A history with any permutation of all the reads preceding the writes would deadlock, therefore, for your example, 2PL alone would be sufficient. In other words, locking the existing data is enough to ensure serializability which is a subtle but crucial difference from the phantom inserts/deletes...

Нет, неверно.

I am not sure what part of my statement you consider incorrect. Could you please clarify ?

Ровно та же самая техника (блокировка целой таблицы) позволяет избежать фантомов в случае insert/delete. В любом случае нужно как-то учитывать данные, которые не удовлетворяют условиям отбора сейчас, но могут удовлетворять позже. Поэтому если мы разрешаем использовать табличные блокировки (а они по сути нужны только тогда, когда нет предикатных блокировок реализованных любым способом), то никакой разницы между insert/delete или update нет.

It's true that predicate locking (or its implemented subsets) are enough to ensure serializability but again that's not the point I was trying to make. I believe I showed that the example you presented can be handled by a 2PL scheduler without need for predicate locking of any kind. If you think it's not so, please show where the mistake is.

[tengiz]

It's true that predicate locking (or its implemented subsets) are enough to ensure serializability but again that's not the point I was trying to make. I believe I showed that the example you presented can be handled by a 2PL scheduler without need for predicate locking of any kind. If you think it's not so, please show where the mistake is.

vc, табличная блокировка - это частный случай предикатной блокировки, когда предикатом является просто константное логическое выражение всегда дающее резальтатом TRUE. Поэтому говорить, о 2PL без предикатных блокировок, но имея в виду, что табличные блокировки разрешены - несколько странно. И именно поэтому 2PL без предикатных блокировок (и без частного их случая в виде табличных блокировок) не будет правильно работать со сценариями типа того, который мы разбираем. Вне зависимости от того используем мы delete/insert или ограничиваемся только update (который всегда логически сводится к delete/insert).

[vc]

It's true that predicate locking (or its implemented subsets) are enough to ensure serializability but again that's not the point I was trying to make. I believe I showed that the example you presented can be handled by a 2PL scheduler without need for predicate locking of any kind. If you think it's not so, please show where the mistake is.

vc, табличная блокировка - это частный случай предикатной блокировки, когда предикатом является просто константное логическое выражение всегда дающее резальтатом TRUE. Поэтому говорить, о 2PL без предикатных блокировок, но имея в виду, что табличные блокировки разрешены - несколько странно. И именно поэтому 2PL без предикатных блокировок (и без частного их случая в виде табличных блокировок) не будет правильно работать со сценариями типа того, который мы разбираем. Вне зависимости от того используем мы delete/insert или ограничиваемся только update (который всегда логически сводится к delete/insert).

Sorry, I was sloppy in my descriptions. What I've always meant is that 'not exists' /'count(*)' in your examples will scan each row and as a result will use row-level locks which are equivalent to using a table lock due to a full table scan. Never did I mean that a 'true' table lock is needed (I am aware as I've said several times that a table level lock is a crude implementation of predicate locking, the subtler variety being key range locking). None is needed (in addition to row locks) in order to ensure serializability in your examples.

[tengiz]

Sorry, I was sloppy in my descriptions. What I've always meant is that 'not exists' /'count(*)' in your examples will scan each row and as a result will use row-level locks which are equivalent to using a table lock due to a full table scan. Never did I mean that a 'true' table lock is needed (I am aware as I've said several times that a table level lock is a crude implementation of predicate locking, the subtler variety being key range locking). None is needed (in addition to row locks) in order to ensure serializability in your examples.

vc, ok, поправка понятна, однако она по сути мало что меняет в выводе. Давайте ещё раз посмотрим на запрос, о котором мы говорили: (select count (*) from t where col < 0). Если я Вас правильно понимаю, то для того, чтобы всё правильно отработало в отсутствии delete/insert вы предлагаете наложить блокировки на ВCЕ строки в таблице, а не только те, для которых col < 0 (иначе не будет сериализованного выполнения). Т.е. мы вынуждены проигронировать предикат при сканировании (хотя при вычислении результата count(*) предикат, естественно, будет приниматься во внимание).

Но отсюда немедленно неутешительный вывод, что для того, чтобы это всё работало как нам хочется, ЛЮБАЯ операция сканирования данных - для update, для select - неважно, должна будет просканировать и наложить блокировки на все строки всех таблиц участвующих в запросах вне зависимости от наличия или отсутствия предикатов и вне зависимости от того удовлетворяют ли строки предикатам или нет. Другими словами мы только что полностью отменили индексы - ведь нам всё равно всегда придётся сканировать целые таблицы. Согласитесь, это не совсем, мягко говоря, удобно.

[vc]

Давайте ещё раз посмотрим на запрос, о котором мы говорили: (select count (*) from t where col < 0). Если я Вас правильно понимаю, то для того, чтобы всё правильно отработало в отсутствии delete/insert вы предлагаете наложить блокировки на ВCЕ строки в таблице, а не только те, для которых col < 0 (иначе не будет сериализованного выполнения). Т.е. мы вынуждены проигронировать предикат при сканировании (хотя при вычислении результата count(*) предикат, естественно, будет приниматься во внимание).

I should stop taking those shortcuts...

I do not suggest locking all the rows but only those participating in the transactions.

The 'participating' word needs a little clarification. Let's reason from the point of view of an abstract S2PL scheduler. Those 'exists' or 'count(*) == 0' are a bit misleading because they imply that rows satisfying col < 0 are participants whilst the exact opposite is true -- the complement subset is the actual transaction participant. In our case, it just happens so that the complement equals the whole table (if the 'not exists' predicate is true, obviously). Our abstract S2PL picks the rows one by one in some way and places R locks on them. The way it does this is not defined in the S2PL protocol, the optimization through indexes or whatever is up to the implementor. Let's just pretend that there is a way to grab rows efficiently (in the case of a small subset) in some magical way, without requiring to scan the whole set.

So for 'not exists (select * from t where col < 0)' to be true the whole table has to satisfy col >=0. The same goes true for 'count(*)==0'. The idea is that a SQL predicate(s) (not to be confused with predicate locking ;) describes rows participating in a transaction. I believe it's the only reasonable interpretation if we want to express what is going on in serializability theory terms.

If you accept this line of reasoning, then it's clear that some histories will succed and some will dead-lock thus implementing 'true' serializability without resorting to predicate locking.

[tengiz]

vc, небольшая коррекция исходной задачи и мы опять получаем проблему при реализации serializable для delete/insert free транзакций если мы принципиально не хотим пользоваться табличными блокировками:

if (select count (*) from t where col < 0) between 5 and 10 then do some stuff...

В этом случае уже не получится сказать, что дополнительное предикату col < 0 множество строк совпадает с множество всех строк таблицы. Но, тем не менее, нам опять придётся блокировать все строки таблицы t. Просто потому, что и множество строк, которые удовлетворяют предикату, а также и множество строк, которые удовлетворяют дополнительному предикату, гарантированно должны остаться стабильными. А когда некое подможество объединяется с дополнительным ему подмножеством, то ясно, что результат всегда будет одним и тем же - всё множество.

[vc]

vc, небольшая коррекция исходной задачи и мы опять получаем проблему при реализации serializable для delete/insert free транзакций если мы принципиально не хотим пользоваться табличными блокировками:

if (select count (*) from t where col < 0) between 5 and 10 then do some stuff...

Correct me if I am wrong but 'traditional' serializability theory deals with r/w operations over subsets that are members of the same poset with respect to inclusion.

If my recollection is right, then, as before, we need to express the above condition in this (complementary) way:

if (select count (*) from t where col >= 0) between .. and .. then do some stuff [over subsets belonging to the same inclusion poset as the subset defined by the 'col >=0' predicate]...

Clearly, predicate locking, theoretically, would alow queries whose predicates are not restricted in this manner.

[tengiz]

vc, боюсь, что я начинаю терять нить дискусси. Давайте попробуем всё-таки определиться и чётко обозначить что мы обсуждаем. Во-первых, обработка транзакций и реляцонная теория - вещи ортогональные и полностью независимые. Я использую SQL в примерах только потому, что это самый популярный способ общения с современными системами обработки транзакций.

Во-вторых, суть обещаний, которые дают систем обработки транзакций очень проста: если программы, манипулирующие данными (любым способом, написанные на любом языке) работают правильно в единственном экземпляре, то система обработки транзакций гарантирует, что любая их параллельно работающая комбинация тоже будет работать правильно. Откуда сразу следует, что искусственных ограничений на то, что могут и чего не могут делать эти программы практически нет.

В том, числе и ограничения, которое Вы сформулировали, если я его правильно понимаю, а именно - условый оператор может работать с любыми данными, ветвления условного оператора могут работать с любыми данными, совершенно никак не связанными с подмножеством, которое фигурирует в условии. Возвращаясь к нашему примеру - do some stuff может делать всё, что угодно, причём с любыми данными.

Понятно, что наличие подобных ограничений может существенно упростить реализацию систем обработки транзакций и/или обеспечить лучшую производительность, etc. Для чего, по сути, и были придуманы "уровни изоляции", отличные от идеальной изоляции. Но формальная теория не имеет таких ограничений. Причём, как я уже говорил, практически с самого начала. Теоретическая работа описывающая проблему фантомов и её решение при помощи предикатных блокировок была опубликована аж в 1976 году.

[tengiz]

Кстати - заглянул в книгу Грея об обработке транзакций и в книгу Бернштайна об изоляции чтобы уточнить исторические определения статических и динамичских баз данных. Insert/deletе операции о которых там идёт речь на самом деле имеют очень опосредованное отношение к SQL insert/delete. "Статическая" база данных имеет дело со статическим набором объектов - объекты не появляются и не уничтожаются, а также никаким образом не могут меняться так, чтобы из-за изменения исключались бы и попадали бы в поле зрения транзакций. В СУБД поддерживающей хотя бы SQL оператор UPDATE и WHERE clause для SELECT/UPDATE, строки таблиц в принципе не могут считаться объектами в смысле "статической" базы. Для того, чтобы SQL СУДБ была "статической" нужно наложить серьёзные ограничения на возможные операции, что в итоге практически перечеркнуло бы полезность SQL в большинстве приложений.

[vc]

vc, боюсь, что я начинаю терять нить дискусси. Давайте попробуем всё-таки определиться и чётко обозначить что мы обсуждаем.

We are discussing the fact (I believe) that an S2PL scheduler by itself ensures serializable histories for static databases. However, there are at least two restrictions:

1. The database should be static. Maybe 'should be' is too stong a statement, the traditional serializability theory simply says nothing about inserts. It just talks about reads and writes of the existing data. However, as soon as we try to reason about inserts (writing new data), S2PL won't ensure serializability any more (phantoms).

2. If we want to use another more powerful language, like SQL, to describe our transactions, we have to preserve the original simplistic serializability theory language (SL) semantics since otherwise serializability theory is not applicable any more and any discussion becomes meaningless.

SL's vocabulary contains {read, write, precedence, conflict}.

A translation example:

if (select count (*) from t where col < 0) between 5 and 10 then do some stuff...

We cannot offer a translation at this stage because we do not know what 'do some stuff' is (I'll elaborate on why we need to know that later). Let's assume it's 'update t where col >0.

Then the SQL can be translated as:

if count(read(Xi|col >= 0)) between ...; /* we have to invert the predicate in order to create a *conflict* with concurrent writes */; write(Xi|col>0);

The reason we need to know what 'do stuff' is that we have to determine whether the original statement can be re-stated in such a way as to create conflicts, a crucial component of S2PL. Generally speaking, we can ensure that conflicts are in place when the subsets on which read/write operate are a partial order with respect to the 'subset of' operation. In other words, only SQLs where all the predicates define ( or can be re-stated to define) such subsets can be analyzed in terms of serializability theory.

Во-первых, обработка транзакций и реляцонная теория - вещи ортогональные и полностью независимые. Я использую SQL в примерах только потому, что это самый популярный способ общения с современными системами обработки транзакций.

I've talked all the time about transactions, not a word was said about relational theory. When I mentioned sets, I was trying to describe how to re-formulate a SQL so that it could be analyzed using serializability theory.

Во-вторых, суть обещаний, которые дают систем обработки транзакций очень проста: если программы, манипулирующие данными (любым способом, написанные на любом языке) работают правильно в единственном экземпляре, то система обработки транзакций гарантирует, что любая их параллельно работающая комбинация тоже будет работать правильно. Откуда сразу следует, что искусственных ограничений на то, что могут и чего не могут делать эти программы практически нет.

Informally yes you are right. Unfortunately S2PL theory, the cornerstone of all the locking schedulers, limits the set of serializable transactions to conflict serializable only with an additional restriction being that the database' had better be static.

Но формальная теория не имеет таких ограничений.

If by formal theory you mean S2PL, see above regarding restrictions.

Теоретическая работа описывающая проблему фантомов и её решение при помощи предикатных блокировок была опубликована аж в 1976 году.

Well yes Eswaran and others indeed published their work in 1976. However, whilst theoretically interesting, generic predicate locking implementation has at least two problems: detecting conflicts is very expensive and concurrency is not great. What we have today are partial implementations either via entire table locking or key-range locking (if you are lucky to have an appropriate index and the optimizer decides to use it).

Besides, predicate locking is an addition to S2PL so that we cannot say there is some elegant unified serializability theory. Instead, we have rather an eclectic architecture created to ensure decent concurrency in lower isolation modes through S2PL plus serializability via table/index locking under Serializable IL.