(19)国家知识产权局 (12)发明 专利申请 (10)申请公布号 (43)申请公布日 (21)申请 号 202211341678.7 (22)申请日 2022.10.31 (71)申请人 南京航空航天大 学 地址 210016 江苏省南京市秦淮区御道街 29号 (72)发明人 秦小麟　喻婷　朱世彪　陈浩滨　 (74)专利代理 机构 南京钟山专利代理有限公司 32252 专利代理师 上官凤栖 (51)Int.Cl. G06F 9/48(2006.01) G06F 9/50(2006.01) (54)发明名称 一种基于并行的Datalog系统等价数据处理 方法 (57)摘要 本发明提出了一种基于并行的Datalog系统 等价数据处理方法， 并提出了相应的存储介质， 目的在于解决传统Datalog系统求解技术中对含 等价关系的规则的计算存在冗余， 造成计算资源 浪费这一问题。 本发明采用多线程技术， 将计算 的输入按照负载均衡策略分配到不同的线程中， 多个线程同时进行计算并在计算过程中过滤掉 不必要的部分， 使得硬件资源的得到了充分的利 用， 也提高了此类规则的计算效率。 同时， 本发明 采用的数据结构中， 每个存储元素包含了双倍的 信息， 减少了空间的开销。 比起传统的方法， 本发 明能够减少求解中的计算量， 同时减少空间的消 耗， 能提高Datal og系统的性能。 权利要求书2页 说明书5页 附图2页 CN 115543581 A 2022.12.30 CN 115543581 A 1.一种基于并行的Datal og系统等 价数据处 理方法， 其特 征在于， 包括以下步骤： s1： 向内存申请空间并初始化哈希位向量表， 从文件中读取EDB元组数据存入内存中， 并建立B+树 来索引EDB元组数据， 计算入口规则， 将结果存 入哈希位向量表； s2： 向操作系 统申请m个子线程放入线程池中， 启动子线程读取EDB元组数据作为输入 数据； S3： 每个子线程对输入数据执行计算， 并将生成的新元组个数作为返回值放入CPU的通 用寄存器中； S4： 当所有元组计算完成后， 主线程从通用寄存器中取出并累加所有子线程的返回值， 得到生成的新元组个数， 如果不为0， 则将查重后得到的增量元组作为输入数据并返回步骤 S3； 反之， 则结束计算。 2.如权利要求1所述的一种基于并行的Datalog系 统等价数据处理方法， 其特征在于： 步骤S1的具体步骤如下： s11： 向内存申请一块连续空间， 大小为预设的哈希数组的大小； 在哈希数组中下标为i 的元素存放一个指针并指向大小为n ‑i bit的bit数 组， 其中n表 示EDB元组数据中顶 点的个 数， 将所有的bit位置零， 哈希位向量表 中的每一个bit含有双重语义， 既表示元组(x， y)也 表示元组(y， x)； S12： 从文件中读取EDB元组数据存入内存中， 建立B+树来索引EDB元组数据， 选择EDB元 组数据中的一列 作为关键 字； S13： 用户自定义一个比较函数Comp are(x， y)， 设定EDB元组数据中的大小关系， 如果x 大于y， 则交换x与y， 对x执行hash计算， 将元组存入哈希数组下标为hash(x)处指针所指向 的位向量中， 将该位向量中偏移量 为y‑x‑1处的bit置为1， 并标记为增量。 3.如权利要求2所述的一种基于并行的Datalog系 统等价数据处理方法， 其特征在于： 步骤S2中， 所述子线程读取EDB元组数据的具体步骤如下： S21： 主线程根据B+树索引的叶子节点进行数据划分， 将关键字列相同的元组划分至一 个数据块中； 主线程将B+树索引中的关键字封装成任务放入任务队列中， 空闲子线程通过 轮询在任务队列非空时每次从任务队列中读取一个任务执 行； S22： 子线程根据读取到的任务中的关键字查询B+树索引中对应的叶子节点， 并根据叶 子节点中指针指向的数据块中记录的偏移量去EDB元组数据中读取对应元组， 并作为计算 的输入数据； S23： 子线程执行完当前的计算后， 再通过轮询读取任务队列中的任务， 直至任务队列 为空。 4.如权利要求2所述的一种基于并行的Datalog系 统等价数据处理方法， 其特征在于： 步骤S3中， 所述每 个子线程对输入数据执 行计算的具体步骤如下： S31： 子线程i， i∈[1， m]对读取到的数据应用递归规则， 根据增量标记位将增量元组放 入缓冲区中， 对缓冲区中的增量元组根据规则执行连接操作， 在执行连接操作之前过滤掉 无需计算的元组； S32： 子线程i对连接生成的新元组执行查重操作， 计算新元组中与B+树关键字对应的 列的哈希值， 根据哈希值索引到哈希表中相应位置的位向量， 并将元组中另一列的哈希值 作为偏移量定位到位向量中的具体位置， 读取 该位置的数据；权　利　要　求　书 1/2 页 2 CN 115543581 A 2S33： 线程i读取步骤S32中所述位置的数据并判断是否应该插入该元组， 如果该位置的 bit为1， 则说明该元组已存在， 丢弃之； 如果该元组的bit为0， 则说明该元组不存在， 线程i 将该位置的数据置为 1， 代表插入 该元组， 并将该元组标记 为增量； 哈希 位向量表中代表(x， y)位置的bit为1代表(x， y)元组与(y， x)元组均被插入表中； 线程i使用count变量记录当前 线程在本轮 计算中插 入哈希位向量表中的新元组个数。 5.如权利要求4所述的一种基于并行的Datalog系 统等价数据处理方法， 其特征在于： 步骤S31中， 所述在执行连接操作之前过滤掉无需计算的元组具体如下： 对于当前元组(x， y)， 如果Compare函数返回值小于 0， x＞y， 则过滤掉此元组， 不对此 元组执行计算。 6.一种计算机可读存储介质， 存储有计算机程序， 其特征在于， 所述计算机程序使计算 机执行如权利要求1 ‑5任一项所述的基于并行的Datal og系统等 价数据处 理方法。权　利　要　求　书 2/2 页 3 CN 115543581 A 3