É provável que isso esteja desatualizado demais para ser útil, mas postarei caso ajude outras pessoas!

Eu armazeno gráficos não direcionados como seu segundo exemplo e tenho uma restrição de que node_a deve ser menor que node_b. Você então coloca trivialmente um UNIQUE restrição no par e saber que os dados são consistentes. As consultas têm um pouco mais de trabalho comparando node_a com o menor de {a,b} e node_b o outro valor. PostgreSQL (o banco de dados que conheço melhor) fornece GREATEST() e LEAST() funções que ajudam aqui.