CREATE TABLE locations (
   locID int unsigned not null,
   ....
   PRIMARY KEY(locID)
) ENGINE=InnoDB;

CREATE TABLE companies (
   compID int unsigned not null,
   ....
   PRIMARY KEY (compID)
) ENGINE=InnoDB;

CREATE TABLE company_location (
   locID int unsigned not null,
   compID int unsigned not null,
   FOREIGN KEY (locID) REFERENCES locations (locID)
      ON UPDATE CASCADE
      ON DELETE CASCADE,
   FOREIGN KEY (compID) REFERENCES companies (compID)
      ON UPDATE CASCADE
      ON DELETE CASCADE
) ENGINE=InnoDB;

CREATE TABLE contacts (
   contID int unsigned not null,
   ....
   PRIMARY KEY (contID)
) ENGINE=InnoDB;

CREATE TABLE contact_location (
   contID int unsigned not null,
   locID int unsigned not null,
   FOREIGN KEY (locID) REFERENCES locations (locID)
      ON UPDATE CASCADE
      ON DELETE CASCADE,
   FOREIGN KEY (contID) REFERENCES contacts (contID)
      ON UPDATE CASCADE
      ON DELETE CASCADE
) ENGINE=InnoDB;

CREATE TABLE contact_company (
   contID int unsigned not null,
   compID int unsigned not null,
   FOREIGN KEY (compID) REFERENCES company (compID)
      ON UPDATE CASCADE
      ON DELETE CASCADE,
   FOREIGN KEY (contID) REFERENCES contacts (contID)
      ON UPDATE CASCADE
      ON DELETE CASCADE
) ENGINE=InnoDB;