Natural joins are defined, in a semantically correct way, on data structures, called I-tables, of an extended relational database model with indefinite and maybe information. An algorithm for computing natural joins under the extended model is proposed which reduces the number of pair-up operations and block accesses to a linear order of complexity with respect to the size of I-tables. Procedures for the extended natural joins are examined with respect to efficiency, which is evaluated based upon the number of pair-up operations and I/O block accesses. A linear order of pair-up operations is achieved by using the 'compare, concatenate, and then permute' strategy, and a linear order of I/O activities is attained by employing virtual relations with pointers.>