Implementation of a many-to-many relationship with total participation constraints in SQL
It's not easy to do in SQL but it is not impossible. If you want this enforced through DDL alone, the DBMS has to have implemented DEFERRABLE constraints. This could be done (and can be checked to work in Postgres, that has implemented them):

-- lets create first the 2 tables, A and B:
CREATE TABLE a 
( aid INT NOT NULL,
  bid INT NOT NULL,
  CONSTRAINT a_pk PRIMARY KEY (aid) 
 );

CREATE TABLE b 
( bid INT NOT NULL,
  aid INT NOT NULL,
  CONSTRAINT b_pk PRIMARY KEY (bid) 
 );

-- then table R:
CREATE TABLE r 
( aid INT NOT NULL,
  bid INT NOT NULL,
  CONSTRAINT r_pk PRIMARY KEY (aid, bid),
  CONSTRAINT a_r_fk FOREIGN KEY (aid) REFERENCES a,  
  CONSTRAINT b_r_fk FOREIGN KEY (bid) REFERENCES b
 );


Up to here is the "normal" design, where every A can be related to zero, one or many B and every B can be related to zero, one or many A.

The "total participation" restriction needs constraints in the reverse order (from A and B respectively, referencing R). Having FOREIGN KEY constraints in opposite directions (from X to Y and from Y to X) is forming a circle (a "chicken and egg" problem) and that's why we need one of them at least to be DEFERRABLE. In this case we have two circles (A -&gt; R -&gt; A and B -&gt; R -&gt; B so we need two deferrable constraints:

-- then we add the 2 constraints that enforce the "total participation":
ALTER TABLE a
  ADD CONSTRAINT r_a_fk FOREIGN KEY (aid, bid) REFERENCES r 
    DEFERRABLE INITIALLY DEFERRED ;

ALTER TABLE b
  ADD CONSTRAINT r_b_fk FOREIGN KEY (aid, bid) REFERENCES r 
    DEFERRABLE INITIALLY DEFERRED ;


Then we can test that we can insert data. Note that the INITIALLY DEFERRED is not needed. We could have defined the constraints as DEFERRABLE INITIALLY IMMEDIATE but then we'd have to use the SET CONSTRAINTS statement to defer them during the transaction. In every case though, we do need to insert into the tables in a single transaction:

-- insert data 
BEGIN TRANSACTION ;
    INSERT INTO a (aid, bid)
    VALUES
      (1, 1),    (2, 5),
      (3, 7),    (4, 1) ;

    INSERT INTO b (aid, bid)
    VALUES
      (1, 1),    (1, 2),
      (2, 3),    (2, 4),
      (2, 5),    (3, 6),
      (3, 7) ;

    INSERT INTO r (aid, bid)
    VALUES
      (1, 1),    (1, 2),
      (2, 3),    (2, 4),
      (2, 5),    (3, 6),
      (3, 7),    (4, 1),
      (4, 2),    (4, 7) ; 
 END ;


Tested at SQLfiddle.



If the DBMS does not have DEFERRABLE constraints, one workaround is to define the A (bid) and B (aid) columns as NULL. The INSERT procedures/statements will then have to first insert into A and B (putting nulls in bid and aid respectively), then insert into R and then update the null values above to the related not null values from R.

With this approach, the DBMS does not enforce the requirements by DDL alone but every INSERT (and UPDATE and DELETE and MERGE) procedure has to be considered and adjusted accordingly and users have to be restricted to use only them and not have direct write access to the tables. 

Having circles in the FOREIGN KEY constraints is not considered by many the best practice and for good reasons, complexity being one of them. With the second approach for example (with nullable columns), updating and deleting rows will still have to be done with extra code, depending on the DBMS. In SQL Server for example, you can't just put ON DELETE CASCADE because cascading updates and deletes are not allowed when there are FK circles. 

Please read also the answers at this related question:
How to have a one-to-many relationship with a privileged child? 



Another, 3rd approach (see my answer in the above mentioned question) is to remove the circular FKs completely. So, keeping the first part of the code (with tables A, B, R and foreign keys only from R to A and B) almost intact (actually simplifying it), we add another table for A to store the "must have one" related item from B. So, the A (bid) column moves to A_one (bid) The same is done for the reverse relationship from B to A:

CREATE TABLE a 
( aid INT NOT NULL,
  CONSTRAINT a_pk PRIMARY KEY (aid) 
 );

CREATE TABLE b 
( bid INT NOT NULL,
  CONSTRAINT b_pk PRIMARY KEY (bid) 
 );

-- then table R:
CREATE TABLE r 
( aid INT NOT NULL,
  bid INT NOT NULL,
  CONSTRAINT r_pk PRIMARY KEY (aid, bid),
  CONSTRAINT a_r_fk FOREIGN KEY (aid) REFERENCES a,  
  CONSTRAINT b_r_fk FOREIGN KEY (bid) REFERENCES b
 );

CREATE TABLE a_one 
( aid INT NOT NULL,
  bid INT NOT NULL,
  CONSTRAINT a_one_pk PRIMARY KEY (aid),
  CONSTRAINT r_a_fk FOREIGN KEY (aid, bid) REFERENCES r
 );

CREATE TABLE b_one
( bid INT NOT NULL,
  aid INT NOT NULL,
  CONSTRAINT b_one_pk PRIMARY KEY (bid),
  CONSTRAINT r_b_fk FOREIGN KEY (aid, bid) REFERENCES r
 );


The difference over the 1st and 2nd approach is that there are no circular FKs, so cascading updates and deletes will work just fine. The enforcement of "total participation" is not by DDL alone, as in 2nd approach, and has to be done by appropriate procedures (INSERT/UPDATE/DELETE/MERGE). A minor difference with the 2nd approach is that all the columns can be defined not nullable.



Another, 4th approach (see @Aaron Bertrand's answer in the above mentioned question) is to use filtered/partial unique indexes, if they are available in your DBMS (you'd need two of them, in R table, for this case). This is very similar to the 3rd approach, except that you won't need the 2 extra tables. The "total participation" constraint has still to be applied by code.