Incremental homomorphism search

Abstract

An incremental search problem tries to answer how the answer set to some query changes in response to a relatively small change to underlying ground truth data. This can be much more efficient than trying to compute the answer to the new data from scratch. Moreover, in many contexts we have a fixed set of possible changes that we are anticipating, so our algorithm ought to take advantage of this extra knowledge. We’ll first address this in the context of relational databases, which we model as ACSets, with the set of ACSet homomorphisms Hom(Q, X) being the answer set to a query Q, which is itself an ACSet. Then we’ll generalize this story to any category with appropriate structure. This is work-in-progress, which you can check out at https://www.krisb.org/forest/math-00IG.xml.