{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,7,10]],"date-time":"2024-07-10T11:09:23Z","timestamp":1720609763828},"reference-count":0,"publisher":"Centre pour la Communication Scientifique Directe (CCSD)","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"abstract":"We investigate trade-offs in static and dynamic evaluation of hierarchical\nqueries with arbitrary free variables. In the static setting, the trade-off is\nbetween the time to partially compute the query result and the delay needed to\nenumerate its tuples. In the dynamic setting, we additionally consider the time\nneeded to update the query result under single-tuple inserts or deletes to the\ndatabase.\n Our approach observes the degree of values in the database and uses different\ncomputation and maintenance strategies for high-degree (heavy) and low-degree\n(light) values. For the latter it partially computes the result, while for the\nformer it computes enough information to allow for on-the-fly enumeration.\n We define the preprocessing time, the update time, and the enumeration delay\nas functions of the light\/heavy threshold. By appropriately choosing this\nthreshold, our approach recovers a number of prior results when restricted to\nhierarchical queries.\n We show that for a restricted class of hierarchical queries, our approach\nachieves worst-case optimal update time and enumeration delay conditioned on\nthe Online Matrix-Vector Multiplication Conjecture.<\/jats:p>","DOI":"10.46298\/lmcs-19(3:11)2023","type":"journal-article","created":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T07:50:13Z","timestamp":1691567413000},"source":"Crossref","is-referenced-by-count":1,"title":["Trade-offs in Static and Dynamic Evaluation of Hierarchical Queries"],"prefix":"10.46298","volume":"Volume 19, Issue 3","author":[{"given":"Ahmet","family":"Kara","sequence":"first","affiliation":[]},{"given":"Milos","family":"Nikolic","sequence":"additional","affiliation":[]},{"given":"Dan","family":"Olteanu","sequence":"additional","affiliation":[]},{"given":"Haozhe","family":"Zhang","sequence":"additional","affiliation":[]}],"member":"25203","published-online":{"date-parts":[[2023,8,9]]},"container-title":["Logical Methods in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/lmcs.episciences.org\/11711\/pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/lmcs.episciences.org\/11711\/pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,8,9]],"date-time":"2023-08-09T07:50:14Z","timestamp":1691567414000},"score":1,"resource":{"primary":{"URL":"https:\/\/lmcs.episciences.org\/10035"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,8,9]]},"references-count":0,"URL":"https:\/\/doi.org\/10.46298\/lmcs-19(3:11)2023","relation":{"has-preprint":[{"id-type":"arxiv","id":"1907.01988v5","asserted-by":"subject"},{"id-type":"arxiv","id":"1907.01988v4","asserted-by":"subject"},{"id-type":"arxiv","id":"1907.01988v3","asserted-by":"subject"}],"is-same-as":[{"id-type":"arxiv","id":"1907.01988","asserted-by":"subject"},{"id-type":"doi","id":"10.48550\/arXiv.1907.01988","asserted-by":"subject"}]},"ISSN":["1860-5974"],"issn-type":[{"value":"1860-5974","type":"electronic"}],"subject":[],"published":{"date-parts":[[2023,8,9]]}}}