In the last decade, substantial progress has been made towards standardizing the syntax of graph query languages, and towards understanding their semantics and complexity of evaluation. In this paper, we consider temporal property graphs (TPGs) and propose temporal regular path queries (TRPQ) that incorporate time into TPGs navigation. Starting with design principles, we propose a natural syntactic extension of the MATCH clause of popular graph query languages. We then formally present the semantics of TRPQs, and study the complexity of their evaluation. We show that TRPQs can be evaluated in polynomial time if TPGs are time-stamped with time points. We also identify fragments of the TRPQ language that admit efficient evaluation over a more succinct interval-annotated representation. Our work on the syntax, and the positive complexity results, pave the way to implementations of TRPQs that are both usable and practical.


翻译:在过去十年中,在将图表查询语言的语法标准化和理解其语义和评价复杂性方面取得了实质性进展。在本文中,我们考虑了时间属性图(TPGs),并提出了将时间纳入TPG导航的定期时间路径查询(TRPQ)建议。从设计原则开始,我们建议自然扩展流行图形查询语言Match条款的语义,然后正式介绍TRPQs的语义,并研究其评估的复杂性。我们表明,如果TPGs有时间标记,TRPQs可以在多音时段进行评估。我们还确定了TRPQ语言的碎片,这些碎片允许在更简洁的间隔内附加说明后进行高效评估。我们关于语义和正面复杂结果的工作为可使用和实用的TRPQs的实施铺平了道路。

0
下载
关闭预览

相关内容

自然语言处理顶会COLING2020最佳论文出炉!
专知会员服务
23+阅读 · 2020年12月12日
经济学中的数据科学,Data Science in Economics,附22页pdf
专知会员服务
35+阅读 · 2020年4月1日
知识图谱本体结构构建论文合集
专知会员服务
106+阅读 · 2019年10月9日
【SIGGRAPH2019】TensorFlow 2.0深度学习计算机图形学应用
专知会员服务
39+阅读 · 2019年10月9日
CCF推荐 | 国际会议信息6条
Call4Papers
9+阅读 · 2019年8月13日
计算机 | 中低难度国际会议信息8条
Call4Papers
9+阅读 · 2019年6月19日
计算机 | IUI 2020等国际会议信息4条
Call4Papers
6+阅读 · 2019年6月17日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
人工智能 | 国际会议/SCI期刊约稿信息9条
Call4Papers
3+阅读 · 2018年1月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Arxiv
0+阅读 · 2021年9月3日
Arxiv
0+阅读 · 2021年9月2日
Arxiv
4+阅读 · 2019年9月5日
VIP会员
相关资讯
CCF推荐 | 国际会议信息6条
Call4Papers
9+阅读 · 2019年8月13日
计算机 | 中低难度国际会议信息8条
Call4Papers
9+阅读 · 2019年6月19日
计算机 | IUI 2020等国际会议信息4条
Call4Papers
6+阅读 · 2019年6月17日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
Call for Participation: Shared Tasks in NLPCC 2019
中国计算机学会
5+阅读 · 2019年3月22日
大数据 | 顶级SCI期刊专刊/国际会议信息7条
Call4Papers
10+阅读 · 2018年12月29日
A Technical Overview of AI & ML in 2018 & Trends for 2019
待字闺中
16+阅读 · 2018年12月24日
disentangled-representation-papers
CreateAMind
26+阅读 · 2018年9月12日
人工智能 | 国际会议/SCI期刊约稿信息9条
Call4Papers
3+阅读 · 2018年1月12日
Auto-Encoding GAN
CreateAMind
7+阅读 · 2017年8月4日
Top
微信扫码咨询专知VIP会员