Det här är sannolikt alldeles för inaktuellt för att vara användbart, men jag kommer att skriva om det hjälper andra människor!
Jag lagrar oriktade grafer som ditt andra exempel och har en begränsning att nod_a måste vara mindre än node_b. Du placerar sedan trivialt en UNIQUE begränsning på paret och vet att data är konsekventa. Frågor måste arbeta lite mer genom att jämföra node_a med det minsta av {a,b} och node_b det andra värdet. PostgreSQL (den DB jag känner bäst) tillhandahåller GREATEST() och LEAST() funktioner som hjälper här.