冲突可串行化

​专栏内容：

  • 手写数据库toadb
    本专栏主要介绍如何从零开发，开发的步骤，以及开发过程中的涉及的原理，遇到的问题等，让大家能跟上并且可以一起开发，让每个需要的人成为参与者。
    本专栏会定期更新，对应的代码也会定期更新，每个阶段的代码会打上tag，方便阶段学习。

​开源贡献：

  • toadb开源库

个人主页：我的主页
管理社区：开源数据库
座右铭：天行健，君子以自强不息；地势坤，君子以厚德载物.

文章目录

  • 冲突可串行化
  • 前言
  • 概述
  • 冲突
    • 冲突的概念
    • 冲突的发生条件
    • 冲突可串行化
  • 优先图检测方法
  • 总结
  • 结尾

前言

随着信息技术的飞速发展，数据已经渗透到各个领域，成为现代社会最重要的资产之一。在这个大数据时代，数据库理论在数据管理、存储和处理中发挥着至关重要的作用。然而，很多读者可能对数据库理论感到困惑，不知道如何选择合适的数据库，如何设计有效的数据库结构，以及如何处理和管理大量的数据。因此，本专栏旨在为读者提供一套全面、深入的数据库理论指南，帮助他们更好地理解和应用数据库技术。

数据库理论是研究如何有效地管理、存储和检索数据的学科。在现代信息化社会中，数据量呈指数级增长，如何高效地处理和管理这些数据成为一个重要的问题。同时，随着云计算、物联网、大数据等新兴技术的不断发展，数据库理论的重要性日益凸显。

因此，本专栏的分享希望可以提高大家对数据库理论的认识和理解，对于感兴趣的朋友带来帮助。

概述

商用数据库管理系中的调度器通常强制执行被称为“冲突可串行化”的条件，它比前一篇博文中分享的可串行化的一般要强，它是基于冲突这一概念。

我们通常执行的很多并发事务，都会发生冲突，本文就来分享一下突冲的原因，以及如何检测冲突发生，如何做到冲突可串行化。

冲突

首先我们先来了解一下冲突是什么？

冲突的概念

冲突，即调度中一对连续的动作，它们满足，如果它们的顺序发生交换，那么它们涉及的事务至少有一个的行为会改变。

冲突的发生条件

一般什么情况下会发生冲突呢？

数据库的操作可以分为写和读两种，我们看一下两个事务，分别有一个操作时，什么情况下为会产生冲突。

  • 当两个事务对同一数据库元素读时，先后顺序交换，并不发生结果的改变，不会冲突；
  • 当两个事务操作同一个数据元素时，有一个读，一个写时，先后顺序交换，读操作的事务的结果就会不一样，这时就会产生冲突；
  • 当两个事务操作同一个数据元素时，两个事务都进行写操作，先后顺序交换，两个事务的结果都不会一样；
  • 当两个事务操作不同数据库元素时，不管是读还是写，顺序交换，结果都不会受影响，所以不会产生冲突；

从上面例子可以得到这样一个结论：

  • 不同事务操作同一个数据库元素；
  • 操作中至少有一个是写操作；

那么我们将一个执行序列进行调度，进行任意非冲突的可串行化调度，目标是将这一序列转化为可串行化，如果能达到这一点，那么它最初调度是可串行化的调度，因为在做每一个非冲突可串行化调度时，初始状态一样，对数据库的影响在不同序列下是一样的。

冲突可串行化

  • 如果对于并发执行的序列进行一系列相邻动作的非冲突交换，能转换为另一个，这两个调度可以称为冲突等价的。

  • 如果一个冲突调度等价于一个可串行化调度，那么可以称这个调度为冲突可串行化；

当然冲突可串行化是可串行化的充分非必要条件，

优先图检测方法

通过上面的冲突发生条件分析，说明事务的语义会影响串行化，但是对于调度器来说，它不会深入到事务执行的细节，但是调度器能够看来自事务的读写请求，以及那些数据元素发生了改变，这样它可以通过数据元组的访问来识别冲突。

在一个调度执行序列中，可以确定冲突动作对应的事务的先后顺序，如何事务先后顺序在不同冲突动作上，呈现出不同的顺序，那么我们认为是冲突不可串行化的。

那这一特点通过优先图就可以体现出来。

T1->T2->T3

如果是这样一个图，那么就是冲突可串行化的。

T1->T2->T3->T2

如果是这样一个图，T2与T3之间存在了一个环，那么就是冲突不可串行化的。

总结

在数据库并发事务情况下，冲突是不可避免的，通过优先图的方法来检测冲突，使得调度器能够找到一种冲突可串行化的调度方案。

这是一个简单的C语言程序，它使用了状态模式来输出”Hello, world!”：

#include #include // 定义状态结构体typedef struct State State;struct State {void (*printMessage)(void);};// 定义转换函数void printHello(void) {printf("Hello, world!\n");}// 定义初始状态State initialState = { .printMessage = printHello };// 定义状态转换函数void transition(State *state) {switch (*state) {case 'H':(*state).printMessage = printHello;break;default:printf("Invalid state\n");break;}}int main() {State state = initialState;transition(&state);return 0;}

这个程序定义了一个状态结构体，其中有一个函数指针用于指向打印消息的函数。然后定义了一个初始状态，该状态中的函数指针指向printHello函数。transition函数接受一个指向状态的指针，并根据当前状态来改变它指向的函数。在main函数中，我们首先设置初始状态，然后调用transition函数来改变状态。

结尾

非常感谢大家的支持，在浏览的同时别忘了留下您宝贵的评论，如果觉得值得鼓励，请点赞，收藏，我会更加努力！

作者邮箱：study@senllang.onaliyun.com
如有错误或者疏漏欢迎指出，互相学习。