基于核外计算的Datalog引擎设计与实现
作者:
作者单位:

作者简介:

张奕裕(1997-),男,博士生,主要研究领域为系统软件,编译优化;王归航(1997-),男,硕士生,主要研究领域为系统软件,程序语言;左志强(1986-),男,博士,副研究员,CCF专业会员,主要研究领域为系统软件,软件工程,程序语言;李宣东(1963-),男,博士,教授,博士生导师,CCF会士,主要研究领域为软件工程,形式化方法.

通讯作者:

左志强,E-mail:zqzuo@nju.edu.cn

中图分类号:

TP311

基金项目:

国家自然科学基金(61802168);江苏省自然科学基金(BK20191247)


Design and Implementation of Datalog Engine Based on Out-of-core Computing
Author:
Affiliation:

Fund Project:

  • 摘要
  • |
  • 图/表
  • |
  • 访问统计
  • |
  • 参考文献
  • |
  • 相似文献
  • |
  • 引证文献
  • |
  • 资源附件
  • |
  • 文章评论
    摘要:

    随着新兴技术的迅速发展, 领域软件对开发效率提出了新的要求. Datalog语言作为一门具有简洁语法和良好语义的声明式编程语言, 能帮助开发人员快速开发和解决问题, 近年来越来越受到重视与欢迎. 但解决真实场景问题时, 现有的单机Datalog引擎计算规模往往受限于内存容量大小, 不具有可扩展性. 为解决上述问题, 设计并实现基于核外计算的Datalog引擎. 方法首先设计一系列计算Datalog程序所需的支持核外计算的操作算子, 然后将Datalog程序转换合成带核外计算算子的C++程序, 接着方法设计基于Hash的分区策略和基于搜索树剪枝的最少置换调度策略, 将相应的分区文件调度执行计算并得到最终结果. 基于该方法, 实现原型工具DDL (disk-based Datalog engine), 并选取广泛应用的真实Datalog程序, 在合成数据集以及真实数据集上进行实验, 实验结果体现了DDL良好性能以及高可扩展性.

    Abstract:

    As emerging technologies develop rapidly, domain software puts forward new requirements for development efficiency. In addition, as a declarative programming language with concise syntax and well-defined semantics, Datalog can help developers solve complex problems rapidly and achieve smooth development and thus has attracted wide attention in recent years. However, when solving real-world problems, the existing single-machine Datalog engines are often limited by the size of memory capacity and possess no scalability. To solve these problems, this study designs and implements a Datalog engine based on out-of-core computing. Firstly, a series of operators supporting out-of-core computing are designed to compute the Datalog program, and then the program is converted into a C++ program with the operators. Next, the study designs a partition strategy based on Hash and a minimum replacement scheduling strategy based on search tree pruning. After that, the corresponding partition files are scheduled and computed to generate the final results. Based on this method, the study establishes the prototype tool DDL (disk-based Datalog engine) and selects widely used real-world Datalog programs to conduct experiments on both synthetic and real-world datasets. The experimental results show that DDL has positive performance and high scalability.

    参考文献
    相似文献
    引证文献
引用本文

张奕裕,王归航,左志强,李宣东.基于核外计算的Datalog引擎设计与实现.软件学报,2023,34(8):3587-3604

复制
分享
文章指标
  • 点击次数:
  • 下载次数:
  • HTML阅读次数:
  • 引用次数:
历史
  • 收稿日期:2021-08-09
  • 最后修改日期:2021-10-09
  • 录用日期:
  • 在线发布日期: 2022-01-28
  • 出版日期: 2023-08-06
文章二维码
您是第位访问者
版权所有:中国科学院软件研究所 京ICP备05046678号-3
地址:北京市海淀区中关村南四街4号,邮政编码:100190
电话:010-62562563 传真:010-62562533 Email:jos@iscas.ac.cn
技术支持:北京勤云科技发展有限公司

京公网安备 11040202500063号