Method for rapidly searching elements or attributes or for rapidly filtering fragments in binary representations of structured, for example, XML-based documents

• US 7,464,098 B2
• Filed: 06/25/2002
• Issued: 12/09/2008
• Est. Priority Date: 06/25/2001
• Status: Expired due to Fees

• Current Assignee: Siemens AG
• Original Assignee: Siemens AG
• Inventors: Hutter, Andreas, Heuer, Jörg
• Primary Examiner(s): TIMBLIN, ROBERT M
• Application Number:
  US10/482,357
• Publication Number:
  US 20040193581A1
• Time in Patent Office: 2,359 Days
• Field of Search: 707/3, 707/101, 715/234
• US Class Current: 1/1
• CPC Class Codes: G06F 16/81 Indexing, e.g. XML tags; Data structures therefor; Storage structures
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99942 Manipulating data structure, e.g. compression, compaction, compilation

Abstract

A method serves to encode textual paths for indexing and querying structured, for example, XML-based documents and serves to execute and improved filtering of binarily represented XML documents. A development of the method results in all indices being identical even in the event that a polymorphism is inserted therein. When storing these textual paths for indexing or querying, only one smaller volume of data has to be stored or transmitted. A comparison of this data can also subsequently ensure more rapidly during a query since the volume of data to be compared is smaller.

Claims

1. A method for searching of elements in binary representations of structured XML-based documents, comprising the steps of:

encoding a textual path for indexing elements or attributes, wherein the path comprises data types;

replacing at least one of the data types, that are instanced in the path and which are derived through polymorphism, with standardized data types, wherein the respective standardized data type is obtained by

deriving a basic data type of the respective data type, and

searching a data type to establish that the searched data type contains the element or attribute following in the path and that is uniquely determined with reference to its derivation from the basic data type;

providing a unique identification for the textual path using a bit pattern after encoding, wherein the bit pattern includes the searched elements or attributes.

2. The method according to claim 1, wherein after the step of searching the data type to establish the searched data type contains the element or attribute following in the path and that is uniquely determined with reference to its derivation from the basic type, the standardized data type is further defined by having the lowest or highest type code or the lowest or highest number of inheritance steps proceeding from the basic type.

3. The method according to claim 1, wherein the textual path is encoded by specifying a path type and an encoded absolute path, without the use of position codes.

4. The method according to claim 1, wherein the textual path is encoded by specifying a path type, an absolute type code, and an encoded relative path, without the use of position codes.

5. The method according to claim 4, wherein the textual path is encoded by additionally specifying a number of types and by means of a number of tuples, determined by the number of types from a respective absolute type and a respective schema branching code.

6. A method for filtering fragments in binary presentations of structured XML-based documents, comprising the steps of:

encoding a context path for indexing elements or attributes wherein the path comprises data types;

replacing at least one of the data types that are instanced in the path and which are derived through polymorphism with standardized data types, wherein the respective standardized data type is obtained by

deriving a basic data type of the respective data type, and

searching a data type to establish that the searched data type contains the element or attribute following in the path and that is uniquely determined with reference to its derivation from the basic data type;

providing a unique identification for the context path using a bit pattern after encoding, wherein the bit pattern includes the searched elements or attributes.