MS-Similarity: Let dist be a tuple distance function on a relation R, and t be a maximum distance threshold, and x and y be two tuples in R, we then say that x is type MS-similar (Multimedia Stream Similar) to y with respect to dist, denoted x =dist= y iff x and y belongs to the same window, and dist(x,y) =< t.

Type-MS Functional Dependency: Let R be a relation with attribute set U, and X, Y are subsets of U. X<sub>g1(t`)</sub> --> Y<sub>g2(t``)</sub> is a type-MS functional dependency (MSFD) relation iff for any two tuples t1 and t2 in R, if t1[X] =g1(t`)= t1[X], then t1[Y] =g2(t``)= t2[Y], where t` and t`` are similarity thresholds, and ti[X] is the projection of the tuple ti over the set of attributes X, and similarly is ti[Y].