2.3 Sets in Software Systems: Data Structures, SQL, and Approximate Membership Queries

Mathematical sets have only membership, no order or duplicates. In software, List, Set, database result sets, and cache filters each carry their own semantics. Calling them all "sets" obscures issues like duplicates, nulls, equality, and false positives.

Choose the Right Abstraction

Abstraction	Order Preservation	Duplicate Handling	Typical Question
Set	Not part of semantics	Not retained	Is an element part of the set?
Sequence / List	Retained	Retained	What is the nth element?
Multiset / Bag	Typically not concerned	Tracks frequency	How many times does a value appear?
Map	Implementation-dependent; not required by the abstraction	Keys are unique	What value corresponds to a given key?

Items in an order are typically sequences or multisets, not ordinary sets: buying two identical items should not reduce to one due to deduplication. User permissions that only care about "whether they have access" are better modeled as sets.

Program Collection Equality Protocol

In mathematics, equality of elements is defined by a given model. Hash sets, however, require an implementation-level protocol: equal elements must produce consistent hash values, and any fields that influence equality or hashing during key operations must remain unchanged.

Save this complete example as SetDemo.java, then run javac SetDemo.java and java SetDemo with JDK 21. It prints true:

import java.util.HashSet;
import java.util.Set;

public class SetDemo {
    record UserId(String value) {}

    public static void main(String[] args) {
        Set<UserId> users = new HashSet<>();
        users.add(new UserId("u-17"));
        System.out.println(users.contains(new UserId("u-17"))); // true
    }
}

Java records provide value-based equality semantics derived from their components, making them well-suited for such identifiers. If mutable objects are used as HashSet elements and fields participating in equals/hashCode are modified after insertion, the element may remain in the bucket but fail to be found using either the old or new values.

Here the component is an immutable String. Records do not recursively freeze components: lists may remain mutable, and default equality for array components is not elementwise equality. A tree collection’s comparator must also match the intended equality semantics. See Java Record and the Set contract.

"The set elements must be hashable" is not a universal mathematical rule across languages. Tree sets can rely on total ordering, bit sets on integer indexing, and linear implementations may even require only equality checks. The requirements stem from the underlying implementation strategy.

Complexity Must Be Considered in Context

A typical hash set, when well-distributed and properly resized, offers average constant-time membership queries; worst-case performance and specific guarantees depend on the actual implementation. Balanced tree sets generally provide logarithmic query times while maintaining sorted order. Bitmaps enable fast set operations like union and intersection through bitwise operations in compact integer domains.

When choosing a data structure, consider:

• The number of elements and key distribution;
• Whether stable ordering or range queries are needed;
• Memory constraints;
• The cost of equality and hashing operations;
• Concurrency read/write protocols;
• Whether persistence or cross-process serialization is required.

Do not assume that because an API is named Set, all operations are O(1).

SQL Defaults Often Follow Bag Semantics

Run the SQL below in order in a fresh PostgreSQL or DuckDB session. These temporary synthetic tables supply every later query:

CREATE TEMP TABLE user_roles(user_id VARCHAR, role VARCHAR);
INSERT INTO user_roles VALUES ('u1', 'viewer'), ('u2', 'viewer'), ('u2', 'admin');
CREATE TEMP TABLE team_a AS SELECT role FROM user_roles;
CREATE TEMP TABLE team_b(role VARCHAR);
INSERT INTO team_b VALUES ('viewer'), ('viewer');
CREATE TEMP TABLE users(id VARCHAR PRIMARY KEY);
INSERT INTO users VALUES ('u1'), ('u2'), ('u3');
CREATE TEMP TABLE purchases(user_id VARCHAR);
INSERT INTO purchases VALUES ('u1'), (NULL);

Relational models are built on sets, but SQL query results typically allow duplicate rows:

SELECT role FROM user_roles;

The query returns three rows, including viewer twice. SELECT DISTINCT role FROM user_roles deduplicates by role, yielding viewer and admin. Stable output order requires an explicit ORDER BY.

Similarly:

SELECT role FROM team_a
UNION
SELECT role FROM team_b;

UNION performs deduplication, while UNION ALL preserves duplicates. Preserving duplicates often avoids sorting or hashing for deduplication. Choose the form that matches the required result.

Here UNION yields two distinct roles; UNION ALL retains five rows. During duplicate elimination, DISTINCT and UNION also merge nulls in corresponding positions. That does not make the comparison NULL = NULL true.

An INNER JOIN can be understood as a Cartesian product filtered by a predicate:

R ⋈_condition S = {pair ∈ R×S | condition(pair)}

Yet in SQL, duplicate rows and NULL cause the result count to diverge from pure set intuition. Relational algebra provides a foundational model for understanding queries, but it should not override the actual semantics of SQL.

Outer joins also add null-extended rows for unmatched inputs, so the filtering expression does not fully describe LEFT JOIN.

NOT IN and NULL Pitfalls

Objective: Identify users with no purchase history.

SELECT u.id
FROM users u
WHERE u.id NOT IN (SELECT p.user_id FROM purchases p);

If a subquery might produce NULL, SQL three-valued logic will make the comparison result become UNKNOWN, potentially returning no rows at all. A more reliable approach is usually to use a correlated NOT EXISTS.

SELECT u.id
FROM users u
WHERE NOT EXISTS (
  SELECT 1
  FROM purchases p
  WHERE p.user_id = u.id
);

The specific execution plan should still be determined by the database optimizer and indexes; semantic correctness is a prerequisite before optimization.

For this data, NOT IN returns no rows, while NOT EXISTS returns u2 and u3. The outer users.id is a non-null primary key. If outer IDs can also be null, define the intended behavior rather than assuming unconditional equivalence.

Review Permissions with Set Algebra

Definition:

Direct(u)       User's direct permissions
Roles(u)        Set of roles assigned to the user
Granted(role)   Permissions granted to a role
Denied(u)       Explicitly denied permissions

A strategy is defined as:

Effective(u)
= (Direct(u) ∪ ⋃_{r∈Roles(u)} Granted(r)) \ Denied(u)

This formula explicitly enforces deny precedence. Resource scopes, conditional grants, and validity periods can require relations or decisions based on attributes beyond a flat permission set. Do not force complex ABAC policies into flat strings of permission sets.

Bloom Filter Represents an Approximate Membership Relation

When dealing with large sets and the primary goal is to quickly determine whether an element definitely does not exist, a Bloom Filter is a suitable choice. Elements are inserted by applying multiple hash functions to set positions in a bit array. During queries, the same positions are checked:

Any bit is 0 → the element was not inserted
All bits are 1 → the element may have been inserted

A standard Bloom Filter allows false positives: it reports "possibly present" even when the element is actually absent. Under the correct assumptions (only insertions, no deletions, and proper implementation) it never produces false negatives.

This Python 3 example uses eight bits and two position functions chosen for easy arithmetic. It first produces a false positive, then shows why clearing bits is not a safe deletion operation:

bits = [False] * 8

def positions(value):
    return (value % 8, (value // 8 + value) % 8)

def insert(value):
    for pos in positions(value):
        bits[pos] = True

def maybe_contains(value):
    return all(bits[pos] for pos in positions(value))

insert(1)
insert(2)
print(maybe_contains(1), maybe_contains(9), maybe_contains(3))
# True True False: 9 has not been inserted.

insert(9)
for pos in positions(1):
    bits[pos] = False  # Deliberately unsafe attempt to delete 1.
print(maybe_contains(9))  # False, although 9 was inserted. Do not delete this way.

Value 1 uses (1,1), 2 uses (2,2), and the absent 9 uses (1,2), so both its positions are already set. After actually inserting 9, clearing the bits for 1 breaks the shared position and loses 9. These deliberately simple, correlated position functions cannot estimate production false-positive rates.

It is not a precise mathematical set alternative:

• It cannot enumerate all elements;
• Standard versions do not support safe deletion;
• The false positive rate depends on the size of the bit array, the number of hash functions, and the number of inserted elements;
• Inconsistencies in hashing or persistence compromise the guarantees.

To defend against cache penetration, you can first check a Bloom Filter. However, if the filter reports "possibly present," a real storage lookup is still required. Treating an approximate structure as an authoritative source would incorrectly allow unauthorized users, making it unsuitable for security-critical decisions.

The no-false-negative guarantee concerns elements fully inserted into the filter. If storage gains a record before the filter is updated, or rebuilding omits records, the system can still reject real data. Updates, recovery, and version changes must preserve coverage. Configure capacity, error targets, and growth for the actual implementation. See Redis’s Bloom filter documentation; this example uses no Redis service.

Types Can Be Understood Through Set Semantics, But Not Entirely

Thinking of types as sets of allowed values is very helpful: integer types correspond to value ranges, subtype relationships resemble set inclusion, and union types resemble set unions. However, real languages also involve:

• Operations and behaviors, rather than value sets alone;
• null, exceptions, non-termination, and other semantic aspects;
• Mutability and type variance;
• Nominal type identity;
• Runtime representations and undefined behaviors.

Thus, "types are sets" is a semantic model, not a complete definition of all type system details.

Completion Check

Choose among Set, List, Multiset, Map, or an approximate structure for each of the following data scenarios, and explain your reasoning:

1. Shopping cart item lines;
2. User permissions;
3. Log event sequence order;
4. Word frequency counts;
5. Pre-filtering of one billion crawled URLs;
6. Unique task IDs queried within a time range.

Write a SQL query to return "users belonging to a project but not frozen," and explain how duplicate rows and NULL might affect the result.

References

• PostgreSQL: Combining Queries
• PostgreSQL: Comparison Functions and Operators