Now you have me wondering if, for any given database containing nulls, there is an equivalent normalized schema that represents the same information without nulls - for example, if you have a Student table with a Date of Graduation attribute that might be null, use instead an additional table of Graduated Students. It looks to me like there might be some tricky corner cases in defining 'equivalent' (you cannot query the second database for students with null graduation dates, but you can query for those without graduation dates.)

If so, then the follow-up question is whether there is a three-valued logic that always gives the same result as a particular null-free representation (my guess is yes and no, respectively.)