Eu tenho uma tabela com quatro colunas que são todas não anuláveis, e os dados são tais que todas as quatro são necessárias para distinguir um registro único. Isso significa que, se eu fosse criar uma chave primária, ela precisaria abranger todas as colunas. As consultas na tabela quase sempre serão para recuperar um único registro, ou seja, todas as colunas serão filtradas na consulta.
Como todas as colunas precisarão ser pesquisadas, ter uma chave primária me beneficia (além de impor a exclusividade dos registros)?
No seu caso, esses campos são chaves naturais .
Chaves substitutas x chaves naturais para chave primária
Prefiro adicionar uma chave substituta para separar o gerenciamento do modelo de negócios e do banco de dados. Outra questão é usar índices clusterizados e não clusterizados na chave primária.
Geralmente é recomendado que você tenha uma chave substituta em tais situações, então chaves estrangeiras em outras tabelas (e quaisquer referências de registro que possam ser armazenadas externamente, como se fossem carregadas em query strings onde uma requisição http(s) refere-se a uma dos registros) têm algo a que se referir que não mudará se os dados na linha mudarem. Se você fizer isso, essa será sua chave primária.
Se você não adicionar essa chave substituta, considerando como você descreve os dados que estão sendo acessados, ter todas as quatro colunas como a chave primária não seria uma desvantagem. Se você tornar a chave o índice clusterizado da tabela, isso ajudará essas solicitações, pois haverá um nível na árvore b no disco para descer para localizar os dados de uma determinada linha.
Chaves compostas como chaves primárias também apresentam problemas de tamanho de índice que podem afetar o uso do disco, velocidades de io e backups. Você pode querer revisar as postagens de Kimberly Tripp sobre chaves primárias e índices clusterizados aqui: http://www.sqlskills.com/BLOGS/KIMBERLY/post/The-Clustered-Index-Debate-again!.aspx
Eu também sugeriria uma chave substituta neste caso, em vez de uma chave natural.
Se você tiver uma tabela representando um relacionamento muitos-para-muitos com apenas 2 colunas, parece razoável.
Cf. esta pergunta SO
Mas admito que adiciono chaves substitutas mesmo nesses casos.