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	Key-to-value mapping	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.

record UserId(String value) {}

Set<UserId> users = new HashSet<>();
users.add(new UserId("u-17"));

boolean found = 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 their fields are modified after insertion into the equals/hashCode, the element may remain in the bucket but fail to be found using either the old or new values.

"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

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

SELECT role FROM user_roles;

If ten users all have viewer, the result might contain ten instances of viewer. Only DISTINCT explicitly removes duplicates.

Similarly:

SELECT role FROM team_a
UNION
SELECT role FROM team_b;

UNION performs deduplication, while UNION ALL preserves duplicates. Preserving duplicates often avoids the cost of sorting or hashing to eliminate redundancy, when business logic doesn't require set semantics, it's better to express the actual requirements.

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.

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 the relevant 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.

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 overrides." When the system includes resource scopes, conditional authorization, or time-bound validity, a simple set-based model becomes insufficient, more complex relational or attribute-based decision models may be required. 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.

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.

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