US 6,654,734 B1Grant
System and method for query processing and optimization for XML repositories
Issue Date:2003-11-25
•22 Claims
•6 Drawing Sheets
Abstract
A computer program product is provided as a system for querying a repository of XML documents. The data in the XML documents are viewed by a query system as a graph that allows queries on content, structure, inter-document links, and intra-document links. The query language uses XML syntax and is based on tree pattern match semantics. The features of the query language allow the query system to compute a DTD for the query language and to use it to validate the user query formulation. Query optimization is done using schema-based optimization and index based optimization. Optimization uses the schema for (a) minimizing the number of documents on which the query need to be executed; (b) eliminating redundant conditions specified in the query; and (c) simplifying expensive query constructs. The query system maintains three sets of indices for each XML document: (a) value indices corresponding to text; (b) structure indices corresponding to tree structure patterns; and (c) link indices corresponding to link relationships.
Metadata
Assignee
- International Business Machines Corporation
Inventors
- Murali Mani
- Neelakantan Sundaresan
Application Information
Application Number:US 09/652,328
Filing Date:2000-08-30
Priority Date:2000-08-30
Art Unit:7
Classifications
IPC:
G06F 1730
Field of Search:
709224705 714705 1
Patent Drawings (6 sheets)
Description
Field of the Invention
[0002] The present invention relates to the field of data processing, and particularly to a software system and associated method for use with a search engine, to search indexed and raw data obtained from systems that are linked together over an associated network such as the Internet. This invention more particularly pertains to a computer software product for retrieving resources in XML documents through the extensive use of schema (Document Type Definition) for query processing and optimization.
Background of the Invention
[0003] The World Wide Web (WWW) is comprised of an expansive network of interconnected computers upon which businesses, governments, groups, and individuals throughout the world maintain inter-linked computer files known as web pages. There is an increasing interest in caching and indexing web pages so as to facilitate the query process using the indexed information. To this end, a crawler crawls the web and extracts metadata, or information about the data on the web, and stores the metadata in a data repository or data store. The vastness of the unstructured WWW causes users to rely primarily on Internet search engines to retrieve or locate information.
[0004] Pages on the WWW commonly use HTML as the computer language that describes and displays the page information on the web. HTML is a computer language primarily used for browsing or viewing documents on the web. An HTML document is typically treated as a single block of text, which is easily indexed and searched.
[0005] Increasingly, web pages are written using XML, a computer language more complex than HTML that renders information for viewing on the web. Also, the hierarchical nature of XML makes it suitable for describing meta (index) information. The XML standard specification requires that XML documents be well formed, i.e. always have a proper nested structure. However, XML documents need not be valid to meet the XML specification, i.e. the document may not have a schema or may not be validated against an associated schema. In such cases, it is possible to infer the schema from the document. But the multiplicity of non-uniform schemas is difficult, time consuming, and inefficient for a search engine to search or query. To optimize the query process, the number of schemas queried must be minimized.
[0006] Traditionally, query process optimization has been focused either on the structure or on the content of the XML document. The optimization technique based on structure or schemas does not look at the entire XML document but rather searches the schema or its Document Type Definition (DTD). DTD is a language that describes the structure of an XML document. This query optimizer extracts from the (DTD) three kinds of structural relationship sets or rules:
[0007] Obligation, which for a particular element is the set of dependents that this element must necessarily have.
[0008] Exclusivity, which for an element is the set of ancestors that must be present for that particular element.
[0009] Entrance location, which describes the elements that should be present in any path between two nodes.
[0010] The limitation of this query optimization is that only three structural relationship sets are used. Queries usually contain other structural conditions that are not captured by these three relationships.
[0011] The second traditional approach to query optimization is to use indices. Indexing has typically been studied by persons skilled in the database field, who do not consider that indexing to be a requirement for tree pattern matching, but rather consider path indices, which are insufficient for tree pattern matching.
[0012] There is therefore still an unsatisfied need for an XML query optimization system that meets the following criteria:
[0013] The number of schemas queried by the query optimizer must be minimized in order to optimize the query process with respect to the query processing time and the size of the query index.
[0014] An XML document has structure and content that need to be indexed together.
[0015] Provides an indexing structure for tree pattern matching.
[0016] The structure extracted by the query optimizer must consider all structural relationship sets present in the schema.
[0017] Existing query optimization systems do not meet all the foregoing criteria above, and the need for such a system has heretofore remained unsatisfied.
Summary of the Invention
[0018] This invention describes a system and method this need, and provide the capability to optimize the XML document query process by:
[0019] minimizing the number of schemas examined by a search engine by reducing the number of different schemas in the data store;
[0020] indexing both structure and content of the XML document to minimize the number of steps in the query process; and
[0021] extracting from the DTD all structural relationship sets applying to a specific XML document.
[0022] This feature will enable the system of the present invention to minimize the time required to process a search request while also minimizing data storage requirements.
[0023] The query system of the present invention provides several features and advantages, related to the following:
[0024] data model;
[0025] query language; and
[0026] index format.
[0027] The data model of the query system of the present invention views the XML repository as a set of schema/data pairs where, for every schema, the query system maintains the set of documents that conform to that schema. The data in an XML document is viewed by the query system as a graph with the “edges” between the graphs used to represent inter-document links. This data model allows queries on content, structure, plus inter-document links and intra-document links.
[0028] The query language uses XML syntax and supports tree pattern matching. This allows the query system to compute a DTD for the query language and use it to validate the user query during query formulation. Using a tree structure instead of the traditional path expression, makes the query language easier to use, and allows the query language to specify conditions on siblings in the tree structure. The query language also:
[0029] returns both the subtree rooted at the element and the element (with or without attributes);
[0030] allows restructuring of documents, since many queries require the query result in a different structure than the source document;
[0031] allows specification of grouping result elements;
[0032] supports specifications of regular path expressions for reaching an element;
[0033] supports queries on the order among child nodes;
[0034] identifies data types associated with the different content values in a XML document;
[0035] supports common database constructs for supporting set operations;
[0036] supports the semantic as well as the literal view for both intra-document and inter-document links; and
[0037] queries the text content of the nodes of an XML document individually, combined at the node level, and combined at the subtree level.
[0038] The query system of this invention maintains three kinds of indices for an XML document: a value index corresponding to text; a structure index corresponding to tree structure patterns; and a link index corresponding to link relationships. These indices are organized as a trie, ensuring that the index access cost is linear with respect to the size of the query and independent of the number of indices present. For storage and search efficiency, the structure pattern is converted to a string.
Brief Description of the Drawings
[0039] The various features of the present invention and the manner of attaining them will be described in greater detail with reference to the following description, claims, and drawings, wherein reference numerals are reused, where appropriate, to indicate a correspondence between the referenced items, and wherein:
[0040] FIG. 1 is a schematic illustration of an exemplary operating environment in which a query system of the present invention can be used;
[0041] FIG. 2 is a block diagram that illustrates the two main components of the query system of FIG. 1, the indexing system and the query processor, shown used in the context of an Internet search;
[0042] FIG. 3 is a block diagram that depicts the main components of the query system of FIGS. 1 and 2;
[0043] FIG. 4 depicts the components of a query processor of FIG. 2 that forms part of the query system of FIGS. 1-3;
[0044] FIG. 5 is a graphical representation of an exemplary DTD used by the query system of FIG. 3; and
[0045] FIG. 6 is a bock diagram representing the query process according to the present invention.
Detailed Description of the Invention
[0046] The following definitions and explanations provide background information pertaining to the technical field of the present invention, and are intended to facilitate the understanding of the present invention without limiting its scope:
[0047] API (application program interface): A specific method prescribed by a computer operating system or by another application program by which a programmer writing an application program can make requests of the operating system or another application.
[0048] Child (also daughter): From graph theory, a node pointed to by a path from a parent.
[0049] Crawler: A program that automatically explores the World Wide Web by retrieving a document and recursively retrieving some or all the documents that are linked to it.
[0050] DOCTYPE declaration: An XML document type declaration that contains or points to markup declarations which provide a grammar for a class of documents. The Name in the document type declaration matches the element type of the root element.
[0051] DOM (Document Object Model): A platform- and language-neutral interface that allows programs and scripts to dynamically access and update the content, structure and style of documents. The Document Object Model provides a standard set of objects for representing HTML and XML documents, a standard model of how these objects can be combined, and a standard interface for accessing and manipulating them.
[0052] DTD (Document Type Definition): defines the schema of semi-structured documents such as SGML (Standard Generalized Markup Language), HTML, or XML documents.
[0053] Element: “Tagged” text; text encoded with formatting or other information.
[0054] Internet: A collection of interconnected public and private computer networks that are linked together with routers by a set of standards protocols to form a global, distributed network.
[0055] Leaf: Terminal node of a tree; a node with no child/daughter.
[0056] Node: A point or vertex in a graph.
[0057] Parent: A node (as in a graph) with a successor (child/daughter).
[0058] Path: The sequence of nodes encountered in the route between any two nodes (inclusive).
[0059] QEP (Query Execution Plan): An execution plan that instructs the server how to process a statement.
[0060] Root node: A node with no parent but typically with children.
[0061] Schema: Format or structure. It defines the structure and type of contents of constituent structures of, for example, a database, XML documents, etc.
[0062] Search engine: A remotely accessible World Wide Web tool that allows users to conduct keyword searches for information on the Internet.
[0063] Semi-structured: Implying a schema either explicitly or implicitly.
[0064] Server: A software program or a computer that responds to requests from a client.
[0065] Tags: Codes (as in HTML or XML) that give instructions for formatting or action.
[0066] Tree: A hierarchical structure that is made up by nodes. Nodes are connected by edges from one node (parent) to another (child). A single node at apex of the tree is known as the root node, while the terminus of a path in the opposite direction is a leaf.
[0067] Trie: A tree data structure used to efficiently store and search a set of strings. The trie has the following property: at most one node in the trie corresponds to a prefix.
[0068] URL (Uniform Resource Locator): A unique address that fully specifies the location of a content object on the Internet. The general format of a URL is protocol://server-address/path/filename.
[0069] Web browser: A software program that allows users to request and read hypertext documents. The browser gives some means of viewing the contents of web documents and of navigating from one document to another.
[0070] Web document or page: A collection of data available on the World Wide Web and identified by a URL. In the simplest, most common case, a web page is a file written in HTML and stored on a web server. It is possible for the server to generate pages dynamically in response to a request from the user. A web page can be in any format that a web browser or a helper application can display. The format is transmitted as part of the headers of the response as a MIME type, e.g. “text/html”, “image/gif”. An HTML web page will typically refer to other web pages and Internet resources by including hypertext links.
[0071] Web Site: A database or other collection of inter-linked hypertext documents (“web documents” or “web pages”) and associated data entities, which is accessible via a computer network, and which forms part of a larger, distributed informational system such as the WWW. In general, a web site corresponds to a particular Internet domain name, and includes the content of a particular organization. Other types of web sites may include, for example, a hypertext database of a corporate “intranet” (i.e., an internal network which uses standard Internet protocols), or a site of a hypertext system that uses document retrieval protocols other than those of the WWW.
[0072] World Wide Web (WWW): An Internet client—server hypertext distributed information retrieval system.
[0073] XML: extensible Markup Language. A standard, semi-structured language used for Web documents. During a document authoring stage, XML “tags” are embedded within the informational content of the document. When the web document (or “XML document”) is subsequently transmitted by a web server to a web browser, the tags are interpreted by the browser and used to parse and display the document. In addition to specifying how the web browser is to display the document, XML tags can be used to create hyperlinks to other web documents.
[0074] FIG. 1 portrays the overall environment in which a query system 10 according to the present invention may be used. The query system 10 includes a software or computer program product that is typically embedded within, or installed on a host server 15. Alternatively, the query system 10 can be saved on a suitable storage medium such as a diskette, a CD, a hard drive, or like devices. While the query system 10 will be described in connection with the WWW, the query system 10 can be used with a stand-alone database of terms that may have been derived from the WWW and/or other sources.
[0075] The cloud-like communication network 20 is comprised of communication lines and switches connecting servers such as servers 25, 27, to gateways such as gateway 30. The servers 25, 27 and the gateway 30 provide the communication access to the WWW Internet. Users, such as remote Internet users are represented by a variety of computers such as computers 35, 37, 39, and can query the host server 15 for the desired information.
[0076] The host server 15 is connected to the network 20 via a communications link 42 such as a telephone, cable, or satellite link. The servers 25, 27 can be connected via high speed Internet network lines 44, 46 to other computers and gateways. The servers 25, 27 provide access to stored information such as XML or web documents indicated generally at 50, 55, and 60. The XML documents 50, 55, 60 most likely include embedded links to other locally stored pages, and links 70, 72, 74, 76 to other web sites or documents 55, 60 that are stored by various web servers such as the server 27.
[0077] The XML documents 50, 55, 60 can be represented as the WWW 20 in FIG. 2. Searches on the WWW 20 are performed by the query system 10. The query system 10 generally includes a query processor 80 and an indexing system 85. The indexing system 85 extracts data from the XML documents on the WWW 20 and stores that data in the index repository 90 as XML documents.
[0078] In use, the user enters a query through the browser for search engine 95. The search service provider 100 forwards the query to the query system 10. The query processor 80 then generates a Query Execution Plan (QEP) that specifies any indices for use in the search. The QEP is optimized for the document object model (DOM). The DOM is an application program interface (API) used in this case for traversing the XML document tree structure in the index repository 90.
[0079] The QEP retrieves the index document stored on the index repository 90 by means of a set of index keys. These index keys are stored in the index repository 90, with each index key storing the set of references within the document. The QEP looks up the specified index structures for a key K, and obtains the set of element references. It then looks up the source document and retrieves the elements corresponding to these references.
[0080] FIG. 3 shows the main components of the query system 10 used for processing and indexing XML documents. The query system 10 generally includes two main components: a preprocessor 105 and a query processor 80 of FIG. 2.
[0081] The preprocessor 105 is used to optimize query execution and includes a schema extractor 110, a relation set generator 115, and an indexing system 85. Data generated by the preprocessor 105 are stored in the index repository 90. The schema extractor 110 first extracts the schema for new or unprocessed documents 125. If the new or unprocessed document 125 does not have a schema, the schema extractor 110 discovers a schema for this document 125, as described for example in co-pending patent application titled “Method and System for Discovering a Majority Schema in Semi-structured Data”, filed on Jul. 27, 2000, assigned to the same assignee as the same application, and incorporated herein by reference. The results of the schema extractor 110 are stored in the index repository 90 as documents 130. The DTD and the data in the document 130 are then used by the other components of the preprocessor 105.
[0082] The relation set generator 115 computes structural relationship sets 135 between elements and attributes from the schema (either defined or discovered by the schema extractor 110). These structural relationship sets 135 are later used for query optimization and processing. The relation set generator 115 computes eight different structural relationship sets; child, parent, attribute, reachability, ancestor, obligation, exclusivity, and entrance location. Only obligation, exclusivity, and entrance location are examined by existing XML query systems. These eight structural relationship sets are used by the query system 10 to filter documents that will produce an empty result set, for strength reduction of the user query, i.e. to replace complex query constructs with simpler ones and eliminate redundant conditions. A description of these structural relationship sets 135 and how they are determined is given below.
[0083] Child
[0084] The child structural relationship set for an element A denoted by C(A) is given by:
[0085] C(A)={(C1, T1), (C2, T2), . . . ,(Cn, Tn)}
[0086] where C1, C2, . . . , Cnrepresent all the child elements which A can have. Tiassociated with a Cidenotes the derived parent-child relationship between A and Ci. This can be either +, *, ? or ONCE. ONCE is used to denote a child that can occur exactly once.
[0087] Parent
[0088] The parent structural relationship set for an element A, denoted by P(A) is defined as:
[0089] P(A)={P1, P2, . . . , Pn}
[0090] where P1, 1≦q≦n represents a possible parent element for A.
[0091] Attribute
[0092] The attribute relation set for an element A is given by:
[0093] Attr(A)={(At1, Dec1, Def1; Val1), (At2, Dec2, Def2, Val2), . . . , (Atn, Decn, Defn, Valn)}
[0094] where At1, At2, . . . , Atnare the name of all the attributes which A can have. Decidenotes the declared type of Ati, Defidenotes the default type of Atiand Validenotes the default string value defined for that attribute (if any).
[0095] Reachability
[0096] The reachability set for an element A, denoted by R(A) is given by:
[0097] R(A)={(A1, L1), (A2, L2), . . . , (A n1Ln)} where A1, A2, . . . , Anare possible descendants of A as computed from the DTD graph. The Liassociated with Airepresent the set of levels at which Aican be present as a descendant of A. The reachability set for the leaf nodes in the graph is the empty set. For convenience of explanation, we define a set R′(A) which is obtained from R(A) by omitting the level information:
[0098] R′(A)={A1, A2, . . . , An}
[0099] The set R′(A) represents the set of elements which can be present as a descendant of A in a document conforming to the DTD. For an element A which has n children denoted by S={C1, C2, . . . , Cn}, the recurrence relation used to obtain the set R′(A) is given by:
[0100] R′(A)=C1∪R′(C1)∪C2∪R′(C2)∪ . . . ∪Cn∪R′(Cn)
[0101] The level information for an element Aiε R′(A) is obtained as follows. Let D1, D2, . . . , Dk⊂S be such that Aiε R′(Dj)|1≦j≦k. Let Li(B) represent the set of levels associated with Aiin the reachability set for B. Then
[0102] Li(A)=L′i(D1)∪L′i(D2)∪ . . . ∪L′i(Dk)
[0103] L′i(E)={e1+1, e2+1, . . . , ep+1}|Li(E)={e1, e2, . . . , ep}
[0104] Ancestor
[0105] The ancestor structural relationship set for an element A denoted by G(A) is given by:
[0106] G(A)={(P1, L1), (P2, L2), . . . , (Pn, Ln)}
[0107] where Pi, 1≦i≦n represents a possible ancestor element which can be present in the document. The level information, Liassociated with an ancestor, Pirepresents the set of levels at which Pican be present as an ancestor with respect to A. The ancestor structural relationship sets can be computed from the reachability structural relationship sets as follows. If (Ei, Li) ε R(A), then (A, Li) ε G(Ei).
[0108] Obligation
[0109] The obligation set for an element A denoted by O(A) is given by:
[0110] O(A)={(A1, L1), (A2, L2), . . . , (An, Ln)}
[0111] where A1, A2, . . . , Anare descendants of A that must be present in every document conforming to the DTD. The Liassociated with Airepresents the set of levels at which Aican be present as a descendant of A. This is the same as the set of levels present in the reachability set. As for the reachability set, we define a set O′(A) which is obtained from O(A) by omitting the level information.
[0112] O′(A)={A1, A2, . . . , An}
[0113] Consider an example in which element A's content model is given by:
[0114] A→((((C1|C2), C3)|C4?), C5*, C2)
[0115] In computing the obligation set of an element A, content model subtrees with the * or ? operators are ignored. This reduces the above content model to (((C1|C2), C3), C2). Then an AND-OR tree is constructed with AND representing “,” and OR representing “|” with the elements as the leafs. The obligation set O″(N) for a node N in the AND-OR tree is computed recursively as follows.
[0116] For an element node (leaf node), O″(N)=O′(N).
[0117] For a node N, we define Contrib(N)=O″(N)∪N if N is a leaf node, and O″(N), otherwise.
[0118] For an AND node N, with n child nodes C1, C2, . . . , Cn(the child nodes can be OR nodes or element nodes), the obligation set is given by:
[0119] O″(N)=∪i=0nContrib(Ci).
[0120] For an OR node N, with n child nodes C1, C2, . . . , Cn(the child nodes can be AND nodes or element nodes), the obligation set is given by
[0121] O″(N)=∪i=0nContrib(Ci).
[0122] Exclusivity
[0123] The exclusivity set for an element A, denoted by E(A) is given by:
[0124] E(A)={(A1, L1), (A2, L2), . . . , (An, Ln)}
[0125] where A1, A2, . . . Anare ancestors of A that must be present in every document conforming to the DTD. The level set Liassociated with an element Airepresents the set of levels at which Aican be present as an ancestor of A. (This is the same as the set of levels at which A can be present as a descendant of Aiobtained in the reachability sets.) Let E′(A) denote the exclusivity structural relationship set for A without the level information, that is E′(A)={A1, A2, . . . , An}. For an element A with n possible parents, P1, P2, . . . , Pn, E′(A) is defined recursively as follows:
[0126] E′(A)=(P1∪E′(P1))∩(P2∪E′(P2))∪ . . . ∪(Pn∪E′(Pn))
[0127] Entrance Location
[0128] The entrance location set for an element A, denoted by EL(A) is given by:
[0129] EL(A)={(B1, {(C11, L111, L112), (C12, L121, L122) . . . (C1n, L1n1, L1n2)}),
[0130] (B2, {(C21, L211, L212), (C22, L221, L222) . . . (C2n, L2n1, L2n2)}), . . . ,
[0131] (Bk, {(Ck1, Lk11, Lk12), (Ck2, Lk21, Lk22) . . . (Ckn, Lkn1, Lkn2)})}
[0132] The above equation says that for every occurrence of the path (Bi, A) in the XML document, there always exist the elements {Ci1, Ci2, . . . , Cin} in the (Bi, A) path. The level information associated with an element Cijis given by two sets of levels. Lij1represents the set of levels at which Cijcan be present as a descendant of Bi, and Lij2represents the set of levels at which A can be present as a descendant of Cij. Again the level information is obtained from the reachability sets. Therefore we define EL′(A) as:
[0133] EL′(A)={(B1, {C11, C12,. . . C1n}),
[0134] (B 2, {C21, C22, . . . C2n}), . . . ,
[0135] (Bk, {Ck1, Ck2, . . . Ckn})
[0136] For an element, A with n possible parents, {P1, P2, . . . , Pn}, the entrance location is obtained as follows.
[0137] For every parent Pi, we add (Pi, { }) to the entrance location structural relationship set.
[0138] If two parents, Piand Pjhave the terms (B1, S1) and (B1, S2) respectively in the entrance location sets, then the set for A will contain (B1, ((Pi∪S1)∪(Pj∪S2)).
[0139] Various index structures for the new or unprocessed document 125 of FIG. 3 are built by the indexing system 85. The resulting index structures 140 are stored in the index repository 90. The indexing system 85 is shown in more detail in FIG. 4.
[0140] Three types of indices are maintained by the indexing system 85 (FIG. 4): a value index 145 corresponding to the text; a structure index 150 corresponding to the tree structure patterns, and a link index. The link index can be maintained as simple mappings from ID names to elements. The value index 145 includes a text index 155 and an attribute index 160. For each element in the XML document, the indexing system 85 finds the different text values and stores in the text index 155 the element references that have this value. The attribute index 160 maintains a list of references for the text values of each element and each attribute within the element.
[0141] Tree indexing represents a novel feature of the present invention. A tree index can be a nested index 165 or a path index 170. Reference is made to Chen. W, Aberer. K, Neuhold. E. J, “Efficient Algorithms for Determining the Optimal Execution Strategy for Path Queries in OODBS,” Proc. of SEBD′96, San Miniato (Pisa), Jul. 3-5, 1996, pp. 441-452. For a particular pattern, the nested index 165 maintains the set of references to all the elements that satisfy this pattern. The path index 170 maintains references for eiements that satisfy every sub-pattern.
[0142] A tree pattern is converted to a string (e.g. Euler string) by the query system 10. A tree pattern is considered as having multiple sub-patterns, corresponding to each position in the Euler string. For example, in the following Euler string “book.author.book.author.book” there are five sub-patterns:
[0143] 1. book
[0144] 2. book.author
[0145] 3. book.author.book
[0146] 4. book.author.book.author
[0147] 5. book.author.book.author.book
[0148] All the structure indices are converted into Euler strings and stored as a trie. All four indices of FIG. 4 are stored as an XML document, but in a restricted format. The query executor 185 (FIG. 3) uses the available indices as well as the structural relationship sets for optimization.
[0149] The query processor 80 of FIG. 3 performs the queries and returns the result set 180 to the user. The query processor 80 includes three parts: the query optimizer 175, the query executor 185, and the result consolidator 190. The query optimizer 175 builds an “optimal” QEP for the document. The query executor 185 executes the QEP obtained by the query optimizer 175. A schema generator then computes the schema (DTD) for the result set 180, creating an output document for the result set 180.
[0150] An important feature of the query system 10 of this invention is the manner in which data is viewed. An XML document is viewed by the query system as a graph with the “edges” between the graphs used to represent inter-document links. This data model allows queries on content, structure, plus inter-ocument links and intra-document links. XML is used to represent both hierarchical structure and data. Structure is represented using nested elements and data is represented using text nodes and attribute values. The example below shows a sample XML document and a DTD for that document. This document represents a small library database consisting of two books and one monograph.
[0151] DTD for example database:
[0152] <!DOCTYPE library [
[0153] <!ELEMENT library (book/monograph)*>
[0154] <!ELEMENT book (title, author*, publisher?)>
[0155] <!ELEMENT title (#PCDATA)>
[0156] <!ELEMENT author EMPTY>
[0157] <!ATTLIST author firstName CDATA #REQUIRED middleInitial CDATA #IMPLIED lastName CDATA #REQUIRED>
[0158] <!ELEMENT publisher (#PCDATA)>
[0159] <!ELEMENT monograph (title, editor+, publisher?)>
[0160] <!ELEMENT editor (monograph*)>
[0161] <!ATTLIST editor firstName CDATA #REQUIRED middleInitial CDATA #IMPLIED lastName CDATA #REQUIRED>
[0162] ]>
[0163] XML Document for example database:
[0164] <library>
[0165] <book>
[0166] <title>The XML Handbook</title>
[0167] <author firstName=“Charles” middleInitial=“F” lastName=“Goldfarb”/>
[0168] <author firstName=“Paul” lastName=“Prescod”/>
[0169] <publisher>Prentice Hall</publisher>
[0170] <book>
[0171] <book>
[0172] <title>XML Complete</title>
[0173] <author firstName=“Steven” lastName=“Holzner”/>
[0174] <publisher>McGraw-Hill</publisher>
[0175] </book>
[0176] <monograph>
[0177] <title>Active rules in database systems</title><editor firstName=“Norman” middleInitial=“W” lastName/=“Paton”/><publisher>New York: Springer</publisher>
[0178] </monograph>
[0179] </library>
[0180] The query system 10 views the DTD as a directed graph, rooted at an element called the DOCTYPE declaration. FIG. 5 shows the directed graph view of the database example, where the DOCTYPE declaration is “library” 195. Elements, attributes, and the regular expression operators are used to represent the content model form nodes in the graph. The DTD semantics are not completely captured by relational schemas as DTD “simplification” is important for XML-relational conversion.
[0181] FIG. 6 shows a more detailed description of a method of operation 200 for the query processor 80 of FIG. 3. Given a query (Q) 201, a source extractor 205 first extracts the source documents on which the query will be executed, creating the document list 210. A source specified in the query 201 can be either a document in the repository 90 or the result set of a nested query.
[0182] A document filter 215 then uses the pre-computed structural relationship sets 135 (S) to eliminate documents that do not qualify for the query (Q) 201. This allows the query system 10 to avoid querying documents that will not contribute to the result set. By eliminating empty results for the query 201, processing time is dramatically reduced. If (Q+S) generates a non-empty result, the query processor 80 proceeds to the query optimizer 175. If (Q+S) generates an empty result, the query processor 80 loops back and considers the next document.
[0183] Table 1 lists some sample conditions in the query and the corresponding conditions in the structural relationship set that cause a document to be eliminated. As an example, Table 1 enumerates conditions for a source document D in the document list for query Q to be filtered out. S(D) denotes the relationship sets computed for D. In item 1, the query requires that B be a descendant of A at one of the depths in L, but from the reachability sets, it is known that B is not a descendant of A at any of the depths in L. The query in item 5 requires that A have two child elements with tag name B, but from the child relationship sets, it is known that A can have at most one child which is B. The query in item 6 requires that A have an attribute At with value V, but from the attribute relationship sets, it is known that A cannot have an attribute At.
| TABLE 1 | ||
|---|---|---|
| No. | Condition specified in Q | Condition present in S(D) for D to be filtered out |
| 1 | (B, L) ε Des(A) | ((B, _) ∉ R(A) OR (((B, L′) ε R(A)) AND (L ∩ L′ = φ))) |
| 2 | (B, L) ε Anc(A) | ((B, _) ∉ G(A) OR (((B, L′) ε G(A)) AND (L ∩ L′ = φ))) |
| 3 | (B, L) ∉ Des(A) | ((B, L′) ε O(A) AND (L′ |
| 4 | (B, L) ∉ Anc(A) | ((C,L′) ε E(A) AND (L′ |
| 5 | B, B ε Child(A) | (((B, ∪NCE) ε C(A)) OR ((B, ?) ε C(A))) |
| 6 | (At, V) ε Attrib(A) | (At,_, _, _) ∉ Attr(A) |
[0184] The query optimizer 175 of FIGS. 3 and 6 performs two tasks: strength reduction of expensive query constructs and choice of an optimal QEP. Strength reduction involves eliminating redundant query constructs and replacing expensive constructs with simpler constructs. For example, an expensive construct would be a query for all descendents of books that are authors; a simpler construct to obtain the same result would be a query for children of books that are authors. The expensive construct asks the query system to select all books from the document at any depth from the document root level that satisfy the remaining conditions. However, from the reachability sets, the query system knows that book elements can only be present at a height of 1 from the document root level, so the query system need only check the child elements for books.
[0185] A few exemplary conditions for using the structural relationship sets for strength reduction are illustrated in Table 2. Table 2, shows strength reduction of the user query as implemented by the query optimizer 175, wherein C represents the condition specified in the original query, S(D) represents the relationship sets for the source document being considered and C′ represents the reduced condition corresponding to C. Items 1, 2, 3, and 4 remove redundant conditions. Item 5 also removes redundant conditions, but from a query with negation. Items 6 and 7 show how complex constructs (which typically require traversal to an arbitrary depth or height) are simplified.
| TABLE 2 | |||
|---|---|---|---|
| No. | Condition specified in C | Condition present in S(D) | Condition in C′ |
| 1 | (B, L) ε Des(A) | (((B, L′) ε O(A)) AND (L′ | φ |
| 2 | (B, L) ε Anc(A) | (((B, L′) ε E(A)) AND (L′ | φ |
| 3 | (B, L) ε Des(A) | (((C, {(B, L′, L′ | φ |
| AND(C, L | AND(L′ | ||
| 4 | B ε Child(A) | (((B, +) ε C(A)) OR ((B, ONCE) ε C(A))) | φ |
| 5 | (B, _) ∉ Des(A) | (B, _) ∉ R(A) | φ |
| 6 | (B, ANY) ε Des(A) | (B, L) ε R(A) | (B, L) ε Des(A) |
| 7 | (B, L) ε Anc(A) | (((B, L′) ε E(A)) AND (L′ | φ |
[0186] With the strength reduced query construct determined, the query optimizer 175 enumerates candidate QEPs for the “reduced” query. The “optimal” QEP is chosen by estimating the “cost” to perform the QEP. A cost model is used to estimate index access cost, the I/O cost for accessing elements, and the number of elements to be accessed. From (Q+S+I) the OQEP is selected and passed on to the query executor 185 for execution.
[0187] The query executor 185 executes the OQEP obtained from the query optimizer 175 and obtains the result set 180 for the document being considered. The query executor 185 uses the actual XML document in the document list 210 being reviewed, the structural relationship set (S) 135 and the indices (I) 140. The QEP is optimized for the document object model (DOM). The DOM is an application program interface (API) used by the query executor 185 for traversing the XML document tree structure. The query executor 185 is defined in terms of operators that are in turn defined by the DOM API. The operators used by the query system in the QEP are unique to this invention and are described below:
[0188] Root Operator returns the document root element. It is represented by Root(D), where D is the document under consideration.
[0189] Tree Traversal Operators are used to traverse the source document tree and perform pattern matches. For a tree traversal operator V, the subtree rooted at V (say T) specifies a pattern match condition. The candidate elements for V are checked for the pattern match. V returns true if and only if the candidate elements for V matched the pattern specified in T. The query system uses five different tree traversal operators, which are described below. Let A be the candidate element being considered for pattern match at the parent node of V. (Note that a tree traversal operator is never present as the root node of a QEP and therefore A is always defined.)
[0190] Descendant Operators identify descendant elements of A that satisfy the pattern match. These operators are denoted by Des(E, N, L, P), where E is a set of element names (the tag name for a candidate element for V should be specified in E) and L is the set of depths at which a candidate element for V can be present as a descendant of A. N is a count used to indicate how many of the candidate elements for this operator should satisfy the pattern match for V to return true. P specifies the path for reaching a candidate element for V from A. The specification of P is optional, and when no regular path expression is specified, P takes the value φ.
[0191] Ancestor Operators identify the ancestor elements of A that qualify. An ancestor operator is denoted by Anc(E, N, L, P), where E and N are as explained before. L is the set of heights at which a candidate element can be present as an ancestor of A. The optional P specifies the regular path expression for reaching A from a candidate element for V.
[0192] Sibling Operators identify the siblings of A that qualify. They are denoted by Sib(E, L), where E is a set of element names and L is the set of levels at which a candidate element can be present as a sibling of A. Right sibling levels are represented using positive numbers, and left sibling levels using negative numbers.
[0193] Text Operators perform match on the value contained in a text node of A. Three different text operators are defined by the query system 10.
[0194] Text1(Op, S) denotes the text operator used to check the value contained in any individual text node of A. Op is an operator, and S is a string or variable reference. This operator returns true if and only if A has a text node with value Val, such that Val(Op)S is true.
[0195] Text2(I, Op, S) denotes the text operator used to check the text value obtained by concatenating all the text node descendants of A at a height specified by “I”.
[0196] Text3(Op, S) is used to check the text value obtained by concatenating all the text node descendants of A in a depth first order.
[0197] Attribute Operators perform matches on the attribute values of A. These operators are denoted by Attr(At, Op, S). This operator returns true if and only if A has an attribute named At with value Val which satisfies Val(Op)S. (It also uses type coercion.)
[0198] Logical Operators are AND, CR and NOT operators. A logical operator combines the boolean pattern match results of its children.
[0199] Aggregate Operators supported at present are Count and GroupBy operators. The Count operator is specified as Count(E1, E2, V), and it returns the number of children of E1that have tag E2and sets V to this value. The Group Operator is specified as Group(E1, S), and it groups all the children of E1based on the values for the attributes in S, and returns this grouped element.
[0200] Index Scan Operator is used to retrieve elements from a specified index structure. It is denoted by Index(F, S, K), where F is the index file name, S is the kind of index (this can be structure, text, or attribute) and K is the key used to obtain the set of element references. This operator looks up the specified index structures for the key K and obtains the set of element references. It then looks up the source document and retrieves the elements corresponding to these references.
[0201] Join Operator combines the results obtained from its child operators. This operator is denoted by Join(C), where C is a condition on which the join is performed. (This operator cannot be a leaf in the QEP).
[0202] A result set 180 obtained from the execution of the QEP, is then passed to the schema generator 220 (FIG. 6). The schema generator 220 then generates the DTD for the result set 180. This output DTD is obtained as a function of the user query and the DTD for the source document in the document list 210 that is being queried.
[0203] The process described for FIG. 6 is repeated for each document extracted by the source extractor 205. When the query processor 80 has processed all the documents extracted by the source extractor 205, the results are combined into one XML document by the result consolidator 190. The output DTDs computed by the schema generator 220 are merged and a DTD for the result document is obtained. This result document along with the output DTD is sent back to the user.
[0204] It is to be understood that the specific embodiments of the invention that have been described are merely illustrative of certain application of the principle of the present invention. Numerous modifications may be made to system of the invention described herein without departing from the spirit and scope of the present invention. Moreover, while the present invention is described for illustration purpose only in relation to the WWW, it should be clear that the invention is applicable as well to databases and other tables with indexed entries.
Claims
What is claimed is:
1. A query processing method for querying a plurality of hierarchical documents having corresponding schemas and contents, comprising:
extracting structural relationship sets from the schemes;
comparing a query against the structural relationship sets to determine if the query is to be executed on the hierarchical documents; and
optimizing the query processing by filtering documents from the plurality of hierarchical documents that will produce an empty result;
wherein optimizing the query processing comprises maintaining an indexing structure for tree pattern matching;
wherein, for each non-filtered document, the indexing structure comprises three indices:
a value index that corresponds to a document content;
a structure index that corresponds to a tree structure pattern of the non-filtered document; and
a link index that corresponds to link relationships between the non-filtered document and the plurality of hierarchical documents; and wherein optimizing the query processing further comprises, for each non-filtered document:
organizing the three indices as a trie; and
querying the trie using tree pattern matching.
2. The query processing method of claim 1, wherein optimizing the query processing further further comprises eliminating the documents that will produce an empty result.
3. The query processing method of claim 1, wherein optimizing the query processing comprises removing redundant query constraints, and simplifying complex constraints, if any.
4. The query processing method of claim 3, wherein optimizing the query processing comprises determining if a query constraint will always be true, and removing such constraint.
5. The query processing method of claim 3, wherein optimizing the query processing further comprises simplifying complex query constraints into simpler query constraints.
6. The query processing method of claim 5, further comprising:
precomputing results for tree structure patterns of the non-filtered documents;
converting the tree structure patterns into strings;
storing the strings as part of the trie;
storing the precomputed results corresponding to each string as part of the indexing structure; and
optimizing the query processing by querying the indexing structure.
7. The query processing method of claim 6, further comprising precomputing results for common tree structure patterns.
8. The query processing method of claim 7, wherein precomputing results comprising converting the tree structure patterns into strings, and maintaining a result for each tree structure pattern.
9. The query processing method of claim 7, wherein optimizing the query processing the documents comprise XML documents.
10. A query system for querying a plurality of hierarchical documents having corresponding schemas and contents, comprising:
a preprocessor comprising a relation set generator that computes structural relationship sets between elements and attributes of a schema, and an indexer that computes values and structure indices; and
a query processor for performing a query and returning a result set, comprising:
a query optimizer that builds an execution plan for a document; and
a query executor that executes the execution plan;
wherein the query processor compares the query against the structural relationship sets to determine if the query is to be executed on the documents; and
wherein the query processor optimizes a query processing by filtering documents that will produce an empty result;
wherein the query processor optimizes by using the indices instead of executing the query on the actual documents;
wherein the query processor maintains an indexing structure for tree pattern matching;
wherein, for each non-filtered document, the indexing structure comprises three indices:
a value index that corresponds to a document content;
a structure index that corresponds to a tree structure pattern of the non-filtered document; and
a link index that corresponds to link relationships between the non-filtered document and the plurality of hierarchical documents; and wherein, for each non-filtered document, the query processor further
organizes the three indices as a trie; and
queries the trie using tree pattern matching.
11. The query system of claim 10, wherein the query processor further comprises a result consolidator.
12. The query system of claim 11, wherein the query processor further comprises:
a schema extractor for extracting structural relationship sets from the schemas; and
an indexing system.
13. The query system of claim 10, wherein the query processor optimizes the query processing by determining if the query to be executed on the hierarchical documents will produce an empty result, and eliminating all the documents conforming to the common schema that will produce an empty result.
14. The query system of claim 10, wherein the query processor further optimizes the query processing by removing redundant query constraints, and by simplifying complex constraints, if any.
15. The query system of claim 12, wherein the preprocessor further optimizes the query processing by:
precomputing results for tree structure patterns;
converting the tree structure patterns into strings;
storing the strings as a trie;
storing the precomputed results corresponding to each string as an index; and
optimizing the query processing by querying the index.
16. The query system of claim 15, wherein the hierarchical documents comprise XML documents.
17. A query system having instruction codes for querying a plurality of hierarchical documents having corresponding schemas and contents, comprising:
a preprocessor comprising a first set of instruction codes for computing structural relationship sets between elements and attributes of a schema, and a second set of instruction codes for computing values and structure indices;
a query processor for performing a query and returning a result set, comprising:
a third set of instruction codes for building an execution plan for a document; and
a fourth set of instruction codes for executing the execution plan;
a fifth set of instruction codes for comparing the query against the structural relationship sets to determine if the query is to be executed on the documents; and
a sixth set of instruction codes for optimizing a query processing by filtering documents that will produce an empty result;
a seventh set of instruction codes for optimizing by using the indices instead of executing the query on the actual documents;
an eight set of instruction codes for maintaining an indexing structure for tree pattern matching;
wherein, for each non-filtered document, the indexing structure comprises three indices:
a value index that corresponds to a document content;
a structure index that corresponds to a tree structure pattern of the non-filtered document; and
a link index that corresponds to link relationships between the non-filtered document and the plurality of hierarchical documents; and wherein, for each non-filtered document, the query processor further
organizes the three indices as a trie; and
queries the trie using tree pattern matching.
18. The query system of claim 17, wherein the query processor further comprises a result consolidator.
19. The query system of claim 18, wherein the query processor further comprises:
a schema extractor for extracting structural relationship sets from the schemas; and
an indexing system.
20. The query system of claim 17, wherein the query processor optimizes the query processing by determining if the query to be executed on the hierarchical documents will produce an empty result, and eliminating all the documents conforming to the common schema that will produce an empty result.
21. The query system of claim 17, wherein the query processor further optimizes the query processing by removing redundant query constraints, and by simplifying complex constraints, if any.
22. The query system of claim 19, wherein the preprocessor further optimizes the query processing by:
precomputing results for tree structure patterns;
converting the tree structure patterns into strings;
storing the strings as a trie;
storing the precomputed results corresponding to each string as an index; and
optimizing the query processing by querying the index.
Patent Citations (2)
| Patent | Date | Inventor | Cited By |
|---|---|---|---|
| US6463440(B1) | 2002-10-01 | Hind et al. | Examiner |
| US2002/0169788(A1) | 2002-11-01 | Lee et al. | Examiner |
Non-Patent Literature (22)
- Abiteboul. et al., “The Lorel Query Language for Semistructured Data,” International Journal of Digital Libraries, Apr. 1997, 1(1):68-88.Applicant
- Bohm. K, et al., “Query Optimization for Structured Documents Based on Knowledge of the Document Type Definition,” Proceedings of IEEE International Forum on Research and Technology Advances in Digital Libraries (ADL'98), Santa Barabara, California, Apr. 1998, pp. 196-205.Applicant
- Chen. W. et al., “Efficient Algorithms for Determining the Optimal Execution Strategy for Path Queries in OODBS,” Proc. of SEBD'96, San Miniato (Pisa), Jul. 3-5, 1996, pp. 441-452.Applicant
- Deutsch. A, et al., “Storing Semistructured Data with STORED,” SIGMOD Conference, Philadelphia, Pennsylvania, Jun. 1-3, 1999, pp. 431-442.Applicant
- Goldman. R, et al., “From Semistructured Data to XML: Migrating the Lore Data Model and Query Language,” Proceedings of the 2nd International Workshop on the Web and Databases (WebDB '99), Philadelphia, Pennsylvania, Jun. 1999.Applicant
- Girardot, M, et al., “Millau: an encoding format for efficient representation and exchange of XML documents over the WWW,” 9th International World Wide Web Conference, Amsterdam, Netherlands, May 2000.Applicant
- Goldman. R, et al., “DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases,” Proceedings of the Twenty-Third International Conference on Very Large Data Bases, Athens, Greece, Aug. 1997, pp. 436-445.Applicant
- Goldman. R, et al., “Approximate DataGuides,” Proceedings of the Workshop on Query Processing for Semistructured Data and Non-Standard Data Formats, Jerusalem, Israel, Jan. 1999.Applicant
- Liefke. H, et al., “XMill: an Efficient Compressor for XML Data,” University of Pennsylvania, Department of Computer Science, Technical Reports, 1999, p. 1-26.Applicant
- Milo. T, et al., “Index Structures for Path Expressions,” 7th International ICDT Conference, Jerusalem, Israel, Jan. 10-12, 1999, pp. 277-295.Applicant
- Nestorov. S, et al., “Extracting Schema from SemiStructured Data,” SIGMOD Conference 1998, 295-306.Applicant
- Ramesh. B, et al., “Nonlinear Pattern Matching in Trees,” Journal of the Association for Computing Machinery, vol. 39, No. 2, Apr. 1992, pp. 295-316.Applicant
- Shanmughasundaram. J, et al., “Relational Databases for Querying XML Documents: Limitations and Opportunities,” Proceedings of the 25th VLDB Conference, Edinburg, Scotland, 1999.Applicant
- Robie. J, “The Design of XQL,” http://www.texcel.no/whitepapers/xql-design.html, printed Jul. 11, 2000.Applicant
- Robie. J, et al., XML Query Language (XQL), http://www.w3.org/TandS/QL/QL98/pp/xql.html, printed Jul. 11, 2003.Applicant
- Widom. J, “Data Management for XML Research Directions,” http://www-db.stanford.edu/widom/xml-whitepaper.html, printed Jul. 11, 2000.Applicant
- Extensible Markup Language (XML) 1.0, W3C Recommendation Feb. 10, 1998, http://www.w3.org/TR/REC-XML, printed Jul. 11, 2000.Applicant
- Deutsch. A, et al., “XML-QL: A Query Language for XML,” Submission to the World Wide Web Consortium Aug. 19, 1998, http://www.w3.org/TR/NOTE-XML-ql, printed Jul. 11, 2000.Applicant
- “Document Object Model (DOM) Level 1 Specification,” Version 1.0, W3C Recommendation, Oct. 1, 1998 http://www.w3.org/TR/REC-DOM-Level-1.Applicant
- W3C XML Specification DTD (“XMLspec”) http://www.w3.org/XML/1998/06/XMLspec report-19980910.htm, printed Jul. 11, 2000.Applicant
- XML Path Language (XPath) Version 1.0, W3C Recommendation, Nov. 16, 1999, http://www.w3.org/TR/1999/REC-xpath-19991116.Applicant
- XSL Transformations (XSLT) Version 1.0, W3C Recommendation, Nov. 16, 1999, http://www.w3.org/TR/1999/REC-xslt-19991116.Applicant