Papers for

database architects

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Finite dependence profiles reveal structure in symmetry based data sets

Finite Dependence and Invariance Hierarchies for Finitely Supported Structures

Abstract: Finite support indicates that the dependence is limited, but not how each finite context controls what can be observed. For a data symmetry G \leq Sym(A) and a finitely supported G-set X, we study the finite-dependence profile X^S = {x : Fix_G(S) fixes x}, indexed by finite contexts S \subseteq A. For relations on A^n this yields Boolean algebras B^{(n)}_{G,S} = Inv_n(Fix_G(S)), forming the invariance hierarchy. The hierarchy separates several nominal principles. Its meet law is the relation-algebra form of the Bojanczyk-Klin-Lasota least-support criterion, while level injectivity is fungibility. The independent join law governs composition across unions of contexts; it holds for locally oligomorphic automorphism groups of ultrahomogeneous structures in purely relational languages of arity at most two, but can fail for unary observations over ternary data. Freshness remains valid sort by sort, and its unrestricted some/any form characterizes full equality symmetry among closed groups. With least supports, orbit-finiteness implies finite context levels and a uniform support bound; under local oligomorphicity the converse also holds. Pointwise closure does not change the profile, and standard atomic-site presentations show that suitable ultrahomogeneous structures with the same age have equivalent action topoi, even though their material FSS universes may retain different external cardinal data. Contextual orientability gives a complementary pointed invariant whose threshold is the least support size of choice from unordered pairs. For countable omega-categorical structures with degenerate algebraic closure, the meet law is equivalent to weak elimination of imaginaries.

Mon 14 SeptLogic in Computer Science
The gist
This work looks at how information depends on limited parts of data that has symmetry, like when certain rearrangements do not change what you see. The authors analyze how the context of a small data subset controls what can be observed, forming a hierarchy of ways data can stay the same under these symmetries. They find connections to principles about minimal information needed to support elements in data and how certain symmetries behave in relational structures. Their study helps clarify complex relationships among dependencies, supports, and invariances in structured data.
Open 2609.15879v1