<?xml version="1.0" encoding="utf-8"?>
<export-example>
  <doc>
    <id>7977</id>
    <completedYear/>
    <publishedYear>2024</publishedYear>
    <thesisYearAccepted/>
    <language>eng</language>
    <pageFirst>1</pageFirst>
    <pageLast>26</pageLast>
    <pageNumber/>
    <edition/>
    <issue>5</issue>
    <volume>2</volume>
    <type>conferenceobject</type>
    <publisherName>ACM</publisherName>
    <publisherPlace/>
    <creatingCorporation/>
    <contributingCorporation/>
    <belongsToBibliography>0</belongsToBibliography>
    <completedDate>--</completedDate>
    <publishedDate>--</publishedDate>
    <thesisDateAccepted>--</thesisDateAccepted>
    <title language="eng">Insert-Only versus Insert-Delete in Dynamic Query Evaluation</title>
    <abstract language="eng">We study the dynamic query evaluation problem: Given a full conjunctive query 𝑄 and a sequence of updates&#13;
to the input database, we construct a data structure that supports constant-delay enumeration of the tuples in&#13;
the query output after each update.We show that a sequence of 𝑁 insert-only updates to an initially empty database can be executed in total time O(𝑁 w(𝑄 ) ), where w(𝑄) is the fractional hypertree width of 𝑄. This matches the complexity of the&#13;
static query evaluation problem for 𝑄 and a database of size 𝑁 . One corollary is that the amortized time per&#13;
single-tuple insert is constant for 𝛼-acyclic full conjunctive queries. In contrast, we show that a sequence of 𝑁 inserts and deletes can be executed in total time eO(𝑁 w( b𝑄 ) ), where b𝑄 is obtained from 𝑄 by extending every relational atom with extra variables that represent the “lifespans” of tuples in the database. We show that this reduction is optimal in the sense that the static evaluation runtime of b𝑄 provides a lower bound on the total update time for the output of 𝑄. Our approach achieves amortized optimal update times for the hierarchical and Loomis-Whitney join queries.</abstract>
    <parentTitle language="eng">Proceedings of the ACM on Management of Data</parentTitle>
    <identifier type="doi">10.1145/3695837</identifier>
    <enrichment key="opus.import.date">2025-03-17T20:19:32+00:00</enrichment>
    <enrichment key="opus.source">sword</enrichment>
    <enrichment key="opus.import.user">importuser</enrichment>
    <enrichment key="BegutachtungStatus">peer-reviewed</enrichment>
    <enrichment key="opus.doi.autoCreate">false</enrichment>
    <enrichment key="opus.urn.autoCreate">true</enrichment>
    <licence>Keine Lizenz - Es gilt das deutsche Urheberrecht: § 53 UrhG</licence>
    <author>Mahmoud Abo Khamis</author>
    <author>Ahmet Kara</author>
    <author>Dan Olteanu</author>
    <author>Dan Suciu</author>
    <collection role="institutes" number="FakIM">Fakultät Informatik und Mathematik</collection>
    <collection role="othforschungsschwerpunkt" number="16311">Digitalisierung</collection>
  </doc>
</export-example>
