# US 7,467,157 B1 · Generation of semantically valid xpath expressions

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

- Number: US 7,467,157 B1
- Document ID: US7467157B1
- Status: Granted
- Kind: B1
- Application number: 11/841,099
- Filed: 2007-08-20
- Granted: 2008-12-16
- Earliest claimed: 2007-08-20
- Assignees: International Business Machines Corporation
- Inventors: Wallace Chen; Ciby Mathew
- Web page: https://patentgrep.com/patent/US7467157B1

## CPC

- G06F 11/3684: {for test design, e.g. generating new test cases}
- G06F 16/832: Query formulation
- G06F 40/143: Markup, e.g. Standard Generalized Markup Language [SGML] or Document Type Definition [DTD]
- G06F 40/226: Validation
- Y10S 707/99943: Generating database or data structure, e.g. via user interface
- Y10S 707/99944: Object-oriented database structure
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- Y10S: TECHNICAL SUBJECTS COVERED BY FORMER USPC CROSS-REFERENCE ART COLLECTIONS [XRACs] AND DIGESTS

## Abstract

A method for automatically generating semantically valid XPath expressions in a computer system is provided. The method includes populating an instance of a sequence-type model by organizing XML data into a hierarchical structure consistent with the sequence-type model. The method also includes priming the instance of the sequence-type model to remove ambiguities and redundancies, while retaining semantic validity of the instance of the sequence-type model. The method further includes scanning the instance of the sequence-type model to identify one or more location paths that match a search pattern, where an initial scan originates at a root of the hierarchical structure and subsequent scans originate from a termination point of a prior scan to incrementally search for location steps by searching along XPath axes. The method additionally includes determining whether a sequence type at each location step matches the search pattern and outputting a result as semantically valid XPath expression output.

## Claims

### Claim 1

A method for automatically generating semantically valid XPath expressions in a computer system, comprising:
populating an instance of a sequence-type model by organizing eXtensible Markup Language (XML) data into a hierarchical structure consistent with the sequence-type model;
priming the instance of the sequence-type model to remove ambiguities and redundancies, while retaining semantic validity of the instance of the sequence-type model;
scanning the instance of the sequence-type model to identify one or more location paths that match a search pattern, wherein an initial scan originates at a root of the hierarchical structure and subsequent scans originate from a termination point of a prior scan to incrementally search for location steps by searching along XPath axes;
determining whether a sequence type at each location step matches the search pattern to form scan results;
cumulating and categorizing the scan results to yield a set of location paths that are semantically valid XPath expressions, wherein the XPath expressions provide tests of functionality of an XPath evaluation engine, including one that is embedded in an XQuery and index evaluation engine, ensuring a shared sequence-type model between generators for XPath and XML data, and concurrent stress testing of the evaluation engines; and
outputting the scan results as semantically valid XPath expression output.

### Claim 2 (depends on 1)

The method of claim 1 wherein the sequence-type model is a symmetrical alternate form of an XML schema model that is formatted for searching convenience.

### Claim 3 (depends on 2)

The method of claim 2 wherein the sequence-type model is a hierarchy of a multiplicity indicator and an item type, the item type providing an inheritance definition for a node type and an atomic type.

### Claim 4 (depends on 1)

The method of claim 1 wherein the scanning is applied to each axis as defined in the XPath language.

### Claim 5 (depends on 1)

The method of claim 1 further comprising:
filtering a context step using a predicate, wherein the filtering is performed using a comparison of the context step against a literal value or relative location path.

### Claim 6 (depends on 1)

The method of claim 1 wherein the priming eliminates cyclic definitions.

### Claim 7

A method comprising:
a storage medium executable by a computer processor for implementing the method comprising:
populating an instance of a sequence-type model by organizing eXtensible Markup Language (XML) data into a hierarchical structure consistent with the sequence-type model;
priming the instance of the sequence-type model to remove ambiguities and redundancies, while retaining semantic validity of the instance of the sequence-type model;
scanning the instance of the sequence-type model to identify one or more location paths that match a search pattern, wherein an initial scan originates at a root of the hierarchical structure and subsequent scans originate from a termination point of a prior scan to incrementally search for location steps by searching along XPath axes;
determining whether a sequence type at each location step matches the search pattern to form scan results;
cumulating and categorizing scan results to yield a set of location paths that are semantically valid XPath expressions wherein the XPath expressions provide tests of functionality of an XPath evaluation engine, including one that is embedded in an XQuery and index evaluation engine, ensuring a shared sequence-type model between generators for XPath and XML data, and concurrent stress testing of the evaluation engines; and
outputting the set of location paths as semantically valid XPath expression output.