CMU15-445数据库系统5:事务和并发控制
这是CMU数据库课程15-445的第五个大的部分,主要讲数据库中的事务和并发控制的内容,在2021秋的课程里应该对应Lecture15-Lecture16
事务
事务的概念
事务(Transaction)是数据库中最重要的一个抽象,一个事务指的是在一个共享的数据库上一系列操作的执行(可以是一个或者多个),这些操作共同组成一个更高级的功能(比如复杂的SQL查询),事务不允许被部分执行。
事务的处理
最简单的事务处理系统就是一次处理一个事务,为了执行一个事务,数据库会对整个数据库中的文件进行备份并且在副本上进行事务对应的一系列改变,如果事务执行成功了,那么新的文件会变成当前的数据库文件,如果执行失败,那么这个事务对数据库文件进行的任何改变都不会被保存下来,这种方法非常慢,而且不支持并发。
处理事务更好的方法是允许一个系统并发的执行多个事务,并且同时保证系统的正确性和公平性,但是并发执行存在一些挑战,如果不加任何限制就直接执行一系列并发的操作,存在的问题包括:
暂时的不一致性:不能避免,但并不是问题
永久的不一致性:对于数据库系统来说无法接受,必须想办 ...
论文阅读笔记29:异构GCN
ICLP2020论文《Composition-based Multi-Relational Graph Convolution Networks》阅读笔记,并合其他常见的异构图神经网络结合进行分析对比
Introduction
异构图神经网络是在同构图神经网络的基础上发展而来的,其目的是用来对异构图的进行表示学习,相比于同构图,异构图在真实世界中更加常见,因此异构图神经网络也有很多应用场景,比如自然语言处理/知识图谱/分子性质预测等等。图卷积网络是非常重要的一类图神经网络,而已有的异构图卷积网络主要有R-GCN及其变种,他们的主要设计思路是对于不同的边(即Relation)使用不同的图卷积核,并且图卷积核对于一个关系中不同的实体的权重是不同的,比如R-GCN的结点更新策略是:
而这样的方法往往面临着过参数化(Over-parameterization)的问题,即设置了过多的参数,导致模型的学习效果反而下降,同时这些方法大多数只能学习到结点的表示,而不能学习边的表示,因此限制非常多。
而本论文中提出的模型CompGCN就是为了解决为了解决这些问题,Comp ...
CMU15-445数据库系统Project3:Query Execution
CMU15-445的Project3,目标是实现若干种数据库操作的查询执行器,这一Project的重大意义在于理解Bustub数据库引擎中对于executor的模块和迭代查询处理模型的设计和实现。
START
这一个Project中我们需要实现数据库中多种操作的执行器,包括:
访问方式:顺序扫描
数据修改:查询,删除,更新
复杂操作:循环嵌套Join,Hash Join,聚合,Limit和Distinct
同时Bustub并不支持真正的SQL语句,所以执行的都是手动编写的查询计划。同时Bustub中采用的是迭代模型,在这种模型中,每一个查询计划的执行器都需要实现一个Next()函数,当调用执行器的这个函数的时候,执行器会返回一个元组或者一个提示已经没有更多元组了的标志,通过这个方法,每个执行器实现一个循环结构来持续调用子结点的Next()函数,从子结点中一个接一个检索元组并进行操作。
在Bustub中,每个Next()函数会返回一个元组和代表了这个元组的RID(RID实际上就是元组的唯一标识),下面我们就要按顺序来实现一堆不同操作的执行器,包括 ...
对我校软件工程专业本科课程设置的一些意见
lz是软件工程专业的一个普通本科生,三年多时间的本科学习过程中,我深感我们专业本科教学中存在诸多问题,最近花了一点时间简单总结了一下软件工程培养方案的专业课程中存在的问题,同时也提出了一些自己的意见,准备反馈给学院相关的领导老师。 事实上有的问题你知道,我知道,他们知道,他们知道我们知道,我们也知道他们知道,但就是没人愿意做出改变。我也清楚,这些意见大概率不会被学院所接受和采纳,但我依然想把我想说的东西说出来。知其不可为而为之,也未尝不可。全文共计11000字,可能需要花一点时间阅读。
前言
各位计算机学院的领导,老师,你们好!我是计算机学院软件工程专业18级的一名普通学生。我们学院的计算机科学与技术和软件工程都是教育部认证的A+专业,一般情况下可以认为在全国范围内属于顶尖水平,但是我接下来要说的内容,可能和A+专业这个名头没什么关系。
我想说的是,这两个专业在本科教学这方面仍然存在很多问题,尤其是软件工程专业,和世界一流大学的目标仍然有很大的差距。我自己是软件工程专业的,所以我对CS专业的情况不做任何评论,但是两个专业有很多课程是相通的,所以两者的情况我相信 ...
CMU15-445数据库系统4:查询优化
这是CMU数据库课程15-445的第四个大的部分,主要讲查询优化相关的内容,在2021秋的课程里应该对应Lecture13-Lecture14,这一部分内容比较少
查询优化
SQL语句是声明式的语句,只告诉了数据库系统要做什么,而没有说过要怎么做,因此数据库系统需要自己将SQL语句转化成对应的查询计划,但是一个查询往往可以有多种不同的查询计划,即运算符可以用不同的顺序来执行,那么如何来选择执行效率最高的查询计划呢?这就是这一节需要讨论的问题——我们要对查询进行优化,找到最好的查询。
一般来说常见的查询优化策略有以下两种不同的方式:
使用静态规则,也叫做启发式的方法,即利用特定的规则对查询进行优化,移走查询中低效率的部分,这些规则可能需要通过catalog来了解数据库中数据存储的结构,但是不需要对数据本身进行检验
基于cost的搜索,将数据读出,并估计出执行不同的等效查询计划的cost,然后选择cost最低的方案执行
查询的优化是数据库中最难搞的一部分工作,数据库系统中通过优化器模块专门来负责对查询进行优化,也有一些数据库系统尝试用机器学习的方法去 ...
论文阅读笔记28:多模态BERT
BERT模型是NLP领域近几年来最成功的预训练模型之一,而BERT一经提出,很多模仿BERT架构并用于其他的任务中的类BERT模型也不断涌现,这一次读的几篇文章都是多模态BERT相关的内容,分别是VisualBERT,VL-BERT和ViLBERT
Introduction:多模态BERT
BERT预训练模型在NLP领域的成功已经不需要我再多说了,它的成功引来了深度学习的其他领域比如CV的争相效仿,各种各样不同却又相同的类BERT模型不断涌现出来,说它们不同是因为这些BERT模型在细节上各有区别,分别对应不同的使用场景做了不同的挑调整和优化,而说它们相同是因为它们都遵循了预训练+微调的范式,通过在海量的数据集上进行预训练,来完成下游任务。今天的重点在于多模态的BERT模型,这一系列模型都是BERT在多模态任务上的应用。
关于多模态任务
所谓的多模态任务,常见的有图片标准Image Captioning,可视问答VQA,图片-文本检索和可视常识推理等等,多模态的任务往往需要将给定的图片和文本信息结合起来,找到它们的内在联系,这也是多模态任务的最大特征,即数据集 ...
CMU15-445数据库系统3:查询处理
这是CMU数据库课程15-445的第二个大的部分,主要讲数据库中的索引相关的内容,在2021秋的课程里应该对应Lecture09-Lecture12
数据库系统处理查询的时候经常需要进行的操作有排序,聚合和连接(Join),下面先简单说一下每一种操作的不同实现方式。
常见的查询操作
排序
数据库系统往往需要对数据元组进行排序,而比如面临ORDER BY,GROUP BY等查询指令的时候,如果内存中能放得下所有的数据那自然就最好了,这样排序就可以直接在内存中进行,但是往往数据量一大起来之后这种美好的设想就无法实现了,而数据库系统中采取的解决方案是:采用外部归并排序(External Merge Sort)来完成对大量元组数据的排序。外部归并排序需要同时使用磁盘和内存,具体操作可以分成以下两个步骤:
排序:外部归并排序首先需要在小的chunk(块)中对内部的所有数据进行排序,要保证块的大小可以被内存接受,写完之后再写回磁盘中
归并:然后将磁盘中各个块内已经排序的块进行归并,得到总体的排序结果
同时,归并的方式最简单的是二路归并排序,这个应该在数据结 ...
CMU15-445数据库系统Project2:Hash Index
上一个Project中,我们实现了Bustub中的Buffer Pool模块,实现了包括LRU置换算法,Buffer Manager和并行Buffer等内容,而这次的Project2需要我们自己实现Bustub中的Index模块
START
Bustub中的索引采用的是Hash Index,并且今年的Project中采用了可扩展的Extendable Hash作为索引的核心组成部分,并要求实现并发的控制等操作。
整个实验分成了三个部分,分别是Page相关的数据结构的实现,Hash表本身的实现和并发控制的实现,下面进入正题。
PAGE LAYOUTS
第一部分我们需要实现索引页的基本数据结构,前面我们已经提到过,Buffer Manager的功能是对页进行管理,里面集成了Disk Manager,LRU等多个组件,就是为了对各种各样的页的读写和置换进行有效的管理,而现在就轮到了我们真的实现其中的一些页的时候。可扩展Hash中,页分成了两种,一种是目录页(Directory page),另一种是桶页面(Bucket Page),目录页面主要保存的是Hash的结 ...
论文阅读笔记27:图对比学习
这次阅读的两篇论文是图对比学习相关的内容,虽然我对图对比学习不是很感兴趣,但是因为下周组会要讲这两篇论文,就顺便拿出来看一看了,正好之前CS231N里也稍微了解了一点对比学习相关的东西,就当是开开眼了。两篇论文分别是2021IJCAI上的《CuCo: Graph Representation with Curriculum Contrastive Learning》和2021WWW上的《Graph Contrastive Learning with Adaptive Augmentation》
Introduction
对比学习contrastive learning是近几年来无监督学习领域非常热门的一个话题,对比学习的目标是在数据没有标注的情况下通过数据增强和正负样本对比的方式来学习数据的表示向量,并用于其他的任务中。
对比学习的核心理念以一言蔽之,就是“一切都是相比较而言的”,对比学习往往通过对数据通过各种手段进行扩增,得到两个不相同但是相似的数据,称为一个对,然后和其他扩增后的数据一起放到编码器中去训练,再得到每个数据的表示向量之后,通过一个基于相似度的 ...
论文阅读笔记26:K3M多模态商品知识图谱预训练
2021ACM MM论文《Knowledge Perceived Multi-modal Pretraining in E-commerce》该论文提出了一种可以有效解决信息缺失和信息噪声问题的多模态知识图谱预训练的方法,并在多项下游任务中取得了非常好的表现。
Introduction
在电商领域中,知识图谱已经有了一些应用,而对于海量的电商数据而言,其商品数据中可能包含了结构化信息,文本和图像等多种模态的信息,但同时,这些信息又有可能是不完整或者充满噪声的,比如下面的图中,第一个商品的信息是完整的,而第二三个商品的信息则有噪声或者缺失:
商品数据
面对众多的下游任务,每种商品各自的表示就显得尤为重要,商品表示的预训练已经被证明是一种非常有效的手段,而面对多模态的商品数据和数据有大量缺失和噪声的实际场景下,直接使用多模态的预训练方式效果不尽如人意,而本论文汲取了之前一篇论文商品知识图谱预训练的思想,在商品数据预训练的过程中融入多模态数据和知识三元组,增强预训练模型的鲁棒性,解决数据缺失和数据噪声的问题,从而得到更好的商品表示向量。
本文的贡献在于: ...
论文阅读笔记25:SMORE大规模知识图谱系统
论文《SMORE: KNOWLEDGE GRAPH COMPLETION AND MULTI-HOP REASONING IN MASSIVE KNOWLEDGE GRAPHS》的阅读笔记,该论文提出了在超大规模数据量的场景下进行知识图谱的补全河推理的方法,从算法和系统机制设计两个层面解决了超大规模数据的情况下的知识图谱补全河多跳推理问题。
Introduction
开篇的第一句依然是介绍知识图谱是一系列由头尾实体和对应的关系组成色三元组,并且在各种AI系统中非常重要,知识图谱中有两种非常重要的推理方式,一种是单条的推理,也就是链接预测或者叫做知识图谱补全,另一种就是多跳的推理,这种推理方式可以对一个给定的逻辑查询来查找对应的实体结果是否存在。
目前大部分知识图谱推理的方法都是基于embedding的,然而已经存在的可扩展性好的Knowledge Graph Embedding(KGE)框架都只能支持单跳的推理,与此同时支持多跳推理的方法又在大规模数据量的场景中训练缓慢,不能很好的规模化使用,因此本论文提出了一种可以规模化使用的多跳推理框架(Scalable ...
Stanford-CS231N-Assignment札记7:自监督学习与课程总结
Stanford2021年春季课程CS231N:Convolutional Neural Networks for Visual Recognition的一些作业笔记,这门课的作业围绕视觉相关的任务,需要从底层手动实现一大批经典机器学习算法和神经网络模型,本文是作业的第七部分,包含了自监督学习和整个课程的总结
自监督学习Self-Supervised Learning
自监督学习的概念
自监督学习(Self-supervised Learning)是这几年机器学习和深度学习领域非常火热的一个研究方向,这种学习方式可以在数据没有标注的情况下学到好的数据表示,并且这种方式取得了巨大的成功,因为实际场景中,很多数据集都是没有标注或者难以标注的(要花费大量的成本),而自监督学习可以在数据没有标注的情况下就学到足够好的数据表示,并可以将其用到下游任务中。
另一个问题是,什么样的表示才是一个好的表示,一般我们认为能够尽可能提取数据中的重要特征并将其编码到向量空间中的才是好的表示,同时具有相似特征的数据,它们的表示向量也应该相似,比如两张图片中如果表示的是同一个物体,那么 ...
Stanford-CS231N-Assignment札记6:模型可视化和GAN
Stanford2021年春季课程CS231N:Convolutional Neural Networks for Visual Recognition的一些作业笔记,这门课的作业围绕视觉相关的任务,需要从底层手动实现一大批经典机器学习算法和神经网络模型,本文是作业的第六部分,包含了GAN的实现和手写数字生成等具体的任务。
神经网络模型的可视化
其实在做GAN之前还有一个任务是做神经网络的可视化,这里的可视化不是说把模型的架构可视化成图表,而是对模型中的图像梯度进行可视化的呈现。
对于一个神经网络模型,我们往往要定义一个loss函数来衡量我们对模型现在训练得到的结果和真实情况之间的不匹配程度(也可以叫我们对模型的unhappiness),然后我们通过反向传播的方法对各个参数的梯度进行更新,用这样的方法使得模型的经验损失达到最小。而在这个作业中,我们将使用一个已经在imagenet上预训练好的CNN模型,然后计算其反向传播时候的梯度,并对dX进行可视化,得到的结果如下:
image-20211111164643556
可以发现求出的梯度比较大的地 ...
CMU15-445数据库系统Project0&1:Storage&Buffer
这是CMU的15-445数据库系统课程的Project记录,记录一些写Project时候的想法,感悟和收获,首先是Project0和Project1
CMU15-445-Project0
CMU15-445的课程Project是用cpp实现一个关系型数据库Bustub中的关键代码,但是这个数据库好像就是一个底层引擎,并没有前端系统(即SQL解析器),不过无伤大雅(大概),总之首先从lab0开始。
lab的初始代码被放在一个GitHub的公开仓库中,首先git clone一下然后按照要求运行一下安装脚本就算配置好环境了,应该说第一步配置环境算是比较简单的,而lab0的主要目的是复习C/cpp的基本语法和Cmake等工具的使用方式。
Project0主要是写几个和矩阵相关的类,首先是矩阵类Matrix,然后是行矩阵类RowMatrix和矩阵运算类RowMatrixOperations,这里要实现的内容主要就是:将矩阵首先用一维数组来表示,然后在行矩阵中用二维数组表示一个矩阵,然后实现矩阵的加法和乘法等各种操作。
大部分代码都是没啥含金量的,Project0主要 ...
Stanford-CS231N-Assignment5:RNN/LSTM与图片描述
Stanford2021年春季课程CS231N:Convolutional Neural Networks for Visual Recognition的一些作业笔记,这门课的作业围绕视觉相关的任务,需要从底层手动实现一大批经典机器学习算法和神经网络模型,本文是作业的第五部分,包含了RNN/LSTM的实现和在Image Captioning任务上的应用
Image Captioning
Image Captioning是一个经典的多模态任务,需要结合CV和NLP的知识共同完成,这类任务也可以叫图片描述,看图写话,即给定一张图像,我们要生成符合这张图像的描述性话语,这就涉及到一个问题,那就是如何在训练过程中,同时利用图像和文本的信息得到合适的模型,因此Image Captioning任务需要将CV和NLP的知识相结合。
本实验中使用的数据集是著名的COCO数据集,同时使用了预训练好的VGG模型进行降维之后的图像表示向量作为图像的特征,文本处理部分则需要我们自己实现RNN/LSTM
RNN
RNN的结构
RNN指的是循环神经网络,是一种设计出来用于处 ...
论文阅读笔记24:MMKG多模态知识图谱表示学习
这一次的论文阅读笔记聚焦于多模态知识图谱的表示学习和补全,选择了三篇前几年的论文,分别是发表在2017IJCAI上的《Image-embodied Knowledge Representation Learning》,发表在2018ACL上的《A Multimodal Translation-Based Approach for Knowledge Graph Representation Learning》和2018年EMNLP的《Embedding Multimodal Relational Data for Knowledge Base Completion》
Introduction
我们知道知识图谱是由一系列三元组组成的,而知识图谱除了可以包含本身的结构化信息(作为一张异构图)以外,还可以包含各种不同模态的信息,比如文本,图像和数值,包含这些信息的知识图谱也被叫做多模态知识图谱(Multimodal KG)
事实上大部分知识图谱表示学习的方式都是从三元组的结构化表示出发,而忽略了很多结构化以外的信息,比如知识图谱三元组本身是文本,而在多模态KG中 ...
Stanford-CS231N-Assignment札记4:卷积神经网络CNN
Stanford2021年春季课程CS231N:Convolutional Neural Networks for Visual Recognition的一些作业笔记,这门课的作业围绕视觉相关的任务,需要从底层手动实现一大批经典机器学习算法和神经网络模型,本文是作业的第四部分,包含了卷积神经网络以及其关键组件的实现(卷积层,池化层)
卷基层Convolution Layer
什么是卷积层?
卷积的计算公式
卷积层是CNN中最核心的一个idea,通过卷积核(实质上就是一种滤波器)对输入的特征进行卷积运算,如果输入的数据是语音,那么数据是一维的,就可以进行一维卷积,如果输入的是矩阵,那么就可以进行二维的卷积,而CNN一般是用来处理图像的,图像是一种三维的数据(因为图像有颜色通道,每个通道上是一个二维矩阵,常见的RGB图像就是3颜色通道),就需要用三维的卷积核对输入进行卷积操作。
假设一个卷积核的大小是,那么 卷积的计算公式如下:
image-20211107214343564
比如上面这张图中,一个大小为32x32x3的图像使用一个 ...
Stanford-CS231N-Assignment札记3:Normalization和DropOut
Stanford2021年春季课程CS231N:Convolutional Neural Networks for Visual Recognition的一些作业笔记,这门课的作业围绕视觉相关的任务,需要从底层手动实现一大批经典机器学习算法和神经网络模型,本文是作业的第三部分,包含了Normalization和Dropout两种训练trick的实现。
标准化Normalization
Normalization是神经网络训练中的另一种trick,中文译名是标准化或者归一化,我比较喜欢前一种翻译。最早应该是在这篇论文中提出的,是一种提高神经网络训练效率和预测准确度的trick,有好几种不同的形式,比如批标准化(batch normalization),层标准化(layer normalization)等等
不同的标准化操作
批标准化Batch Normalization
概念
批标准化在神经网络中通过一个批标准化层来实现,这个层一般都放在激活函数层之前,每次训练的时候选择一个小批量的数据集进行训练,然后将这样一个小批量的数据进行标准化处理,具体 ...