Words (Tokens)

A Full-Text query allows you to search for words inside text data. For example, with a Full-Text query you can search for the word “werewolf” in the title of any of our movies. The basic unit of Full-Text search is often referred to as a token rather than a word. Token is a more precise term – in Western languages, tokens generally map to words, though some search engines count some phrases, parts of words, and possibly punctuation, as tokens. In many non-Western languages (especially those where whitespace is not used to separate meaningful strings), there is no clear concept of a word, and a Full-Text engine has to make some tough decisions on where to draw token boundaries (or how to otherwise derive tokens from a piece of text). For the rest of this chapter we use the term word for convenience.

A common question from non-Full-Text users is, “If Full-Text search is about looking for words inside text, then XQuery already does that with the contains function. So what’s missing?” The contains function does not do a Full-Text search – it does a substring search. The main difference is that a Full-Text search will generally match only a complete word, and not just part of a string. For example, a Full-Text search for “dent” will not match a piece of text that contains the word “students,” but a substring search will.

Also, when running a Full-Text search, there is generally an assumption that the match will be case-insensitive,² so that “dent” will match “DENT” as well as “dent” (and “Dent” and “dEnt” and “DEnt” and so on). With substring queries, matching is usually case-sensitive (depending on the collation used), so that the text being searched has to match the case of the search term.

Special Operations

A Full-Text query should be able to support some special operations that are not applicable to structured search (non-Full-Text search over dates, numbers, and short strings). These operations fall into four classes.

The not combiner is also a little different in Full-Text queries. First, the unary not (“not dog”) is famously difficult to execute efficiently with most Full-Text indexes. Many Full-Text languages disallow the unary not altogether – i.e., they only allow not as a combiner (“cat not dog”). Also, there is a strong case for a mild not in Full-Text query. The mild not says, “Don’t match this phrase, but don’t exclude text that contains it either.” For example, suppose you are researching government policy on housing, and you want to search for government bills that contain the word “house.” You don’t want the phrase “house of representatives” to trigger a match, because that’s not the sense of “house” you are looking for. At the same time, you don’t want to exclude everything that contains “house of representatives,” because then you would miss a lot of things that should match. So a search for “house” will bring back too many results, while a search for “house not (house of representatives)” will bring back too few. Only “house mild not (house of representatives)” will return everything that contains the word “house,” while ignoring any occurrence of “house” as a part of “house of representatives.”

Higher-Level Operations

If a Full-Text language implements a set of special operations such as those just discussed, then an expert searcher can get good, predictable results by combining words, phrases, and operators in intelligent ways. However, these operations are completely mechanical on the part of the search engine – they do not imply any real understanding of the content or of the user’s intent, and they put the burden of formulating just the right query on the user. This may work well if the user is an expert in both the subject domain and the capabilities of the Full-Text tool, but a Full-Text query engine should be able to do better than that. We discuss search more broadly in Chapter 18, “Finding Stuff” – for now, let’s briefly look at two ways to make Full-Text search smarter and easier.

Concept search allows you to search for a concept rather than a word or phrase. If you are a wine connoisseur, you might want to find everything that is about wine (the concept). You could start by searching for wine (the word), then apply stemming to find anything that contains the word “wine” or the word “wines,” then apply the thesaurus operation to find anything that contains narrow terms for wine (“merlot,” “chianti,” “zinfandel,” and so on). But it would be much better to be able to express directly in the Full-Text query language that you want to search for the concept of wine, e.g., by querying for “about(wine).” Some Full-Text query engines already offer a concept search – as computers get smarter and faster, we expect concept search to become more widespread and more accurate.

Suppose that your Full-Text query engine is not capable of concept search, or that you are particularly knowledgeable about your domain and the needs of your users. It is common for a search application to do progressive relaxation – that is, to progressively relax the query that the user typed in until some reasonable set of results (say, enough to fill a computer screen) is returned. In our example of a concept search for wine, we assumed that the wine researcher wanted to find everything that was about wine. In many situations, such as e-commerce, you want the first 20 or so results that most closely match the criteria the user typed in, and you want them very quickly – the complete set of possible results is not important. So a Full-Text query engine might provide support for query templates, which allow you to describe the relaxation steps. For an online bookstore search, the steps might be:

Note that both concept search and progressive relaxation could be considered as parts of an application rather than parts of a Full-Text query language. The language designer might say, “I’m giving you the basic building blocks to express any query – if you want concept search or progressive relaxation, go build it using these blocks.” Or she might say, “These higher-level operations are important and useful – I’ll put some constructs into the language so you can express them directly, without a lot of coding.” See also Section 13.2.5 for some discussion topics around what should go into a Full-Text query language.

Inexact Answers and Relevance (Score)

When you execute a regular structured query, you generally expect an exact answer. For example, if you search for all movies that were released in 1985, there is a single correct answer – there is no room for debate as to whether a particular movie was, or was not, released in 1985. When you run a Full-Text query, the result set can be subjective – the ordering of the results set always is.

Let’s take a simple example first – search for “Sheltie rescue.” We used Google (which is a search application) and found 118,000 pages on the Internet that contain the phrase “Sheltie rescue.” This is an exact answer – every page in the results set contains the phrase “Sheltie rescue” at least once, and every Full-Text engine that searches the same corpus (set of documents) should return the same results set. As we make the query more complex, as long as the operations are well-defined, the results set is predictable. However, some operations will bring in the engine’s “secret sauce” – e.g., thesaurus operations may use different thesauri – and this make the results set inexact.

The ordering of the results set, on the other hand, is always subjective. The Salton algorithm⁵ calculates a relevance score for a particular result by counting the number of times the query term occurs in the document. The algorithm takes account of how common the term is in the corpus overall, and some variations also take account of the length of the document. Most Full-Text engines use something based on this algorithm, plus (for web searches) some variation on the PageRank algorithm made famous by Google (see Chapter 18, “Finding Stuff”) to allocate a relevance score to each result. Results can be ordered according the relevance ranking (the size of the relevance score). But most, if not all, Full-Text engines then add some unpublished smarts – some “secret sauce” – to make their relevance ranking more effective.

In the early days of Full-Text development at Oracle, the Full-Text team devised some simple tests to measure the accuracy of the relevance scoring (and consequently the relevance ranking) of Full-Text query results. They took a fairly small corpus and had humans rank the results of some queries, and then they had their nascent Full-Text engine rank the results of those queries. They found that the Full-Text engine agreed with a human’s ranking only about 60% of the time. But they also found that humans agreed with other humans only about 40% of the time! Even when there is little ambiguity in the query term, such as a query for “dog,” people disagree wildly about how “doggy” a particular item is, and whether one item is more or less “doggy” than another.

In summary, relevance scoring by humans is highly subjective, and relevance scoring by computers is generally proprietary, used by Full-Text vendors to differentiate their engines. This makes the semantics of relevance ranking impossible to standardize.

Performance

A Full-Text query is also different from a substring query in the area of performance (or at least expectations of performance). When you run a Full-Text query, you expect it to run much faster than a full scan through all the text being searched. This superior performance comes, of course, from the existence of a Full-Text index. The most common form of Full-Text index is an inverted list. This consists of a list of all the words that occur anywhere in the corpus (the set of documents that is the universe of search). Associated with each word is a list of the items in which that word occurs. When you search for “dog,” the Full-Text engine looks up the word “dog” in the list and finds all the items where that word occurs.

There are some common variations on the inverted list structure. Many Full-Text indexes index n-grams rather than words. Here’s how n-grams work: If the item to be indexed is “Mary had a little lamb,” a word index would split this into “Mary,” “had,” “a,” “little,” and “lamb,” and track all items that contain each of those words. An n-gram index might split the same phrase into “M,” “Ma,” Mar,” “ary,” “ry,” “y,” “h,” “ha,” “had,” “ad,” “a,” etc. This example is based on a 3-gram or tri-gram index, though the “n” may have other values. An n-gram index is particularly useful when many queries have wildcards at the beginning and/or end of a word, for languages such as Chinese and Japanese where the exact “word” structure is difficult to determine, and for text that is inaccurate (because it was typed or OCRed poorly).

The structure of an inverted index dictates some characteristics of Full-Text engines:

In summary, a Full-Text index increases the performance of Full-Text queries. It is generally built as an inverted list. This means that changes to the data are not (generally) reflected immediately in the index; that the index must be periodically optimized (manually or under the covers); and that some query options must be chosen at index build time.

1. single-word search

2. phrase search

3. support for stop words

4. single character suffix

5. 0 or more character suffix

6. 0 or more character prefix

7. 0 or more character infix

8. proximity searching (unit: words)

9. specification of order in proximity searching

10. combination using AND

11. combination using OR

12. combination using NOT

13. word normalization, diacritics

14. ranking, relevance

Approaches – Objects

One obvious way to implement XQuery Full-Text would be to follow SQL’s lead. After all, ANSI and ISO had been down this path already – they defined SQL/MM (SQL Multimedia and Application Packages) Part 2¹⁰ to extend the SQL language to incorporate Full-Text search (Part 1 defines the framework, and other parts define SQL support for Spatial and Image data). SQL/MM takes an objects-based approach. It defines a new UDT (user-defined type) called FullText, to represent any data that is Full-Text-searchable. It then defines methods on the FullText object, including a CONTAINS method to test whether a document matches a text query, and a RANK method to return the relevance score of a text query. Example 13-1¹¹ shows a table created with a column of type FullText and a query against that table. The query returns the docno for each row in the table where the document contains “standard” or “standards” in the same paragraph as a word that sounds like “sequel” (e.g., “SQL”). The results are ordered by the relevance score of the same text query.

Approaches – Functions

The idea of reusing the definitions generated by another standards body might seem appealing. But XQuery is an expression-based language with functions – it does not have objects. The obvious way to graft the SQL/MM approach onto XQuery would be to define two functions, say, mmcontains and mmscore (the function name contains is already taken by a substring function). An XQuery based on these functions might look like Example 13-2.

The advantages of this approach are:

So the standard could be defined quickly, and at least some vendors could implement it quickly and easily. The disadvantages of this approach, though, are:

That is, the string that makes up the second parameter is not a part of the outer language – it’s a string with its own “sublanguage.” Suppose you wanted to use such a query in your application but that you wanted the words “standard” and “sequel” to be replaced with variables (instead of being literals) – perhaps a user types them into some web page, perhaps they are derived somehow. You can’t express that easily in the XQuery – i.e., the string cannot contain variables (or expressions) where the search terms in the example are hard-coded. There are ways around this – you could allow some kind of string substitution in the parameter string, just as the Perl language does. Or you could just build up the string in a separate step, before calling the function.

Note that some of the verbosity comes from having to type in the sublanguage string twice, once for mmcontains and once for mmscore. If you want to be able to score (and therefore rank) results only on the same criteria you use to select items, you can avoid this. The filter function (mmcontains) could have a side effect – e.g., calling mmcontains might set a local variable to a score value. Several existing Full-Text implementations use a side effect to filter and produce a score in one step.

Approaches – Many-Functions

In the previous sections, we explored extending XQuery and XPath to handle Full-Text search by following the ANSI/ISO approach of introducing a special object and some methods, and then we looked at the possibility of introducing those methods into XQuery and XPath as two functions, which we (arbitrarily) called mmcontains and mmscore. A major objection to this approach is that it involves a sublanguage – the string containing the text query expression is, from XQuery’s point of view, just any old string (and not an expression). That means it’s clumsy to construct, and users must learn and use new operators that have similar, but not identical, semantics to operators they already use in XQuery (and, or, not, etc.). While there are clearly workarounds to these issues, many feel that this approach makes Full-Text a second-class citizen in the world of XQuery, that Full-Text is not quite (and, more importantly, never can be) a fully integrated part of XQuery under this scheme.

An alternative approach is to make every Full-Text operation a true, first-class XQuery function, doing away with the sublanguage string altogether. So, instead of the XPath expression

you would write

We have (arbitrarily) used a prefix “mf” (for “many-functions”). This could be part of a function-naming convention, or it could (with the right syntax) be a namespace prefix that identifies the mf set of functions, or it could be dropped altogether as long as the function names didn’t clash with existing XQuery function names. In this example, mfand-contains is a first-class XQuery function, and its arguments – “dog”, “cat” – are just regular XQuery strings. The drawback of this approach is obvious – instead of two functions with many operators (inside a sublanguage), this approach yields many functions. The maximum number of functions needed is twice the number of operators in the sublanguage, i.e., one function for each operator for contains, plus one function for each operator for ranking. However, on closer inspection it becomes clear that only combining operations and proximity operations (as described earlier in this section) need a function each, while matching options and word expansions need far fewer functions. Let’s rewrite Example 13-2 to see how this might work in practice.

In Example 13-3, we needed to introduce two functions, mf-sameParagraph-contains and mf-sameParagraph-rank, to express “match these words in the same paragraph,” but we only needed to introduce one function, mf-expand-words, to express stemming and soundex.¹²

Approaches – Summary

In this section, we described three alternative approaches to extending XQuery and XPath to do Full-Text search – objects, functions, and many-functions. The ability to do Full-Text queries is extremely important to XQuery – some might even say that XQuery without Full-Text is not a viable language. Some of the database and query vendors clearly appreciate this importance, and they have not waited for the W3C spec to become a Recommendation before implementing XQuery Full-Text in some form. As you will read in Section 13.2.6, the functions and many-functions approaches have already been implemented by at least one vendor.

In the next section, we look at the approach currently being pursued by the Full-Text Task Force of the W3C XQuery Working Group. We expect this will be part of some (near-)future XQuery spec.

1. A string literal – “dog”

2. A string literal with more than one word – “Mother Mary comes to me”

3. A sequence of strings – (“Mother Mary comes to me”, “Speaking words of wisdom”, “Let it be”)

4. A variable – $myVariable

5. The context item –. (“dot”)

6. A built-in function – string-value (. /title [1])

7. A user-defined function – myFunctions:getUserInput()

8. An expression enclosed in {} –

    {for $i in collection (myRules/rule) return rule/searchTerms}

• “any” – each member of the sequence is interpreted as a phrase, and the FTContains expression evaluates to true if there is a match for any (that is, at least one) of those phrases in the text being searched.

• “all” – each member of the sequence is interpreted (again) as a phrase, and the FTContains expression evaluates to true if there is a match for all (that is, every one) of those phrases in the text being searched.

• “phrase” – the sequence is flattened into a single string (the strings are concatenated, with whitespace in between). The FTContains expression evaluates to true if there is a match for that new string, treated as a phrase, in the text being searched.

• “any word” – the sequence is flattened into a single string, and FTContains evaluates to true if any word in that new string matches a word in the text being searched.

• “all words” – the sequence is flattened into a single string, and FTContains evaluates to true if each word in that new string matches at least one word in the text being searched.

• FTOrderedlndicator – “… ‘dog’ && ‘cat’ ordered …” matches text that contains both “dog” and “cat,” where “dog” comes before “cat.” If this option is “unordered” (the default), the order of the words in the text does not affect the match.

• FTWindow – “… ‘dog’ && ‘cat’ window exactly 5 words …” matches text that contains both “dog” and “cat” within a window of 5 words. The unit can be “words,” “sentences,” or “paragraphs.” All three units are implementation-dependent (they are part of the tokenization process). The window option is a shorthand for a common form of distance (see next item) – i.e., any expression using window could be rewritten using distance.

• FTDistance – “… ‘dog’ && ‘cat’ distance exactly 5 words …” matches text that contains both “dog” and “cat” exactly 5 words apart (i.e., with exactly 5 intervening words). The unit of distance can be “words,” “sentences,” or “paragraphs.” The distance can be specified “exactly,” as a minimum distance (“at least 3 words”), a maximum distance (“at most 7 words”), or as a range (“from 3 to 7 words”).

• FTTimes – “… ‘dog’ occurs at least 3 times …” matches text that contains the word “dog” at least 3 times. You can also specify an exact number of occurrences (“occurs exactly 5 times”), a maximum number of occurrences (“occurs at most 7 times”), or a range (“occurs from 3 to 7 times”).

• FTScope – “… ‘dog’ && ‘cat’ same sentence …” matches text that contains both “dog” and “cat” in the same sentence. The possible units for FTScope are “sentence” and “paragraph.”

• FTContent – “… ‘dog’ at start …” matches text that contains “dog” at the beginning (i.e., “dog” is the first word in the text). You can also specify that the word must be the last word in the text (“at end”), or that the word (or phrase) must match the entire content of the text being searched (“entire content”).

• FTCaseOption – “… ‘Dog’ case sensitive …” matches text that contains the word “Dog” with an uppercase “D” and lowercase “og.” Other options are “lowercase” or “uppercase” (convert the query term to lowercase/uppercase before attempting to match it) and “case insensitive” (do not take case into account when attempting to match the query term).

• FTDiacriticsOption – “… ‘résumé’ diacritics insensitive …” matches text that contains “résumé without taking diacritics into account (e.g., “resume” will match). As well as the diacritics options “sensitive” and “insensitive,” you can specify “with diacritics” or “without diacritics.”¹⁵

• FTStemOption – “… ‘dog’ with stemming …” matches text that contains any word with the same linguistic root as “dog” (“dog” or “dogs”).

• FTThesaurusOption – “… ‘dog’ with thesaurus at ‘http://example.com/myThesaurus.xml’ relationship ‘BROADER TERM’ at most 2 levels …” matches text that contains “dog” or “canine” or “mammal.” Possible relationships include at least those defined in the ISO 2788 Thesaurus standard,¹⁶ but there may be additional (implementation-defined) relationships. For hierarchical relationships, you can also specify an exact/minimum/maximum/range of levels to be considered.

• FTStopwordOption – “… $q with stop words …” matches text that contains any word in $q, ignoring any stop words (words that have been defined by your implementation to be “noise words”).

• FTLanguageOption – “… ‘dog’ with language ‘Russian’ …” tells the query processor that the query language is “Russian.” This may affect the way case, diacritics, thesaurus, and stemming options are processed.

• FTWildCardOption – “… d.*g with wildcards …” matches text that contains any word that starts with a “d,” ends with a “g,” and has zero or more characters in between. If the option is “without wildcards” (the default) then “d.*g” is interpreted literally. Other possible wildcard designators are “.?” (zero or 1 characters), “.+” (one or more characters), or, e.g., “{3, 7}” (from 3 to 7 characters).

Score

We will not give a full description of score here, as the definition of score is likely to change significantly. The current draft spec shows score as a (second-order) function, taking as its argument a Boolean combination of FTContains expressions. Another possible approach is to make score a clause in the FLWOR expression (a bit like a let clause), binding a variable to the (second-order) evaluation of some FTContains expressions combined with the XQuery and or or. The relative importance of terms in the query is set by the weight operator in the right-hand side of the FTContains expression(s). The grammar for a score clause might look like this:

Some XQuery Full-Text Examples

Example 13-5 is a very simple XQuery Full-Text query that returns the year of every movie with “werewolf” in the title. Note that the query does not include any match options, so, e.g., case sensitivity, stemming, and stop words are all defaulted.

Example 13-6 is a less simple example. In this example we assume an additional element in the movies data sample, a description, and we assume that a variable $myInput exists, representing some input typed by a user.

The query in Example 13-6 returns the titles of all movies that are about American werewolves, according to some additional criteria, ordered by their American werewolf-ness. Let’s start with the where clause – there are three criteria here, and if a movie meets any of those criteria it will get into the results set.

So much for defining what goes into the results set. Now, in what order should we deliver the results? We use the score clause to calculate a relevance score, and then we order the results using the order by clause. Note that we could just repeat the whole query as part of the score clause, but we have decided we want to rank the results based on different criteria than the ones used to decide which movies appear in the results set. We want movies with “werewolf” in the title to appear very high in the results, and we want movies with “american” in the title to appear somewhat high in the results. We also want movies with either of those words in the description to get a slight boost. That’s all we can say about this query – we cannot predict the score for any particular movie, for the scoring algorithm and the effect of weights are implementation-defined. Note that the two FTContains expressions in the score clause are ored together, using the XQuery or and not the Full-Text | |. That’s because the score clause binds a variable to some set of (second-order) FTContains expressions, combined with the XQuery Boolean and or or.

Our last example is an XPath example. The Full-Text extensions are designed to be useful as part of XPath 2.0 as well as XQuery 1.0. Example 13-7 produces a sequence of titles of movies whose description contains either “American” at the start of the description or “werewolf” at least 3 times in the description.

If you want to try out some examples for yourself, we recommend going to the W3C’s XQuery home page and following the link to the XQuery Full-Text Test page.¹⁷ Here, you can type in an XQuery Full-Text expression and see its parse tree (though not its results). This is an excellent way to check the syntax of any XQuery and to get a feel for how XQueries are parsed.

Semantics

We cannot leave this section without mentioning the semantics part of the XQuery Full-Text Language and Semantics spec. A great deal of care and effort have gone into formally defining the semantics of those parts of the XQuery Full-Text language that can be formally defined – i.e., those parts that are not implementation-defined. This formal definition is an important part of the spec, but we prefer to use these formal semantics as a safety net, to help us figure out what behavior is expected when the descriptive sections are incomplete or unclear.¹⁸ We urge the interested reader to browse the semantics section of the spec, especially if she intends to build an XQuery Full-Text engine. (The XQuery Full-Text semantics section is rather dense. As an introduction to the concepts used in describing the XQuery Full-Text semantics, you might want first to read the TexQuery paper¹⁹ on which it’s based.)

Definition of score

XQuery Full-Text has two major parts. FTContains is a Boolean expression with a precise definition.²⁰ score is a way of measuring the relevance of each result to the query – for each match, just how good a match is it? The XQuery Full-Text Language spec gives a lot of detailed semantic definition to say exactly what should be the result of the evaluation of any particular FTContains expression. But what can we say about score?

Certainly we must define the data type that results from the evaluation of score – XQuery is a strongly typed language, and we need to know whether score results in an integer or a float. It’s fairly clear that we should also define the range of possible values for score; otherwise, scores from different implementations cannot be compared. But what does the value of the score actually mean? At the time of writing, the score clause binds a value to a variable, and that value must be of data type xs:float, in the range [0, 1]. So far, so good, but with this definition I could build an XQuery Full-Text engine that always returns 0 (or 1, or 0.5, or …) for score and claim compliance with the spec.

The spec also says that for “score values greater than 0, a higher score must imply a higher degree of relevance.” Yet relevance is implementation-defined, and it is in any case highly subjective. We believe this is a good rule to have, but it can only be followed in spirit (and not to the letter).

Then there is the question of the relationship between the value of score and the Boolean value of FTContains for the same query over the same data. Should a score of 0 imply that FTContains is false? Conversely, should an FTContains value of false imply that the score is 0? This is currently noted as an issue – we believe that, for now, the value of score and ftcontains should not be bound together.

Finally, there is the notion of score using second-order functions. Informally, a second-order function is one that has to be processed as a string, not one that can be evaluated immediately. In the current XQuery Full-Text spec, the score clause binds a variable to an expression. But this is no ordinary expression – a query processor cannot evaluate that expression on its own and then substitute the result in the query. The expression is always an FTContains (or a series of FTContains expressions combined using and or or), which would always evaluate to a Boolean. Rather, the processor has to consume this special expression as if it were a string – “what would the score be for a query that consisted of just these FTContains expressions?” XQuery has so far avoided second-order functions, so the current score clause is something “special.”

How Standard?

The questions around score (earlier) bring up the question of just how “standard” XQuery Full-Text can possibly be. The basic algorithms for calculating score, and hence ranking results by relevance, are well known – we have described Salton’s algorithm and PageRank elsewhere in this book (see Chapter 18, “Finding Stuff”). But search engine vendors generally add their own “secret sauce” to these algorithms, each claiming that its engine gives better ranking than any other. That means that we cannot standardize the semantics for score²¹ – it has to be implementation-dependent.

Similarly, tokenization – the exact method for breaking Full-Text down into tokens (usually words) – is implementation-dependent. So an XQuery Full-Text engine can choose to tokenize text, for example, so that the tokenized output contains the stemmed values for each word in the text (all words with the same linguistic root as each word in the text). Such a tokenizer would result in every XQuery Full-Text search being a stemmed search, even though the spec says that stemming is optional and that the default is not stemmed.

Add to this list thesaural search (the contents of thesauri are not standardized) and stemming (the semantics of stemming is not defined), and it’s clear that two compliant W3C XQuery Full-Text engines could give a wide range of results for the same query.

We believe that it is worthwhile to standardize the syntax of Full-Text search. While some would argue that we should stop there, we also believe that it is worthwhile to standardize the semantics of Full-Text search as much as possible, though we must also recognize the limitations of this approach.

Delineating Embedded XQuery Expressions

One of the goals of the W3C XQuery Full-Text language is that Full-Text operations should be a first-class part of the XQuery language. That means we need to be able to mix Full-Text and other kinds of expressions freely in a query. It’s difficult to do that unless you know where the Full-Text productions apply and where the XQuery productions apply. The easiest way out of this dilemma is either to introduce a new kind of parentheses that enclose a Full-Text expression (actually an FTSelection, the right-hand side of a Full-Text expression), or to introduce a new kind of parentheses that enclose an XQuery expression when it occurs inside an FTSelection. At the time of writing, XQuery Full-Text uses “{}” to enclose an XQuery expression inside an FTSelection, but this may change.

Defining Query Options Indirectly

It should be clear to the reader by now that a Full-Text query has a lot of options – the language, thesaurus (or thesauri), stopword list(s), etc., that provide the context of a matching operation. Some of these options can be fully described as part of the query – e.g., the language – but others cannot – it’s not practical to reproduce a 300-word stopword list or a 10,000-term thesaurus as part of each query. That means we need a mechanism to describe some options indirectly – “I want to use the English maritime stopword list and the English pharmaceuticals thesaurus for this query.” Possibly, we also need a mechanism for defining those pointers (“When I say English maritime stopword list, I mean the following words …”). Probably, we need some mechanism for setting defaults, e.g., the default thesaurus to use, in the query prolog.

API vs. Solution

When looking at the progress of XQuery Full-Text, we should draw a clear distinction between a Full-Text API and a Full-Text solution. It is the API that should be standardized – a set of low-level functions and/or expressions that can be used as building blocks for real-world solutions. Any suggestions that higher-level functionality (such as the best way to search across enterprise documents) should be standardized are to be resisted.

IBM, Microsoft

Neither IBM nor Microsoft has, at the time of writing, announced plans to support W3C XQuery Full-Text. Both have been active on the task force (as can be seen from the list of editors’ affiliations), so they may well implement XQuery Full-Text when it becomes part of the standard.

Microsoft currently recommends using SQL Server’s Full-Text indexing capabilities to create a Full-Text index on XML documents, and doing Full-Text search to prefilter documents before applying XQuery.²² This approach is better than nothing, but it’s a long way from XQuery Full-Text – it only allows you to search across whole XML documents (minus element tags and attributes).

We haven’t managed to find any information on IBM’s plans in this area. IBM does offer Full-Text search in a number of its products, and they are active on both the XQuery Working Group and the XQuery Full-Text Task Force, so we look forward to hearing about their XQuery Full-Text product plans.

Oracle

Like Microsoft, Oracle also provides Full-Text search as part of its database. But the Oracle Text index, and its operators CONTAINS and SCORE, are XML-aware – it’s possible to search for a text query expression (words and phrases combined with Booleans, stemming, thesauri, fuzzy match, etc.) either WITHIN a specified element or attribute or in an XPath (INPATH). Oracle’s CONTAINS follows the spirit of the SQL/MM spec – that is, it’s a function that takes two arguments, a column name and a string containing a text query expression (describing what you are searching for). The text query expression language does not follow SQL/MM exactly, but it does provide an equally rich set of features.

Oracle’s XQuery implementation also includes a vendor-defined extension function, ora:contains, that provides Full-Text search as part of XQuery or XPath. The ora : contains function follows the “functions” approach described earlier in this chapter – that is, it’s a single function that takes in a node or item (what to search over) and a string representing the text query (what to search for) and returns a Boolean (matched or not matched).

These two approaches represent the classic “Who’s on top?” dilemma for Full-Text search over XML in a mixed environment.²³ Is it better to express the query as “dog and cat within/movies/movie/title” – making Full-Text “on top” and restricting the results with an XPath? Or is it better to express the query as “/ movies/movie/title[. ora:contains “dog and cat”] “ – making the XPath “on top” and describing the Full-Text search on individual elements? With Oracle’s CONTAINS and ora:contains, you can do either. In fact, you can do both – and combining CONTAINS and ora:contains in the same query gives you a lot of the benefits of XQuery Full-Text without having to wait for a W3C XQuery Full-Text Recommendation. ora:contains can be used in any of Oracle’s SQL/XML or extension functions that use XPath, so, for example, you can locate a document using CONTAINS and then pull out the interesting parts of that document using extractNode ( ) with an XPath argument that uses ora : contains.²⁴

In the latest version of Oracle’s database, Oracle has implemented a pre-Recommendation version of XQuery, callable via the SQL/XML extension functions XMLQUERY and XMLTABLE. The ora:contains XPath function can be used as part of an XQuery in either of those functions to provide XQuery Full-Text in a SQL context – see Example 13-8.²⁵

Mark Logic

Mark Logic²⁶ has implemented a variation on the “many-functions” approach described earlier in this chapter. The MarkLogic Content Server includes an XQuery implementation extended with a set of functions for Full-Text search. The MarkLogic Server supports a function cts:search($searchable-expression, $search-query). cts:search is similar to Oracle’s ora:contains, except that the second argument can be made up of other cts functions. There is one function to perform a simple word or phrase search (cts:word-query); one function for each of the combining operations (cts:and-query, cts:or-query, cts:and-not-query, cts:not-query); plus one function to describe proximity operations (cts:near-query). An optional argument to these functions allows you to specify matching options and word expansions (case sensitivity, punctuation sensitivity, stemming, wildcards, and language).

With this compromise – using arguments rather than functions to represent matching options and word expansions – the number of functions is kept manageable, but the language is fully integrated with XQuery. There is no string argument that represents an opaque sublanguage, so any of the query terms can be derived from XQuery expressions. One could argue that this is more composable than the grammar extension approach – in this many-functions approach, the matching options and word expansions are strings, which could presumably be derived from XQuery expressions, while in the grammar extension approach they are language keywords, which cannot.

Mark Logic claims their XQuery Full-Text functions map closely to the functionality in the W3C XQuery Full-Text working drafts, providing a lower-level API that can be used to implement the W3C XQuery Full-Text functionality when it becomes a Recommendation. See Example 13-9 for examples of W3C XQuery Full-Text queries and their equivalents using the Mark Logic language.

The Mark Logic language does have some differences in approach (as opposed to merely differences in surface syntax) from the W3C working draft. Most important, in the Mark Logic language, score is implicit – i.e., the cts:search function returns results implicitly ordered by score. This makes the queries shorter, at the cost of some control. And there are some detailed differences, representing shortcuts – e.g., if a query term is in all-lowercase, it has case-insensitive matching options by default; if it is in mixed-case or uppercase, it has case-sensitive matching options by default. These differences aside, Mark Logic’s language is an important step in the direction of XQuery Full-Text.

Usage Scenarios

The first thing found in the Requirements is a statement of the XML update usage scenarios that the Working Group believes it is necessary to address. (“Usage scenarios” are not the same thing as “use cases,” the latter being more detailed. No use cases have been published for the XQuery update facility at the time of this writing.) The scenarios are:

General Requirements

The Requirements include a number of items that don’t fit neatly into any of the other categories discussed in this section, but that are seen as overall requirements for the XQuery Update Facility. They are:

Relationship to XQuery 1.0

The XQuery Update Facility’s relationship to XQuery itself has implications on the design of the Update Facility.

XML Query Update Functionality

This set of requirements identifies the specific capabilities that the XQuery Update Facility must have in order to be useful.

Transaction Characteristics

Whenever multiple changes are made to data, there is a need to ensure that the end result is consistent with the intent of those changes. Most data management systems provide some sort of transaction capability to provide that consistency. A popular and widely respected book³⁰ uses the term ACID to describe the properties of transactions.

• Should there be a concept of an XQuery “program,” analogous to XQuery modules, in which update statements are allowed?

• Should XQuery functions be allowed to contain update statements or expressions? If so, should there be explicit syntax to mark, in XQuery library modules, the signatures of such functions as having side effects?

• Should there be explicit syntax for starting and terminating a sequence of update operations that are intended to function as an atomic unit (such as a SQL’s START TRANSACTION and COMMIT/ROLLBACK statements that start and terminate transactions), or should that be done by some other facility (such as a transaction manager external to the XQuery implementation)?

• What implications are caused by update expressions or statements on the declarative nature of XQuery as a whole? What kinds of rules might be required to limit the ability of implementations to “reorder” the evaluation of expressions based on the presence of update operations?

Oracle

Oracle, like the other implementers discussed in this chapter, does not support an XQuery syntax-based approach to updating XML documents. Instead, Oracle provides three mechanisms for responding to users’ needs in this area. Applications must choose between the three strategies and cannot, for example, locate and retrieve data using one technique and update it using another.

One approach is a DOM-based API (part of Oracle’s XMLDB), which requires programs to invoke methods on a DOM object representing an XML document. That API is based on the W3C’s Document Object Model,³¹ which provides methods for traversing the DOM representation of an XML document, retrieving values from desired nodes, and updating the document by inserting nodes, deleting nodes, modifying the values of nodes, and so forth.

A second approach is a Java API that defines a class to represent the XML type, along with methods such as deleteXML(), insertXML( ), and updateXML( ). The Java API is heavily used by Oracle’s customer base, and it is likely to be augmented by the emerging XQJ (XQuery API for Java^™) API³² under development in the Java Community Process. You’ll read more about XQJ in Chapter 14, “XQuery APIs.”

The other approach, more directly related to XQuery, is based on SQL/XML (about which you will read in Chapter 15, “SQL/XML”). In SQL/XML, applications use ordinary SQL statements to access XML data stored as values of the XML type in columns of database tables. A SQL function, XMLQuery ( ), allows applications to evaluate XQuery expressions against those XML values. Oracle extensions³³ to SQL/XML provide the ability to update those XQuery expressions. The extension functions are:

Unfortunately, Oracle’s extension functions are not true update functions, in that they do not update an XML value “in place.” Instead, they are really transformation functions that return an updated copy of the value on which they operate. Therefore, they are side effect-free functions. When used in a context (such as a SQL UPDATE statement) where values are being replaced, then these functions have the semantics of update functions.

Similar functions are provided by Oracle in their XML SQL Utility (SMU), which is part of their PL/SQL language.

We would anticipate that, once an XQuery Update Facility has been defined in the W3C, Oracle would update their XQuery implementation to support the Update Facility, in addition to the other strategies they already provide for updating XML.

IBM

At the time of writing, IBM had not yet released an XQuery implementation. Naturally, they have not released an XQuery update capability either.

IBM has, however, offered a tool that “provides an XML view of relational tables and a query of those views as if they were XML documents.” This tool, named XML for Tables, is available³⁴ on IBM’s alpha Works site. The tool, which implements a subset of XQuery, translates XQuery expressions into SQL expressions that are executed by DB2. The tool does not, however, appear to have any ability to update the data behind those XML views.

IBM has frequently indicated that a future version of DB2 will support XQuery directly. Presumably that support will include XQuery updating capabilities at the same time. We presume that IBM will add support for the XQuery Update Facility when that spec has been finalized.

Microsoft

Microsoft’s SQL Server 2005 provides an implementation of (a subset of) XQuery. As part of that implementation, they have built some extensions that support XML updates. Unlike Oracle, these extensions do not depend on SQL/XML capabilities, but are provided through a method operating on instances of their XML type.

That method, modify ( ), is invoked as part of the SET clause of a SQL UPDATE statement. The parameter of the method is a character string that expresses one of several types of updates, including insert, replace value of, delete, etc., as well as an XQuery expression that identifies the nodes to be modified and the values to be used for the modifications.

Microsoft provides a set of .NET classes used with XML. Some of these classes provide a wide variety of methods that support setting the values of nodes, inserting nodes into specified locations, deleting nodes, and replacing nodes. These classes and their methods are unrelated to XQuery, but they serve roughly the same function as the classes and methods of Oracle’s DOM-based API.

Microsoft offers yet another approach to updating XML, based on a facility they call updategrams. An updategram “represent[s] changes to an XML instance that, when combined with an annotated schema, persist these changes back to relational changes.”³⁵ Updategrams are defined to be XML documents using a specific vocabulary that captures updates to the (relational) data that underlies an XML view.

The vocabulary uses elements <before> and <after> as children of a <sync> element. Each <sync> element represents a single update to the XML view, with the <before> and <after> elements providing the values of the “existing” state of the data being updated and the new value resulting from the update, respectively. If a particular <sync> element contains a <before> element and not an <after> element, it represents a deletion of data; the presence of an <after> and not a <before> element indicates an insertion, and the presence of both corresponds to a modification of existing data. (Some observers suggest that an updategram is, in effect, isomorphic to a change log that records actions taken to update such data.)

As the XQuery Update Facility reaches its final development stages, we expect that Microsoft will enhance SQL Server’s XQuery support to align with the Update Facility specification.

Mark Logic

The MarkLogic Content Server includes an XQuery implementation extended with a set of functions for update. The functions are:

The MarkLogic Server evaluates an XQuery module by spawning an evaluation thread that operates on a snapshot of the database. All the updates appearing in the module are collected, and a change vector (i.e., a time-ordered list of changes) is computed and journaled. The XQuery module has an implied commit that guarantees that either all the changes or none of the changes become persistent.

Mark Logic update evaluation guarantees atomicity, isolation, and durability. Consistency is satisfied, but only in a relatively weak sense, since integrity constraints are not explicitly part of the Mark Logic architecture. Integrity is expressed via denormalized documents: All the elements collected in one document are maintained as a consistent collection. Isolation is maintained in the strongest sense: Each query evaluation thread operates on a static snapshot, and all the updates refer to the original values, even if an update subexpression modifies one of the values appearing elsewhere in the XQuery module

In addition, the MarkLogic Server implements the WebDAV protocol and therefore a complete document properties infrastructure. Updates to document properties are expressed using the following functions:

XUpdate

We’ve seen how four data management vendors are dealing with XML update requirements today. It’s also worth mentioning another sort of standards activity in the open source community: XML:DB is “an industry initiative … [that] provides a community for collaborative development of specifications for XML databases and data manipulation technologies.” It also provides open source reference implementations of their specifications.

Among the specifications being developed by XML:DB is one named “XUpdate.” (Perhaps “has been developed” would be more appropriate, as the latest draft’s date would suggest.) The most recent draft of the XUpdate specification³⁶ is dated 2000-09-14, but there continues to be a certain amount of industry buzz about XUpdate and its applicability to the strong requirement for a language to update XML documents.

XUpdate instructions are in the form of an XML document that contains elements in the xupdate namespace (http://www.xmldb.org/xupdate). XUpdate uses XPath 1.0 as the expression language used to select XML nodes for further processing by the instructions embedded in those elements. Each update must be enclosed in an <xupdate:modifications> element. The update elements themselves are:

Most of these update elements correspond very closely to the kinds of updates supported by Oracle’s and Microsoft’s approaches and to the W3C’s requirements for an XQuery Update Facility. In fact, one might argue that XUpdate’s syntax is reasonably analogous to Microsoft’s updategrams.

<xupdate : append>, <xupdate : insert-after>, and <xupdate : insert-before> may have child elements: <xupdate : element>, <xupdate : attribute>, <xupdate : text>, <xupdate : comment>, and <xupdate : processing-instruction>.

<xupdate:update> has a select attribute containing an XPath expression that identifies the node set to be updated. The content of the <xupdate:update> element supplies the new content of the elements in the identified node set.

<xupdate:remove> has a select attribute containing an XPath expression that identifies the nodes to be removed.

<xupdate:rename> has a select attribute containing an XPath expression that identifies a set of element or attribute nodes (the other node types are not allowed). The content of the <xupdate:rename> element provides the new name of the identified nodes.

<xupdate:variable> has two attributes: name (which specifies the name of the variable being created) and select (which specifies the value assigned to that variable). The value of a variable is obtained through the use of the <xupdate:value-of> element, whose select attribute provides the name of the variable whose value is wanted. <xupdate:value-of> can be used in other situations as a child element, where it provides a value to be used in evaluating that child element. The syntax and semantics of these elements are similar to those of the analogous variable declaration facility in XSLT (<xsl:variable> and <xupdate :value-of>). <xupdate:variable> and <xupdate:value-of> have no obvious correlation to anything in the update facilities of the vendors we’ve surveyed in this section.

The XUpdate specification has a heading for Conditional Processing, but there is no content under that heading. However, the XUpdate DTD indicates that the <xupdate:if> element has an attribute named test, whose content must be a Boolean expression, that determines whether or not the contents of the <xupdate:if> are evaluated. The contents of the element can be any mixture of text and child elements <xupdate:element>, <xupdate:attribute>, <xupdate:text>, <xupdate:processing-instruction>, and <xupdate:comment>.

A Google search for XUpdate turns up over 30,000 references, many of which describe implementations of the incomplete five-year-old specification. While XUpdate contains some very useful ideas and has received some industry attention, we don’t believe that it is a long-term solution to the problem of integrating XML updating facilities into XQuery. The primary difficulty is that XUpdate uses an XML syntax instead of XQuery’s more user-friendly syntax. Another, less critical, reason is that the specification is incomplete in several ways: The syntax and semantics of some elements are not specified at all, and the descriptions of the other elements are imprecise and can be interpreted by different implementers in different ways.