O PostgreSQL pode ter uma restrição de exclusividade em elementos de matriz?

O caminho justo

Você pode querer reconsiderar a normalização seu esquema. Não é necessário que todos "juntem-se mesmo para a consulta mais simples" . Crie uma VIEW por isso.

A tabela poderia ficar assim:

CREATE TABLE hostname (
  hostname_id serial PRIMARY KEY
, host_id     int  REFERENCES host(host_id) ON UPDATE CASCADE ON DELETE CASCADE
, hostname    text UNIQUE
);

A chave primária substituta hostname_id é opcional . Eu prefiro ter um. No seu caso hostname pode ser a chave primária. Mas muitas operações são mais rápidas com um simples e pequeno integer chave. Crie uma restrição de chave estrangeira para vincular à tabela host .
Crie uma visualização como esta:

CREATE VIEW v_host AS
SELECT h.*
     , array_agg(hn.hostname) AS hostnames
--   , string_agg(hn.hostname, ', ') AS hostnames  -- text instead of array
FROM   host h
JOIN   hostname hn USING (host_id)
GROUP  BY h.host_id;   -- works in v9.1+

Começando com a página 9.1 , a chave primária no GROUP BY cobre todas as colunas dessa tabela no SELECT Lista. As notas de lançamento para a versão 9.1:

Permitir não GROUP BY colunas na lista de destino da consulta quando a chave primária é especificada no GROUP BY cláusula

As consultas podem usar a visualização como uma tabela. Pesquisar um nome de host será muito mais rápido assim:

SELECT *
FROM   host h
JOIN   hostname hn USING (host_id)
WHERE  hn.hostname = 'foobar';

No Postgres 9.2+ um índice de várias colunas seria ainda melhor se você pudesse obter uma varredura somente de índice fora disso:

CREATE INDEX hn_multi_idx ON hostname (hostname, host_id);

Começando com Postgres 9.3 , você pode usar uma MATERIALIZED VIEW , as circunstâncias permitirem. Especialmente se você lê com muito mais frequência do que escreve na mesa.

O lado negro (o que você realmente perguntou)

Se eu não conseguir convencê-lo do caminho correto, também ajudarei no lado sombrio. Eu sou flexível. :)

Aqui está uma demonstração de como impor a exclusividade de nomes de host. Eu uso uma tabela hostname para coletar nomes de host e um gatilho na tabela host para mantê-lo atualizado. Violações exclusivas geram uma exceção e abortam a operação.

CREATE TABLE host(hostnames text[]);
CREATE TABLE hostname(hostname text PRIMARY KEY);  --  pk enforces uniqueness

Função de gatilho:

CREATE OR REPLACE FUNCTION trg_host_insupdelbef()
  RETURNS trigger AS
$func$
BEGIN
-- split UPDATE into DELETE & INSERT
IF TG_OP = 'UPDATE' THEN
   IF OLD.hostnames IS DISTINCT FROM NEW.hostnames THEN  -- keep going
   ELSE RETURN NEW;  -- exit, nothing to do
   END IF;
END IF;

IF TG_OP IN ('DELETE', 'UPDATE') THEN
   DELETE FROM hostname h
   USING  unnest(OLD.hostnames) d(x)
   WHERE  h.hostname = d.x;

   IF TG_OP = 'DELETE' THEN RETURN OLD;  -- exit, we are done
   END IF;
END IF;

-- control only reaches here for INSERT or UPDATE (with actual changes)
INSERT INTO hostname(hostname)
SELECT h
FROM   unnest(NEW.hostnames) h;

RETURN NEW;
END
$func$ LANGUAGE plpgsql;

Acionar:

CREATE TRIGGER host_insupdelbef
BEFORE INSERT OR DELETE OR UPDATE OF hostnames ON host
FOR EACH ROW EXECUTE PROCEDURE trg_host_insupdelbef();

Fiddle SQL com execução de teste.

Use um índice GIN na coluna da matriz host.hostnames e operadores de matriz para trabalhar com isso:

Por que meu índice de array PostgreSQL não está sendo usado (Rails 4)?
Verifique se algum array de valores está presente em um array Postgres