注记数据库及其在图书借阅系统中的应用

胡丽君，郑波尽，孙爽

（中南民族大学 计算机科学学院， 武汉 430074）

20世纪70年代，CODD提出了关系模型［1-2］，解决了数据逻辑独立性和物理独立性；同时期，CHEN提出了实体-关系（E-R）数据模型［3］，他将数据库想象成一个实体实例的集合.关系模型发展至今，其应用最为广泛，常见的关系数据库产品有MySQL［4］、SQL Server［5］、ORACLE［6］、IBM DB2［7］、SQLite［8-9］等.关系数据库在一定程度上满足了用户的某些需求，但是它迫使开发人员和数据存储都致力于一个固定的数据模式，阻碍了数据存储的灵活性且过多地限制最终用户；它还仅能处理确定性的数据操作，很难适应具有多语义数据的查询与存储的场景.主要原因在于数据库的存储模式用自顶向下的方式进行设计，对数据进行了严格的约束和规范. 例如，目前研究较为热门的轻量型关系型数据库SQLite，其所有的操作都必须严格遵循SQLite的数据组织架构和缓慢的事务处理过程，导致SQLite的灵活性和操作效率低［10］.研究人员也做了很多努力来优化SQLite的性能.如文献［11］通过采用红黑树替代B树来优化SQLite的存储结构，提升SQLite的操作性能，但其存储模式采用的仍然是“先有模式，后有数据”的方法来“被动”存储和处理数据.文献［12］提出了基于Android平台的tile Pyramid模型，使网格数据的存储不受数据库本身的限制，但对于其他结构的数据存储，会大大增加RAM的消耗，操作效率方面也未能得到有效的提升.以上的优化方法没有从根本上提升灵活性，当在数据结构不恒定的场景下对数据进行更新或修改时，仍会导致巨大的编程工作，而存储可变数据结构一直是数据管理中的伴随问题.

因此，本文首次提出了名为注记数据库的原型库，采用“先有数据，再有结构”的自下而上的设计方法；利用给数据加注记或关联注记的方式管理和完善数据的语义信息结构和保持数据之间的关联.“先有数据，再有结构”是指数据存储之前，不考虑存储模式结构，用户可以潜在地存储任何类型的数据，灵活性非常大.通过结合注记，能够帮助用户厘清数据的语义信息以及数据之间的关联关系，将数据库里的数据内容“组织”在一起，以更高效的方式检索、处理、修改数据，并呈现给用户.

1 注记数据库的介绍

注记数据库是一个更关注灵活性而不关注大规模数据存储的数据库，它利用增量式方法为现实世界建模.采用先有数据再有结构的设计思想，根据用户的认知利用注记将数据关联在一起，既保留了数据的语义，又保持了数据之间的关系.

1.1 注记的概念

注记是一种对多语义数据的表示方法.这种方法最早在2004年提出，表示用户为了检索的需要，对信息或对象进行自由标注［13-15］；但是这种自由标注方式是以一种平面的方式进行标注，无法表达更复杂的数据信息结构以及数据之间的关联关系.

不同于自由注记，本文提出利用注记来表示复杂的数据之间的关系，从而实现关系数据库的功能.当然，如果放松约束，也能够实现一些NoSQL数据库的功能.为了可以表达关系数据库，需要将注记划分成2种类型，即普通注记和识别注记.普通注记用于表达关系数据库中的普通属性，即非键属性；识别注记用于表达关系数据库中的键属性.在关系数据库中，表实际上是一个N元组，其中，一个或者多个元构成唯一标识，称为键；在每一个表中，至少存在一个键.因此，在注记数据库中，用识别注记来表示表中的键；对于关系数据库中的组合主键，为方便起见，在注记数据库中可建立一个隐含的识别注记；对于普通关系数据库中的属性，则对应普通注记.

1.2 注记数据库的基本内部架构

如图1所示，本文提出的注记数据库的内部架构图由5个模块组成：（1）数据缓存区模块；（2）数据打标处理模块；（3）数据与注记的存储模块；（4）数据操作模块；（5）注记操作模块.

图1 注记数据库的内部架构Fig.1 Annotation database internal architecture

1.2.1 数据缓存区模块

当用户将数据存入注记数据库的时候，首先要将数据暂存在数据缓存区模块.该模块是为了高效且顺利进行数据打标处理而引入的数据暂存区域，它是数据存入注记数据库内存前的缓冲区.

1.2.2 数据打标处理模块

数据打标处理模块用于为用户暂存在数据缓存模块中的数据分配id（记为Did）；再为该数据进行注记并分配注记id（记为Zid）.此时需要判断注记的类型，注记的类型是根据数据中具备识别特征的数据和不具备识别特征的数据来判断该注记类型是否为识别注记或普通注记.如果是识别注记则为该数据进行标识，如果是普通注记需要将数据关联到识别注记数据上，使得数据之间产生关联.注记表示为数据赋上语义信息，识别注记表示可以在语义上标识或赋予普通注记存在的意义，并将它们“集合在一起”，因此，任何的普通注记数据都需要关联到识别注记数据上.

1.2.3 数据与注记的存储模块

经过打标处理模块后的数据和注记会存入内存中.注记数据库的存储结构根据存储的内容分为数据区、注记区和关联关系区.数据区用来存储数据单元、数据与注记关系单元，注记区用来存储注记单元，关联关系区用来存储数据关系单元.在存储过程中，对于每一项数据或者注记都统一使用128比特的标识符UUID来表示.信息处理时，都是基于UUID进行处理.因此，数据单元用来存储数据以及分配的Did，保证每一个数据具有唯一的UUID；注记单元用来存储该数据的注记Zid和注记名Zname，保证每一个注记名具有唯一的UUID；数据与注记关系单元，用来存储数据的Did和打标的注记Zid，即用来建立数据与注记的关系；数据关系单元，用来存储数据打标处理过程中的识别注记数据与普通注记数据以及识别注记数据与识别注记数据的关系.其中Didy表示识别注记数据id，Didn表示普通注记数据id. 若识别注记数据id为Did1y，与Did1y关联的所有注记数据id为Did1y，Did1n，Did2n，…，Didmn，识别注记数据与普通注记数据的关联关系用二元组(Didy，Didin)表示，其中i∈(1，m)；与Did1y关联的识别注记数据id是其自身Did1y，关联关系用(Didqy，Didpy)表示，此时q=p，表示自关联关系；若与Did2y关联的所有注记数据id为Did2y，Did1n，Did2n，…，Didpn，且所述Did1y与Did2y存在关联关系，则该关联关系用(Didqy，Didpy)表示，此时q≠p；这时表示的是一个二元关联关系.对于三元及以上关联关系，可以采用类似的机制处理或者采用加入一个隐含识别注记的方式来处理.

数据关系除了保持数据之间的联系外，还有2个主要作用：（1）从语义的角度，赋予了普通注记数据存在的意义；（2）从查询多条数据的角度，通过selection就可以获得需要的数据，并不需要进行繁杂的join 操作，提高了查询效率.

1.2.4 数据的操作模块

对数据的基本操作即对数据的插入、查询、删除、修改，基本操作流程如下.

（1）插入数据：插入的数据又分为普通注记数据和识别注记数据.首先用户向注记数据库插入数据，由系统分配一个Did给数据，并存入数据单元；为Zname分配一个Zid，并存入注记存储单元；将数据与注记关联存入数据注记单元；如果该数据为识别注记数据，需将该注记标识并存入数据关系单元；如果该数据为普通注记数据，需要关联到识别注记数据再存入数据关系单元.

（2）查询数据：通过所给的已知条件依次查询该数据关联的识别注记数据的Did、该识别注记数据关联的所有普通注记数据Did、注记Zid，再依据selection条件过滤掉不相关数据，即得到想要查询的数据.

（3）删除数据和修改数据：二者都是在查询数据的基础上，进行相应的操作，需要注意的是删除数据只需要删除相应的Did，与该Did的关联关系记录都会被删除.

1.2.5 注记的操作模块

在注记存储单元中，每一个Zid对应的注记名Zname都不会是唯一的.如张三，这条数据表示“名字”，或者“姓名”“name”等多种语义信息.当用户对数据进行注记后，需要对注记进行管理操作.

（1）添加注记：当用户存储一条数据时，为了便于表达该数据的语义信息，为该数据添加注记；

（2）新增注记：当用户想为数据标上其他的语义信息，可以通过新增注记的方式为其再次打标，新增的注记关联到已存在的Zid上；

（3）查询注记：当用户想要查询一条数据及其语义信息，可根据数据的Did和注记的Zid查询到该数据的Zname；

（4）删除注记：当注记不准确或者使用次数为0的时候，可以对它进行删除操作.

2 注记数据库应用实例

为了更具体地说明注记数据库的设计思想，以学生-借书为例，分析注记数据库灵活的存储方式以及数据间的关联关系.

图书借阅系统中的数据信息日益渐增，数据结构不确定；当用注记数据库存储时，元组中数据可以为乱序，通过关联的注记重新排成正确的序（图2）.

图2 学生-借书信息表Fig.2 Students-borrowing-books information table

案例1：假设目前有2条并不齐全的读者信息数据库样本.注记名标为学号、读者姓名、年龄、性别、手机号、地址，以学号作为识别注记数据，其他作为普通注记数据：（2020110，李明，25，男，18376514321），（2020113，张三，学生，13345627651，男，武汉）.

案例2：假设目前有2条书籍信息数据库样本.注记名标为书籍编号、书名、作者、出版社名称，以编号作为识别注记数据，其他作为普通注记数据：（TP0001，计算机导论，王志强，电子工业出版社），（TP1111，数据库系统，王珊，高等教育出版社）.

案例3：假设一条借书信息数据库样本，注记名标为学号、书籍编号、借书时间、归还时间，在关系数据库中，以学号、书籍编号二者组合作为主键，这里借助一个隐含的借书单据号Did作为识别注记数据，其他作为普通注记数据：（08090910，2020113，TP0001，2021-08-09，2021-09-10）.

先将以上数据记录分配Did并分别存入数据区的学生信息表、书籍信息表和借书信息表中；再将分配好Did的数据进行打标，并分配注记Zid，将Did与Zid存入数据注记信息表中，如图2（a）所示；将注记名与Zid存入注记区的注记信息表中，如图2（b）所示；对打标过程中的识别注记数据进行标识，将其Did以及与其关联的所有注记数据（包含其本身）的Did以链表的形式存入关联关系区中数据关系关联关表中，如图2（c）所示.为简明起见，UUID简化成了一个标号，如图2（c）中Did为1_0表示识别注记，其数据信息为（学号，2020110），其关联的注记Did为1_0（本身），1_3，1_4，1_5，1_6，从对应的图2（b）注记区信息表和2（a）数据区信息表中通过Did得到，学号为2021110的其余信息分别为（年龄，25），（姓名，李明），（性别，男），（电话号码，18376514321）.

学生和书之间存在着借阅关系.从图2中的数据区、注记区、关联关系区的表中，可以得到学生-借书的关联关系参照图，如图3所示.其中识别注记数据学号2020113、书编号TP0001、借书单据号08090910均关联了其它普通注记数据；数据关联关系如图3（a）所示.学生和书籍之间存在的借阅关系有一个隐含的识别注记数据借书单据号Did，学号和书籍编号的Did均以普通注记数据关联在借书单据号Did上，如图3（b）所示.

当需要查询读者信息、书籍信息、借书信息时，x先可通过查询借书关联关系查到借书单据号Did、学号Did、书籍编号Did，再通过这三者查询到它们所关联的其他数据信息，最后根据已知条件通过Selection筛选出最终合适的查询结果；当需要修改数据信息或注记信息时，只需要在查询的基础上进入对应的数据区或注记区对该数据作相应的处理，极其灵活方便.

3 与关系数据库操作的等价性

数据的操作分为查询操作和插入、删除、修改操作两大部分，后者在前者的基础上进行操作.在关系数据库中，关系的查询操作分为笛卡尔积（x）、连接（j）、选择（s）、投影（p）4大主要操作，并、交、差等简单的集合运算，这里不多介绍.先对关系数据库中查询的4个主要操作进行回顾并用x-j-s-p表达注记数据库查询，反之同理；证明注记数据库与关系数据库在表达上相互等价.

3.1 关系查询的4个主要操作定义

关系数据库中表被表示为实体属性的集合，一张表表示一个关系，则可记为R(A1，A2，...，An)，其中R表示关系，A1，A2，...，An表示属性.

定义1（笛卡尔积）记作×，给定两个关系S和G，S×G是将S中所有元组和与G中所有元组进行并操作得到的属性集作为其结果.设S=R(a1，a2，...，am)，G=R(b1，b2，...，bn)，那么S×G可定义为：

定义2（连接）记作∞，给定两个关系S和G，S∞G是将S和G的公共属性上相等的所有元组作为结果.设S=R(a1，a2，...，am，b1，b2，...，bn)，G=R(b1，b2，...，bn，c1，c2，...，cp)，其中，a1，a2，...，am是S独有的属性，c1，c2，...，cp是G独有的属性，b1，b2，...，bn是S和G共同的属性，那么S∞G可定义为：

定义3（选择）记作σF(R)，其中F表示一个逻辑命题公式，由变量、常量和逻辑运算构成.选择运算是指从关系R中选择出使得F为真的属性集合，可以定义为：

定义4（投影）记作πa1，a2，...，am(R)，设关系R(A1，A2，...，An)且a1，a2，...，am⊂A1，A2，...，An，投影运算定义的结果定义为当所有在R中的属性被限制在属性集(a1，a2，...，am)时获得的关系r，可定义为：

3.2 注记数据库的查询操作

为了便于二者的相互表达，需对注记数据库先引入几个符号.

（1）注记数据库中的数据和注记通过Did和Zid将它们关联起来.将所有的Did元素用向量表示D=＜d1，d2，...，dn＞，其中di（i=1，2，…，n）指向Data和Zid；所有的Zid元素用向量表示Z=＜z1，z2，...，zn＞，其中zj（j=1，2，…，n）指向Zname；

（2）数据和注记关联存在，且每一个Did都指向一个数据和一个Zid，同一个Zid会存在多个语义相同的Zname且与多个Data关联.

注记数据库的查询操作主要是先通过给定的条件查找识别注记值的Did，再通过该Did去查询与之关联的普通注记的值及其Zname，所组成的结果构成最终的查询结果.定义简单关联关系查询算子如下：

其中：f表示满足的查询条件；Qf(d1，d2，...，dm)(d*)表示在d1，d2，...，dm中查询识别注记值的id，用d*表示；∧表示将前一个查询结果中选择作为后一个查询条件；Qf(d*)(d1，d2，...，dn)表示查找与识别注记值关联的所有普通注记值，d1，d2，...，dm⊂d1，d2，...，dn；Q(Z[d])表示查询所有的普通注记值的Zname.

定义复杂关联关系查询算子如下.

设关联关系S1=(x1，x2，...，xn)，S2=(y1，y2，...，yn)，由S1和S2得到关联关系S3=(x1，x2，...，xn，y1，y2，...，yn，w1，w2，...，wn)，其中x1，x2，...，xn，y1，y2，...，yn分别表示关联关系S1和S2的数据Did，w1，w2，...，wn为S3独有的数据Did，可定义为：

3.3 注记数据库的查询操作表达关系代数的查询

上节从普通关联关系和复杂关联关系角度定义了注记数据库查询操作的2个原语，本节采用上述两个原语表达关系数据库的查询操作.

关系数据库中属性的集合作为关系，即R(A1，A2，...，An)，这个(A1，A2，...，An)指向注记名(z1，z2，...，zm)和数据(d1，d2，...，dn)，主属性Aˉ指向数据的识别注记数据d*.简单的关系查询被关联关系查询表示如下：

假设关系R(a1，a2，...，an)，根据关联关系查询可定义：

假设关系R1(a1，a2，...，an)，R2(b1，b2，...，bn)，由R1与R2得到关系R(a1，a2，...，an，b1，b2，...，bn，c1，c2，...，cn)，复杂的关系查询被关联关系查询可定义为 ：

综上，可知注记数据库的关联关系查询算子可以表达关系数据库中的关系查询.

3.4 关系代数查询操作表达注记数据库的查询

对于同一组注记＜z*，z1，z2，...，zn＞的数据关联关系可对应关系数据库中实体的一行记录或元组表示为t＜d*，d1，d2，...，dn＞，其中d*表示为识别注记数据Did，d1，d2，...，dn表示与d*关联的注记数据Did. 如果存在一组记录＜d*，d1，d2，...，dn＞中与zj对应的di不存在或与规范性数据类型不一致，则将该di数据记为null.那么元组t可定义为：

对于同一组注记＜z1，z2，...，zm＞的元组t的集合(t1，t2，...，tn)可以转换为关系数据库中的一个关系，定义为：

用关系查询的x-j-s-p表达注记数据库如下.

（1）笛卡尔积.给定两个关联关系S和G，设S=C(t1，t2，...，tk)，G=C(t1，t2，...，tm)，其中，t1，t2，...，tk⊂t1，t2，...，tn；t1，t2，...，tm⊂t1，t2，...，tn根据笛卡尔积的定义，那么S×G可定义为：

（2）连接.给定两个关联关系S和G，设S=C(t1，t2，...，tn)对应注记＜z1，z2，...，zk＞，G=C(t1，t2，...，tm)对应注记＜z1，z2，...，zm＞.根据连接的定义，那么S∞G可定义为：

（3）选择.给定关联关系S=C(t1，t2，...，tn)，那么C关系中元素可能满足条件Q的所有元组用选择可定义为：

（4）投影.给定关联关系S=C(t1，t2，...，tn)，G=C(t1，t2，...，tm)，其中，t1，t2，...，tn⊂t1，t2，...，tm，将满足条件Q的元组t1，t2，...，tm映射到t1，t2，...，tn中，用投影可定义为：

综上所述，注记数据库中的数据Did组成关联关系可用关系数据库的元组表示，满足关系查询算子；反之同理，关系数据库中的关系是一张二维表，表中的一行表示一个元组，一列表示一个属性，而属性指向注记数据库中的数据和注记名，则关系数据库可被注记数据库表达，为证明注记数据库与关系数据库之间的等价提供了理论基础.

4 结语

本文通过回顾传统数据库的理论和存储模式等相关研究，针对数据结构不恒定场景数据的存储问题，提出一个灵活存储数据信息的原型库——注记数据库.它所遵循的核心原则是灵活性，首先，以用户和数据为中心，采用先有数据，再有逻辑结构的自上而下的设计思想，处理不同类型的数据，不需要遵循一个严格固定的结构；其次，提出给数据库里的数据添加注记或关联注记的方式来实现数据间关系的表示，既保持数据关系又保留数据语义信息；最后，通过将注记数据库与关系数据库的查询算子作相互表达，为二者的相互映射提供理论基础.

目前的注记数据库还处于初期阶段，对于在云环境下注记数据库与文件系统结合等应用方面的问题，值得进一步研究.