We investigate trade-offs in static and dynamic evaluation of hierarchical queries with arbitrary free variables. In the static setting, the trade-off is between the time to partially compute the query result and the delay needed to enumerate its tuples. In the dynamic setting, we additionally consider the time needed to update the query result in the presence of single-tuple inserts and deletes to the input database. Our approach observes the degree of values in the database and uses different computation and maintenance strategies for high-degree and low-degree values. For the latter it partially computes the result, while for the former it computes enough information to allow for on-the-fly enumeration. The main result of this work defines the preprocessing time, the update time, and the enumeration delay as functions of the light heavy threshold and of the factorization width of the hierarchical query. By conveniently choosing this threshold, our approach can recover a number of prior results when restricted to hierarchical queries.
Acyclicity itself is necessary for having constant delay enumeration: A conjunctive query admits constant delay enumeration after linear-time preprocessing if and only if it is free-connex acyclic @cite_24 . This is based on a stronger hypothesis that the existence of a triangle in a hypergraph of @math vertices cannot be tested in time @math and that for any @math , testing the presence of a @math -dimensional tetrahedron cannot be tested in linear time. An in-depth pre-2015 overview on constant-delay enumeration is provided by Segoufin @cite_29 .
@cite_24 @cite_29
2624791742 2234276446
Au-dela de la decision de problemes de satisfaisabilite, on s’interesse a la generation exhaustive de leurs solutions, l’enumeration. Nous interrogeons d’abord la pertinence du probleme d’enumeration dans le cadre tres classique de la logique propositionnelle. La dichotomie de Creignou et Hebrard prouve deja l’equivalence entre les classes polynomiales pour la decision non triviale et celles pour l’enumeration. On donne des algorithmes d’enumeration optimaux pour chacune de ces classes, qui generalisent tout algorithme de decision non triviale, suggerant que l’enumeration est le probleme pertinent dans ce cadre. Ensuite, nous completons et simplifions des resultats de dichotomie de qui etablissent un lien etroit entre la facilite d’une requete conjonctive et une notion d’acyclicite d’hypergraphe. On prouve alors, grâce a un nouvel algorithme, des resultats similaires pour la classe duale de celle des requetes conjonctives. Finalement, en generalisant le resultat classique de combinatoire de Brouwer et Kolen, on unifie l’ensemble de ces resultats sous forme d’une dichotomie pour l’enumeration des requetes conjonctives dites signees, qui etablit un lien fort entre facilite de l’enumeration et facilite de la decision. We survey some of the recent results about enumerating the answers to queries over a database. We focus on the case where the enumeration is performed with a constant delay between any two consecutive solutions, after a linear time preprocessing. This cannot be always achieved. It requires restricting either the class of queries or the class of databases. We consider conjunctive queries and describe several scenarios when this is possible.