DOI

Context-free path queries (CFPQ) extend the regular path queries (RPQ) by allowing context-free grammars to be used as constraints for paths. Algorithms for CFPQ are actively developed, but J. Kuijpers et al. have recently concluded, that existing algorithms are not performant enough to be used in real-world applications. Thus the development of new algorithms for CFPQ is justified. In this paper, we provide a new CFPQ algorithm which is based on such linear algebra operations as Kronecker product and transitive closure and handles grammars presented as recursive state machines. Thus, the proposed algorithm can be implemented by using high-performance libraries and modern parallel hardware. Moreover, it avoids grammar growth which provides the possibility for queries optimization.

Язык оригиналаанглийский
Название основной публикацииAdvances in Databases and Information Systems - 24th European Conference, ADBIS 2020, Proceedings
РедакторыJérôme Darmont, Boris Novikov, Robert Wrembel
ИздательSpringer Nature
Страницы49-59
Число страниц11
ISBN (печатное издание)9783030548315
DOI
СостояниеОпубликовано - авг 2020
Событие24th European Conference on Advances in Databases and Information Systems,ADBIS 2020 - Lyon, Франция
Продолжительность: 25 авг 202027 авг 2020

Серия публикаций

НазваниеLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Том12245 LNCS
ISSN (печатное издание)0302-9743
ISSN (электронное издание)1611-3349

конференция

конференция24th European Conference on Advances in Databases and Information Systems,ADBIS 2020
Страна/TерриторияФранция
ГородLyon
Период25/08/2027/08/20

    Предметные области Scopus

  • Теоретические компьютерные науки
  • Компьютерные науки (все)

ID: 84890048