As more information sources become available in multimedia systems, the development of multimedia database management systems (MDBMSs) to efficiently model and search multimedia data, especially video data, becomes very crucial for multimedia applications. In response to such a demand, a probabilistic-based mechanism called the Markov Model Mediator (MMM) to facilitate an MDBMS for video database systems is presented. In our previous studies, the spatial relations of the semantic objects in the image/video data modeled by the MMM mechanism are assumed given by image processing/computer vision techniques or by human annotations. In this paper, an unsupervised video segmentation method that can identify objects with their corresponding spatial relations automatically is incorporated into the MMM mechanism. Based on the information obtained, users can retrieve video materials from video databases via database queries. Hence, both multimedia data modeling and image processing capabilities are integrated into the MMM mechanism.