面向双时态RDF星型查询的两阶段索引方法

doi:10.12068/j.issn.1005-3026.2025.20230298

摘要/Abstract

摘要：

为了对时间信息进行表示和处理，随之开展了时态RDF（temporal resource description framework）的扩展研究，而如何对时态RDF数据进行有效的管理也逐渐成为了一个重要问题.构建有效的索引机制是管理时态RDF数据和提高查询效率的重要途径之一.本文提出了一种针对双时态RDF（bitemporal RDF）星型查询的两阶段索引方法：第一阶段索引提出一种基于双时态RDF节点邻域信息的候选集生成方法，第二阶段索引进一步提出一种基于位图索引的结果集生成方法.通过两阶段索引可以避免星型查询中成本昂贵的连接操作，快速得到查询结果.在查询效率和索引性能方面进行了对比实验，验证了所提方法的有效性.

关键词: 资源描述框架（RDF）, 双时态RDF, 星型查询, 两阶段索引, 位图索引

Abstract:

In order to represent and process time information， the extended research on temporal RDF （temporal resource description framework） model has been carried out， and how to effectively manage temporal RDF data has gradually become an important issue. Constructing a reasonable and effective index mechanism is one of the important ways to manage temporal RDF data and improve query efficiency. A two-stage indexing method for bitemporal RDF star query was proposed. First-stage indexing proposes a candidate set generation method based on bitemporal RDF node neighborhood information， and second-stage indexing further proposes a result set generation method based on bitmap indexing. With two-stage indexing， expensive join operations in star queries can be avoided and query results can be obtained quickly. This paper conducts comparative experiments in terms of query efficiency and index performance to verify the effectiveness of the proposed method.

Key words: resource description framework（RDF）, bitemporal RDF, star query, two-stage indexing, bitmap indexing

中图分类号:

TP 18

王刚, 张薇, 陈宏栉, 张富. 面向双时态RDF星型查询的两阶段索引方法[J]. 东北大学学报（自然科学版）, 2025, 46(2): 18-27.

Gang WANG, Wei ZHANG, Hong-zhi CHEN, Fu ZHANG. Two-Stage Indexing Method for Bitemporal RDF Star Query[J]. Journal of Northeastern University(Natural Science), 2025, 46(2): 18-27.

图/表 16

参考文献 17

1	Manola F， Miller E. RDF 1.1 primer ［EB/OL］. （2014-06-24）［2023-03-15］. .
2	Gutierrez C， Hurtado C， Vaisman A. Temporal RDF ［M］//Lecture Notes in Computer Science. Berlin， Heidelberg： Springer， 2005： 93-107.
3	Pugliese A， Udrea O， Subrahmanian V S. Scaling RDF with time ［C］// International Conference on World Wide Web. New York： Association for Computing Machinery， 2008： 605-614.
4	Wang H T， Tansel A U. Temporal extensions to RDF ［J］. Journal of Web Engineering， 2019， 18（3）： 125-168.
5	Runge L， May W. Towards semantic identification of temporal data in RDF ［C］// Proceedings of the 34th Workshop on Basics of Database Systems. Calw： CEUR， 2023： 1-8.
6	Yan L， Zhang Z Q， Yang D. Temporal RDF（S） data storage and query with HBase ［J］. Journal of Computing and Information Technology， 2020， 27（4）： 17-30.
7	Bellamy-McIntyre J. LSPARQL： transaction time queries in RDF ［D］. Auckland： The University of Auckland， 2020.
8	Li H X. A new query method for the temporal RDF model RDFMT based on SPARQL ［C］// Artificial Intelligence and Information Systems. New York： Association for Computing Machinery， 2021： 1-6.
9	Meijer L. Bi-VAKs： bi-temporal versioning approach for knowledge graphs ［D］. Delft： Delft University of Technology， 2022.
10	Ma R Z， Han X， Yan L， et al. Modeling and querying temporal RDF knowledge graphs with relational databases ［J］. Journal of Intelligent Information Systems， 2023， 61（2）： 569-609.
11	Chawla T， Singh G， Pilli E S， et al. Storage， partitioning， indexing and retrieval in big RDF frameworks： a survey ［J］. Computer Science Review， 2020， 38： 100309.
12	Zhao P， Yan L. A methodology for indexing temporal RDF data ［J］. Journal of Information Science & Engineering， 2019， 35（4）： 923-934.
13	Zhou T Y， Liu Y， Zhang H， et al. Optimization of bit matrix index for temporal RDF ［M］//Communications in Computer and Information Science. Singapore： Springer Nature Singapore， 2022： 95-107.
14	Zang S Q， Han S， Yuan P P， et al. HyperBit： a temporal graph store for fast answering queries ［J］. Data & Knowledge Engineering， 2023， 144： 102128.
15	Zhang F， Li Z Y， Peng D H， et al. RDF for temporal data management： a survey ［J］. Earth Science Informatics， 2021， 14（2）： 563-599.
16	Chawla T， Singh G， Pilli E S， et al. Research issues in RDF management systems ［C］// Emerging Trends in Communication Technologies. Piscataway： IEEE， 2016： 1-5.
17	Guo Y B， Pan Z X， Heflin J. LUBM： a benchmark for OWL knowledge base systems ［J］. Journal of Web Semantics， 2005， 3（2/3）： 158-182.

主语	谓语	宾语	有效时间	事务时间
dep:S0	rdf:type	org:FullProfessor	2000-12—2010-07	2000-12
dep:S0	org:teacherOf	dep:Course0	2000-12—2010-07	2000-12
dep:S0	org:worksFor	Department0	2000-12—2010-07	2000-12
dep:S1	rdf:type	org:FullProfessor	2010-09—now	2011-11
dep:L0	rdf:type	org:Lecturer	2002-03—2010-06	2012-12
…	…	…	…	…

主语	谓语	宾语	有效时间	事务时间
dep:S0	rdf:type	org:FullProfessor	2000-12—2010-07	2000-12
dep:S0	org:teacherOf	dep:Course0	2000-12—2010-07	2000-12
dep:S0	org:worksFor	Department0	2000-12—2010-07	2000-12
dep:S1	rdf:type	org:FullProfessor	2010-09—now	2011-11
dep:L0	rdf:type	org:Lecturer	2002-03—2010-06	2012-12
…	…	…	…	…

宾语	主语	（最小值，最大值）	主语的邻域信息
2	1	（2，6）	［2~6］
3	1	（2，6）	［2~6］
	7	（3，11）	［3，4，8~11］
	12	（3，16）	［3，13~16］
4	1	（2，6）	［2~6］
5 6	7 1 1	（3，11）（2，6）（2，6）	［3，4，8~11］［2~6］［2~6］
8	7	（3，11）	［3，4，8~11］
9	7	（3，11）	［3，4，8~11］
10	7	（3，11）	［3，4，8~11］
11	7	（3，11）	［3，4，8~11］
13	12	（3，16）	［3，13~16］
14	12	（3，16）	［3，13~16］
15	12	（3，16）	［3，13~16］
16	12	（3，16）	［3，13~16］

宾语	主语	（最小值，最大值）	主语的邻域信息
2	1	（2，6）	［2~6］
3	1	（2，6）	［2~6］
	7	（3，11）	［3，4，8~11］
	12	（3，16）	［3，13~16］
4	1	（2，6）	［2~6］
5 6	7 1 1	（3，11）（2，6）（2，6）	［3，4，8~11］［2~6］［2~6］
8	7	（3，11）	［3，4，8~11］
9	7	（3，11）	［3，4，8~11］
10	7	（3，11）	［3，4，8~11］
11	7	（3，11）	［3，4，8~11］
13	12	（3，16）	［3，13~16］
14	12	（3，16）	［3，13~16］
15	12	（3，16）	［3，13~16］
16	12	（3，16）	［3，13~16］

数据集	双时态三元组数	时间区间数	时间点数
数据集1	16 000	5 000	2 500
数据集2	50 000	8 000	4 000
数据集3	140 000	16 000	8 000
数据集4	300 000	32 000	16 000