2

Suppose I have a table

create table log (id serial, logged_at timestamp, event_type integer)

Can I efficiently (without making every row writable only once or by some special user) ensure that ∄ (r1, r2) ∈ log X log (r1.id > r2.id ∧ r2.logged_at > r1.logged_at)

So events in log partially ordered by time and we can always have total order via monotonically increasing sequence.

8
  • By constraint, do you mean a declarative constraint or would you be ok with a trigger validating modifications to the table? Aug 23, 2019 at 19:30
  • Why do you need that? Why isn't the ordering imposed by the timestamp enough? Aug 23, 2019 at 21:39
  • @a_horse_with_no_name timestamp do not impose total order. Do I need to elaborate on that more? Aug 24, 2019 at 8:32
  • @Lennart I would consider using trigger as 'inefficient', but If you think it can be O(1) operation I would like to hear about that. Aug 24, 2019 at 8:33
  • Anything concerning more than the current row can hardly be O(1), declarative or not. A primary key constraint is normally O(log(n)) for example Aug 24, 2019 at 9:26

2 Answers 2

1

Some assumptions, it is not allowed to manipulate the log, so I'll just handle the insert. id in itself is monotonically increasing, so what need to check is whether there exists a ts bigger than the current ts:

create or replace function validate_total_order() 
returns trigger as $$                                                                              
begin 
    if exists ( select 1 from log where logged_at > NEW.logged_at ) then 
        raise exception 'some message...'; 
    end if; 
    return new; 
end; 
$$ language plpgsql;

create trigger validate_total_order 
before insert on log 
for each row 
    execute procedure validate_total_order();

with an index on logged_at, it should be reasonable fast.

1

This sounds like an occurrence of: can the database enforce constraints across rows? (I assume that the X sign in the formula means "such that")

As a general rule, the answer is no, because when a row is being modified by a transaction, the state of the other rows is always uncertain due to possible modifications by not-yet-committed concurrent transactions.

An application may handle this correctly by implementing an adequate locking strategy preventing concurrent writes, or checking the constraint at the serializable isolation level, but that does not prevent a random session to just issue an UPDATE in the table without these safety measures, that would potentially result in quietly violating the constraint.

There are few kinds of table-level constraints that the SQL engine knows how to enforce, like unique constraints and exclusion constraints, but your formula doesn't look like an expression that could be used by such constraints.

3
  • Is it possible that X be a cartesian product?
    – 48347
    Aug 24, 2019 at 12:21
  • Like ∄ (r1, r2) ∈ log X log meaning there is no such (r1, r2) pair belonging to the cartesian product of log and log.
    – 48347
    Aug 24, 2019 at 12:29
  • That's exactly the case. I even used unicode symbol for product I believe. Not an X letter. Aug 24, 2019 at 16:23

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.