Relations synchronisées et complexité de l'évaluation des requêtes

Abstract

Les relations synchronisées sont des relations sur les mots définies par des automates finis avec un mouvement synchrone des têtes. Elles sont considérées comme une extension naturelle des langages réguliers en dimension supérieure. Elles ont des propriétés théoriques robustes et sont suffisamment expressives pour trouver des applications dans une grande variété de domaines. Un de ces domaines est celui des bases de données de graphes, où le formalisme d'interrogation des Regular Path Queries est étendu avec des conjonctions et des relations synchronisées pour produire des Extended Conjunctive Regular Path Queries (ECRPQs). Ces requêtes, lorsqu'elles sont exploitées sur des bases de données, produisent des sommets avec des chemins dont les étiquettes correspondent à une relation synchronisées donnée.Nous étudions la caractérisation logique des relations synchronisées en nous appuyant sur le théorème d'Eilenberg et al., selon lequel l'ensemble des relations définissables par des formules du premier ordre de la théorie des mots avec les prédicats préfixe, égale_longueur et dernière_lettre, est exactement l'ensemble des relations synchronisées. Nous étudions la hiérarchie d'alternance des quantificateurs de cette logique, en montrant qu'elle s'effondre en puissance expressive au troisième niveau. De plus, nous caractérisons les niveaux inférieurs de cette hiérarchie - les niveaux un et deux et leurs fermetures booléennes - en fournissant une description combinatoire des sous-classes relationnelles correspondant aux niveaux inférieurs de cette hiérarchie. Un problème important dans ce contexte est l'appartenance ; pour un sous-ensemble C donné de relations synchrones, le problème de l'appartenance à C demande si une relation synchrone d'entrée appartient à C ou non.Nous montrons que l'appartenance à C est décidable pour toutes les sous-classes C de relations définissables dans les niveaux inférieurs de la hiérarchie d'alternance des quantificateurs.Nous étudions également le problème de l'évaluation des requêtes pour les ECRPQs, qui est connu pour être PSpace-complet.Un thème commun de la recherche sur l'évaluation des requêtes conjonctives et des CRPQ est de considérer des sous-classes de requêtes qui sont plus faciles à évaluer ; en d'autres termes, nous voulons spécifier exactement quelles sous-classes admettent une évaluation en temps polynomial. Nous introduisons une nouvelle abstraction basée sur les hypergraphes pour les ECRPQs, qui nous permet de définir des mesures afin de simplifier le problème d'évaluation. En utilisant ces mesures, nous énonçons précisément les conditions sur les sous-classes de ECRPQs qui admettent une évaluation en temps polynomial, NP-complet et PSpace-complet.