Jeg kan godt lide at bruge aggregering til dette med betinget aggregering. For eksempel til din første punkt:
select a.carid
from attributes a
group by a.carid
having sum( (attribute, value) in ( ('color', 'red'), ('color', 'blue') ) ) > 0 and
sum( (attribute, value) in ( ('wheels', '2') ) > 0;
> 0
betyder, at kombinationen attribut/værdi eksisterer. Brug = 0
for at angive, at det ikke virker.