2023/12/09 by David, Claire, Francis, Nadime, Marsault, Victor
#Data Structures and Algorithms (cs.DS) #Databases (cs.DB) #FOS: Computer and information sciences #Formal Languages and Automata Theory (cs.FL)
paper · doi:10.48550/arxiv.2312.05505
We consider the Distinct Shortest Walks problem. Given two vertices s and t of a graph database D and a regular path query, enumerate all walks of minimal length from s to t that carry a label that conforms to the query. Usual theoretical solutions turn out to be inefficient when applied to graph models that are closer to real-life systems, in particular because edges may carry multiple labels. Indeed, known algorithms may repeat the same answer exponentially many times. We propose an efficient algorithm for multi-labelled graph databases. The preprocessing runs in O|D|×|A| and the delay between two consecutive outputs is in O(λ×|A|), where A is a nondeterministic automaton representing the query and λ is the minimal length. The algorithm can handle ε-transitions in A or queries given as regular expressions at no additional cost.