1
$\begingroup$

Let's assume that there is a finite, continuous sequence, where the elements' value is a function of their index, i.e.:

an = f(n) where f is an arbitrary function

Is there a known such sequence where by applying a simple aggregate function (precisely sum, average, max, min) to the elements we can tell whether there is at least one item missing between the first and last element, and calculate which element it was (or even, which elements they were)?

E.g. is there a way to tell that "a1, a2, a4" misses a3 by only using the above, simple functions?

The actual problem is that I have a set of rows in an relational database table where independently running worker processes can issue inserts to. The rows represent batches of work, where each batch is part of the same set of work items. E.g.:

  • Batch 1: items 1-10
  • Batch 2: items 11-20
  • Batch 3: items 21-30

I'd like to be able check in the table whether all batches were done (i.e. all items processed) or there are batches missing (e.g. items 10-19 were not processed for some reason). Calculating e.g. the sum of a column of all rows in a database table is a simple and fast operation.

I'm a software developer who learned maths in his native language, not English, so forgive me if my terminology is inaccurate. Thank you in advance.

Edit:

The reason I'm looking for an approach different than something that just iterates over the items is that the number of batches can be potentially very big. Similarly it's not possible to use an approach that would create database rows for each batch at once (what would potentially mean creating thousands of rows e.g. when starting the work).

$\endgroup$
  • $\begingroup$ This sounds (for finite size "batches") like error-correcting codes, though the mathematics may not be as simple as required for your application. $\endgroup$ – hardmath Mar 30 '14 at 12:18
1
$\begingroup$

One simple-minded way to do this is by enumerating the items as powers of two:

  • Batch 1-10 gets numbered $2^0$ through $2^9$

  • Batch 11-20 gets numbered $2^{10}$ through $2^{19}$

  • Batch 21-30 gets numbered $2^{20}$ through $2^{29}$

The sum of the sequence of processed items in a batch then tells us everything about what was processed. The sum uniquely corresponds to the set of processed items, because the bits are all placed distinctly.

This approach is certainly used in many low-level applications, to make detection of the presence or absence of individual items/conditions easily checked.

$\endgroup$
  • $\begingroup$ Thank you for your answer. Very simple and straightforward solution. Since it's not needed to be able to tell if an individual work item was processed, just a whole batch, this is possible with a bit sequence as long as the number of batches. $\endgroup$ – Piedone Mar 30 '14 at 19:17
0
$\begingroup$

I would let the database server do the work. If you have (say) 25 batches, create 25 dummy batch records and take the complement to the working batches, (i.e., everything in the dummy set that is not in the working set.) I would do the same for the items---create one dummy set of items for a completed batch and again take the completment against all working batches. I have flagged this thread so it can be transferred to a programming site.

$\endgroup$
  • $\begingroup$ Thank you for you answer. I edited the question to clarify why in the first place I'm looking for a solution that's not a straightforward one. $\endgroup$ – Piedone Mar 30 '14 at 18:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.