Indexing structured documents

Methods and apparatus, including computer program products, for indexing structured documents. A method includes identifying a structured document in a file system for indexing, the structured document having an identifier and at least one indexing-property, extracting at least one index-value from the structured document in accordance with a pre-defined extraction rule-set and storing the at least one index-value with the identifier in an index-value data structure.

BACKGROUND

The present invention relates to indexing structured documents.

Servers located around the Internet and contained in Intranets serve up content (e.g., pages, documents) to users on demand. A user, interacting through a search engine, enters a text query for information and the search results are displayed to the user as text, graphics, audio and/or video through a graphical user interface most often referred to as browser software. There are several functions that are part of a search engine, such as information gathering, indexing, categorization, and searching. Information gathering usually uses Web crawlers to send visited pages to an index engine. The index engine uses some form of inverted files and, given a word, returns a list of references that contain the word. Categorization, or clustering, attempts to categorize the pages according to attributes, such as topics. The searching allows the user to ask content-based queries and get ranked result sets.

SUMMARY

In one aspect, the invention features a method for indexing structured documents including identifying a structured document in a file system for indexing, the structured document having an identifier and at least one indexing-property, extracting at least one index-value from the structured document in accordance with a pre-defined extraction rule-set, and storing the at least one index-value with the identifier in an index-value data structure.

One or more of the following may also be included. The file system for indexing may be a Web based Distributed Authoring and Versioning (WebDAV) file system. The at least one indexing-property may be selected from the group of document-type, URL and document-version. The structured document may be a markup language document with a markup-language selected from the group of XML, XHTML and WML. The index-value data structure may be stored as a relational database table. The WebDAV file system may be stored in a relational database management system (RDMS). The pre-defined extraction rule set may include XPath-expressions. The file system may be processed by a first processor and identifying, extracting and storing may be executed by a second processor.

Identifying, extracting and storing may be executed synchronously or asynchronously when generating the structured document in the WebDAV file system.

Identifying, extracting and storing may be repeated for a number of structured documents in the file system.

In another aspect, the invention features a method including identifying a plurality of structured documents in a file system for indexing, each of the structured documents having an identifier and at least one indexing-property, extracting at least one index-value from each of the structured documents in accordance with a pre-defined extraction rule-set, and storing the at least one index-value with the identifier in an index-value data structure for each of the plurality of structured documents.

One or more of the following may also be included. Identifying may include determining whether the structured document is locked. The file system may be a WebDAV file system. Each of the structured documents may be a markup language document.

Embodiments of the invention may have one or more of the following advantages.

The process allows a user to ask structured queries into a database of structured documents.

The process improves intelligent indexing of structured documents for providing scalable search engines in a Web-based Distributed Authoring and Versioning (WebDAV) file system environment.

The process indexes structured documents in a relational database and can perform versioned indexing, i.e., indexing of multiple versions of a structured document.

The process can execute on multiple processors synchronously or asynchronously.

Other features, objects, and advantages of the invention will be apparent from the description and drawings, and from the claims.

DETAILED DESCRIPTION

As shown inFIG. 1, a system10includes a computer12linked to computers14,16via a network18. Computer12includes processor20, memory22, bus24, and, optionally, input device26and output device28. Input device26and output device28are sometimes collectively referred to as a user interface (UI)30. Memory22includes an indexing structured documents process100that communicates with a carrier32and generates a signal34.

As shown inFIG. 2, memory22includes a World Wide Web Distributed Authoring and Versioning (WebDAV) file system200linked to process100. The WebDAV file system200may be used to administer structured documents. WebDAV is an Internet Engineering Task Force (IETF) standard for collaborative authoring on the Web, a set of extensions to the Hypertext Transfer Protocol (HTTP) that facilitates collaborative editing and file management between users located remotely from each other on the Internet.

WebDAV enables remote groups to work together in various ways. For example, WebDAV—conforming tools may be used by a virtual organization to develop business plans, create software, or write libraries of information. A WebDAV work group is part of the applications section of the World Wide Web Consortium (W3C); their charter states its goal as to “define the HTTP extensions necessary to enable distributed Web authoring tools to be broadly interoperable, while supporting user needs.” WebDAV adds write access to the read access afforded by HTTP. WebDAV enables users to collaborate over the World Wide Web in the same way as they might over a corporate intranet.

WebDAV features include:Locking (also known as concurrency control), which prevents accidental overwriting of files.XML properties, which facilitate operations (such as storage and retrieval) on metadata, that data about other data that can be organized;The DAV protocol, which enables property setting, deleting, and retrieving;The DASL (DAV Searching and Locating) protocol, which enables searches based on property values for locating resources on the Web;namespace manipulation, which supports copy and move operations. Collections, which are similar to file system directories, may be created and listed.

WebDAV provides PUT and GET functions to upload/download structured documents to/from a web server. WebDAV provides further functions, such as MKCOL to make collections (directories), COPY and MOVE to copy, move and rename files and DELETE to delete files or collections. These functions allow one to use a server that is supporting WebDAV as a file system, in which WebDAV can be considered to be an access protocol to the file system. The implementation of the file system is independent from the access protocol. Collections and files are referred to as resources. For example, in one implementation, resources can be stored in the file system and further information, such as properties, can be stored in a relational database management system (RDBMS). In another implementation, properties and resources all can be stored in a RDBMS.

WebDAV also provides other functions, such as PROPFIND to list the properties of a resource, and PROPPATCH to set and change properties of resources through applications that make use of the resources.

File system200stores documents, such as structured document210. Structured document210can be a markup-language document, such as an XML-, XHTML- or WML-document. Structured document210has at least one indexing-property, such as IP-1and/or IP-2, and further has an identifier ID-1.

Identificator110identifies structured document210in file system200for indexing. For example, structured document210has at least one indexing-property IP-1and/or IP-2. An indexing-property can be a document-type, a URL and/or a document-version. Identificator110can access indexing-properties IP-1, IP-2of structured document210via interface101-1. In one example, access to indexing-properties is implemented by using the WebDAV function PROPFIND. In another example, accessing the indexing-properties can be implemented with a corresponding Structured Query Language (SQL)-statement. Identificator110compares the indexing-properties of structured document210with reference indexing-properties. For example, the reference indexing-properties can be stored in a corresponding table of a relational database system. Preferably, identificator110accesses the reference indexing-properties via interface101-2. In another example, reference indexing-properties are stored in a specific property data structure. Index-value data structure140or the specific property data structure may be implemented as database tables in a RDBMS or as a further structured document, such as an XML file, that can be stored, for example, in file system200. If identificator110identifies indexing-property IP-1and/or IP-2matching corresponding reference indexing-properties, the structured document210is subject to indexing.

Extractor120extracts at least one index-value IV-1from structured document210in accordance with pre-defined extraction rule set130. Extractor120is connected to pre-defined extraction rule set130via interface101-4and to structured document210via interface101-5. Pre-defined extraction rule set130includes extraction rules130-1,130-2,130-3. In one embodiment of the invention, extraction rules130-1,130-2,130-3are XPath-expressions.

XPath is a language that describes a way to locate and process items in Extensible Markup Language (XML) documents by using an addressing syntax based on a path through the document's logical structure or hierarchy. This makes writing programming expressions easier than if each expression had to understand typical XML markup and its sequence in a document. XPath also allows the programmer to deal with the document at a higher level of abstraction. XPath is a language that is used by and specified as part of both the Extensible Stylesheet Language Transformations (XSLT) and by XPointer (SML Pointer Language). It uses the information abstraction defined in the XML Information Set (Infoset). Since XPath does not use XML syntax itself, it could be used in contexts other than those of XML.

XPath uses syntax something like an informal set of directions for finding a particular geographic location. When telling someone how to find the Minneapolis campus of the University of Minnesota within the United States, for example, one might write:US/MN/Mpls/SE/WashingtonAve/bridge
which would put the user in the middle of the campus.

XPath uses the concepts of the concept node (the point from which the path address begins), the logical tree that is inherent in any XML document, and the concepts expressing logical relationships that are defined in the XML Information Set, such as ancestor, attribute, child, parent, and self. XPath includes a small set of expressions for specifying mathematics functions and the ability to be extended with other functions.

In another example, once the indexing of structured document210is finalized, an index status of structured document210is set to a value that indicates that the structured document has already been indexed. For example, the index status can be implemented as a property of structured document210that is set by using the WebDAV function PROPPATCH.

In an embodiment, identificator110and extractor120perform synchronously when a structured document is generated in file system200by using, for example, the WebDAV function PUT. For example, a document-check-in application generates structured document210and concurrently identificator110checks if structured document210is subject to indexing. If so, extractor120extracts index values (e.g. IV-1) according to extraction rule set130and the extracted index values are stored in index-value data structure140together with identifier ID-1of structured document210.

In another embodiment, identificator110and extractor120perform asynchronously. In other words, structured document210already exists in file system200. However, it is not yet indexed (for example indicated by the index status). Identificator110and extractor120are triggered by a specific event. The specific event can be a control signal launched by a user or automatically generated by system10, for example, at a specific point in time or at a regular interval, to continuously scan file system200for new structured documents to be indexed. For example, when a trigger occurs at night when only a few users interact with computer system10, a large number of structured documents (e.g. in a batch run) can be processed without using CPU time that is needed by system processes for user interaction.

A specific implementation of extracting a specific index-value from structured document210is now explained by way of example.

The code shown in table 1 below illustrates a simplified XML-example of structured document210having identifier ID-1=“1111.”

Extraction rule130-1corresponds to the following XPath expression:XPath_Index_Name=“/department/employeelist/name/text( )”

In other words, exctractor120extracts index-values (e.g. Peter, Michael, etc.) that are stored under the indexing-property name XPath_Index_Name in the code. Table 2 below shows entries that are stored in index-value data structure140when applying the Xpath-expression130-1to the above code of structured document210.

An example of another extraction rule130-2is:

Applying extraction rule130-2to code above adds another entry for indexing-property XPath_Index_employeenumber to index-value data structure140, as shown in table 3 below.

Index-value data structure140can store index-values of a large number of structured documents. By using index-value data structure140, structured documents can be identified via a corresponding query. For example, a query can request all structured documents that describe a department having more than three employees. In the example, the query at least identifies structured document210with identifier “1111”.

By using a unique identifier for each version of a structured document or by using a version-property of the structured document, versioned indexing, i.e., indexing of multiple versions of a structured document, is automatically provided.

As shown inFIG. 3, a computer90for indexing structured documents includes a file system200and process100residing in memory92. Computer90includes a first processor94and a second processor96, referred to sometimes as shared memory processors. The file system200is operated by first processor94. In other words, program instructions to run file system200are executed by first processor94. Process100is executed by second processor96. Shared memory processors are utilized to improve performance of indexing computer90. By using different processors for running the file system200and for performing indexing (process100) of structured documents in the file system200, the indexing has no impact on the performance of the file system200(e.g. the system response time when a user wants to check in a document into the file system).

FIG. 4shows a locking mechanism300for asynchronous indexing of structured documents. Symbolrefers to locked and symbolrefers to select and lock. To speed up indexing of structured document210and other structured documents220-250stored in file system200, multiple indexing processes301,302are used. In the example, first indexing process301recognizes that structured document250is already locked by another indexing process (not shown). Therefore, first indexing process301skips the locked structured document250and selects the next unlocked structured document210in file system200. Concurrently with selecting structured document210first indexing process301locks structured document210while indexing the document. Second indexing process302recognizes that structured document210and250are already locked by other indexing processes and selects the next unlocked structured document220. Concurrently with selecting structured document220second indexing process302locks structured document220while indexing the document. By using the select and lock feature, waiting times for indexing processes301,302(until a locked structured document gets unlocked again) can be minimized.

As shown inFIG. 5, a process400for indexing structured documents in a computer storing a Web based Distributed Authoring and Versioning (WebDAV) file system200includes the acts of identifying (410), extracting (420) and storing (430).

In identifying (410), process400identifies structured document210in the WebDAV file system200for indexing. Structured document210has at least one indexing-property IP-1, IP-2and has identifier ID-1. For example, the at least one indexing-property IP-1and/or IP-2can be a document-type, a URL, a document-version, etc. Structured document210can be a markup-language document, such as an XML-, XHTML- and WML-document. In an embodiment, the WebDAV file system200is stored in a relational database management system.

In extracting (420), process400extracts at least one index-value IV-1from structured document210in accordance with pre-defined extraction rule-set130. In one embodiment of the invention, pre-defined extraction rule set130includes XPath-expressions130-1,130-2,130-3.

In storing (430), process400stores the at least one index-value IV-1together with identifier ID-1in index-value data structure140. For example, index-value data structure140can be stored as a relational database table.

In one embodiment, WebDAV file system200is operated by first processor94and process400is executed by second processor96.

In one example, process400is executed synchronously when generating the structured document210in the WebDAV file system200. In another example, process400is executed asynchronously upon generating structured document210in WebDAV file system200. In this example, process400is executed for structured document210by first indexing process301and can be executed for structured documents220,230,240,250of WebDAV file system200by second indexing process302. By using multiple indexing processes, multiple structured documents can be indexed concurrently. Preferably, second indexing process302skips structured document210when it is locked by first indexing process301and selects an unlocked structured document220from the structured documents220,230,240,250. By concurrently locking the unlocked structured document220, second indexing process302prevents further indexing processes to access further structured document220. Preferably, upon indexing a structured document, process400sets a corresponding indexing status of the document.

To provide for interaction with a user, the invention can be implemented on a computer having a display device such as a CRT (cathode ray tube) or LCD (liquid crystal display) monitor for displaying information to the user and a keyboard and a pointing device such as a mouse or a trackball by which the user can provide input to the computer.

The invention has been described in terms of particular embodiments. Other embodiments are within the scope of the following claims. For example, steps of the invention can be performed in a different order and still achieve desirable results.