=Paper=
{{Paper
|id=Vol-256/paper-10
|storemode=property
|title=A Method for Evaluating Full-text Search Queries in Native XML Databases
|pdfUrl=https://ceur-ws.org/Vol-256/submission_17.pdf
|volume=Vol-256
|dblpUrl=https://dblp.org/rec/conf/syrcodis/Pastukhov07
}}
==A Method for Evaluating Full-text Search Queries in Native XML Databases==
https://ceur-ws.org/Vol-256/submission_17.pdf
A Method for Evaluating Full-text Search Queries in Native
XML Databases
Roman Pastukhov
Institute for System Programming of the Russian Academy of Sciences
ignatich@mail.ru
Ph.D. advisor: Grinev M. N.
Abstract
2 Related work
In this paper we consider the problem of
efficiently producing results for full-text The recent increase in the number of XML repositories
keyword search queries over XML documents. [4] has motivated extensive work on designing
We describe full-text search query semantics languages for XML full-text search [5, 6, 7, 8, 9].
and propose a method for efficient evaluation There has been extensive research in information
of keyword search queries with these retrieval on the efficient evaluation of full-text queries
semantics suitable for native XML databases. [3], including structured full-text queries [10] and of
Method uses inverted file index which may be XML queries such as XQuery/IR [11], XSEarch [5],
efficiently updated when a part of some XML XIRQL [7], XXL [8] and Niagara [12]. However, these
document is updated. works develop algorithms for specific full-text
predicates in isolation.
1 Introduction The idea of computing the most specific elements
for conjunctive queries has been actively explored using
One of the main features of XML databases is ability to deepest common ancestors [13, 14, 15]. We extend this
store semi-structured data as well as structured data. idea to support the efficient evaluation of queries with
XQuery and XPath languages allow addressing parts of complex full-text predicates.
XML documents and querying them. These languages
are convenient for querying regularly structured data. If 3 Data Model & Query Semantics
data is semi-structured or its structure is unknown
making queries using these languages becomes difficult.
In such cases it is easier to use keyword search queries. 3.1 XML Data Model
One of the key advantages of keyword search queries is The eXtensible Markup Language (XML) is a
its simplicity – users do not have to learn a complex hierarchial format for data representation and exchange.
query language and can issue queries without prior An XML document consists of nested XML elements
knowledge about the structure of the underlying data. starting with root element. Each element can have
Keyword searching over XML introduces new attributes and text values, in addition to nested sub-
challenges. The result of a keyword search query is not elements.
always the entire document, but can be a deeply nested
XML element. In general XML keyword search results 3.2 Full-text Search Query Semantics
can be arbitrarily nested elements, and returning the
“deepest” node containing the keywords usually gives Full-text search queries concerned in this paper are
more context information (see [1, 2]) composed of keywords and four operations –
In this paper we describe semantics of full-text conjunction, disjunction, proximity and order.
queries over XML documents and a method for Conjunction and disjunction operations combine several
evaluating such queries in an XML database system that (at least 2) sub-queries into a single query. Proximity
supports XQuery data model [3]. and order operations are applied to a single query to
produce another query.
Consider a query Q consisting of several keywords
and a mapping M that maps some of these words to
occurrences of these words in an XML document. If Q
has a sub-query q than M|q denotes a restriction of M to
Proceedings of the Spring Young Researcher's the set of keywords in q. Lets define a predicate
Colloquium On Database and Information Systems matches(Q, M) to be true when one of the following
SYRCoDIS, Moscow, Russia, 2007 conditions is true:
01 Op-And(lists)
02 Current_match[i] = for all i = {0, …, lists.count - 1}
03 while lists are not completely processed:
04 Choose i, such that lists[i] is the list with the lowest numbering scheme
number;
05 Elem = lists[i].next;
06 If nodes in current_match have no common ancestor with elem:
07 If all lists in current_match are not empty:
08 Put values from current_match to output stream
09 Current_match[i] = for all i = {0, …, lists.count - 1}
10 Add elem to current_match[i];
12 If all lists in current_match are not empty:
13 Put values from current_match to output stream;
Listing 1
01 Op-Or(lists)
02 while lists are not completely processed:
03 choose i, such that lists[i] is the list with the lowest numbering scheme
number;
04 output l[i].next to the output stream;
Listing 2
• If Q is a single keyword and M has a mapping occurrences (including position of word in node text) in
for this word. nodes along with their identifiers and numbering
• If Q is a conjunction query with sub-queries scheme labels.
S={q0, q1, … , qn} and {∀q∈S | matches(q, A numbering scheme assigns a unique label to each
M|q)} node of an XML document according to some scheme-
• If Q is a disjunction query with sub-queries specific rules. The labels encode information about
S={q0, q1, … , qn} and {∃q∈S | matches(q, relative position of the node in the document. Thus, the
M|q)} main purpose of numbering scheme is to provide
• If Q is a proximity query with distance d and mechanisms to quickly determine the structural
sub-query q, such than matches(q, M) is true relationship between a pair of nodes.
and the maximal distance between the words in Most native XML databases use some sort of
image of M is no more than (d-1). numbering scheme.
We will require numbering scheme to provide these
• If Q is an order query with sub-query q, such
mechanisms:
that matches(q, M) is true, M is injective and
(1) determining ancestor-descendent
the order of the words in q matches the orders
of their images defined by M. relationship between to nodes;
The result of query Q consists of elements E such (2) comparing nodes by document order;
(3) determining whether two nodes have a
that E is the “deepest” common ancestor of image of
common ancestor;
some mapping M that makes predicate matches(Q, M)
true. Practically every numbering scheme used in native
XML databases provides mechanisms (1) and (2). If it
doesn’t provide mechanism (3) we can easily modify it
4 Query processing by adding document root identifier to numbering
In order to evaluate the result of a query Q we will scheme labels. This modified numbering scheme will
translate this query into a query plan tree. Each node provide mechanism (3).
corresponds to one of the four operations (conjunction,
disjunction, proximity or order), leaves correspond to 4.2 Data used by operations
keywords in the query and edges correspond to relations To represent a list of all matches that is transferred
between queries and sub-queries. between operators we will use tuples that consist of lists
Each operator node receives a list of all matches of word occurrences similar to the contents of inverted
from its child nodes and produces a result to its parent. files in the index. Operators in the query plan tree
Output of the root operator (corresponding to the leaves corresponding to keywords in the query will
whole query) is transformed to a set of nodes. simply read an inverted file for this word and return
tuples consisting of a single list describing some node
4.1 Index structure and word positions of the keyword in the text of this
To allow efficient query evaluation we will use an node. Just like inverted files, lists in tuples contain
inverted index which contains a list of all word numbering scheme labels for nodes.
01 Op-Order(list)
02 while list is not completely processed:
03 elem = list.next;
04 if elem.width == 1:
05 put elem to output stream;
06 else:
07 create a list ord_list of all word occurrences in lists of elem along with
list number (list contains pairs ) in document order;
08 initialize array of pointers to ord_list p, to make p[i] point to the first
occurrence of a word from elem’s i’th list, which is after p[i-1] in the ord_list
(for i>0);
09 p[n] points to the end of ord_list, n = elem.width
10 while all elements of p are defined:
11 output tuple i’th list of which consists of elements of elem’s i’th list
between p[i] and p[i+1] in ord_list;
12 p[0] = first element belonging to 0’th list which is after p[1] in
ord_list;
13 for each i in [1..n-1]:
14 p[i] = first element belonging to i’th list which is after p[i-1] in
ord_list;
Listing 3
If a tuple consists of n lists, then we will say that
width of this tuple is n (denoted as t.width in the 4.5 Order operation
pseudo-code, here t is a variable referencing some Order operation filters tuples returned by its sub-query
tuple). operator, so that all word occurrences in matches are in
A tuple represents a set of matches that is Cartesian the correct order (it’s always corresponds to the orders
product of sets of word occurrences in each list (i.e. if of lists in tuple). This may split one tuple into several
we choose one word in each list of a tuple we will get tuples. Pseudo-code for this operation is shown in
one of the matches represented by this tuple) listing 3.
All nodes in a tuple always have a common
ancestor. Tuples in an output stream of some operator
are returned in the document order of their respective 4.6 Proximity operation
“deepest” common ancestors of nodes in each tuple.
Proximity operation filters tuples returned by its sub-
4.3 Conjunction operation query operator, so that all word occurrences in matches
are within a window of specific size. Pseudo-code for
This operator simply combines tuples from its sub- this operation is shown in listing 4.
queries to a single tuple. Pseudo-code for this operation Since we do not have information about indices of
is shown in listing 2. the first word in the nodes, this operator may produce
false matches which should be checked at later stages of
4.4 Disjunction operation query execution by computing exact values of node
Disjunction operation returns all tuples produced by its staring word index array (sw array in the pseudo-code).
sub-query operators in document order. Pseudo-code for This is not needed if all words in the match that need to
this operation is shown in listing 1. fit in some window are in the same node.
01 Op-Window(list, window):
02 while list is not completely processed:
03 elem = list.next
04 if elem.width == 1:
05 put elem to output stream;
06 else:
07 create a list L of all different nodes in elem with a maximal word number
for each node. List is ordered by document order of nodes;
08 for each node U in the list L compute sw[U] as the sum of maximal word
numbers of nodes before node u;
09 while all lists elem[i], i={0..elem.width-1} are not empty:
10 choose word W with minimum S(W) = sw[node that contains W] + the ordinal
number of word W in the text of node;
11 if all lists elem[i], i={0..elem.width-1} contain words W1, such that
S(W1) < S(W) + window:
12 output a tuple that consists of all words W1 from lists of elem, such
that S(W1) < S(W) + window (if word W1 is in i’th list of elem, it will be in the
i’th list of the resulting tuple) to the output stream;
Listing 4
5 Conclusion [12] C. Zhang, J. Naughton, D. DeWitt, Q. Luo, G.
Lohman. On Supporting Containment Queries in
In this article we described semantics for full-text Relational Database Management Systems.
search queries over XML data and proposed query SIGMOD 2001.
evaluation method suitable for native XML databases. [13] L. Guo, F. Shao, C. Botev, J. Shanmugasundaram.
Method uses inverted file indices which can be XRANK: Ranked Keyword Search over XML
effectively updated: if node changes do not affect its Documents. SIGMOD 2003.
ancestor or sibling nodes in the index. [14] A. Schmidt, M. Kersten, M. Windhouwer.
Proposed method allows efficient evaluation of most Querying XML Documents Made Easy: Nearest
full-text queries described in [9]. Concept Queries. ICDE 2001.
[15] Y. Xu, Y. Papakonstantinou. Efficient Keyword
6 Future work Search for Smallest LCAs in XML Databases.
SIGMOD 2005.
Investigating the following problems may lead to
improving the proposed query evaluation method:
• devise an efficient compression method
suitable for proposed inverted file index (and a
fixed numbering scheme);
• add relevance calculation and see how can
index be changed to allow efficient evaluation
of ranked queries;
• if the result of a full-text query will be
presented as a set of nodes, some operations
may not need to return a full set of matches
that include word occurrences, instead they can
return just a set of matching nodes. This may
be used to improve query evaluation
performance;
• see whether the proposed method can be
modified to allow “not“ or “mild not”[9]
queries;
References
[1] N. Fuhr, K. Grobjohann, “XIRQL: A Language for
Information Retrieval in XML Documents”, SIGIR
Conf., 2001.
[2] A. Schmidt, M. Kersten, M. Windhouwer,
“Querying XML Documents Made Easy: Nearest
Concept Queries”, ICDE Conf., 2001.
[3] XQuery 1.0 and XPath 2.0 Data Model (XDM)
http://www.w3.org/TR/xpath-datamodel/
[4] Initiative for the Evaluation of XML Retrieval.
http://inex.is.informatik.uni-duisburg.de/2005/
[5] S. Cohen, J. Mamou. Y. Kanza, Y. Sagiv.
XSEarch: A Semantic Search Engine for XML.
VLDB 2003.
[6] D. Florescu, D. Kossmann, I. Manolescu.
Integrating Keyword Search into XML Query
Processing. WWW 2000.
[7] N. Fuhr, K. Grossjohann. XIRQL: An Extension of
XQL for Information Retrieval. SIGIR 2000.
[8] A. Theobald, G. Weikum. The Index-Based XXL
Search Engine for Querying XML Data with
Relevance Ranking. EDBT 2002.
[9] The World Wide Web Consortium. XQuery 1.0
and XPath 2.0 Full-Text. Working draft.
http://www.w3.org/TR/xquery-full-text/.
[10] E. W. Brown. Fast Evaluation of Structured
Queries for Information Retrieval. SIGIR 1995.
[11] J. M. Bremer, M. Gertz. XQuery/IR: Integrating
XML Document and Data Retrieval. WebDB 2002.