Toda tabela deve ter uma chave primária substituta/artificial de campo único?

Vou dizer que não, nem sempre, mas na maioria das vezes sim. .

Estas são algumas circunstâncias em que você não precisa de uma chave substituta ou artificial:

• Tabelas de interseção puras . Se não houver risco de a interseção ser o alvo de uma chave estrangeira e se houver pouco ou nenhum risco de a interseção atrair atributos independentes (ou seja, algo diferente de FK para as duas tabelas pai), você poderá usar a combinação de FKs como PK com razoável confiança.
• Tabelas de consulta com chaves de negócios estáticas . Se você tiver uma
  tabela de pesquisa com uma chave de negócios exclusiva que é fixada externamente ao seu
  negócio e que tem chance zero de mudar para qualquer
  finalidade prática, usar a chave de negócios diretamente pode tornar
  as coisas mais simples. Um exemplo pode ser uma lista de códigos de estado ou província
  ou uma lista de números padrão ANSI, etc.
• Tabelas contendo dados consolidados de várias fontes independentes . Se o seu sistema tiver muitas fontes de dados que devem ser agrupadas em uma única tabela, digamos na matriz, às vezes você precisará de uma chave composta que inclua o valor da chave do sistema de origem e um código indicando qual era o sistema de origem.

Há também algumas situações em que a antiga chave substituta de número inteiro crescente monotonicamente não é ideal. Você pode ter chaves que são substitutos alfanuméricos. Estes podem incluir:

• Situações em que você precisa mesclar dados de várias fontes independentes. Para evitar colisões de chaves, você pode usar GUIDs em vez de chaves IDENTITY.
• Situações em que você é forçado a usar representações de teclas não numéricas. Digamos que você tenha um banco de dados de placas. Sua chave pode ser o valor alfanumérico em vez de um número puro.
• Situações em que algum requisito externo força você a aplicar compactação ao seu valor de chave. Em vez de usar 10 dígitos para um int32, você pode usar seis dígitos de base 36.

Por que na maioria das vezes sim? A resposta mais fundamental para essa pergunta é que é um inferno se você precisar modificar um valor de chave primária em qualquer tabela. Como quase tudo que um usuário pode ver ou tocar está sujeito a uma atualização em algum momento, usar um valor de chave visível é convidar o inferno. Usar uma chave substituta evitará que você caia nessa armadilha.

Dito isso, lembre-se que há espaço para a YAGNI aplicar esse conceito. Você não precisa forçar tabelas de código com chaves de IDENTIDADE em todos os cantos do seu esquema, apenas no caso de alguém decidir que o símbolo de gênero masculino em sua tabela de funcionários precisa mudar de M para X ou algo bobo.

"depende"

Sim: os campos substitutos IDENTITY/AUTONUMBER são bons quando a chave natural é ampla e não numérica. Nota: isso pressupõe a fusão de "PK" e índice clusterizado que ocorre por padrão no SQL Server e Sybase, etc.

Não: muitas/muitas tabelas quando as 2 chaves pai são suficientes. Ou quando a chave natural é curta e de tamanho fixo, por exemplo, código da moeda

Claro, um ORM inteligente (leia-se: (n)Hibernate) pode superar essas regras...

Editar: lendo a pergunta novamente

Uma tabela muitos/muitos com 2 chaves pai substitutas terá uma coluna PK múltipla.
No entanto, não precisa de outra coluna substituta.

Se uma tabela tiver uma chave substituta (IDENTITY, etc.), ela não precisará ser de várias colunas.

Você pode ter uma superchave que inclua o substituto, mas isso seria para impor outras regras (por exemplo, subtipos )

Não.

Eu diria que certamente há casos em que as chaves de campo único são inferiores às chaves compostas, pelo menos para fins de chaves estrangeiras . Isso não quer dizer que você não deva ter uma chave substituta de campo único também, se preferir, mas eu pessoalmente prefiro que a chave que é usada com mais frequência como alvo de uma chave estrangeira seja chamada de chave primária

Vou tentar ilustrar meu ponto nos seguintes exemplos, nos quais:

• brandé marca de carro, por exemplo, Ford, Toyota etc
• dealeré uma concessionária física, vinculada a uma marca (por exemplo, uma concessionária Ford que vende apenas Fords)
• modelé o tipo de carro, por exemplo, Ford Focus, Ford Fiesta, etc.
• stocké a contagem atual de carros no pátio para cada concessionária

Se criarmos uma chave substituta de campo único para dealere modelda seguinte forma:

create table brand( brand_id integer primary key );

create table dealer( dealer_id integer primary key, 
                     brand_id integer references brand )

create table model( model_id integer primary key, 
                    brand_id integer references brand )

create table stock( model_id integer references model, 
                    dealer_id integer references dealer, 
                    quantity integer,
                      primary key(model_id, dealer_id) )

então é possível inserir uma linha stockque liga um Ford dealera um modelo "Toyota". Adicionar brand_id references branda stockapenas piora o problema. Por outro lado, se mantivermos a chave estrangeira como parte da chave primária da seguinte forma:

create table brand( brand_id integer primary key );

create table dealer( brand_id integer references brand, 
                     dealer_id integer, 
                       primary key(brand_id, dealer_id) )

create table model( brand_id integer references brand, 
                    model_id integer, 
                      primary key(brand_id, model_id) )

create table stock( brand_id integer, 
                    model_id integer, 
                    dealer_id integer, 
                    quantity integer,
                      primary key(brand_id, model_id, dealer_id),
                      foreign key(brand_id, model_id) references model,
                      foreign key(brand_id, dealer_id) references dealer )

agora, a regra de que as concessionárias "Ford" só podem estocar carros "Ford" é aplicada naturalmente pelo modelo.

Observe que no exemplo 'chaves compostas', dealer_idpode ou não ser único, de acordo com a preferência. Não precisa ser único (ou seja, uma chave alternativa), mas muito pouco se perde ao fazê-lo (talvez um pouco de espaço de armazenamento) e pode ser muito útil, então é assim que costumo configurá-lo, por exemplo:

create table dealer( brand_id integer references brand, 
                     dealer_id serial unique, 
                       primary key(brand_id, dealer_id) )