Why am I getting `Impossible WHERE noticed after reading const tables` in explain query?
You are getting the message


  Impossible WHERE noticed after reading const tables


This is documented in the page you already linked.


  MySQL has read all const (and system) tables and notice that the WHERE clause is always false


const tables are defined as


  The table has at most one matching row, which is read at the start of
  the query.  ... const is used when you compare all parts of a PRIMARY KEY or UNIQUE
  index to constant values.


You have a UNIQUE KEY on  (fromid,toid). The query on WHERE fromid=78 AND toid=60 can be satisfied by reading this unique index. From the message you are getting this must return no results.

Similarly the query WHERE fromid=60 and toid=78 AND (is_approved='s'  OR is_approved='f' OR is_approved='t') can also use this index to locate the row of interest (though it still has a residual predicate to evaluate were any row to match).

Your other query is different

SELECT rid
FROM   relationship
WHERE  fromid = 60
       AND toid = 78
       AND is_approved = 's'
        OR is_approved = 'f'
        OR is_approved = 't' 


AND has a higher precedence than Or, so this is the same as 

SELECT rid
FROM   relationship
WHERE  ( ( fromid = 60 ) AND ( toid = 78 ) AND ( is_approved = 's' ) )
        OR ( is_approved = 'f' )
        OR ( is_approved = 't' ) 


This can no longer use that index and has different semantics in that it will return any rows where is_approved IN ('f','t') irrespective of what the values in the other columns are.