Composite key as foreign key of multiple tables

You have couple options. I'd describe one I like the most, but you can find others searching for 'resolving polymorphic association in database'. Add a common table for companies and contacts (I'd prefer to rename contacts to people or persons), say party. Thus, companies and contacts will have FK to party. Then you add link table party_address(address_id,party_id) with FKs to addresses and party respectively.

UPDATE For instance (I know it's oversimplified, normally you may have different address_type, address change history, etc, but I guess it illustrates idea).

Note: enum is used because mysql still doesn't have check constraints. Unique constraint on (party_id, party_type) added so child tables can have a foreign key references to it; thus, optional relationship implemented and enforced on database level- Party can be either Person or Organization; no way it can be Person and Organization at the same time.

  CREATE TABLE PARTY (party_id int not null auto_increment primary key,
party_type enum('person','organization') not null,
CONSTRAINT UQ_PARTY UNIQUE(party_id,party_type));

CREATE TABLE PERSON (party_id int not null primary key, 
party_type enum('person') NOT NULL DEFAULT 'person',
....
CONSTRAINT FK_PERSON_PARTY FOREIGN KEY(party_id,party_type) 
 REFERENCES PARTY(party_id,party_type));

CREATE TABLE ORGANIZATION (party_id int not null primary key, 
party_type enum('organization') NOT NULL DEFAULT 'organization',
....
CONSTRAINT FK_PERSON_PARTY FOREIGN KEY(party_id,party_type) 
 REFERENCES PARTY(party_id,party_type));

CREATE TABLE ADDRESS(address_id INT NOT NULL auto_increment PRIMARY KEY,
.... );

CREATE TABLE PARTY_ADDRESS (party_id INT NOT NULL, address_id INT NOT NULL,
CONSTRAINT PK_PARTY_ADDRESS PRIMARY KEY(party_id,address_id),
CONSTRAINT FK_PARTY_ADDRESS_PARTY FOREIGN KEY (party_id) REFERENCES PARTY(party_id),
CONSTRAINT FK_PARTY_ADDRESS_ADDRESS FOREIGN KEY (address_id) REFERENCES ADDRESS(address_id));

The benefits of using a surrogate key (that's your newly created single field), in my opinion, outweigh the downsides in most cases.

But there are a few cases that you may experience some drawbacks.

Think of a company's employees that work different shifts on different days of the week. Here's a simplified database:

SHIFT(ShiftID, Shift, SomeOtherColumn);
EMPLOYEE(EmployeeID, FirstName, LastName);
[TRANSACTION](TransactionID, ShiftID, EmployeeID, Date);

So, as constructed, we've created a surrogate key for each table. If we need to, say, find out what shift correspond to a particular shiftID from a particular transactionID, we'd have to run a second query. That's the downside of using a surrogate key in that case.

If the fields Shift and SomeOtherColumn from the SHIFT table can be assumed to be a candidate key (a composite primary key, in other words), then we would have to declare both fields in the our FOREIGN KEYconstraint DDL when we created the [TRANSACTION] table. So, we would be able to directly query the actual Shift from the [TRANSACTION] table without having to run an additional query.

Another issue with using a catch-all surrogate key is that it has no intrinsic value. So, if you work for a larger organization, but there are different databases (in other departments, for examples) that refer to the same items with different primary keys (surrogate keys), you may have a bit of an issue if you have join their data regularly.

Ditto for the developer who has 2 or 3 apps, maintains a different user database for each, with a different surrogate ID for each user but may have a ton of duplicate users between them.

Personally, I go on a case by case basis, but lean toward using a surrogate key more unless there is an outstanding reason I should not.