Skip the theory and see how Answer Set Programming helps you analyze real-world query complexity in systems such as Firestore. Dive in and build tools, not just theorems.
Rather than diving into yet another textbook explanation of Disjunctive Normal Form (DNF), let's explore this through concrete examples. While many explanations focus on formal definitions and theory, we'll take a hands-on approach using Answer Set Programming (ASP) to understand how DNF applies to real-world query systems like Firestore.By modeling DNF transformations as a constraint satisfaction problem, we can move beyond abstract mathematical notation to gain practical insights into query complexity and validation. This isn't just about understanding the rules — it's about building tools to automatically analyze and validate complex queries against system limitations.
Simple DNF
Disjunctive Normal Form (DNF) is a way to express logical formulas using OR and AND. Just like the FOIL method from algebra class (remember "First, Outer, Inner, Last" when multiplying (a + b)(c + d)?), we'll distribute terms to get a standard form.Let's look at some examples:
a OR b: Already in DNF - simple terms connected by OR.
(a AND b) OR c: Also in DNF - an AND group and a simple term connected by OR.
a AND (b OR c): Not in DNF - the OR is trapped inside an AND.To fix this, distribute a across (b OR c):
(a AND b) OR (a AND c)
(a OR b) AND (c OR d): Not in DNF - just like FOIL, we need to multiply these terms:
(a AND c) OR (a AND d) OR (b AND c) OR (b AND d)
The key is that when we're done:
OR operations must be at the outer level
AND operations must be contained within the OR terms
Each term contains only simple predicates joined by AND
DNF by Example
Let's start with a simple database-like query:Find employees who are in Sales AND have either high performance OR 5+ years experienceIn logical form: sales AND (performance OR years)To convert this to DNF, we distribute sales across the OR:(sales AND performance) OR (sales AND years) Now let's look at another example:Find employees who are either (in Sales AND have high performance) OR (in Marketing AND work remotely)This is already in DNF:(sales AND performance) OR (marketing AND remote)Why? Because each OR term contains its own AND group - we don't need to distribute anything.
Counting DNF Terms with ASP
While converting to DNF by hand is straightforward for simple cases, real-world queries can get complex quickly. Let's use ASP to mechanically count the number of disjunctive terms that would appear in a query's DNF form.
Basic Structure
First, we need to represent our query structure. We'll use a tree where:
Leaf nodes are simple predicates (like database WHERE clauses)
Internal nodes are either AND or OR operations
Each node knows its parent to maintain the tree structure
With our tree structure in place, we can now tackle the core challenge: counting how many terms will appear in the DNF expansion without actually performing the expansion. While this counting mechanism might seem abstract, it forms the foundation for validating complex queries in systems like Firestore, which impose limits on query complexity. By encoding query structure as a tree and tracking how terms combine, we can automatically analyze whether queries will exceed system limitations.The key insight is that the number of DNF terms follows simple multiplication / addition rules:
root((1, 0)) .
and_node((1, 0), 2, 3) . % Top AND
or_node((2, 1), 4, 5) . % A OR B
where((3, 1), ("C", "=", 1)) . % C
where((4, 2), ("A", "=", 1)) . % A
where((5, 2), ("B", "=", 1)) . % B
This yields 2 (
{result(2)}
) DNF terms: (A AND C) OR (B AND C).
Pathological Case
Now for something more challenging. Consider this nested monstrosity:
(A OR (B AND (C OR D))) AND ((E OR F) OR (G AND (H OR I)))
{
(1,"AND")
(2,"OR")
(4,("A","=",1))
(5,"AND")
(6,("B","=",1))
(7,"OR")
(8,("C","=",1))
(9,("D","=",1))
(3,"OR")
(10,"OR")
(12,("E","=",1))
(13,("F","=",1))
(11,"AND")
(14,("G","=",1))
(15,"OR")
(16,("H","=",1))
(17,("I","=",1))
}
This is where manual counting becomes error-prone. Let's encode it in ASP:
root((1, 0)) .
and_node((1, 0), 2, 3). % Top level AND
% Left side: A OR (B AND (C OR D))
or_node((2, 1), 4, 5) . % A OR (...)
and_node((5, 2), 6, 7) . % B AND (...)
or_node((7, 5), 8, 9) . % C OR D
% Right side: (E OR F) OR (G AND (H OR I))
or_node((3, 1), 10, 11) . % (...) OR (...)
or_node((10, 3), 12, 13) . % E OR F
and_node((11, 3), 14, 15) . % G AND (...)
or_node((15, 11), 16, 17) . % H OR I
% Leaf nodes (simplified for clarity)
where((4, 2), ("A", "=", 1)) .
where((6, 5), ("B", "=", 1)) .
where((8, 7), ("C", "=", 1)) .
where((9, 7), ("D", "=", 1)) .
where((12, 10), ("E", "=", 1)) .
where((13, 10), ("F", "=", 1)) .
where((14, 11), ("G", "=", 1)) .
where((16, 15), ("H", "=", 1)) .
where((17, 15), ("I", "=", 1)) .
Running this through our counter yields 12 (
{result(12)}
) disjunctive terms!
From Counting to Constraints
While counting DNF terms helps us understand query complexity, real-world systems such as Firestore care about more than just the number of terms. They also impose constraints on what can appear within each disjunctive term. Two key constraints are:
Maximum one array-contains clause per disjunction
Cannot combine array-contains with array-contains-any in same disjunction
Rather than checking these constraints after DNF expansion (which could be expensive), we can extend our ASP model to track operator usage through the query tree. The key insight is that operator counts in disjunctive terms follow the same pattern as our DNF term counting:
OR nodes take the maximum count from their children (since each disjunctive term comes from one branch)
AND nodes sum their children's counts (since operators from both branches appear in the same term)
By grouping operators that can't coexist, we can use a single counting mechanism to enforce both types of constraints:
OR case: OR nodes take the maximum count from their children since each disjunctive term comes from exactly one branch of the OR. This reflects that when we expand to DNF, each term follows only one path through OR nodes:
AND case: AND nodes sum their children's counts since operators from both branches appear together in the resulting disjunctive terms. When we expand to DNF, all conditions joined by AND must appear in the same term:
Now that we can count DNF terms, let's tackle a real-world challenge: Firestore's constraints on array operations within disjunctive terms.
Example: Mixed Operators
Let's analyze a query that combines array operations with regular clauses in a non-DNF structure:Find items that are either tagged as "urgent" OR have "active" status, AND are categorized as "work"In logical form: ( (tags ARRAY-CONTAINS "urgent") OR (status == "active") ) AND (categories ARRAY-CONTAINS "work")
{
(1,"AND")
(2,"OR")
(4,("tags","array-contains","urgent"))
(5,("status","==","active"))
(3,("categories","array-contains","work"))
}
root((1, 0)) .
and_node((1, 0), 2, 3) . % Top AND
or_node((2, 1), 4, 5) . % Left side OR
where((4, 2), ("tags", "array-contains", "urgent")) . % First array-contains
where((5, 2), ("status", "==", "active")) . % Regular clause
where((3, 1), ("categories", "array-contains", "work")) . % Second array-contains
When expanded to DNF, this becomes:
( (tags ARRAY-CONTAINS "urgent") AND (categories ARRAY-CONTAINS "work") )
OR ( (status == "active") AND (categories ARRAY-CONTAINS "work") )
Our operator counting mechanism results in
{
result_group_count/2
"array-contains"
2
"array-ops"
2
}
, revealing that the first disjunctive term would contain two array-contains operations (tags and categories). This violates Firestore's constraint of "at most one array-contains per disjunction."
Beyond Theory: ASP in Practice
Our journey through DNF wasn't just about converting logical formulas — it revealed how Answer Set Programming turns theoretical concepts into practical tools. Rather than manually expanding complex queries (and likely making mistakes), we've built a mechanical way to:
Count disjunctive terms without explicit expansion
Track operator usage across query branches
Validate constraints within logical groupings
The power comes from ASP's declarative approach. We specify what makes a valid query rather than how to check it. The solver handles all the complex bookkeeping, letting us focus on expressing the rules correctly.
Application: Firestore Query Validation
This mechanical analysis becomes immediately practical when working with Firestore, which imposes specific limits on query complexity:
Maximum 30 disjunctions in DNF form
At most one array-contains per disjunction
No mixing of certain array operators
Our ASP model validates all these constraints simultaneously without requiring manual query expansion. Even complex queries that combine multiple OR conditions with array operations can be automatically checked for validity. For a complete guide to modeling and validating Firestore queries with ASP, see Firestore Queries.Rather than trying to juggle these rules in your head while writing queries, let ASP handle the verification. The same principles we used for DNF counting extend naturally to checking Firestore's array operation constraints.Now back to your regularly scheduled Firestore documentation!
Appendix: ASP Validation Rules
When modeling complex query structures in ASP, we need to ensure our encoded queries are well-formed. Rather than discovering issues at runtime, we can use ASP's constraint checking to validate the structure as part of the model.
Node Types and Relationships
First, we establish what constitutes a valid node and define parent-child relationships:
Node IDs must be sequential starting from 1 to avoid gaps:
used_id(ID) ← node(ID) .
max_id(M) ← M = #max{ID : used_id(ID)} .
error(("Missing node ID ", ID, " (IDs must be sequential from 1)")) ←
max_id(M), ID = 1..M, not used_id(ID) .
Finally, we need to enforce that no errors exist in our query structure. While generating error messages is useful for debugging, we ultimately want to reject any query structure that violates our rules. This single constraint ensures that no solution will be accepted if it contains any validation errors:
⊥ ← error(_) .
This approach of separating error detection (generating meaningful messages) from error enforcement (rejecting invalid structures) gives us the best of both worlds - detailed feedback during development and strict validation in production.
Visualizing Query Trees
When working with complex query structures, visualization becomes essential for understanding and debugging. We can transform our internal representation into a visual tree format using labeled nodes that preserve both structure and identity:
% Create labeled nodes for visualization with IDs
node_label(ID, (ID, "AND")) ← and_node((ID,_),_,_) .
node_label(ID, (ID, "OR")) ← or_node((ID,_),_,_) .
node_label(ID, (ID, L)) ← where((ID,_),L) .
node_label(ID, (ID, "ROOT")) ← root((ID,_)) .
% Convert to parent木/2 format using node labels with IDs for visualization
parent木(L1, L2) ←
has_child(P, C),
node_label(P, L1),
node_label(C, L2) .
This transformation captures both the hierarchical relationships and the unique identity of each node, making it easier to track how complex queries combine and branch. The inclusion of node IDs ensures unambiguous visualization even when multiple nodes share similar properties.The result is a clear tree representation that helps bridge the gap between abstract query structure and concrete understanding — essential when working with nested combinations of AND/OR operations.
Your brain wasn't meant to juggle 47 database constraints at once. Here's how Answer Set Programming turns Firestore's query rules into executable logic.2 January 2025
A classic concurrency puzzle illustrating how simple individual actions can lead to complex system-level behavior. Through Answer Set Programming, we explore the interplay between resource management and synchronization.6 January 2025
