Certain Query Answering on Hyperstreams
Requêtes Logiques sur les Hyperflux
Résumé
Hyperstreams are collections of streams with references. The hope is that structured data on a hyperstream can be monitored with lower latency than when communicated on a stream, since data on hyperstreams may be received in parallel rather than in a purely sequential manner. In order to show this, however, it is necessary to develop algorithms for answering logical queries on hyperstreams, given that the existing algorithms are restricted to streams. Therefore, we study the question of whether certain query answering (CQA) on hyperstreams is feasible in theory and practice.
We study the complexity of CQA on hyperstreams. We first show that CQA is closely related to the problems of regular pattern matching and inclusion, and thus to the problem of transition inhabitation for automata for words and trees. This permits us to classify the complexity of CQA for various classes of automata and hyperstreams. We obtain polynomial time results for linear hyperstreams without compression and queries defined by deterministic stepwise hedge automata. For the general case, the complexity goes up to ExpTime.
We then develop an efficient approximation algorithm for CQA on hyperstreams. This algorithm has large coverage in that it applies to arbitrary hyperstreams and classes of query automata, and runs in polynomial time. However, it may not always detect the certain query answers with lowest latency.
The third contribution is an algorithm for CQA on streams that runs in combined linear time in the case of boolean queries. This algorithm is efficient in practice also in the monadic case, in contrast to all previous proposals. We show this experimentally by applying the algorithm to the navigational queries of the usual XPath benchmark, on which all previous approximation-free approaches to CQA failed. Deterministic stepwise hedge automata enable this algorithm.
Les hyperflux sont des collections de flux de données avec références. Sachant qu’ils permettent la réception de données en parallèle plutôt que de manière purement séquentielle, l’on peut espérer que des données structurées transmises par leur biais puissent être traitées avec une latence moindre qu’avec un flux. Nous proposons ainsi de développer des algorithmes d’évaluation de requêtes logiques sur les hyperflux de données. Pour ce faire, nous nous intéressons à la faisabilité théorique et pratique d’un algorithme de décision du problème de certitude d’une réponse (CQA) sur les hyperflux.
Nous étudions la complexité du CQA sur les hyperflux. Nous montrons d’abord que le CQA est intimement lié à des problèmes de correspondance de motifs dans les langages réguliers, et donc aux problèmes d’habitation des transitions d’automates de mots et d’arbres. Cela nous permet d’établir une classification de la complexité du CQA pour des classes d’automates et d’hyperflux variées. Nous obtenons des résultats en temps polynomial pour les hyperflux linéaires sans compression et les requêtes définies par des automates déterministes pour forêts. Pour le cas général, la complexité atteint ExpTime.
Nous développons ensuite un algorithme efficace pour l’approximation du CQA sur les hyperflux. Cet algorithme a une grande couverture, du fait qu’il s’applique à des hyperflux et des classes d’automates arbitraires, et s’exécute en temps polynomial. Cependant, il ne détecte pas toujours les réponses certaines avec une latence minimale.
La troisième contribution est un algorithme pour le CQA sur les flux, qui s’exécute en temps polynomial dans le cas de requêtes booléennes. Cet algorithme est aussi efficace en pratique pour le cas monadique, à l’inverse de toutes les précédentes propositions. Nous le montrons expérimentalement en appliquant l’algorithme aux requêtes navigationnelles XPath habituellement prises pour référence, avec lesquelles toutes les approches précédentes de CQA sans approximation ont échoué. L’utilisation d’automates spéciaux pour les forêts a permis la mise en place dudit algorithme.
Origine : Fichiers produits par l'(les) auteur(s)