Es probable que esto esté demasiado desactualizado para ser útil, ¡pero lo publicaré en caso de que ayude a otras personas!
Almaceno gráficos no dirigidos como su segundo ejemplo y tengo la restricción de que node_a tiene que ser menor que node_b. Luego colocas trivialmente un UNIQUE restricción en el par y saber que los datos son consistentes. Las consultas tienen que funcionar un poco más al comparar node_a con el menor de {a,b} y node_b con el otro valor. PostgreSQL (la base de datos que mejor conozco) proporciona GREATEST() y LEAST() funciones que ayudan aquí.
