经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » 程序设计 » C++ » 查看文章
利用C++实现?然连接操作算法
来源:jb51  时间:2022/8/1 17:09:20  对本文有异议

1. 实验目的

本次实验三需要完成的内容为实现然连接(natural join)操作算法,对两个关系进然连接,具体实现基于块的嵌套循环连接(Block-based Nested Loop Join)算法。

我们要实现的函数在 executer.cpp 文件中。

  1. bool NestedLoopJoinOperator::execute(int numAvailableBufPages,
  2. File &resultFile)

2. 实验内容

首先,我们读取两个表头的信息

  1. TableId leftTableId = catalog->getTableId("r");
  2. TableId rightTableId = catalog->getTableId("s");
  3. badgerdb::File left = File::open(catalog->getTableFilename(leftTableId));
  4. badgerdb::File right = File::open(catalog->getTableFilename(rightTableId));

运用两层循环寻找两个表中名称与类型完全相同的属性,将他们全部标记出来,用于之后的自然连接操作。

  1. vector<int> leftForeignKeyId;
  2. vector<int> rightForeignKeyId;
  3. for (int i = 0; i < leftTableSchema.getAttrCount(); i++)
  4. {
  5. for (int j = 0; j < rightTableSchema.getAttrCount(); j++)
  6. {
  7. if ((leftTableSchema.getAttrName(i) == rightTableSchema.getAttrName(j)) && (leftTableSchema.getAttrType(i) == rightTableSchema.getAttrType(j)))
  8. {
  9. leftForeignKeyId.push_back(i);
  10. rightForeignKeyId.push_back(j);
  11. break;
  12. }
  13. }
  14. }

准备操作做完后,开始进行自然连接操作。

用循环从磁盘中读取两个页面的信息,记录 io 操作次数

  1. for (badgerdb::FileIterator leftPage = left.begin(); leftPage != left.end(); leftPage++)
  2. {
  3. badgerdb::Page *bufferedLeftPage;
  4. bufMgr->readPage(&left, (*leftPage).page_number(), bufferedLeftPage);
  5. numIOs += 1;
  6.  
  7. for (badgerdb::FileIterator rightPage = right.begin(); rightPage != right.end(); rightPage++)
  8. {
  9. badgerdb::Page *bufferedRightPage;
  10. bufMgr->readPage(&right, (*rightPage).page_number(), bufferedRightPage);
  11. numIOs += 1;

之后,从表中读取全部的元组的信息,进行对比。

读取的元组信息有特殊的格式,并不能直接利用,所以需要先了解元组在表中储存的格式,然后进行解读。元组的存储方式可以从 storage.cpp 中的 createTupleFromSQLStatement 函数中得知。

  1. switch (dataType) { // (int) 56 (0011 1000) -> (char) '\0''\0''\0''8'
  2. case INT: { // convert int value into 4 byte representation
  3. case CHAR: { // (char(5) ) 'abc' -> 'abc00'
  4. case VARCHAR: { // (varchar(8) ) 'abc' -> '3''abc' (3 refer to the ascii
  5. // code number correspond alpha)

于是,我们根据注释的存储方式编写解析函数,该函数输入为文件中存储的元组,输出为数组表示的直观的元组内容。

  1. vector<string> analyze(string record, badgerdb::TableSchema schema)

先读取其中一个表的元组,用块来存储。

  1. for (badgerdb::PageIterator leftRecord = bufferedLeftPage->begin(); leftRecord != bufferedLeftPage->end(); leftRecord++)
  2. {
  3. vector<string> leftInfo = analyze(*leftRecord, leftTableSchema);
  4. numUsedBufPages += 1;
  5. block.push_back(leftInfo);
  6. if (block.size() < BLOCK_SIZE)
  7. {
  8. continue;
  9. }

然后读取另一个表的元组信息,

  1. for (badgerdb::PageIterator rightRecord = bufferedRightPage->begin(); rightRecord != bufferedRightPage->end(); rightRecord++)
  2. {
  3. numUsedBufPages += 1;

将两个元组当中的属性名相同的属性列信息进行对比,

  1. bool f = true;
  2. for(int i = 0; i < leftForeignKeyId.size(); i++)
  3. {
  4. if(leftInfo[leftForeignKeyId[i]] != rightInfo[rightForeignKeyId[i]])
  5. {
  6. f = false;
  7. break;
  8. }
  9. }

如果全部相同,则代表需要进行自然连接操作。

  1. if(f)
  2. {
  3. string current_line = "INSERT INTO TEMP_TABLE VALUES (" + leftInfo[0];
  4. for (int i = 1; i < leftTableSchema.getAttrCount(); i++)
  5. {
  6. current_line = current_line + ", " + leftInfo[i];
  7. }
  8. for (int i = 0; i < rightTableSchema.getAttrCount(); i++)
  9. {
  10. current_line = current_line + ", " + rightInfo[i];
  11. }
  12. current_line = current_line + ");";
  13.  
  14. string tuple = HeapFileManager::createTupleFromSQLStatement(current_line, catalog);
  15. numResultTuples += 1;
  16. HeapFileManager::insertTuple(tuple, resultFile, bufMgr);
  17. }

否则不进行任何操作。

在全部循环都结束之后,块中可能还会有剩余的信息没有进行处理,此时再单独对剩余信息进行处理,代码基本相同。

3. 实验结果

代码运行结果如下:

到此这篇关于利用C++实现?然连接操作算法的文章就介绍到这了,更多相关C++连接操作算法内容请搜索w3xue以前的文章或继续浏览下面的相关文章希望大家以后多多支持w3xue!

 友情链接:直通硅谷  点职佳  北美留学生论坛

本站QQ群:前端 618073944 | Java 606181507 | Python 626812652 | C/C++ 612253063 | 微信 634508462 | 苹果 692586424 | C#/.net 182808419 | PHP 305140648 | 运维 608723728

W3xue 的所有内容仅供测试,对任何法律问题及风险不承担任何责任。通过使用本站内容随之而来的风险与本站无关。
关于我们  |  意见建议  |  捐助我们  |  报错有奖  |  广告合作、友情链接(目前9元/月)请联系QQ:27243702 沸活量
皖ICP备17017327号-2 皖公网安备34020702000426号