Querying the World Wide Web.
The World Wide Web is a large, heterogeneous, distributed collection of documents connected by hypertext links. The most common technology currently used for searching the Web depends on sending information retrieval requests to index servers. One problem with this is that these queries cannot exploit the structure and topology of the document network. In this paper we propose a query language, Web-SQL, that takes advantage of multiple index servers without requiring users to know about them, and that integrates textual retrieval with structure and topology-based queries. We give a formal semantics for Web-SQL using a calculus based on a novel query locality, that is, how much of the network must be visited to answer a particular query.  Finally, we describe a prototype implementation of WebSQL written in Java.
Introduction
The World Wide Web[BLCL + 94] is a large, heteroge-
neous, distributed collection of documents connected by
hypertext links. Current practice for finding documents
of interest depends on browsing the network by following
links and searching by sending information retrieval
requests to "index servers" that index as many documents
as they can find by navigating the network.
Correspondence to: Alberto O. Mendelzon
preliminary version of this paper was presented at the 1996
Symposium on Parallel and Distributed Information Systems
The limitations of browsing as a search technique are
well-known, as well as the disorientation resulting in
the infamous "lost-in-hyperspace" syndrome. As far as
keyword-based searching, one problem with it is that
users must be aware of the various index servers (over
a dozen of them are currently deployed on the Web),
of their strengths and weaknesses, and of the peculiarities
of their query interfaces. To some degree this can be
remedied by front-ends that provide a uniform interface
to multiple search engines, such as Multisurf[HGN
Savvysearch [Dre96], and Metacrawler [SE95].
A more serious problem is that these queries cannot
exploit the structure and topology of the document net-
work. For example, suppose we are looking for an IBM
catalog with prices for personal computers. A keyword
search for the terms "IBM," "personal computer," and
"price," using MetaCrawler, returns 92 references, including
such things as an advertisement for an "I Bought
Mac" T-shirt and the VLDB '96 home page. If we know
the web address (called URL, or "uniform resource loca-
tor") of the IBM home page is www.ibm.com, we would
like to be able to restrict the search to only pages directly
or indirectly reachable from this page, and stored
on the same server. With currently available tools, this
is not possible because navigation and query are distinct
phases: navigation is used to construct the indexes, and
query is used to search them once constructed. We propose
instead a tool that can combine query with naviga-
tion. The emphasis must be however on controlled navi-
gation. There are currently tens of millions of documents
on the Web, and growing; and network bandwidth is still
a very limited resource. It becomes important therefore
to be able to distinguish in queries between documents
that are stored on the local server, whose access is relatively
cheap, and those that are stored on remote serves,
whose access is more expensive. It is also important to
be able to analyze a query to determine its cost in terms
of how many remote document accesses will be needed
to answer it.
In this paper we propose a query language, WebSQL,
that takes advantage of multiple index servers without
requiring users to know about them, and that in-
Alberto O. Mendelzon, George A. Mihaila, and Tova Milo
tegrates textual retrieval with structure and topology-based
queries. After introducing the language in Section
2, in Section 3 we give a formal semantics for WebSQL
using a calculus based on a novel "virtual graph" model
of a document network. In Section 4, we propose a new
theory of query cost based on the idea of "query local-
ity," that is, how much of the network must be visited to
answer a particular query. Query cost analysis is a pre-requisite
for query optimization; we give an algorithm
for characterizing WebSQL queries with respect to query
locality that we believe will be useful in the query optimization
process, although we do not develop query optimization
techniques in this paper. Finally, in Section
5 we describe a prototype implementation of WebSQL
written in Java. We conclude in Section 6.
Related Work
There has been work in query languages for hyper-text
documents [BK90, CM89, MW93] as well as query
languages for structured or semi-structured documents
Our work
differs significantly from both these streams. None of
these papers make a distinction between documents
stored locally or remotely, or make an attempt to capitalize
on existing index servers. As far as document struc-
ture, we only support the minimal attributes common to
most HTML documents (URL, title, type, length, modification
date). We do not assume the internal document
structure is known or partially known, as does the work
on structured and semi-structured documents. As a con-
sequence, our language does not exploit internal document
structure when it is known; but we are planning to
build this on top of the current framework.
Closer to our approach is the W3QLwork by Shmueli
and konopnicki[KS95]. Our motivation is very similar to
theirs, but the approach is substantially different. They
emphasize extensibility and interfacing to external user-written
programs and Unix utilities. While extensibility
is a highly desirable goal when the tool runs in a known
environment, we aim for a tool that can be downloaded
to an arbitrary client and run with minimal interaction
with the local environment. For this reason, our query
engine prototype is implemented in the Java programming
language [SM] and can be downloaded as an applet
by a Java-aware browser. Another difference is that
we provide formal query semantics, and emphasize the
distinction between local and remote documents. This
makes a theory and analysis of query locality possible.
On the other hand, they support filling out forms encountered
during navigation, and discuss a view facility
based on W3QL, while we do not currently support ei-
ther. In this regard, it is not our intention to provide
a fully functional tool, but a clean and minimal design
with well-defined semantics that can be extended with
bells and whistles later.
Another recent effort in this direction is the We-
bLog language of Lakshmanan et al. [LSS96]. Unlike
WebSQL, WebLog emphasizes manipulating the internal
structure of Web documents. Instead of regular expressions
for specifying paths, they rely on Datalog-like
recursive rules. The paper does not describe an implementation
or formal semantics.
The work we describe here is not specifically addressed
to digital libraries. However, a declarative language
that integrates web navigation with content-based
search has obvious applications to digital library construction
and maintenance: for example, it can be used
for building and maintaining specialized indices and on-line
bibliographies, for defining virtual documents stored
in a digital library, and for building applications that integrate
access to specific digital libraries with access to
related web pages.
2 The WebSQL Language
In this section we introduce our SQL-like language for
the World Wide Web. We begin by proposing a relational
model of the WWW. Then, we give a few examples for
queries, and present the syntax of the language. The formal
semantics of queries is defined in the following section

One of the difficulties in building an SQL-like query
language for the Web is the absence of a database
schema. Instead of trying to model document structure
with some kind of object-oriented schema, as in [CACS94,
95], we take a minimalist relational approach. At
the highest level of abstraction, every Web object is identified
by its Uniform Resource Locator (URL) and has
a binary content whose interpretation depends on its
type (HTML, Postscript, image, audio, etc. Also, Web
servers provide some additional information such as the
type, length, and the last modification date of an object.
Moreover, an HTML document has a title and a text.
So, for query purposes, we can associate a Web object
with a tuple in a virtual relation:
where all the attributes are character strings. The url is
the key, and all other attributes can be null.
Once we define this virtual relation, we can express
any content query, that is, a query that refers only to
the content of documents, using an SQL-like notation.
Example 1. Find all HTML documents about "hyper-
text".
FROM Document d
SUCH THAT d MENTIONS "hypertext"
Since we are not interested just in document content,
but also in the hypertext structure of the Web, we make
hypertext links first-class citizens in our model. In partic-
ular, we concentrate on HTML documents and on hyper-text
links originating from them. A hypertext link is specified
inside an HTML document by a sequence, known as
an anchor, of the form !A HREF=href?label!/A? where
(standing for hypertext reference) is the URL of the
referenced document, and label is a textual description
Querying the World Wide Web 3
of the link. Therefore, we can capture all the information
present in a link into a tuple:
where base is the URL of the HTML document containing
the link, href is the referred document and label is
the link description. 2 All these attributes are character
strings.
Now we can pose queries that refer to the links
present in documents.
Example 2. Find all links to applets from documents
about "Java".
FROM Document x
Anchor y SUCH THAT base = x
WHERE y:label CONTAINS "applet";
In order to study the topology of the Web we will
want sometimes to make a distinction between links that
point within the same document where they appear, to
another document stored at the same site, or to a document
on a remote server.
Definition 1. A hypertext link is said to be:
- interior if the destination is within the source document; 3
local if the destination and source documents are different
but located on the same server;
global if the destination and the source documents
are located on different servers.
This distinction is important both from an expressive
power point of view and from the point of view of the
query cost analysis and the locality theory presented in
Sect. 4.
We assign an arrow-like symbol to each of the three
link types: let 7! denote an interior link, ! a local link
and ) a global link. Also, let = denote the empty path.
Path regular expressions are built from these symbols using
concatenation, alternation (j) and repetition ( ). For
is a regular expression that represents
the set of paths containing the zero length path
and all paths that start with a global link and continue
with zero or more local links.
Now we can express queries referring explicitly to the
hypertext structure of the Web.
Example 3. Starting from the Department of Computer
Science home page, find all documents that are linked
through paths of length two or less containing only local
links. Keep only the documents containing the string
'database' in their title.
2 Note that Anchor is not, strictly speaking, a relation, but a
multiset of tuples - a document may contain several links to the
same destination, all having the same label.
3 In HTML, links can point to specific named fragments within
the destination document; the fragment name is incorporated into
the URL.For example, http://www.royalbank.com/fund.html#DP;
refers to the fragment named DP within the document with URL
http://www.royalbank.com/fund.html. We will ignore this detail
in the rest of the paper.
SELECT d:url; d:title
FROM Document d SUCH THAT
WHERE d:title CONTAINS "database";
Of course, we can combine content and structure
specifications in a query.
Example 4. Find all documents mentioning 'Computer
Science' and all documents that are linked to them
through paths of length two or less containing only local
links.
FROM Document x SUCH THAT
x MENTIONS "Computer Science",
Document y
Note we are using two different keywords, MENTIONS
and CONTAINS, to do string matching in the
FROM and WHERE clauses respectively. The reason
is that they mean different things. Conditions in the
FROM clause will be evaluated by sending them to index
servers. The result of the FROM clause, obtained by
navigation and index server query, is a set of candidate
URL's, which are then further restricted by evaluating
the conditions in the WHERE clause. This distinction
is reflected both in the formal semantics and in the im-
plementation. We could remove the distinction and let
a query optimizer decide which conditions are evaluated
by index servers and which are tested locally. However,
we prefer to keep the explicit distinction because index
servers are not perfect or complete, and the programmer
may want to control which conditions are evaluated by
them and which are not.
The BNF specification of the language syntax is
given in the Fig. 1. The syntax follows the standard
SQL SELECT statement. All queries refer to the WWW
database schema introduced above. That is, Table can
only be Document or Anchor and Field can only be a
valid attribute of the table it applies to.
In this section we introduce a formal foundation for Web-
SQL. Starting from the inherent graph structure of the
WWW, we define the notion of virtual graph and construct
a calculus-based query language in this abstract
setting. Then we define the semantics of WebSQL queries
in terms of this calculus.
3.1 Data Model
We assume an infinite set D of data values, and a finite
set T of simple Types whose domains are subsets of D.
Tuple types with attributes a i of
simple type t i , are defined in the standard
way. The domain of a type t is denoted by dom(t). For a
4 Alberto O. Mendelzon, George A. Mihaila, and Tova Milo
Query := SELECT AttrList FROM DomainSpec
Attribute := Field j TableVar.Field
Field :=
TableVar :=
DomainSpec := DomainTerm f, DomainTermg
DomainTerm := Table TableVar SUCH THAT DomainCond
DomainCond := Node PathRegExp TableVar
Node := StringConstant
Condition := BoolTerm fOR BoolTermg
BoolTerm := BoolTerm fAND BoolTermg
Attribute CONTAINS StringRegExp
PathFactor := PathPrimary[*]
PathPrimary := Link
Fig. 1. WebSQL Syntax
tuple x, we denote by x:a i the value v i associated with
the attribute a i .
We distinguish a simple type Oid 2 T of object
identifiers, and two tuple types Node and Link with the
following structure:
The attribute names in the two definitions are all dis-
tinct. We shall refer to tuples of the first type as Node
objects and to tuples of the second type as Link objects.
In our model of the World Wide Web, documents will
be mapped to Node objects and the hypertext links between
them to Link objects. In this context, the object
identifiers (Oid) will be the URL's and the Node and
Link tuples will model the WebSQL Document and Anchor
virtual tables introduced informally in Section 2.
Virtual Graphs
The set of all the documents in the Web, although finite,
is undetermined: no one can produce a complete list of
all the documents available at a certain moment. There
are only two ways one can find documents in the Web:
navigation starting from known documents and querying
of index servers.
Given any URL, an agent can either fetch the associated
document or give an error message if the document
does not exist. This behavior can be modeled by
a computable partial function mapping Oid's to Node
objects. Once a document is fetched, one can determine
a finite set of outgoing hypertext links from that docu-
ment. This can also be modeled by a computable partial
function mapping Oid's to sets of Link objects. In prac-
tice, navigation is done selectively, by following only certain
links, based on their properties. In order to capture
this, we introduce a finite set of unary link predicates
The second way to discover documents is by querying
index servers. To model the lists of URL's returned
by index servers we introduce a (possibly infinite) set of
unary node predicates
each predicate P we are interested in the set fxjx 2
trueg. For example, a particular
node predicate may be associated with a keyword, and it
will be true of all documents that contain that keyword
in their text.
Definition 2. A virtual graph is a 4-tuple
are computable partial
functions, PNode is a set of unary predicates on
dom(Oid), and P Link is a finite set of unary predicates
on dom(Link).
- The set fae Node (oid)joid 2 dom(Oid) and ae Node is
defined on oidg is finite;
- for all oid 2 dom(Oid): ae Node (oid) is defined ,
ae Link (oid) is defined;
finite and for all e 2
and ae(e:to) is defined (we say that
e is an edge from v
ae Node (e:to));
- every predicate ff 2 P Link is a partial computable
Boolean function on the set dom(Link), and ff is defined
on all the links in ae Link (oid) whenever ae Link (oid)
is defined.
- the function val defined by

Example 5. A virtual
where:
isiting T oronto?::: 00
national capital::: 00
ourist information::: 00
url ae Link (url)
to Ottawa 00 ];
"Back to T oronto 00
"Back to T oronto 00
and fContains tourist ; Contains capital g, P
fContains go ; Contains back g.
Querying the World Wide Web 5
Note that a virtual graph
induces an underlying directed graph E)
oid2dom(Oid) ae Link (oid).
However, a calculus cannot manipulate this graph directly
because of the computability issues presented
above. This captures our intuition about the World Wide
Web hypertext graph, whose nodes and links can only be
discovered through navigation.
3.2 The Calculus
Now we proceed to define our calculus for querying virtual
graphs. We introduce path regular expressions to
specify connectivity-based queries. We then present the
notions of range expressions and ground variables to restrict
queries so that their evaluation does not require
enumerating every node of the virtual graph, and finally
we define calculus queries.
Path regular expressions
Consider a virtual graph \Gamma and denote its underlying
graph E). A path in \Gamma is defined in the same
way as in a directed
path if and only if for every index
path p is called simple
if there are no different edges e i 6= e j in p with the same
starting or ending points.
In order to express queries based on connectivity,
we need a way to define graph patterns. Recall P Link
is the set of link properties in a virtual graph. Let
link property, and let e be a link
object. If true then we say that e has the property
ff. We define the set of properties of a link e by
trueg. We sometimes choose
to view  (e) as a formal language on the alphabet P Link .
For each property ff that is true of e,  (e) contains the
single-character string ff. To study the properties of a
path, we extend the definition of the set of properties of
a link to paths as follows: if is a path then
we define
is the concatenation
of the languages L and L 0 .
Example 6. Suppose we want to require that a property
ff hold on all the links of a path
can be expressed easily in terms of   by requiring that
In order to specify constraints like in the example
above we introduce path regular expressions, which are
nothing more than regular expressions over the alphabet
P Link . With each regular expression R over the alphabet
P Link we associate a language L(R) ' P
Link in the
usual way.
Definition 3. We say that the path p matches the path
regular expression R if and only if:  (p) " L(R)
In other words, the path p matches the path regular expression
R if and only if there is a word w in the set of
properties  (p) that matches the regular expression R.
Range expressions
The algebra for a traditional relational database is based
on operators like select (oe), project (-) and Cartesian
product (\Theta). Because all the contents of the database is
assumed to be available to the query engine, all these
operations can be executed, in the worst case by enumerating
all the tuples. In the case of the World Wide
Web, the result of a select operation cannot be computed
in this way, simply because one cannot enumerate
all the documents. Instead, navigation and querying of
index servers must be used. We want our calculus to express
only queries that can be evaluated without having
to enumerate the whole Web. To enforce this restriction,
we introduce range conditions, that will serve as restrictions
for variables in the queries.
Definition 4. Let
a virtual graph. Let G(\Gamma E) be its underlying
graph. A range atom is an expression of one of the following
forms:
are Oids or variable names,
and R is a path regular expression;
x is an Oid or a variable
are Oids or variable names;
A range expression is an expression of the
are range atoms, x are all the
variables occurring in them and T i 2 fNode; Linkg specifies
the type of the variable x i , for
Consider a valuation - : fx;
that maps each variable into a node or an edge of
the underlying graph. We extend - to dom(Oid) by
(oid), that is, - maps each Oid appearing
in an atom to the corresponding node. The following
definition assigns semantics to range atoms.
Definition 5. Let
a virtual graph. Let A be a range atom. We say that A
is validated by the valuation - if:
there exists a simple path from
-(u) to -(x) matching the path regular expression R;
Now we can give semantics to range expressions.
Definition 6. Consider a range expression
Amg. Then the set of tuples
is an valuation s:t: A 1 ; :::; Am
are all validated by -g is called the range of E .
Example 7. The set of all nodes satisfying a certain node
predicate P together with all their outgoing links may be
specified by the following range
6 Alberto O. Mendelzon, George A. Mihaila, and Tova Milo
Ground Variables and Ground Expressions
Although Definition 6 gives a well-defined semantics for
all range expressions, problems may arise when examining
the evaluation of \Psi (E) for certain expressions E . For
example, expressions like fx :
(find all pairs of nodes connected by a link of type ff)
nodes and
all links outgoing from them) cannot be algorithmically
evaluated on an arbitrary virtual graph, since their evaluation
would involve the enumeration of all nodes. We
impose syntactic restrictions to disallow such range ex-
pressions, in a manner similar to the definition of safe
expressions in Datalog.
Consider a virtual graph
Let us examine the evaluation of atoms for all the three
cases in Definition 4:
determining all pairs of nodes
separated by simple paths matching the path
regular expression R is possible only if u is a constant.
Indeed, if u is known, we can traverse the graph starting
from u to generate all simple paths matching R,
thus determining the values of x. If u is a variable
and x is a constant, since Web links can only be traversed
in one direction, there is no way to determine
the values of u for arbitrary R without enumerating
all the nodes in the graph. All the more so when both
u and x are variables. A similar argument shows that
u must be a constant in A = F rom(u; x).
- the atoms of the form P (x) where P 2 PNode pose
no problem since the set fx 2 V jP
computable (by Definition 2).
The above considerations lead to the following definition.
Definition 7. A variable x occurring in a range atom A
is said to be independent in A if it is the only variable in
the atom. If two variables u and x appear in an atom A in
this order (i.e.
then we say that x depends on u in A.
The idea is that independent variables can be determined
directly, whereas dependent variables can be determined
only after the variables they depend upon have been assigned
values. The following definition gives a syntactic
restriction over range expressions that will ensure computability

Definition 8. Let
be a range expression. A variable x xng is said
to be ground in E if there exists an atom A i such that
either x is independent in A i , or x depends in A i on a
variable u that is ground in E . The expression E is said
to be ground if all the variables in E are ground.
Theorem 1. Consider a virtual graph
Amg. If E is ground then
\Psi (E) is computable.
Proof. Consider the following dependency graph
being
the dependency relation (i.e. there is an edge from x i to
only if x j depends on x i in some atom A k ).
We distinguish two cases depending on the presence of
cycles in GD . We will consider first the acyclic case and
then we will reduce the cyclic case to the acyclic one by
transforming the expression E into an equivalent one.
Case I (GD acyclic): By doing a topological sort we
can construct a total order among the variables which
is compatible with the dependency relation, that is, a
permutation oe 2 S(n) s.t.
j.
To simplify the notation, we can rename the variables
according to the permutation oe so that each variable
depends only on variables preceding it in the list
For each variable x i we define the set I x i ' f1; :::; mg
as the set of the indices of the atoms where x i occurs
either as an independent or dependent variable. Since
every variable is ground, all sets I x i are non-empty.
does not depend on any other variable and
is ground, all its occurrences in atoms are independent
occurrences. This means that we can compute the set of
values of x 1 in \Psi (E):
Furthermore, let us consider one element c 1 in this set
(if this set is empty, then \Psi (E) is also empty and its
computation is complete). We replace all occurrences of
x 1 in atoms with the constant c 1 (denote the transformed
atoms by A m). The occurrences of x 2
in the atoms A i with i 2 I x2 are either independent or
dependent on x 1 . Therefore, after the substitution of x 1
by c 1 all the occurrences of x 2 in A i [x 1
became independent. This means that we can compute
the set of all values of x 2 in the tuples where x 1 is
Now we consider an arbitrary element c 2 of the above set
(if it is empty, then go back and choose another value for
We replace all occurrences of x 2 in atoms with the
constant c 2 and iterate the process, sequentially for all
the other variables. That is, we compute the sets:
sequentially, for 2 - k - n. Once we have computed the
last set, for every element c n in that set we add the tuple
to \Psi (E). Then, recursively, we take another
value for c n\Gamma1 in its set and recompute the set for xn ,
and so on, until we compute all the tuples. This recursive
procedure is described in Fig. 2.
Querying the World Wide Web 7
Procedure
for all c 2 M
else
end for
/* Main Program */
OUTPUT: \Psi (E)
array 1::n of Object
Fig. 2. Algorithm computing \Psi (E)
Case II (GD cyclic): Consider a cycle in GD : x
. From the definition of atoms we
infer that all the variables in the cycle are of the type
Node (a Link variable always has outdegree zero in the
dependency graph). From the fact that all variables are
ground we infer that at least one of the vertices in the
cycle has an incoming edge from outside the cycle or has
an independent occurrence in some atom. Without loss
of generality we can consider that
has this property.
Fig. 3. Breaking a Dependency Cycle
We introduce a new variable xn+1 and replace all occurrences
of x
in the atoms where it depends on x i k by
xn+1 . In this way, the edge x
is replaced by an
thus breaking the cycle (see Fig. 3).
Also, we add a new atom
to E . Please note that all variables are still ground in
the modified expression. We denote the new expression
'. The atom Am+1 ensures that in all tuples in \Psi
different nodes cannot be separated by
an empty path). This means that \Psi
The new dependency graph G 0
D has at least one cycle
less than GD . By iterating this procedure until there
are no cycles left we obtain an expression F that can
be evaluated using the method from Case I. Then, as
the last step, we compute \Psi
concludes the theorem's proof.
Remark 1. The converse of the above theorem is not
true, since there are computable range expressions which
are not ground. For example, consider
is an unsatisfiable link predicate. Here y and z are not
ground but \Psi trivially computable.
However, one can prove 4 that every computable range
expression is equivalent to a ground range expression.
Queries
After restricting the domainfrom a large, non-computable
set of nodes and links to a computable set, we may
use the traditional relational selection and projection to
impose further conditions on the result set of a query.
This allows us to introduce the general format of queries
in our calculus. We assume a given set P s of binary
predicates over simple types. Examples of predicates include
equality (for any type), various inequalities (for
numeric types), and substring containment (for alphanumeric
types).
Definition 9. A virtual graph query is an expression of
the form: -L oe OE E where:
Amg is a range expression

- L is a comma separated list of expressions of the form
some attribute of the type T
- OE is a Boolean expression constructed from binary
predicates from P s applied to expressions x i :a j and
constants using the standard operators -, and :;
The semantics of the select (oe) and project (-) operators
is the standard one.
3.3 WebSQL Semantics
We are now ready to define the semantics of our WebSQL
language in terms of the formal calculus introduced
above. To do this, we need to model the Web as a virtual
graph
is the infinite set of all syntactically correct URL's, and
for every element url 2 dom(Oid), ae Node (url) is either
the document referred to by url, or is undefined,
if the URL does not refer to an existing document. Note
that ae Node (url) is computable (its value can be computed
by sending a request to the Web server specified
in the URL). Moreover, ae Link (url) is the set of all
anchors in the document referred to by url, or is un-
defined, if the URL does not refer to an existing doc-
ument. One can extract all the links appearing in an
HTML document by scanning the contents in search of
4 This comes as a consequence of a more general theorem in
8 Alberto O. Mendelzon, George A. Mihaila, and Tova Milo
!A? and !/A? tags. This means that the partial function
ae Link (url) is computable. In order to model content
queries we consider the following set of Node pred-
icates: where, for each w 2 \Sigma   ,
true if the document n contains the string w.
Finally, we consider the following set of Link predicates:
in accordance with the definition of
path regular expressions in WebSQL.
The semantics of a WebSQL query is defined as usual
in terms of selections and projections. Thus a query of
the form:
translates to the following calculus query: -L oe OE
Ang is obtained from
by using the following transformation rules:
then A
then A
then A
We only allow as legal WebSQL queries those that
translate into calculus queries that satisfy the syntactic
restrictions of Sect. 3.2.
4 Query Locality
Cost is an important aspect of query evaluation. The
conventional approach in database theory is to estimate
query evaluation time as a function of the size of the
database. In the web context, it is not realistic to try to
evaluate queries whose complexity would be considered
feasible in the usual theory, such as polynomial or even
linear time.
For a query to be practical, it should not attempt
to access too much of the network. Query analysis thus
involves, in this context, two tasks: first, estimate what
part of the network may be accessed by the query, and
then the cost of the query can be analyzed in traditional
ways as a function of the size of this sub-network. In
this section, we concentrate on the first task. Note that
this is analogous, in a conventional database context, to
analyzing queries at the physical level to estimate the
number of disk blocks that they may need to access.
For this first task, we need some way to measure the
"locality" of a query, that is, how far from the originating
site do we have to search in order to answer it.
Having a bound on the size of the sub-network needed
to evaluate a query means that the rest of the network
can be ignored. In fact, a query that is sensitive only to a
bounded sub-network should give the same result if evaluated
in one network or in a different network containing
this sub-network. This motivates our formal definition of
query locality.
An important issue is the cost of accessing such a sub-
network. In the current web architecture, access to remote
documents is often done by fetching each document
and analyzing it locally. The cost of an access is thus affected
by document properties (e.g. size) and the by the
cost of communication between the site where the query
is being evaluated and the site where the document is
stored. Recall that we model the web as a virtual graph.
To model access costs, we extend the definition of virtual
graphs, adding a function ae c : dom(Oid) \Theta dom(Oid) !
is the the cost of accessing node j from
node i.
4.1 Locality Cost
We now define the formal notion of locality. For that we
first explain what it means for two networks to contain
the same sub-network. We assume below that all the
virtual graphs being discussed have the same sets of node
and link predicate names.
Link ) be two (extended)
virtual graphs. Let W ' dom(Oid). We say that
agrees
Link (w),
ae c (w; w
2. for all the node predicates PNode , if
defined, then PNode (n) holds in \Gamma iff it holds in \Gamma 0 ,
3. for all the link predicates P Link and for all links l 2
ae Link (w), P Link (l) holds in \Gamma iff it holds in \Gamma 0 .
Informally this means that the two graphs contain
the sub-network induced by W , the nodes of W have
the same properties in both graphs, and in both graphs
this sub-network is linked to the rest of the world in the
same way.
We next consider locality of queries. In our context, a
query is a mapping from the domain of virtual graphs, to
the domain of sets of tuples over simple types. As in the
standard definition of queries, one can further require
the mapping to be generic and computable. Since this is
irrelevant to the following discussion, we ignore this issue
here. Formal definitions of genericity and computability
in the context of Web queries can be found in [AV97,
MM96].
Definition 11. Let Q be a query, let G be a class of
virtual graphs, let \Gamma 2 G be a graph, and let W '
dom(Oid). We say that query Q when evaluated at node
i depends on W , (for \Gamma and G), if i 2 W and for every
that agrees with \Gamma about W ,
Q(\Gamma ), and there is no subset of W satisfying this.
W is a minimal set of documents needed for computing
Q. Note that W may not be unique. This is reason-able
since the same information may be stored in several
places on the network. If Q is evaluated at some node i,
then the cost of accessing all the documents in such W
is the sum of (ae c (i; w)) over all documents w in W such
that ae Node (w) is defined. We are interested in bounding
Querying the World Wide Web 9
cost with some function of the cost of accessing all the
nodes of the network, that is, the sum of ae c (i;
j such that ae Node (j) is defined.
Definition 12. The locality cost of a query Q, when
evaluated at node i, is the maximum, over all virtual
G, and over all sets W on which Q depends
in \Gamma , of the cost of accessing every document in W from
node i.
We are interested in bounding the locality cost of a
query with some function of the cost of accessing the
whole network. If this total cost is n, note that the locality
cost of a query is at most linear in n. Obviously,
queries with O(n) locality are impractical - the whole
network needs to be accessed in order to answer them.
We will be interested in constant bounds, where the constants
may depend on network parameters such as number
of documents in a site, maximal number of URL's in
a single document, certain communication costs, etc.
In general, access to documents on the local server
is considered cheap, while documents in remote servers
need to be fetched and are thus relatively expensive. To
simplify the discussion and highlight the points of interest
we assume below a rather simple cost function. We
assume that local accesses are free, while the access cost
to remote documents is bounded by some given constant.
(Similar results can be obtained for a more complex cost
function). For a few examples, consider the query
FROM Document x SUCH THAT
where "http://www.cs.toronto.edu" is at the local server.
The query accesses local documents pointed to by the
home page of the Toronto CS department, and no remote
ones. Thus the locality cost is O(1). On the other
hand, the query
FROM Document x SUCH THAT
accesses both local and remote documents. The number
of remote documents being accessed depends on the
number of anchors in the home page that contain remote
URL's. In the worst case, all the URL's in the page are
remote. If k is a bound on the number of URL's in a
single document, then the locality cost of this query is
O(k).
As another example, consider the queries
FROM Document x SUCH THAT
FROM Document x SUCH THAT
FROM Document x SUCH THAT
Query local documents reachable from the
CS department home page, and is thus of locality O(1).
Query Q 3 accesses all documents reachable by one global
link followed by an unbounded number of local links. If
k is a bound on the number of URL's in a single doc-
ument, and s is a bound on the number of documents
in a single server, then the locality cost of the query is
O(ks). This is because in the worst case all the URL's
in the CS department home page reference documents in
distinct servers, and all the documents on those servers
are reachable from the referenced documents. The last
query accesses all reachable documents. In the worst case
it may attempt to access the whole network, thus its cost
is O(n).
The locality analysis of various features of a query
language can identify potentially expensive components
of a query. The user can then be advised to rephrase
those specific parts, or to give some cost bounds for them
in terms of time, number of sites visited, CPU cycles con-
sumed, etc., or, if enough information is available, dol-
lars. The query evaluation would monitor resource usage
and interrupt the query when the bound is reached.
A query Q can be computed in two phases. First, the
documents W on which Q depends on are fetched, and
then the query is evaluated locally. Of course, for this
method to be effective, computing which documents need
to be fetched should not be more complex than computing
itself. The following result shows that computing
W is not harder, at least in terms of how much of the
network needs to be scanned, than computing Q.
Proposition 1. For every class of graphs G and every
query Q, the query Q 0 that given a graph \Gamma 2 G returns
a W s.t. Q depends on W , also depends on W .
Proof. We use the following auxiliary definition.
Definition 13. Let Q be a query, let G be a class of
graphs, let G 2 G be a graph, and let W be a set of
nodes in G. We say that Q is W -local for G and G,
if for every graph G 0 2 G that agrees with G about W ,
Note that a query Q depends on W for G and G, if
Q is W -local and there is no W 0 ae W s.t. Q is W 0 -local
for G. We shall call such W a window of Q in G. (Not
that there may be many windows for Q in G.)
The proof is based on the following claim:
Claim. For every two graphs G 1 ; G 2 , every set of nodes
W belonging to both graphs, and every query Q, the
following hold:
(i) If G 1 agrees with G 2 about W and Q is W -local for
-local for G 2 .
(ii) If G 1 agrees with G 2 about W and Q depends on W
for G 1 , then Q also depends on W for G 2 .
Proof. (Sketch) We first prove claim (i). If G 1 is W -
local, then for every graph G 0 2 G that agrees with G 1
about W , This in particular holds for
G 2 . Also, since G 2 agrees with G 1 about W , then the
set of graphs that agree with G 1 about W is exactly the
set containing all the graphs agreeing with G 2 about W .
Alberto O. Mendelzon, George A. Mihaila, and Tova Milo
Thus for every graph G 0 2 G that agrees with G 2 about
follows immediately from claim (i).
We are now ready to prove the proposition. The proof
works by contradiction. Clearly the window W 0 on which
depends must contain W (since W is part of the answer
of Q Assume that W ae W 0 . We shall show that
Q 0 is W -local, a contradiction to the minimality of W 0 .
Assume Q 0 is not W -local. Then there must be some
graph G 0 that agrees with G about W but where Q 0 has
a different answer. i.e. Q does not depend on W for G 0 .
But claim (ii) above says that if G agrees with G 0 about
W and Q depends on W for G,then Q also depends on
W for G 0 . A contradiction.
Although encouraging, the above result is in general
not of practical use. It says that computing W is not
harder in terms of the data required, but it does not say
how to compute W . In fact it turns out that if the query
language is computationally too powerful, the problem of
computing W can be undecidable. For example, if your
query language is relational calculus augmented with
Web-SQL features, the W of a query fx j OE - Q 4 g is
the whole network if OE is satisfiable, and is empty other-
wise. (OE here is a simple relational calculus formula and
has no path expressions).
If the query language is too complex, locality analysis
may be very complex or even impossible. Nevertheless,
there are many cases where locality cost can be analyzed
effectively and efficiently. This in particular is the case
for the WebSQL query language. The fact that the language
makes the usage of links and links traversal explicit
facilitates the analysis task. In the next subsection, we
show that locality of WebSQL queries can be determined
in time polynomial in the size of the query.
4.2 Locality of WebSQL queries
We start by considering simple queries where the FROM
clause consists of a single path atom starting from the
local server, as in the examples above. We then analyze
general queries.
Analyzing single path expressions
The analysis is based on examining the types of links (in-
ternal, local, or global) that can be traversed by paths
described by the path expression. Particular attention
is paid to "starred" sub-expressions since they can describe
paths of arbitrary length. Assume that the query
is evaluated at some node i, and let n denote the cost
of accessing the whole network graph from i. Let k be
some bound on the number of URL's appearing in a
single document, 5 and s some bound on the number of
documents in a single server.
5 If no such bound exists, every path expression containing a
global link is of locality cost O(n) (because in the worst case a
single document may point to all the nodes in the network).
1. Expressions with no global links can access only local
documents and thus have locality O(1).
2. Expressions containing global links that appear in
"starred" sub-expression, can potentially access all
the documents in the network. Thus the locality is
3. Expressions with global links, but where none of the
"starred" sub-expressions contain a global link sym-
bol, can access remote documents, but the number of
those is limited. All the paths defined by such expressions
are of the form ! l
The number of documents
accessed by such path is bounded by
where k and s are the bounds above. This is because
the number of different documents reachable
by a path ! l i is at most min(s; k l i ).Each of these
documents may contain k global links, and in the
worst case all the k min(s; k l i ) links in those documents
point to files on distinct servers. The number
of documents reached at the end of the path is thus
at most (k min(s; k l In order to reach those docu-
ments, in the current Web architecture, all files along
the path need to be fetched. To get a bound on this,
we multiply the number by the length of the path.
The number m is bounded by the number of global
links appearing in the given path expression. l can be
computed by analyzing the regular expression. 6 All
this can be done in time polynomial in the size of the
expression. Thus the whole bound can be effectively
computed.
The above expression is a simple upper bound on the
locality cost. A tight bound can also be computed
in polynomial time. We chose to present the above
bound since the exact expression is very complex and
does not add much insight to the analysis, so we omit
it.
Observe that if any of the starred sub-expressions
contains a local link, then l = s. This is because,
in the worst case, such sub-expressions will attempt
to access all the documents in the server. In this
case the bound becomes min(n; (m(s
Since servers may contain many documents, the locality
cost may be very high. This indicates that such
queries are potentially expensive and that the user
should be advised to provide the query evaluator certain
bounds on resources.
Analyzing queries
To analyze a WebSQL query it is not sufficient to look at
individual path atoms. The whole FROM clause needs
to be analyzed. For example, consider a query
6 It suffices to build a NFA for the expression and compute the
lengths of the maximal path between two successive global links,
not counting epsilon moves and internal links. l i is infinite if the
path between two successive global links contain a cycle with at
least one local link, in which case min(s; k l i
Querying the World Wide Web 11
FROM Document x
Anchor y SUCH THAT base = x
Document z SUCH THAT y !   z
Document w SUCH THAT x ! w
The path expressions in the query involve only local
links. But since the links returned by the index server
may point to remote documents, the paths traversed by
the sub-condition
FROM Document x
Document w SUCH THAT x ! w
are actually of the form ((!j)): !). Similarly, since the
links traversed in "Anchor y SUCH THAT base = x"
can be internal, local, or global, the paths traversed by
the sub-condition
FROM Document x
Anchor y SUCH THAT base = x
Document z SUCH THAT y !   z
are of the form ((!j)):(7! Thus the regular
expression describing the path accessed by the query
is
that querying an index server can be done with locality
c, and that the number of URL's returned by an index
server on a single query is bounded by some number
m. The locality cost of evaluating this query is therefore
bounded by c plus m times the locality bound of
Interestingly, every FROM clause of a WebSQL query
can be transformed into a regular expression describing
the paths accessed in its evaluation. This, together with
the locality cost of querying the index severs used in
the query, and the bounds on the size of their answers,
lets us determine the locality of the FROM clause in
time polynomial on the size of the query. Bounding the
locality of the FROM clause provides an upper bound on
the locality of the whole query; a slightly better bound
can be obtained by analyzing the SELECT and WHERE
clauses.
We first sketch below an algorithm for building a regular
expression corresponding to the paths traversed by
the FROM clause. Next we explain how the SELECT
and WHERE clauses can be used in the locality analysis

To build the regular expression we use the auxiliary
notion of determination.
Definition 14. Recall that every domain term A i in the
FROM clause corresponds to an atom A 0
i in the calculus.
We say that A i determines a variable x, if x is independent
in A 0
i or it depends on another variable of A 0
i . For
two domain terms A i ; A j , we say that A i determines A j
if A i determines any of the variables in A j .
For simplicity, we assume below that every variable
in the FROM clause is determined be a single domain
term. Observe that this is not a serious restriction because
every query can be transformed to an equivalent
query that satisfies the restriction: whenever a variable
depends on several terms, the variables in all these terms
but one can be renamed, and equality conditions equating
the new variables and the old one can be added to
the WHERE clause.
Given this assumption, the determination relationship
between domain terms can be described by a forest.
This forest is then used to derive the regular expression.
The forest is built is follows: The nodes are the atoms
in the FROM clause, and the edges describe the dependency
relationship between variables.
Note that the roots in such a forest are either index
terms (that is, MENTIONS terms), or anchor/path
terms with a constant URL as the starting point. The
non-root nodes are anchor or path terms. For example,
the forest of query Q 5 above contains a single tree of the
FROM Document x SUCH THAT x MENTIONS "VLDB96"
. j
. Document z SUCH THAT y(!)   z
The next step is to replace each term node in the forest
by a node containing a corresponding path expres-
sion: Index terms are replaced by ! j ). Non-root anchor
terms are also replaced by 7!
ones are replaced by the same expression, if the constant
URL appearing in them is at the local server, and
by
are replaced by the regular expression appearing in the
atom. Root ones with a URL at the local server are also
replaced by this regular expression, and otherwise by
concatenated to the expression. So for example, the
above tree becomes
Finally, we take the obtained forest and build from it a
regular expression. This is done by starting at the leaves
and going up the forest, concatenating the regular expression
of each node to the union of the expressions
built for the children, (and finally taking the union of all
the roots of the forest). The expression thus obtained for
the above tree is
The locality of the FROM clause is a bound on the
locality of the query. A slightly better bound can be obtained
by analyzing the SELECT and WHERE clauses.
For the SELECT clause, if the documents corresponding
to variables on which no other variable depend are
not used, (i.e. only data from their URL is retrieved),
it means that the last link of the path is not traversed.
7 Which is equivalent to the expression (((!j)): !) j ((!j)
we obtained in the intuitive discussion above.
Alberto O. Mendelzon, George A. Mihaila, and Tova Milo
This can be easily incorporated into the locality computation
of the regular expression. For the WHERE clause,
if the condition there is unsatisfiable, the locality can be
immediately reduced to O(1).
5 Implementation
This section presents our prototype implementation of a
WebSQL compiler, query engine, and user interface.
Both the WebSQL compiler and query engine are implemented
entirely in Java [SM], the language introduced
by Sun Microsystems with the specific purpose of adding
executable content to Web documents. Java applications
incorporated in HTML documents, called applets, reside
on a Web server but are transferred on demand to the
client's site and are interpreted by the client.
A prototype user interface for the WebSQL system is
accessible from the WebSQL home page
through a CGI script. Also, we have developed a stan-
dalone, GUI-based, Java application that supports interactive
evaluation of queries.
The WebSQL system architecture is depicted in Fig. 4.
User
Interface
WebSQL Compiler
Virtual Machine Query Engine
World Wide Web
File
Query
Object Code
Requests
Lists of URLs
Traversal and
Fig. 4. The Architecture of the WebSQL System
The Compiler and Virtual Machine
Starting from the BNF specification of WebSQL we built
a recursive descent compiler that, while checking for syntactic
correctness, recognizes the constructs in a query
and stores all the relevant information in internal structures

After this parsing stage is complete, the compiler generates
a set of nested loops that will evaluate the range
atoms in the FROM clause. Consider the following query
template:
The WebSQL compiler translates the above query to
a program in a custom-designed object language implementing
the pseudo-code algorithm depicted in Fig. 5.
Compute
for all x 1 2 D 1
Compute
for all x
Compute
for all xn 2 Dn
Write
end for
end for
end for
Fig. 5. The Nested Loops Generated by the Compiler
Note that this nested loops algorithm is equivalent
to the recursive algorithm used in the proof of Theorem
1 (for this restricted form of domain specifying ex-
pressions).
Fig. 6. The WebSQL User Interface
The object program is executed by an interpreter
that implements a stack machine. Its stack is heteroge-
neous, that is, it is able to store any type of object, from
integers and strings to whole vectors of Node and Link
objects. The evaluation of range atoms is done via specially
designed operation codes whose results are vectors
of Node or Link objects.
Querying the World Wide Web 13
The Query Engine
Whenever the interpreter encounters an operation code
corresponding to a range atom, the query engine is invoked
to perform the actual evaluation. There are three
types of atoms, according to Definition 4. Let us examine
each of them in sequence:
the engine generates all simple
paths starting at u that match R, thus determining
the list of all qualifying values of x. Mendelzon and
Wood give in [MW95] an algorithm for finding all
the simple paths matching a regular expression R in
a labeled graph. We adapted this algorithm for the
virtual graph context. (For full details see [Mih96]).
Cw the engine queries a customizable set
of known index servers (currently Yahoo and Lycos)
with the string w and builds a sorted list of URL's
by merging the individual answer sets;
the engine determines first if u
is an HTML document and if it is, it parses it and
builds a list of Link objects out of the set of all the
anchor tags; if u is not an HTML document, the engine
returns the empty list.
The User Interface
In order to make WebSQL available to all WWW users,
we have designed a CGI C program invoked from a
HTML form. The appearance of the HTML form is
shown in Fig. 6, a screen shot of the Hotjava browser.
The input form can be used as a template for the
most common WebSQL queries making it easier for the
user to submit a query. If the query is more complicated
it can always be typed into an alternative text field. After
the query is entered it may be submitted by pressing
the appropriate button. At that point, the Java applet
collects all the data from the input fields and assembles
the WebSQL query. Then the query is sent to the Parser,
which checks the syntax and produces the object code.
The object code is then executed by the Interpreter and
finally a query result set is computed. This set is formatted
as an HTML document and displayed by the browser.
All URL fields that appear in the result are formatted
as anchors so that the user may jump easily to the associated
documents. Fig. 7 contains a screen shot of a
typical result document.
Performance
The execution time of a WebSQL query is influenced by
various factors related to the network accesses performed
in the process of building the result set. Among these factors
we can mention the number and size of the transferred
documents, the available network bandwidth, and
the performance and load of the accessed Web servers.
Because our query processing system does not maintain
any persistent local information between queries it has
to access the Web for every new query. Therefore, care
Fig. 7. WebSQL Query Results
must be taken when formulating queries by estimating
the number of documents that have to be retrieved. We
executed a number of queries by running the Java applet
described in the previous section from within an instance
of the HotJava browser running under Solaris 2.3 on a
SUN Sparcserver 20/612 with 2 CPUs and 256 Mbytes
of RAM.
The execution times for the queries we tested vary
between under ten seconds, for simple content queries,
to several minutes for structural queries involving the
exploration of Web subgraphs with about 500 nodes.
6 Discussion
We have presented the WebSQL language for querying
the World Wide Web, given its formal semantics in terms
of a new virtual graph model, proposed a new notion of
query cost appropriate for Web queries, and applied it
to the analysis of WebSQL queries. Finally, we described
the current prototype implementation of the language.
Looking at Fig. 6, one is skeptical that this complex
interface will replace simple keyword-based search en-
gines. However, this is not its purpose. Just as SQL is
by and large not used by end users, but by programmers
who build applications, we see WebSQL as a tool for
helping build Web-based applications more quickly and
reliably. Some examples:
Selective indexing: As the Web grows larger, we will
often want to build indexes on a selected portion of
the network. WebSQL can be used to specify this
portion declaratively.
14 Alberto O. Mendelzon, George A. Mihaila, and Tova Milo
View definition: This is a generalization of the previous
point, as an index is a special kind of view. Views and
virtual documents are likely to be an important facil-
ity, as discussed by konopnicki and Shmueli [KS95],
and a declarative language is needed to specify them.
Link maintenance: Keeping links current and checking
whether documents that they point to have changed
is a common task that can be automated with the
help of a declarative query language.
Several directions for extending this work present
themselves. First, instead of being limited to a fixed
repertoire of link types (internal, local, and global), we
would like to extend the language with the possibility of
defining arbitrary link types in terms of their properties,
and use the new types in regular expressions. For exam-
ple, we might be interested in links pointing to nodes in
Canada such that their labels do not contain the strings
"Back" or "Home."
Second, we would like to make use of internal document
structure when it is known, along the lines of [CACS94]
There is also a great deal of scope for query opti-
mization. We do not currently attempt to be selective
in the index servers that are used for each query, or to
propagate conditions from the WHERE to the FROM
clause to avoid fetching irrelevant documents. It would
also be interesting to investigate a distributed architecture
in which subqueries are sent to remote servers to be
executed there, avoiding unnecessary data movement.

Acknowledgements

This work was supported by the Information Technology
Research Centre of Ontario and the Natural Sciences and
Engineering Research Council of Canada. We thank the
anonymous reviewers for their suggestions.



--R

Querying and updating the file.
Queries and computation on the Web.
A logical query language for hypertext systems.
The World-Wide Web
From structured documents to novel query facilities.
Expressing structural hypertext queries in Graphlog.
Savvysearch home page.
An algebra for structured office documents.
Visual Web surfing with Hy
A query system for the World Wide Web.
A declarative language for querying and re-structuring the Web

Formal models of web queries.
Queries on structure in hypertext.
Finding regular simple paths in graph databases.
A model to query documents by contents and structure.
Querying semistructured heterogeneous informa- tion


--TR

--CTR
Ke Wang , Huiqing Liu, Discovering typical structures of documents: a road map approach, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.146-154, August 24-28, 1998, Melbourne, Australia
Converting the syntactic structures of hierarchical data to their semantic structures, Information organization and databases: foundations of data organization, Kluwer Academic Publishers, Norwell, MA, 2000
Bhavini C. Patel , Rajshekhar Sunderraman, Querying web data: an object-oriented approach, Proceedings of the 38th annual on Southeast regional conference, April 07-08, 2000, Clemson, South Carolina
Ke Wang , Huiqing Liu, Discovering Structural Association of Semistructured Data, IEEE Transactions on Knowledge and Data Engineering, v.12 n.3, p.353-371, May 2000
Ellen Spertus , Lynn Andrea Stein, Just-in-time databases and the World-Wide Web, Proceedings of the seventh international conference on Information and knowledge management, p.30-37, November 02-07, 1998, Bethesda, Maryland, United States
Kazunori Katoh , Atsuyuki Morishima , Hiroyuki Kitagawa, Agent-based processing of navigational queries in INFOWEAVER, Information organization and databases: foundations of data organization, Kluwer Academic Publishers, Norwell, MA, 2000
Michael Johnson , Farshad Fotouhi , Sorin Draghici, Query-by-structure approach for the web, Data mining: opportunities and challenges, Idea Group Publishing, Hershey, PA,
Athman Bouguettaya , Boualem Benatallah , Mourad Ouzzani , Lily Hendra, WebFindIt: An Architecture and System for Querying Web Databases, IEEE Internet Computing, v.3 n.4, p.30-41, July 1999
Pranam Kolari , Anupam Joshi, Web Mining: Research and Practice, Computing in Science and Engineering, v.6 n.4, p.49-53, July 2004
Tova Milo , Dan Suciu, Type inference for queries on semistructured data, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.215-226, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
Ying Chen , Qiang Zhu , Nengbin Wang, Query processing with quality control in the World Wide Web, World Wide Web, v.1 n.4, p.241-255, 1998
Mary Fernandez , Daniela Florescu , Jaewoo Kang , Alon Levy , Dan Suciu, STRUDEL: a Web site management system, ACM SIGMOD Record, v.26 n.2, p.549-552, June 1997
Laurent Amsaleg , Michael J. Franklin , Anthony Tomasic, Dynamic Query Operator Scheduling for Wide-Area Remote Access, Distributed and Parallel Databases, v.6 n.3, p.217-246, July 1998
S. Tenier , Y. Toussaint , A. Napoli , X. Polanco, Instantiation of Relations for Semantic Annotation, Proceedings of the 2006 IEEE/WIC/ACM International Conference on Web Intelligence, p.463-472, December 18-22, 2006
Masum Z. Hasan , Alberto O. Mendelzon , Dimitra Vista, Applying database visualization to the World Wide Web, ACM SIGMOD Record, v.25 n.4, p.45-49, Dec. 1996
Tolga Urhan , Michael J. Franklin , Laurent Amsaleg, Cost-based query scrambling for initial delays, ACM SIGMOD Record, v.27 n.2, p.130-141, June 1998
S. Bhowmick , Sanjay Madria , Wee-Keong Ng , Ee-Peng Lim, Cost-benefit analysis of web bag in a web warehouse: An  analytical approach, World Wide Web, v.3 n.3, p.165-184, 2000
S. Bhowmick , Wee Keong Ng , Sanjay Madria, Constraint-driven join processing in a web warehouse, Data & Knowledge Engineering, v.45 n.1, p.33-78, April
Alberto O. Mendelzon , Tova Milo, Formal models of Web queries, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.134-143, May 11-15, 1997, Tucson, Arizona, United States
Athman Bouguettaya , Boualem Benatallah , Brahim Medjahed , Mourad Ouzzani , Lily Hendra, Adaptive web-based database communities, Information modeling for internet applications, Idea Group Publishing, Hershey, PA,
Athena Vakali , Yannis Manolopoulos, Caching across heterogeneous information sources: an object-based approach, Information processing and technology, Nova Science Publishers, Inc., Commack, NY, 2001
Serge Abiteboul , Victor Vianu, Regular path queries with constraints, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.122-133, May 11-15, 1997, Tucson, Arizona, United States
Uwe Hohenstein , Andreas Ebert, Automatic migration of files into relational databases, Proceedings of the 2nd international workshop on Web information and data management, p.17-21, November 02-06, 1999, Kansas City, Missouri, United States
Tao Guan , Kam Fai Wong, Nstar: an interactive tool for local web search, Information and Management, v.41 n.2, p.213-225, December
Michael Johnson , Farshad Fotouhi , Sorin Drghici , Ming Dong , Duo Xu, Discovering Document Semantics QBYS: A System for Querying the WWW by Semantics, Multimedia Tools and Applications, v.24 n.2, p.155-188, November 2004
Mengchi Liu , Tok Wang Ling, A Conceptual Model and Rule-Based Query Language for HTML, World Wide Web, v.4 n.1-2, p.49-77, 2001
S. Bhowmick , Sanjay Kumar Madria , Wee Keong Ng, Detecting and Representing Relevant Web Deltas in WHOWEDA, IEEE Transactions on Knowledge and Data Engineering, v.15 n.2, p.423-441, February
Agostino Operational and abstract semantics of the query language G-Log, Theoretical Computer Science, v.275 n.1-2, p.521-560, March 28 2002
Avigdor Gal , John Mylopoulos, Toward Web-Based Application Management Systems, IEEE Transactions on Knowledge and Data Engineering, v.13 n.4, p.683-702, July 2001
M. Ouzzani , B. Benatallah , A. Bouguettaya, Ontological Approach for Information Discovery in Internet Databases, Distributed and Parallel Databases, v.8 n.3, p.367-392, July 2000
Jackie Assa , Daniel Cohen-Or , Tova Milo, Displaying data in multidimensional relevance space with 2D visualization maps, Proceedings of the 8th conference on Visualization '97, p.127-ff., October 18-24, 1997, Phoenix, Arizona, United States
S. Bhowmick , Sanjay Madria , Wee Keong Ng, What can a web bag discover for you?, Data & Knowledge Engineering, v.43 n.1, p.79-119, October 2002
Athman Bouguettaya , Boualem Benatallah , Lily Hendra , Mourad Ouzzani , James Beard, Supporting Dynamic Interactions among Web-Based Information Sources, IEEE Transactions on Knowledge and Data Engineering, v.12 n.5, p.779-801, September 2000
Peter Buneman, Semistructured data, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.117-121, May 11-15, 1997, Tucson, Arizona, United States
graph-based approach for extracting terminological properties from information sources with heterogeneous formats, Knowledge and Information Systems, v.8 n.4, p.462-497, November 2005
Shi-Kuo Chang , Taieb Znati, Adlet: An Active Document Abstraction for Multimedia Information Fusion, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.112-123, January 2001
Dan Suciu, Distributed query evaluation on semistructured data, ACM Transactions on Database Systems (TODS), v.27 n.1, p.1-62, March 2002
Serge Abiteboul , Jason McHugh , Michael Rys , Vasilis Vassalos , Janet L. Wiener, Incremental Maintenance for Materialized Views over Semistructured Data, Proceedings of the 24rd International Conference on Very Large Data Bases, p.38-49, August 24-27, 1998
Silvana Castano , Valeria De Antonellis , Sabrina De Capitani di Vimercati, Global Viewing of Heterogeneous Data Sources, IEEE Transactions on Knowledge and Data Engineering, v.13 n.2, p.277-297, March 2001
Paolo Atzeni , Giansalvatore Mecca, Cut and paste, Proceedings of the sixteenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.144-153, May 11-15, 1997, Tucson, Arizona, United States
Mengchi Liu , Tok Wang Ling, Towards semistructured data integration, Web-enabled systems integration: practices and challenges, Idea Group Publishing, Hershey, PA,
Dan Suciu, Semistructured data and XML, Information organization and databases: foundations of data organization, Kluwer Academic Publishers, Norwell, MA, 2000
David Konopnicki , Oded Shmueli, Database-inspired search, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
Victor Vianu, A Web odyssey: from codd to XML, ACM SIGMOD Record, v.32 n.2, June
Jeffrey Hsu, Critical and future trends in data mining: a review of key data mining technologies/applications, Data mining: opportunities and challenges, Idea Group Publishing, Hershey, PA,
Victor Vianu, A Web Odyssey: from Codd to XML, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.1-15, May 2001, Santa Barbara, California, United States
Raymond Kosala , Hendrik Blockeel, Web mining research: a survey, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.1-15, June, 2000
hypermedia;web searching;query cost;query locality;WebSQL query language;large heterogeneous distributed document collection;hypertext links;formal semantics;information retrieval requests;textual retrieval;virtual graph model;document network;topology-based queries;multiple index servers;calculus;World Wide Web querying