A Multimedia Query Language And Its Query Processing

As a uniform query interface of multimedia database, a multimedia query language is one of the most essential components of multimedia database management system; present multimedia query languages, however, are either designed for one medium or specialized for a particular application, thus inapplicable in multimedia database system. Hence, it is significant to design a powerful general-purpose multimedia query language and study its internal query processing.Focusing on a multimedia query language and its query processing, the following six parts of work have been conducted, including how to design a multimedia query language and its internal query algebra, how to compile a query of this language and generate an equivalent query plan, how to optimize and implement a query plan, and, how to design and implement a prototype system.By analysis of multimedia query requirements, sixteen rules as the criteria that should be satisfied by a good multimedia query language are generalized. According as these rules and based on a semi-structured data organization model, a unified multimedia query language called UMQL is designed, which can support querying familiar multimedia types. Then we use the sixteen design rules mentioned above to analyze and compare UMQL and other multimedia query languages. Results show that, compared with other multimedia query languages, UMQL not only has compact and effective syntax, but also has powerful ability on multimedia query specification, which allows users to query various multimedia data based on their content information such as structure, feature, and spatio-temporal relationship. Using Extended Backus-Naur Form and logic algebra, the syntactic rules and semantic rules specialized for UMQL are defined, and based on them, a UMQL grammar analyzer is designed so as to implement the correctness check of a UMQL query.To represent a UMQL query internally so as to simplify query internal processing and optimization, an internal query algebra called UMQA is proposed. UMQA includes such operators as join, structure selection, normal selection, feature selection, spatio-temporal selection and structure expansion, making UMQA equivalent with UMQL on multimedia query specification. UMQA also includes a complete set of operating formulas over these operators, i.e., equivalent translation formulas, which can ensure a UMQA plan always semantically correct in algebraic translation, and thus establish the foundation of query optimization. Moreover, a mapping algorithm from UMQL to UMQA is presented, which can generate an equivalent UMQA plan for any UMQL query.To optimize a UMQA plan so as to obtain better performance, it is required to study query optimization, mainly focusing on how to place selection operations in a query plan correctly. Based on the comprehensive consideration of selectivity and unit execution cost of each UMQA operation, a multimedia selection placement theory is presented and its algorithm is designed. It uses the equivalent translation formulas to translate a UMQA plan, making the query plan after optimization accordant with the above placement theory as much as possible. This algorithm has a polynomial time complexity, and the theory analysis and experiment result both show that, this algorithm can establish the optimal placement of each multimedia selection operation in a query plan, and thus improve the performance of a query plan effectively.To interpret and implement a UMQA plan so as to obtain multimedia data, it is required to study the efficient implementation of UMQA operators, mainly focusing on the efficient implementation of structure expansion, binary feature selection and binary spatio-temporal selection operators that all cannot solved by traditional methods. For the implementation of structure expansion, a code index scheme is first designed; then two implementation algorithms, one that does use the code index scheme and the other that does not, are given; and last the execution costs of both algorithms are compared and analyzed in theory. For binary selection, two implementation algorithms are given, where one is the improvement of the other, and then the execution cost of both algorithms are compared and analyzed in theory. Finally, the experiment results show that, all these implementation algorithms are feasible and applicable.Based on the above techniques, a prototype system of multimedia query language and its processing is designed and implemented, which provides a unified experiment platform and extension for the problem's research.