| The increase in popularity of XML (eXtensible Markup Language) which employs a tree structured model for representing and manipulating data, has led to an increased interest in tree data models. To query such a data model and get the results of the query many query languages have been developed. But one common thing about these query languages is they are expressed in the form of tree shaped search patterns. Querying an XML document using a tree patterned query is done by matching the tree pattern query (TPQ) with similar patterns in the actual XML document, and the final result set is constructed from the set of all matches found. Since the efficiency of the tree pattern matching depends on the size of the input pattern, it is essential to quickly identify and eliminate redundant nodes in the pattern and do so as efficiently as possible. In an attempt to achieve this goal, this paper concentrates on utilizing the constraints from the XML Document Type Definition (DTD), and creating a complete rule set, which encapsulates the constraints from DTD. The next step is to use these rules in the minimization of TPQ. For this purpose an algorithm called chase is modified to incorporate our rules in to the TPQ. To minimize the actual TPQ, we need to augment the TPQ initially, to incorporate the constraints of our rules. The augmentation phase is followed by minimization phase, which works on the augmented TPQ and obtains the minimized TPQ. |
