In the paper we investigate the following problem: characterize the class of programs over complex data structures stable under natural data structures transformations. We propose a solution based on the composition-nominative approach. According to this approach data structures are considered as nominative data structures and semantics of programs are presented using special program algebras with operations called compositions. We define various data transformations and specify a very general class of compositions based on effective definitional schemes by H. Friedman. We show that this class preserves program stability under natural data structures transformations. This result can be useful in software development and verification.