Subset of Unordered Pairs of Distinct Primary Keys With Normalization I am currently in the process of designing a database. I have one table as follows:

CREATE TABLE Set (
    id INT PRIMARY KEY AUTO_INCREMENT,
    -- other values
);


Now I wish to create another table that will store unordered pairs of distinct primary keys from the Set table, without sacrificing normalization. My first idea was:

CREATE TABLE Pairs (
    id INT PRIMARY KEY AUTO_INCREMENT,
    valueone INT NOT NULL,
    valuetwo INT NOT NULL,
    -- Appropriate foreign key constraints for valueone and valuetwo
);


But this has the problem that I could store, for example the pair valueone=1, valuetwo=1 which I do not want as they are not distinct, or I could store either both or just one of valueone=1, valuetwo=2 and valuetwo=2,valueone=1 which (depending on how I interpret the data) would clearly be de-normalized. What is a natural, normalized way to store this fairly simple piece of information?
You can enforce, that valueone &lt; valuetwo. Unfortunately MySQL doesn't support check constraints with which this would be easy (You can define them, but they have no effect). You'd have to use triggers.

CREATE TRIGGER pairs_bi
               BEFORE INSERT
                      ON pairs
               FOR EACH ROW  
BEGIN
  IF new.valueone &gt;= new.valuetwo THEN
    SIGNAL SQLSTATE '45000'
           SET MESSAGE_TEXT = 'valueone &gt;= valuetwo';
  END IF;
END;

CREATE TRIGGER pairs_bu
               BEFORE UPDATE
                      ON pairs
               FOR EACH ROW  
BEGIN
  IF new.valueone &gt;= new.valuetwo THEN
    SIGNAL SQLSTATE '45000'
           SET MESSAGE_TEXT = 'valueone &gt;= valuetwo';
  END IF;
END;


To enforce uniqueness you can then use a unique constraint/index or, if it where me, I'd simply define the two columns as primary key.

ALTER TABLE pairs
            DROP id;

ALTER TABLE pairs
            ADD PRIMARY KEY (valueone,
                             valuetwo);


db&lt;>fiddle