Fast Determination of Ancestor-Descendant Relationships using Bit Patterns

摘要

As XML is now a standard for data exchange and representation on the Internet, querying of these structures is becoming more and more important. Several languages now exist for this purpose, many of which rely on what is known as a structural join. Structural joins are used to determine structural relationship (specifically, ancestor-descendant and parent-child relationships) between XML elements, which is necessary for evaluating queries. Because these types of relationships can be numerous, an efficient method for their identification is an important task. In this paper, a new method for identifying ancestor-descendant and parent-child relationships is introduced. The technique is based on a numbering scheme which embeds structural information within XML nodes, encoded as bits. This scheme is fast and memory efficient, because of the compactness of bit representation and hardware/software support for their fast processing. Comparisons between the presented method and another commonly used technique support this conclusion.