Abstract: In temporal databases, besides the storage redundancy and update abnormity associated with temporal functional dependencies, there also exist those associated with temporal multi-valued dependencies. In the strong totally ordered temporal scheme with temporal functional dependencies and regular temporal multi-valued dependencies constraints, the solution of the membership problem is essential to design an effective scheme decomposition algorithm. However, in the strong totally ordered temporal scheme, the introduction of multiple time granularities makes it more difficult to solve the membership problem. The concepts of attribute sets’ mixed closure on a certain temporal type, attribute sets’ mixed closure, attribute sets’ mixed dependency base on a certain temporal type and attribute sets’ mixed dependency base in strong totally ordered temporal scheme are proposed. The algorithms of attribute sets’ mixed closure, attribute sets’ mixed dependency base and the membership problem of temporal functional dependencies and regular temporal multi-valued dependencies in strong totally ordered temporal scheme are proposed. The algorithms’ termination and correction are proved and their complexities are discussed. These algorithms are the basis of further normalization of strong totally ordered temporal scheme.