Primary key for link/junction table with time-dependent data
Assuming that:


every country has at most 1 leader in a given point in time (no overlaps).
there may be gaps in a country's leadership (if you don't want to allow that, change the scond constraint to prevtermend = termstart)
termstart &lt; termend, i.e. every term lasts at least 1 day (if that is not the case, you can alter the constraints below, either by making that &lt;= and/or converting the date columns to datetime.)
you want to enforce all these constraints declaratively.


then I think the following (rather complicated) way will do - by simulating a circular linked list for every country):

    CREATE TABLE country_leader (
      countryid integer unsigned NOT NULL,
      seqno integer NOT NULL,
      leaderid integer unsigned NOT NULL,
      termstart date NOT NULL,
      termend date NOT NULL,
      prevseqno integer NOT NULL,
      prevtermend date NOT NULL,
      PRIMARY KEY (countryid, seqno),
      UNIQUE (countryid, prevseqno),
      UNIQUE (countryid, seqno, termend),
      FOREIGN KEY (countryid) 
        REFERENCES country (countryid),
      FOREIGN KEY (leaderid) 
        REFERENCES politician (politicianid),
      FOREIGN KEY (countryid, prevseqno, prevtermend) 
        REFERENCES country_leader (countryid, seqno, termend),
      CHECK (termstart &lt; termend),
      CHECK (prevtermend &lt;= termstart OR seqno = 0),
      CHECK (prevseqno = seqno - 1 OR seqno = 0)
    );