Feature Request: Add `expand` method to explicitly set new difference values in `Collections`

[HarukiMoriarty]

Is your feature request related to a problem? Please describe.

I'm currently using differential-dataflow (0.15.2) as part of a Datalog-based query engine. In our logic-oriented context, we frequently need to explicitly set difference values for records independently of their original differences.

Specifically, two scenarios arise frequently:

• Set-difference queries (e.g., A - B): explicitly setting differences to +1 or -1 for tuples in the computation.
• Exact counting (cardinality): where original differences must be ignored, and each tuple must explicitly be assigned a difference of exactly 1.

Currently, the built-in method explode multiplies provided differences by the original tuple's differences, which does not match our intended semantics when original differences vary.

Describe the solution you'd like

I'd like to propose adding a method named expand, which explicitly sets new differences, independent of original tuple differences:

/// Replaces each record explicitly with another, with a specified difference type.
///
/// Unlike `explode`, the new difference is not multiplied by the original difference.
pub fn expand<D2, R2, I, L>(&self, mut logic: L) -> Collection<G, D2, R2>
where
    D2: Data,
    R2: Semigroup + 'static,
    I: IntoIterator<Item = (D2, R2)>,
    L: FnMut(D) -> I + 'static,
{
    self.inner
        .flat_map(move |(x, t, _)| logic(x).into_iter().map(move |(x, d2)| (x, t.clone(), d2)))
        .as_collection()
}

Describe alternatives you've considered

1. Using the built-in explode method: Not suitable, as it multiplies differences.
2. Using custom patches: Currently, we've patched our local version, but we'd prefer an official method in differential-dataflow for clarity, correctness, and ease of maintenance.

Additional context

A concrete Datalog-based example illustrating the need for expand:

// Represents Datalog's negation operation: Out(x) :- A(x), not B(x)
let difference = A.expand(|x| Some((x, 1)))
                  .concat(&B.expand(|x| Some((x, -1))))
                  .threshold_semigroup(|_, _, old| old.is_none().then_some(semiring_one()));

This clearly expresses "tuples in A but not in B," assigning explicit differences independent of original values, and can't be directly and correctly implemented with explode.

I believe this method is simple, intuitive, and complementary to the existing methods (map, flat_map, explode). I'd appreciate your consideration of this addition.

Thank you very much!

[frankmcsherry]

Thank you for the issue! I have questions!

I see an immediate challenge with the proposed implementation, which is that it seems to ignore retractions. In your example

// Represents Datalog's negation operation: Out(x) :- A(x), not B(x)
let difference = A.expand(|x| Some((x, 1)))
                  .concat(&B.expand(|x| Some((x, -1))))
                  .threshold_semigroup(|_, _, old| old.is_none().then_some(semiring_one()));

If I introduce facts to A and B the thing you want happens. But if you remove facts from A or B, what happens is probably incorrect: each retraction in A (with a negative difference) is converted to an insertion (positive difference), and similarly with B: retractions are treated as further insertions (rather than having the negative values multiply, become a positive, and counteract the previous negative B values).

If you would like to do set difference queries, specifically A - B, I would recommend exactly

B.negate().concat(&A).threshold(...)

This will negate B, add to A, and then with the correct ... retain the strictly positive values. It will continue to contain this even if you retract records from A or B.

It sounds like you've considered this but rejected it, but I can't understand why yet. I did not understand

... which does not match our intended semantics when original differences vary.

I'm also not clear on the "exact counting" application. Counting happens a lot in differential dataflow, and we haven't needed a new operator for it yet. We usually use the .count() operator, specifically. The part where you say

... where original differences must be ignored, and each tuple must explicitly be assigned a difference of exactly 1.

isn't clear; why would you ignore the original differences, especially if you want to maintain the count as the input changes (e.g. with negative differences indicating a retraction, and decrement of the count)?

Q1: The expand operator does not appear to preserve the property that if you consolidate its input at any time and then apply the operator logic, you will have the same result as consolidating its output; do you agree?

Q2: What prevents the proposed set negation logic (or using antijoin(B.distinct())) from correctly implementing set negation including under arbitrary input retractions?

Q3: What prevents .count() from correctly counting things?

Q4: Am I missing something else about your intended uses?

[HarukiMoriarty]

Hi, sorry for the confusion and I really appreciate your thoughtful questions. Let me answer one by one:

Q1: Yes, I agree.

Q2: Yes, the antijoin(B.distinct()) approach should work correctly for set negation under arbitrary input retractions — as long as the semiring supports negation (i.e., implements the Abelian trait). However, we currently use the PRESENT semiring, which does not support negation. This prevents us from using antijoin() and requires us to emulate set difference manually using expand + concat + threshold_semigroup.

Q3: Similarly, .count() does not behave as expected under PRESENT, since it represents logical presence rather than numeric summation. It collapses multiple occurrences into one and cannot track true counts. To use .count() meaningfully for cardinality, the semiring must support true addition (e.g., isize). Therefore, .count() isn't suitable in our current setup with the PRESENT semiring.

Q4: That leads me to a broader question — since PRESENT is attractive for Datalog-style set semantics and performance, is there a principled way to support operations like set difference or counting within the PRESENT framework, or is it fundamentally necessary to switch to a more expressive semiring like isize? I'd love to hear your thoughts on whether there's room to support such functionality without giving up the simplicity and benefits of PRESENT.

I have to admit I'm not very familiar with Differential Dataflow and may have some misunderstandings. I'd really appreciate it if you could share any insights or guidance. Thank you very much!

[frankmcsherry]

What I'm hearing is that you like using Present, which makes sense, but you'd also like to change the semigroup so that you can do other things, like negation or aggregation? My immediate read there is that you might want the count_core() operator, which remaps from any input semigroup to any output semigroup. The count() operator is the specialization of this to isize, which might also be useful for you.

The main concern I have with your operator proposal is that it doesn't uphold some key properties that all other differential operators uphold, mainly that they act as if on functions from (key, val) to members of the semigroup, independent of the physical representation of the collection, and specifically independent of whether the input has been fully consolidated. For example, we might have the input updates

((key, val), time, Present),
((key, val), time, Present)`

which because Present + Present = Present is equivalent to the consolidated collection

((key, val), time, Present),

Your proposed operator will distinguish between these two, giving a count of two in the first case and a count of one in the second.

I can imagine that you are in a situation where you may not be too bothered by this, perhaps just after a distinct() operator that ensures the data are consolidated. You might also not love count_core() because it is stateful, and you happen to know (correctly) that consolidated output can be subjected to your operator and the result will be correct for you. The distinct() operator is already doing the stateful work that count_core() would re-do.

My disposition, at the moment, is that you should probably keep the function as part of your project, as it seems to only be correct to apply in some contexts, and one needs to know what these are. It's by design that this is meant to be easy (you can add whatever functions you want to collections; you aren't required to use only differential's operators). For example, the dogsdogsdogs subproject has several operators that don't make sense in the larger differential space, and need to be held correctly to function properly. They are useful, but also held apart from core differential because of the necessary operating instructions.

Let me know if this all checks out, and especially if I have missed something important to you!

[HarukiMoriarty]

Thanks a lot for the detailed explanation — that really helps clarify things!

It makes sense to keep this function within our project, since it doesn't preserve differential's invariants more broadly.

Appreciate your guidance. Thanks again!