程序设计：问一个设计到数学原理的问题

BingbingNorth

我最近想写一个数据库的实现，当然，就我一个人，要达到工业标准是不可能的，只能编一个模型。我想分三步走。
1。实现关系代数，成果就是实现关系代数的一个函数库，实现嵌入式开发
2。sql解释/执行程序，相当于操作系统的shell
3。网络接口

现在，在进行1的时候我遇到了一个问题，就是实现这一层的功能，不能与sql等价。因为sql操作不仅仅是包含关系运算，还包括数据处理，比如
[code]update table1
set col1=co1+1
where col2>;0[/code]
要想用函数实现，我想到的只能这样：
已经实现了选择和投影关系运算select_project(表名，属性集，逻辑表达式）的情况下，还要编一个数据处理函数void inc_col1()，update函数的接口是这样的：
int update(void (* data_processor)(), 表名，属性集，逻辑表达式）

这样确实实现了功能，但是我觉得有几点不足：
1。复用度不高，无法被sql解释/执行程序有效复用，sql解释/执行程序几乎要重新独立编写。
2。我曾经认为，事务回滚可以用逆运算来实现，比如我举的上面那个例子，但是，大多数情况下，无法用逆运算实现，比如insert，delete就无法用逆运算实现。还有，即使理论上存在逆运算，也无法智能求得逆运算动作，只能由调用者给出（比如上面的例子，其逆运算是col1=co1－1），这还是逆运算比较简单的情况。

我想出现以上如此不合协现象的原因，第一是我可能走了歪路，第二是函数的表示能力比sql语句弱，函数可能相当于线性的确定有限自动机，而sql语句可能是上下文无关文法对应的处理机。（注意我这里说得函数不是指类似于处理sql语句串的函数）

这些想法是否正确？希望大家谈谈自己的看法。

chenhao_no1

和楼主商酌第二点：
把每次操作的是何命令记下。
对于UPDATE只记操作的命令，回滚时可以通过逆运算进行。
对于INSERT，DELETE不仅要记操作的命令，还要记对于哪些字段做了哪些变动。回滚时直接将记录的变动逆着做一边。

如果一个事务中有大量UPDATE，最好也记录下对哪些字段所做的改动。这样在回滚时可以加快速度。

采取这种方法的缺点是要用大量空间保存改动。如果一个事务不停得有改动操作，有可能会超出系统对进程可用内存的限制。不过这个问题还是有办法解决。就是用mmap() and ftruncate() 将变动记录保存在磁盘上。

蓝色键盘

sql用

lex/yacc处理

BingbingNorth

谢谢键盘兄和chenhao_no1兄的回复！
chenhao_no1 兄：
我现在还无法理出个头绪，您的分类很正确，但是“逆运算”是解方程操作，能不能实现挺难说，我怀疑即使是产品化的数据库也没有这个能力。
键盘兄：
我原来提供给数据库开发人员的接口不是sql，而是运算，与加减乘除是同一层次的，跟sql差别很大，sql是解释的。
另外，如果支持sql，难度也不在词法分析和语法分析上，而是关系代数和关系演算上，另外，本人窃以为sql是一门很晦涩的语言，例子我随便可以举出几个。
我想如果我现在的路走不通的话，再考虑用sql作为接口。
而现在的方法究竟能不能走通？这我就很难说了，我想这可能与形式语言的表示能力有关，我的题目“问一个涉及到数学原理的问题”（原来的设是别字）就是指着个。

享受生活

一个人想写一个数据库，不管你多牛，我觉得是不太现实的，即使你写出来了，也是特别丑陋，没什么效率的，
   没什么意义和价值。

chenhao_no1

To BingbingNorth:

SQL语言可有可无。因为SQL语言到最后还是要调用API函数，你干脆直接让客户调用不简单吗。

另外对于（字段名1 >;  11)  || （字段名2>;  12) 这种选择条件采用逆波兰表达式去处理。

对于并发控制可以采用　工作区＋排它锁　去实现。

To  享受生活：

如果程序员不努力向系统级发展，那就是在吃青春饭。
而理解系统的最好方法就是实践。

JohnBull

利用逆运算实现回滚要出人命的!不可能!
你应该参考日志式文件系统的原理,所有的操作通过一个多版本并发层进行,而不要直接修改目标数据.在并发控制层中存放操作"日志",提交的时候把日志flush进目标数据,回滚的话就放弃日志.