关于关系代数的源代码问题

哪位高手有关系代数的源代码啊？一部分也行，小弟正在做一个数据库管理系统，打算查询部分用关系代数做，不想直接用sql，因为还有自己设计的查询语言。如果没有现成的源代码，哪怕跟大家讨论一下设计方法也会受益良多啊！谢谢！

解决方案 »

  1.   

    关系代数（relational algebra）是1970年Codd在一篇论文中提出的，包含了演算关系的运算符，是关系数据库的理论基础。关系代数的基本符号包括选择（selection）、映射（projection）、卡氏积（cartesian product）、差（difference），通过这些符号能够进行多种的关系运算，说到底，就是求关系的闭包。不过，直接用关系代数非常麻烦，因为你必须指明演算顺序和步骤，是一种过程式的语言，好比你用C语言写算法。因此，Codd提出了关系演算（relational calculus），以一种一阶逻辑的形式来表达，这是一种陈述式的语言，好比SQL语句，你只要说明你要什么，具体怎么计算全部交给数据库。Codd还证明了关系代数和关系演算是等价的。所以，关系代数并不好用，一般人们都是用关系演算的。而SQL语句是关系演算的行业标准，所以数据库的一切都是从SQL出发的。所以，无论什么项目，只要跟关系数据库相关的，都应该以SQL为标准查询语言。按照你的需求，我认为你应该把你项目中自己定制的特殊查询翻译成SQL语句或者存储过程然后处理，这样才是一个合理的解决方案。
      

  2.   

    to qisamuelzhang,
    这位大虾说的不错，用关系代数是比较麻烦，但问题是我做的系统还涉及到查询优化（query optimization）问题，如果直接把我的语言转化成SQL可能就失去了对查询过程的进一步控制。正是考虑到想更深入的控制查询的每一步才打算先把我的语言转化成algebra，然后通过logical optimization和phsical optimization来实现对系统的优化。还有，我的语言里涉及到几个我自己定义的功能，个别的目前还没找到用sql表达的方法。在这种需求下，不知这是不是唯一的方法呢？你还有什么其他简洁的方法吗？谢谢！
      

  3.   

    我不是太明白你说的logical optimization和phsical optimization的意思，不过可以肯定的一点是，给定一个SQL语句，数据库将优化执行策略，这点也是许多大型商业数据库比开源免费数据库优越的地方。不过，根据我自己的经验，单个SQL语句的表达能力有限，我一般是把问题转换成一个存储过程，也就是一系列SQL语句的顺序执行序列，这样可以控制问题的粒度，而且更容易追踪执行过程。至于你说的自定义功能，SQL语句一般都支持用户定义的函数（User Defined Function，UDF）以扩展标准的SQL语句，我想通过这个方法应该可以解决你的需求。
      

  4.   

    PS：我认为计算机一方面是科学，另一方面则是工程。科学讲究定理证明，而工程则强调规约，即用类似的方法论套用在另外一个场景中，比如我们常用的设计模式就是一个很好的例子。把新的问题规约到现有问题，利用现有问题的即成优势，可以避免重复发明轮子。SQL潜力很大，多多挖掘，应该可以最快最好的完成任务。
      

  5.   

    我做的系统并不是一个商业系统，纯属研究型。所以对查询的优化完全是通过系统本身实现的，并不依靠数据库管理软件。qisamuelzhang说的把查询转化成若干个小的sql查询的方法我也想过，但这样就影响了查询语言的语义学（semantics），而且基于研究本身的特点问题，我还是想通过关系代数来实现系统的设计。
    我很同意qisamuelzhang对于科学与工程的观点，但问题是我做的现在算不上工程，只是想找一条别人还没走的路试一试^_^
    谢谢！不知你还有没有别的想法呢？
      

  6.   

    logical optimization是指逻辑优化，就是把查询语句转化成关系代数后通过对代数组合顺序的调整来达到对查询的优化，比如一般可以把selection往查询树下推，这样下一步所要处理的数据就少一些。physical optimization是指物理优化，就是在执行最终的查询计划前通过对磁盘访问量等因素来调整对查询的执行方案。
      

  7.   

    很多人经常用关系数据库，但是很少会考虑优化问题，你的研究系统确有点意思。我觉得你完全可以用关系代数描述你的操作以及优化，由于关系代数与关系演算等价，而SQL又是关系演算的标准语言，你的查询应该与SQL等价的。当然，如果抛开SQL不谈，自己实现一套关系代数系统，应该不是非常困难的事情，毕竟才几个操作符而已。祝你好运。
      

  8.   

    先谢谢qisamuelzhang了，打算开始自己做了，以后有什么进展会上来跟大家讨论的，如果大家感兴趣也可以经常来看看！^_^
      

  9.   

    老兄，你的关系代数的库写成了吗？发个我参考参考[email protected]
      

  10.   

    对我有用，麻烦给发一个吧，[email protected]谢谢