Synchronized relations: logical characterization and complexity of query evaluation Synchronized relations are relations on words defined by finite automata with synchronous head movement. They are considered as a natural extension of regular languages in higher dimension. They have robust theoretical properties and are sufficiently expressive to find applications in a wide variety of domains. One such domain is graph databases, where the query formalism of Regular Path Queries is extended with conjunctions and synchronized relations to produce Extended Conjunctive Regular Path Queries (ECRPQs). These queries, when operated on databases, produce vertices with paths whose labels correspond to a given synchronized relation. We study the logical characterization of synchronized relations based on the theorem of Eilenberg et al. that the set of relations definable by first-order word-theoretic formulas with the predicates prefix, equal length, and last letter is exactly the set of synchronized relations.
We study the alternation hierarchy of quantifiers in this logic, showing that it collapses into expressive power at the third level. In addition, we characterize the lower levels of this hierarchy - levels one and two and their Boolean closures - by providing a combinatorial description of the relational subclasses corresponding to the lower levels of this hierarchy. An important problem in this context is membership; for a given subset C of synchronous relations, the C-membership problem asks whether an input synchronous relation belongs to C or not. We show that membership in C is decidable for all subclasses C of relations
that are definable in the lower levels of the quantifier alternation hierarchy. We also study the query evaluation problem for QPRTs, which is known to be PSpace-complete. A common theme in research on conjunctive query evaluation and CRPQs is to consider subclasses of queries that are easier to evaluate; in other words, we want to specify exactly which subclasses admit evaluation in polynomial time. We introduce a new hypergraph-based abstraction for QPRTs, which allows us to define measures to simplify the evaluation problem. Using these measures, we state precisely the conditions on the subclasses of QPRTs that admit evaluation in polynomial time, NP-complete and PSpace-complete.