Should many to many tables have a primary key?

I agree with everything Oded said except

"It can't reasonably be used as a foreign key either."

In this case it's a pick your poison, the mapping table absolutely can be a parent, it's just a matter of the child using a multicolumn FK or not.

Take a simple case of Car and color. Each Year Auto Makers have a certain pallet of colors and each model only comes in limited number of those colors. Many - Many :: Colors to Cars models

So now design the Order table where new cars orders are stored. Clearly Color and Model will be on the Order table. If you make a FK to each of those tables, the database will permit an incorrect model/color combination to be selected. (Of course you can enforce this with code, you can't do so declaratively.) If you make the parent be the many:many table, you'll only get combinations that have been specified.

SO would you rather have a multicolumn FK and point to a PK built on both ModelID and ColorID or do you want a single column FK?

Pick your poison.

EDIT

But if it's not a parent of something, no table needs a surrogate key.

I have done it both ways. Sometimes it is beneficial for adding a feature down the road. For instance, if there was ever a time that a row in the table would ever contain anything more than just the 2 id's. If you don't lack space I would put one in there just because it can't hurt. Sometimes it can interfere with ORM tools like hibernate or ADO.NET but that is minor.

So to sum it up... PROS 1. Allows potential future growth.

CONS 1. Space 2. Confuses some ORM tools.

Such a surrogate key adds nothing except overhead.

Use the natural keys, make them a composite primary key if you care about duplication in this table.

To expand:

In the application, this key will be meaningless and will remain unused.

In the database, it will have no function, as you can't reasonably use it in a query for any type of meaningful result.

It can't reasonably be used as a foreign key either.

If the table tracking the many to many relationship has it's own primary key and that key is used as a foreign key anywhere else in the database then you create a dependency on that relationship. The relationship can never be removed.

For instance in the car color example, if the color for a car is ever discontinued (removed from the many to many relationship table) then any table (i.e. purchase history) referencing the primary key would be broken.