3

I am creating an application with one server node and multiple clients. Each client holds a set of strings, that will be stored in their own local database.

Once a day, all clients will send all their data to the server. The server will calculate the sum of all clients' sets, and then calculate the difference between this total set and each client's.

Small example:

Client1 has {1, 2, 3}

Client2 has {1, 2}

Client3 has {1, 3}

Client4 has {}

They send it to the server, that calculates Client1 + Client2 + Client3 + Client4 = {1, 2, 3} and server persists this result in it's own database.

Then server calculates difference.

Client1 lacks {}

Client2 lacks {3}

Client3 lacks {2}

Client4 lacks {1, 2, 3}

As those set of strings are going to be quite big, I would like to choose a database (SQL or NoSQL), that will be able to optimize those two operations.

Application is written in Spring Boot and will run on Ubuntu. Database needs to be open source. I also need full-text-search. In future there may be multiple server nodes, and they should be at least "eventually consistent".

1

In maths terminology the summed set calculated at the server is called the union. The comparison between the server's set and each client's is called the difference or relative complement.

It is simple enough to write these so any combination of programming language and persistence layer would suffice. However, relational databases are build on set theory and have built-in functionality for precisely these operations, so it makes sense to use one. I have a copy of SQL Server to hand so I'll use it's syntax. Postgres will support this schema and algorithm. MySQL has work-arounds.

Define the upload table thus

create table dbo.Upload
(
  ClientNumber  int          not NULL,  -- change the type to match your needs
  StringValue   varchar(99)  not NULL,  -- whatever type and length is appropriate
);

I'm treating this as a staging table that will be emptied at the end of each day. If it must retain history add the appropriate key columns. I will define a table to hold the server-calculated superset, though this could be a view or function or equivalent.

create table dbo.Superset
(
  StringValue  varchar(99)  not NULL
);

And a list of all clients so I can process ones that send no rows.

create table dbo.Client
(
  ClientNumber  int  not NULL
);
insert dbo.Client(ClientNumber) values (1), (2), (3), (4);

The end-of-day process runs and uploads the clients' data into the staging table

insert dbo.Upload(ClientNumber, StringValue)
values (1, '1'), (1, '2'), (1, '3');

insert dbo.Upload(ClientNumber, StringValue)
values (2, '1'), (2, '2');

insert dbo.Upload(ClientNumber, StringValue)
values (3, '1'), (3, '3');

-- Client 4 sends no rows.

Since I put all the clients' rows in a single table there is no need to union them. We just need to retrieve the unique values

insert dbo.Superset(StringValue)
select distinct
  StringValue
from dbo.Upload;

select * from dbo.Superset;  -- just to check

StringValue
-----------
1
2
3

In SQL the difference operation is performed using the EXCEPT keyword.

select
  c.ClientNumber,
  v.StringValue
from dbo.Client as c  -- read from the reference table so even clients which sent no values are reported.
outer apply           -- executes the sub-query once per outer row i.e. per Client
(
  select              -- read the superset
    ss.StringValue 
  from dbo.Superset as ss

  except              -- remove those rows..

  select
    StringValue
  from dbo.Upload as u
  where u.ClientNumber = c.ClientNumber  -- .. which were sent by the current row in the outer query (Client).
) as v
order by
  ClientNumber,
  StringValue;

ClientNumber StringValue
------------ -----------
1            NULL         -- NULL since client 1 sent everyting

2            3

3            2

4            1            -- Client4 was absent from Upload but is still reported
4            2
4            3

If the correlated sub-query is too tricky executing the sub-query in a cursor would do the same job.

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.