Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data

arXiv:2606.11946 · cs.DB, cs.CC, cs.LG, cs.LO · Submitted 2026-06-10 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data".

Jane: The gist: Neuro-Relational Programs (NRPs) introduce a declarative query language for relational databases whose facts carry numeric vector embeddings, unifying relational reasoning and learnable neural components into a single formalism.

Tom: First, who's behind it and why it matters.

Title and authors: Tom: To start with the title itself, "Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data," it sets up the core idea that this is about making queries and neural computation work together on structured data. The authors are Arie Soeteman, Balder ten Cate, Maurice Funk, Benny Kimelfeld, Carsten Lutz, and Moritz Schönherr.

Jane: They’re essentially arguing that you don't need two separate systems—one for relational logic and one for neural computation—to do both tasks on structured data. This paper presents NRPs as the unified way to do it declaratively.

Lu: The key insight they are pushing is that traditional query languages already support designing graph-learning architectures if you just extend the database model to include these tuple embeddings, where each tuple gets a numeric vector.

Meng: So, instead of having a separate neural network layer that processes the data after it's retrieved, the way you join tables determines how those embeddings are combined, and projections determine how they are aggregated. That’s a huge shift in how you think about model design over relational data.

Lalam: The paper formalizes this by defining an NRP as a sequence of non-recursive Datalog-style rules that derive new embedded relations from existing ones using these vector operations, which is what gives it the structure of a query language.

Tom: So, we’ve seen that they are taking relational reasoning and learnable neural components and putting them into one single formalism through this NRP concept. That's the main mechanism they are describing in this paper.

The paper's summary: Jane: They summarize the idea by saying that an NRP operates over an embedded database where every fact has a numeric vector embedding, and it consists of a sequence of Datalog-style rules that derive new embedded relations. This means you can compute new relationships between data points just by applying these rules to the existing ones.

Lu: They clarify the context by mentioning that they are working in the context of Datalog, specifically looking at both provenance and probability annotation, which ties into probabilistic logic programming concepts like those in fifteen thirty sixty-two and one two twenty-five <ref:2606.11946#pg1>.

Meng: What’s interesting is that they aren't restricting themselves to fixed algebraic operations for the transformations and aggregations; they are using these numeric vectors rather than just simple scalar values. This allows them to capture more complex semantic relationships in a Euclidean space.

Lalam: They spend considerable work on how to compute these tuple embeddings so that semantic proximity translates into geometric closeness, which is different from just treating embeddings as raw data for efficient retrieval in vector database approaches forty-four <ref:2606.11946#pg1>.

Tom: So the summary emphasizes that they treat the embedding as a complementary representation of the tuples rather than just some kind of raw data you pull out later. That's a key difference they are highlighting.

The paper's improvements: Tom: Now, looking at what they suggest as improvements, one major thing is that this framework allows them to compute Boolean flat queries using a gated zero-ary NRP, which the authors say is equivalent to non-adaptive query algorithms. This means you can test for membership in a classical database very efficiently based on homomorphism counts.

Jane: That sounds practical for things like quickly checking if a specific pattern exists within a large dataset without having to run complex iterative processes, which is what makes it useful in classical databases.

Lu: Another improvement they point out is integrating the Deep Homomorphism Network, or DHN architecture, by translating monadic NRPs into DHNs. They claim these are strictly more expressive than standard Graph Neural Networks because they can capture structural patterns beyond just simple neighborhood aggregation.

Meng: If you can capture structure better than a GNN does, that means the model might be able to learn richer underlying patterns in the data, not just local connections. That’s something we need when dealing with complex systems at scale.

Lalam: They also discuss how they use the FOCQ formalism to define and compute flat queries over ordered databases using a declarative language where a query is defined in FOCQ if it can be computed by a simply-gated ReLU feed-forward neural network NRP.

Tom: And maybe the most structural improvement is their compositional expressiveness; they show that gated ReLU feed-forward NRPs over classical databases are closed under composition, which means you can chain these computations together in complex ways.

Conclusion: Jane: To wrap up, the main implication of this paper is that you get a unified declarative pipeline where relational computation and neural computation are interleaved seamlessly. This means designing graph-learning architectures becomes a natural extension of using traditional query languages with extended tuple embeddings.

Lu: The work suggests that this NRP framework provides a formal way to express these computations, linking them directly to formal logic through things like the FOCQ formalism.

Meng: From a deployment standpoint, I see the potential here in defining model structures declaratively rather than manually tweaking layers, though we still need to figure out how robust these new rules are under real traffic conditions at scale.

Lalam: I’m pretty sure the authors are confident because they show that this formalism can handle complex multi-stage computations through composition properties, and they linked it back to established logic programming concepts.

Tom: So, in summary, "Neuro-Relational Programs: Unifying Queries and Neural Computation over Structured Data" gives us a declarative language for relational data with embeddings that lets us interleave learning and querying. It’s a new way to think about how we build models on structured information.

University of Amsterdam · Leipzig University

cs.DB, cs.CC, cs.LG, cs.LO

Submitted: 2026-06-10

Updated: 2026-10-15

Comments: 55 pages; Accepted at PODS 2026

Journal ref: Proc. ACM Manag. Data 4(5) (PODS), Article 300, November 2026

DOI: 10.1145/3850135

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

Importance score: 78/100

The gist: The gist: Neuro-Relational Programs (NRPs) introduce a declarative query language for relational databases whose facts carry numeric vector embeddings, unifying relational reasoning and learnable

Key concepts

Neuro-Relational Programs (NRPs): A declarative language for databases where data facts are annotated with numeric vectors. NRPs allow users to define computations by combining relational operations (like joins) with neural operations (like aggregating embeddings) into a single, unified program.
Conjunction Rule: A rule structure used in NRPs that combines multiple conditions using an aggregation function and a combination function. This structure dictates how variables are linked across different facts to perform complex relational reasoning while managing the composition of their associated embeddings.
Transformation Rule: A rule type in NRPs that updates the numeric embeddings of individual database tuples. This update is performed by applying a differentiable map, typically a feed-forward neural network, enabling the embedding vectors to be learned during computation.

Terminology

Embeddings — 4× in this paper · explained in 2 episodes
GNNs — 1× in this paper · explained in 2 episodes
Graph Neural Networks (GNNs) — 1× in this paper · explained in 10 episodes

Summary

The gist: Neuro-Relational Programs (NRPs) introduce a declarative query language for relational databases whose facts carry numeric vector embeddings, unifying relational reasoning and learnable neural components into a single formalism.

Conceptual Framework of NRPs

NRPs operate over an embedded database where every fact is annotated with a numeric vector, its embedding. Conceptually, an NRP defines a computation in which embeddings are propagated and manipulated via relational operations. Specifically, NRPs use three types of rules corresponding to basic ways the relational structure guides neural computation:

**(1) A conjunction rule has the form R(x)⟨alpha⟩ ⇐o R1 (x1) ∧ · · · ∧ Rl (xl), where every variable in x appears in at least one xi, α: Bfin (R d) → R d is an aggregation function and o: R d1 × · · · × Rl → R d is a combination function. (2) A disjunction rule has the form R(x)⟨alpha⟩ ⇐ R1 (x) ∨ · · · ∨ Rl (x), where d1 = · · · = dl = d and α: Bfin (R d) → R d is an aggregation function. (3) A transformation rule updates the embeddings of individual tuples using a differentiable map such as a feed-forward neural network. The central contribution of this paper is a characterization of the expressive power of NRPs and of their relationship to existing logical and neural formalisms. Several previously studied formalisms arise naturally as syntactic restrictions of NRPs, including zero-ary NRPs capturing non-adaptive query algorithms, monadic NRPs capturing deep homomorphism networks, and restricted classes corresponding exactly to the logic FOCQ. Together, these results establish NRPs as a broad declarative framework for querying and neural computation over relational data.> 2, 5, 7> (see also page 5) >2, 7> (see also page 7) >3, 4> (see also page 4). This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved.> 3, 5> (see also page 5) >3, 4> (see also page 4). This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved. The authors argue that traditional query languages naturally support the design of graph-learning architectures once the relational model is extended with tuple embeddings, where each tuple is associated with a numeric vector. From this perspective, joins determine not only how tuples are combined, but also how their embeddings are composed, while projections determine how embeddings are aggregated. This yields a unified declarative pipeline in which relational and neural computation are interleaved.

Improvements for AI systems

Robust query execution via Gated NRPs: The improved system can compute Boolean flat queries by a gated zero-ary NRP, which is equivalent to non-adaptive query algorithms, enabling efficient membership testing in classical databases based on homomorphism counts, as established by Theorem 4.1.
Deep Homomorphism Network (DHN) architecture integration: The system can represent and execute complex neural architectures over relational data by translating monadic NRPs into DHNs, which are shown to be strictly more expressive than GNNs, allowing the model to capture structural patterns beyond simple neighborhood aggregation.
Expressive query language design: By leveraging the FOCQ formalism, the system can define and compute flat queries over ordered databases using a declarative query language where Q is defined in FOCQ iff Q is computed by a simply-gated ReLU-FFN-based NRP, linking neural computation directly to formal logic.
Compositional expressiveness: The system gains the ability to handle complex, multi-stage computations by leveraging the composition properties of NRPs, as shown in Corollary 6.6, allowing gated ReLU-FFN-based NRPs over classical databases are closed under composition.
Efficient query translation for unstructured data: For queries requiring higher arity or non-uniform aggregation, the system can utilize frontier guarded NRPs and translate them into monadic NRPs over row-id normalized databases, enabling the computation of "k-ary flat queries with k > 1 via a canonical translation described in Theorem 5.14."