PostgreSQL constraint using prefixes

Question

Let's say I have the following PostgreSQL table:

id | key
---+--------
1  | 'a.b.c'

I need to prevent inserting records with a key that is a prefix of another key. For example, I should be able to insert:

• 'a.b.b'

But the following keys should not be accepted:

• 'a.b'
• 'a.b.c'
• 'a.b.c.d'

Is there a way to achieve this - either by a constraint or by a locking mechanism (check the existance before inserting)?

Answer 1

This solution is based on PostgreSQL user-defined operators and exclusion constraints (base syntax, more details).

NOTE: more testing shows this solution does not work (yet). See bottom.

1. Create a function has_common_prefix(text,text) which will calculate logically what you need. Mark the function as IMMUTABLE.

   CREATE OR REPLACE FUNCTION
   has_common_prefix(text,text)
   RETURNS boolean
   IMMUTABLE STRICT
   LANGUAGE SQL AS $$
     SELECT position ($1 in $2) = 1 OR position ($2 in $1) = 1
   $$;
   

2. Create an operator for the index

   CREATE OPERATOR <~> (
     PROCEDURE = has_common_prefix,
     LEFTARG   = text,
     RIGHTARG  = text,
     COMMUTATOR = <~>
   );
   

3. Create exclusion constraint

   CREATE TABLE keys ( key text );
   
   ALTER TABLE keys
     ADD CONSTRAINT keys_cannot_have_common_prefix
     EXCLUDE ( key WITH <~> ); 
   

However, the last point produces this error:

    ERROR:  operator <~>(text,text) is not a member of operator family "text_ops"
    DETAIL:  The exclusion operator must be related to the index operator class for the constraint.

This is because to create an index PostgreSQL needs logical operators to be bound with physical indexing methods, via entities calles "operator classes". So we need to provide that logic:

CREATE OR REPLACE FUNCTION keycmp(text,text)
RETURNS integer IMMUTABLE STRICT
LANGUAGE SQL AS $$
  SELECT CASE
    WHEN $1 = $2 OR position ($1 in $2) = 1 OR position ($2 in $1) = 1 THEN 0
    WHEN $1 < $2 THEN -1
    ELSE 1
  END
$$;

CREATE OPERATOR CLASS key_ops FOR TYPE text USING btree AS
  OPERATOR 3 <~> (text, text),
  FUNCTION 1 keycmp (text, text)
;

ALTER TABLE keys
  ADD CONSTRAINT keys_cannot_have_common_prefix
  EXCLUDE ( key key_ops WITH <~> );

Now, it works:

INSERT INTO keys SELECT 'ara';
INSERT 0 1
INSERT INTO keys SELECT 'arka';
INSERT 0 1
INSERT INTO keys SELECT 'barka';
INSERT 0 1
INSERT INTO keys SELECT 'arak';
psql:test.sql:44: ERROR:  conflicting key value violates exclusion constraint "keys_cannot_have_common_prefix"
DETAIL:  Key (key)=(arak) conflicts with existing key (key)=(ara).
INSERT INTO keys SELECT 'bark';
psql:test.sql:45: ERROR:  conflicting key value violates exclusion constraint "keys_cannot_have_common_prefix"
DETAIL:  Key (key)=(bark) conflicts with existing key (key)=(barka).

NOTE: more testing shows this solution does not work yet: The last INSERT should fail.

INSERT INTO keys SELECT 'a';
INSERT 0 1
INSERT INTO keys SELECT 'ac';
ERROR:  conflicting key value violates exclusion constraint "keys_cannot_have_common_prefix"
DETAIL:  Key (key)=(ac) conflicts with existing key (key)=(a).
INSERT INTO keys SELECT 'ab';
INSERT 0 1