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的实施铺平了道路。