Asymptotic determinacy of path queries using union-of-paths views (Q2402616)

Graph databases (GDB) are focused on efficient storing and querying highly connected data. In practice they mostly use a (labelled) property graph model. Moreover, a native GDB can be any storage solution where connected elements are linked together without using an index (a property called index-free adjacency). The paper is focused on a simplified version of GDB considered as relational databases in which all relations are binary. For querying, path queries and union of path queries are considered. A path query is defined by a single positive integer \(k\). On a given database D, Q returns couples of nodes \((x,y)\) such that there is a path in D from \(x\) to \(y\) of length \(k\). A union of path queries is defined by a finite set of possible integers K. Q returns on D all the pairs of nodes \((x,y)\) that are connected by a path whose length belongs to K. A view specification is a set of such queries. The paper's content is divided into six sections. Section 1 presents informally the notion of view determinacy and some related works. In Section 2, the view determinacy is defined formally. In principle, a view specification \(\mathbf V\) determines a query Q if, for all databases D, the answers to \(\mathbf V\) on D contain enough information to answer Q. The determinacy problem is the problem of deciding, given \(\mathbf V\) and Q, whether \(\mathbf V\) determines Q. The author introduces a slightly weaker \(\alpha\)-asymptotic determinacy problem where we decide the determinacy problem for all queries that ask for a path longer than \(\alpha\). The \(\alpha\) is a fixed function that maps each view to a natural number. Section 3 provides some conditions on Q and \(\mathbf V\) that are necessary for \(\mathbf V\) to determine Q. This makes it possible to restate the asymptotic determinacy problem in a more intuitive way. Section 4 is focused on proving the main theorem of the paper: There exists an explicit and computable function \(\alpha\) for which the \(\alpha\)-asymptotic determinacy problem is decidable. Moreover, when the \(\mathbf V\) determines Q, the decision procedure effectively computes a first-order rewriting of Q using \(\mathbf V\). Section 5 discusses the issue how to move from \(\alpha\)-asymptotic determinacy to general determinacy. Also stronger views and stronger query languages are considered. Section 6 presents some conclusions. The paper is well structured and well written. It is completed by examples documenting the used notions. It gives a meaningful contribution to the theory of graph queries.