# US 2004/0083209 A1 · Query processing method for searching XML data

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2004/0083209 A1
- Document ID: US20040083209A1
- Status: Published application
- Kind: A1
- Application number: 10/641,084
- Filed: 2003-08-15
- Published: 2004-04-29
- Earliest claimed: 2002-10-23
- Assignees: Samsung Electronics Co., Ltd.
- Inventors: Hyoseop Shin
- Web page: https://patentgrep.com/patent/US20040083209A1

## CPC

- G06F 16/835: Query processing
- G06F 16/83: Querying
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)

## Abstract

The present invention relates to a query processing method for searching XML data by which performance of XML query processing can be improved by equivalence class and a path expression reduction algorithm. The query processing method of the present invention includes a step of checking duplication of nodes found while an input XML document is parsed to reconstruct the XML document, storing other nodes, from which duplicated nodes checked in the checking step are excluded, in the form of an additional tree structure, and when a user inputs a query for XML data search, converting a path expression in the input query into the shortest path expression while traversing the tree structure.

## Claims

### Claim 1

A method of processing a query for searching XML data, comprising the steps of:
checking duplication of nodes found while an input XML document is parsed to reconstruct the input XML document;
storing nodes other than duplicated nodes checked in the checking step, said storing performed as a tree structure; and
converting a path expression in an input query into a shortest path expression while traversing the tree structure when a user inputs the query for an XML data search.

### Claim 2 (depends on 1)

The method as claimed in claim 1, wherein shared or recursive nodes are not included in the tree structure, and only one child node is registered in the tree structure when a parent node has a plurality of child nodes that have corresponding names that are identical with respect to each other.

### Claim 3 (depends on 1)

The method as claimed in claim 1, wherein the shortest path expression is a set of nodes belonging to a same equivalence class in the tree structure.

### Claim 4 (depends on 1)

The method as claimed in claim 1, wherein a path expression P in the query is represented as P=A1N1 A2N2 . . . AkNk and is classified into a Head section, an AiNi section, and a Tail section when a length of the path expression is k, and AN denotes <axis-node> pairs for the path expression P.

### Claim 5 (depends on 4)

The method as claimed in claim 4, wherein the AiNi section denotes first to i-th <axis-node> pairs for the path expression P, the Head section is a part in which reduction has been made among lists of the <axis-node> pairs located before the AiNi section, and the Tail section is a part in which the reduction has not yet been made among lists of the <axis-node> pairs located after the AiNi section.

### Claim 6 (depends on 4)

The method as claimed in claim 4, further comprising the step of generating the shortest path expression by searching the first to i-th <axis-node> pairs and the AiNi section to determine whether respective the first to i-th <axis-node> pairs can be deleted.

### Claim 7 (depends on 6)

The method as claimed in claim 6, wherein the determining whether respective pairs can be deleted comprises the steps of:
searching a node of the Tail section from a sub-tree in which a node indicated by the Head section becomes a root node;
deleting the AiNi section when the node of the Tail section has a prefix AiNi; and
changing an axis of the Tail section from ‘/’ to ‘//’.

### Claim 8 (depends on 1)

The method as claimed in claim 1, wherein the tree structure resides in one of a main memory and a disk.

### Claim 9

A system for processing a query for searching XML data, comprising:
a XML query parser that receives an input document from a user and parses said input XML document to generate a reconstructed input XML document;
a XML path expression reducer that receives said reconstructed input XML document, traverses a XML Instance Structure (XIS) tree to check for duplication of nodes, and returns a shortest path expression to said XML query parser, wherein said XIS tree includes nodes other than nodes duplicated in said input XML document, and stored as a tree structure; and
a XML query processor that receives said returned shortest path query from said XML query parser, performs said query by extracting a result from a XML database, and provides said result to said user.

### Claim 10 (depends on 9)

The system of claim 9, wherein said XIS tree is constructed based on an actual structure of said input XML document, and neither shared nodes nor recursive nodes are present in said XIS tree.

### Claim 11 (depends on 10)

The system of claim 10, wherein when a parent node has a plurality of child nodes in said input XML document, only one of said child nodes is registered in said XIS tree.

### Claim 12 (depends on 9)

The system of claim 9, wherein said XIS tree is generated while said input XML document is loaded, and nodes are added to said XIS tree in accordance with a tree traversal algorithm.

### Claim 13 (depends on 12)

The system of claim 12, where said tree traversal algorithm comprises at least one of a pre-order algorithm, an in-order algorithm, and a post-order algorithm, and said traversing occurs during said parsing by said XML query parser.

### Claim 14 (depends on 9)

The system of claim 9, wherein said XIS tree is stored in one of a XML format and a relational database.

### Claim 15 (depends on 9)

The system of claim 9, wherein said shortest path expression is generated based on a path expression reduction algorithm that converts a path expression in said input XML document into a shortest path expression among an equivalence class to which said path expression belongs, through said XIS tree.

### Claim 16 (depends on 9)

The system of claim 9, wherein a path expression P in the query is represented as P=A1N1 A2N2 . . . AkNk and is classified into a Head section, an AiNi section, and a Tail section when a length of the path expression is k.

### Claim 17 (depends on 16)

The system of claim 16, wherein the AiNi section denotes first to i-th <axis-node> pairs for the path expression P, the Head section is a part in which reduction has been made among lists of the <axis-node> pairs located before the AiNi section, and the Tail section is a part in which the reduction has not yet been made among lists of the <axis-node> pairs located after the AiNi section.

### Claim 18 (depends on 16)

The system of claim 16, wherein said XML path expression reducer generates the shortest path expression by searching the first to i-th <axis-node> pairs and the AiNi section to determine whether respective the first to i-th <axis-node> pairs can be deleted.

### Claim 19 (depends on 18)

The system of claim 18, wherein said XML path expression reducer performs the determining whether respective pairs can be deleted by,
searching a node of the Tail section from a sub-tree in which a node indicated by the Head section becomes a root node,
deleting the AiNi section when the node of the Tail section has a prefix AiNi, and
changing an axis of the Tail section from ‘/’ to ‘//’.

### Claim 20 (depends on 9)

The system of claim 9, wherein the XIS tree resides in one of a main memory and a disk.
