Papers for

database designers

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.

Characterizing when certain logic theories have finite models

A characterization of the finite model property for $ω$-categorical theories

Abstract: A first-order theory $T$ has the {\em finite model property} if every first-order sentence that is implied by $T$ has a finite model. We give a characterization of when a complete $ω$-categorical theory $T$ has the finite model property. The characterization makes it possible to transfer stability theoretic results in [29] to certain classes of finite structures. This approach also gives information concerning properties that a sequence of finite ``base structures'' of ever larger size must have in order for its random expansions to a larger vocabulary to have a chance to satisfy a convergence law for first-order logic.

Mon 12 OctLogic in Computer Science
The gist
Some logical theories always have infinite examples, but others can be understood entirely through finite examples. This paper shows how to tell when a particular kind of logical theory, known for being well-behaved and unique in structure, guarantees that all its implied statements can be satisfied by finite models. By doing this, the authors provide a way to connect deep logical properties to patterns found in families of finite structures and their random expansions. This insight helps understand how larger and more complex finite structures might behave logically.
Open → 2610.16163v1

Unified notation resolves relationship label ambiguity in database diagrams

Look Here or Look Across: Unified Cardinality Constraints for N-ary Relationships

Abstract: A cardinality constraint written on an edge of an entity-relationship diagram admits two opposite readings. Under the reading used by UML and by Chen's original model, the label is read with the entity set on the same side of the relationship; under the reading used by standard database textbooks, it is read with the entity set on the opposite side. The two readings are exact opposites, so a reader who assumes the wrong one takes away the opposite of what the designer meant. For binary relationships the difficulty is confined to interpretation, because the two constraints a binary relationship set admits can both be drawn. For relationships among three or more entity sets the picture is worse: a ternary relationship set admits twelve cardinality constraints, and a diagram with three edges can carry at most three of them. This paper presents a notation, Card(R; p; q) = (lower, upper), that removes the ambiguity without taking a side in it, and that is not limited to one constraint per edge. We give the number of constraints an n-ary relationship set admits, show which of them a design determines without ever writing them down, and state two inference rules, decomposition and augmentation, that derive one constraint from another, together with the side conditions under which each is sound. We close with a worked case study that turns three business requirements into three explicit constraints and nine more that the design decides on its own.

Thu 1 OctDatabases
The gist
In diagrams that show how things relate in a database, labels on lines can be read two opposite ways, causing confusion. The authors show that the common ways to read these labels give completely different meanings, especially when more than two things are related. They propose a new way to write these labels to avoid confusion and handle complicated relationships involving many entities. They also explain how many constraints come from a relationship and how some can be logically inferred. To make this clear, they walk through an example from a business setting.
Open → 2610.02603v1

Deciding NP-complete problems on definable equality structures

Karp's NP-complete problems over first-order definable structures

Abstract: We determine the decidability of Karp's NP-complete problems on structures which are first-order definable over the theory of equality, also known as orbit-finite sets with atoms or nominal sets.

Tue 29 SeptComputational ComplexityLogic in Computer Science
The gist
This paper looks at a special kind of math problem called NP-complete problems, which are usually very hard to solve. The authors study these problems but only on structures that can be precisely described using simple logical rules about equality. They find out whether it's possible to decide these problems in that setting. This helps us understand where difficult problems might become easier or at least know when they can be solved.
Open → 2609.38436v1