Eu gosto de usar agregação para isso com agregação condicional. Por exemplo, para seu primeiro marcador:
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;
O
> 0 significa que a combinação atributo/valor existe. Usar = 0 para especificar que não funciona. 
