A Conceptual Model and Rule-Based Query Language for HTML.
Most documents available over the Web conform to the HTML specification. Such documents are hierarchically structured in nature. The existing data models for the Web either fail to capture the hierarchical structure within the documents or can only provide a very low level representation of such hierarchical structure. How to represent and query HTML documents at a higher level is an important issue. In this paper, we first propose a novel conceptual model for HTML. This conceptual model has only a few simple constructs but is able to represent the complex hierarchical structure within HTML documents at a level that is close to human conceptualization/visualization of the documents. We also describe how to convert HTML documents based on this conceptual model. Using the conceptual model and conversion method, one can capture the essence (i.e., semistructure) of HTML documents in a natural and simple way. Based on this conceptual model, we then present a rule-based language to query HTML documents over the Internet. This language provides a simple but very powerful way to query both intra-document structures and inter-document structures and allows the query results to be restructured. Being rule-based, it naturally supports negation and recursion and therefore is more expressive than SQL-based languages. A logical semantics is also provided.
Introduction
Most documents available over the web conform to the HTML specication. They
are intended to be human readable through a browser and thus are constructed
following some common conventions and often exhibit some hierarchical structure.
How to represent such documents at the conceptual level is an important issue.
In the past several years, a number of data models have been developed in the
database community in order to retrieve data from the web, such as UnQL [6],
OEM [27], Strudel [9], etc. For a survey, see [12]. These proposals mainly use rela-
tional, graph-based or tree-based data models to represent the web data. They focus
on inter-document structures, with little attention to intra-document structures
and thus fail to capture the hierarchically structure within HTML documents. For
example, none of the existing data models can represent Michael Ley's DBLP bibliography
HTML document at http://www.informatik.uni-trier.de/ley/db shown
in

Figure

1 in a natural and simple way.
50 MENGCHI LIU AND TOK WANG LING
Because of the di-culties with HTML, XML [5] is fast emerging as the dominant
standard for data representation and exchange over the web. It provides natural
support for describing the hierarchical structure in web documents and allows
specic markup to be created for specic data.
The World Wide Web Consortium (W3C) has recently recommended the Document
Object Model (DOM) as an application programming interface for HTML
and XML documents [30]. DOM denes the logical structure of documents and
the way a document is accessed and manipulated. It represents documents as a
hierarchy of various node objects. With DOM, programmers can access, change,
delete, add or build HTML or XML documents, and navigate their structure. Nev-
ertheless, DOM is a very low level data model for HTML/XML documents as it
is intended for programmers to write programs to access and manipulate HTML
and XML documents, rather than for the user to nd the information within the
documents.
W3C has also recommended XPath [7] as a language for operating on the abstract,
logical structure of an XML document, rather than its surface syntax. It models
an XML document as a tree of various nodes at a level higher than DOM, such
as element nodes, attribute nodes, text nodes, etc. However, how to describe the
abstract, logical structure of an HTML document still remains an open problem.
Another important issue is how to query large HTML documents and perform
inference, not only based on their inter-document structures but also on their intra-document
structures to obtain useful information.
In the past few years, a number of query languages and systems have been
developed in the database community to retrieve data from the web, such as
W3QS [8], WebSQL [23], WebLog [16], UnQL [6], Lorel [2], WebQOL [3], Strudel [9]
and Florid [14]. For surveys, see [1, 11, 24]. Because they are based on the
data models that are limited as mentioned above, they fail to support queries
over intra-document structures. For example, CIA World Factbook web site at
http://www.odci.gov/cia/publications/factbook/ contains abundant detailed information
about each country (and region) in the world in an HTML document, such
as its location, geographic coordinates, area, land boundaries, coastline, popula-
tion, age structure, birth rate, GDP, budget, etc. But there is no simple way to
query such information, let alone to infer any useful information.
The purpose of this paper is twofold. We rst propose a novel conceptual model
for HTML, called HTML-CM, which stands for HTML Conceptual Model. This
conceptual model has only a few simple constructs but is able to represent the
complex hierarchical structure within HTML documents at a level that is close to
human conceptualization/visualization of the documents. Based on this conceptual
model, we then present a rule-based language to query HTML documents over
the Internet, called HTML-QL, which stands for HTML Query Language. This
language provides a simple but very powerful way to query both intra-document
structures and inter-document structures and allows the query results to be restruc-
tured. Being rule-based, it naturally supports negation and recursion and therefore
is more expressive than SQL-based languages. A logical semantics for HTML-QL
is also provided.
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 51
The rest of the paper is organized as follows. Section 2 proposes the conceptual
model HTML-CM and shows how to automatically convert HTML documents into
HTML-CM. Section 3 presents the rule-based query language HTML-QL, including
its syntax, query examples, and logical semantics. Section 4 brie
y describes the
implementation of our web search and inference system that supports HTML-CM
and HTML-QL. Section 5 summarizes and points out further research issues. This
paper is a major revision of the two conference papers in [19, 21].
2. HTML-CM: A Conceptual Model for HTML
In this section, we rst introduce HTML-CM, our conceptual model for HTML.
Then we discuss how to convert HTML documents into HTML-CM. We assume
the existence of two kinds of symbols: a set U of URLs, and a set C of constants.
Note that U is a subset of C.
2.1. Conceptual Model
Each web document in HTML is considered structured in HTML-CM. They have
a title and a body. Our purpose is to extract conceptual structures within HTML
documents. To this end, we ignore the features that are used to enhance the visual
aspects of HTML documents, such as fonts, colors, style, etc.
Denition 1. The notion of objects is dened recursively as follows.
1 A constant c 2 C is a lexical object.
be an object and u 2 U . Then ohui is a linking object, and o is called the
label and u is called the anchor of the linking object.
3 Let a; o be objects. Then a ) o is an attributed object, and a is called the
attribute and o is called the value of the attributed object.
are objects with n > 1, then is a list object.
In an object-relational database, we can have homogeneous tuples and sets. Tuple
elements can be accessed using attribute names while set elements are directly
accessed. In an HTML document, we may have attributed objects together with
other objects. Thus, it is sometimes impossible to distinguish tuples from sets. In
addition, HTML documents conceptually supports lists instead of sets as duplication
is allowed and the order of elements exists. Thus, we use list objects for tuples,
sets and lists in HTML-CM. The attribute names can be used to access components
of list objects that matches them.
52 MENGCHI LIU AND TOK WANG LING
Example 1 The following are examples of objects:
Lexical objects: Computer Science, Database Systems
Linking objects: F acultyhfaculty:htmli, Jim Carterh=faculty=carter=i
Attributed objects: Title ) CS Department, Location ) Europe
List object: fTitle ) CS Dept, Researchhresearch.htmlig
A web document available over the Internet has an associated URL that is used
to access the web document.
Denition 2. Let u be a URL and t an object. Then is a web object.
The web documents have many kinds, such as HTML, postscript, pdf, audio,
video, etc. In this paper, we mainly focus on HTML documents. We model an
HTML document as a list object.
Example 2 The following is an example of web object that represents an HTML
document at a given URL:
Title )CSDept,
Peoplehpeople.htmli)f
Facultyhfaculty.htmli,
Stahsta.htmli,
Studentshstudents.html ig,
Programs )f
Ph.D Programhphd.htmli,
M.Sc Programhmsc.htmli,
B.Sc Programhbsc.htmlig,
Researchhresearch.htmli
Note that a linking object is dierent from a web object even though it is somewhat
similar to a web object. A web object corresponds to a web document while a
linking object is simply part of a web object that represents an HTML document.
Example 3 Consider part of the latest DBLP bibliography server of Michael Ley
at http://www.informatik.uni-trier.de/ley/db shown in Figure 1. It can be represented
as a web object in HTML-CM as shown in Figure 2 with simplied URLs
such as a 1 etc. to t in the paper.
As the above examples show, HTML-CM provides an intuitive representation of
the complex hierarchical structure within HTML documents at a high level that
is close to human conceptualization/visualization of the documents. None of the
other data models can do so in such a simple way.
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 53

Figure

1. DBLP Bibliography
2.2. Converting HTML Documents
HTML documents are intended to be human readable though a browser. They are
constructed following some common conventions and often exhibit some hierarchical
structure. By examining a large number of HTML documents, we have discovered a
set of general rules that can be used to convert HTML documents into web objects
in HTML-CM.
In this subsection, we present the conversion rules top-down and recursively using
the operator C and give some examples.
As HTML documents are not parsed, they may have syntactic errors. To make our
presentation simple, we assume that HTML documents are syntactically correct,
while the implementation can be fault-tolerant like most web browsers. We focus
on HTML 4.01 [28], the latest version of HTML.
54 MENGCHI LIU AND TOK WANG LING
Title )DBLP Bibliography,
Search
Bibliographies
Books )fCollectionshb 51 i, DB Textbookhb 52 ig,
By Subjectshb 4 i )fDatabase Systemshb 61 i, Logic Proghb 62 i, IRhb 63 igg,
Full Text )ACM SIGMOD Anthologyhc 1 i,
Reviews )ACM SIGMOD Digital Reviewhc 2 i,
Links )f
Research Groups )fDatabase Systemshd1i, Logic Programminghd2ig,
Computer Science Organizationhe 1 i )f
ACMhe
IEEE Computer Societyhe 15 i(DLhe
Related Services hf 1 i )f
CoRRhf 11 i, Research Indexhf 12 i, NZ-DLhf 13 i,
CS BibTexhf 14 i, HBPhf 15 i, Virtual Library hf

Figure

2. DBLP Web Object with Simplied URLs
Our conversion method is mainly based on the contents shown with a web browser
and therefore we ignore the features that are used to enhance the visual aspects of
the web documents, such as fonts, colors, style, etc. We assume that there is an
HTML interpreter that can be used to parse the HTML les, remove optional tags
and irrelevant components, and automatically identify the corresponding components
for our denition below in HTML documents based on various tags, such as
An HTML document starts with   tag and ends with   tag. It
normally consists of two parts: head and body. The head mainly species the title of
the document while the body species the contents of the HTML document. HTML
documents can be classied into two kinds based on the kind of the contents: Frame-based
documents whose body starts with   and ends with  ,
and regular documents whose body starts with   and ends with  .
Frame-based documents The purpose of frame-based documents is to allow
the visitor to see more than one page at a time, without completely cluttering up
their screen. Frame-based documents have a number of frames in their body and
each frame contains its own HTML document. We convert frame-based document
as follows.
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 55
Rule 1 Let DF be a frame-based document with frames or nested framesets
its body:
<frameset
and ] be list concatenation operator. Then DF is converted into a list of two
attributed objects using the operator C as follows:
"U"> be a frame, where N is the
name and U is the URL of the frame. Then C(F
Rule 3 Let F  be a frame set, where
each F i for 1  i  n is a frame or a nested frameset. Then C(F
In other words, we convert a possibly nested frameset into a list object and each
frame in a frameset into a linking object in the list object.
Regular documents Regular documents are the main ones that provide various
information over the Internet. We convert them into list objects as follows.
Rule 4 Let DR be a regular document with sections S 1 ; :::; Sn in its body:
)g.
Sections In HTML documents, there can be two kinds of sections: sections with
a heading and sections without a heading. If a section has a heading, then we can
convert it into an attributed objects with the heading as its attribute and the rest
as its value. If it has no heading, we just convert its contents.
Rule 5 Let be a section with a heading H and contents
T and S section without a heading. Then
Example 4 Consider the following HTML document:

Computer Science Department

History
The department was founded in 1970.
Programs
The department offers B.Sc. M.Sc. and Ph.D degrees
Facilities
The department has up to date equipment and software

This HTML document has 3 sections with headings. Using Rules 4 and 5, we can
obtain the following list object:
fTitle )Computer Science Department,
History )The department was founded in 1970,
Programs )The department oers B.Sc. M.Sc. and Ph.D degrees,
Facilities )The department has up to date equipment and softwareg
Within a section, there may be a sequence of paragraphs, lists, tables, etc. In
what follows, we discuss how to convert them using the operator C.
Paragraphs A paragraph in a section immediately follows the tag  . Some
paragraphs may have an emphasized beginning that is usually bold, italic, etc. or
is followed by a colon ':'. We convert them into attributed objects as follows.
Rule 6 Let R be a paragraph with an
emphasized beginning and P a paragraph without an emphasized beginning,
where t is either b, i, em, or strong. Then C(P
C(R). If R has logical parts R 1 ; :::; Rn with n  1, then
Each logical part R i for 1  i  n is converted as a paragraph recursively.
Example 5 The following is a section of CIA World Factbook page about Canada
at http://www.odci.gov/cia/publications/factbook/. It consists of a sequence of
paragraphs.


Geographic coordinates:

Map references:  North America

Area:
total:  9,976,140 sq km
land:  9,220,970 sq km

Land use:
arable land:  5%
permanent crops:  0%
permanent pastures:  3%
forests and woodland:  54%
other:  38% (1993 est.)
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 57
Using Rule 6, we obtain the following list object:
fLocation )Northern North America,
Geographic coordinates )60 00 N, 95 00 W
Map references )North America,
Area )f
total )9,976,140 sq km,
land )9,220,970 sq kmg
Land use )f
arable land )5%,
permanent crops )0%,
permanent pastures )3%,
forests and woodland )54%,
other )38% (1993 est.)gg
Multimedia Features and Hypertexts HTML documents can contain multi-media
features such as images, applets, video clips, sound clips, etc. In HTML-CM,
we convert such features into attributed objects using keywords Image, Applet,
Video, Sound, etc. as their attributes.
In HTML, image les are referenced using image links. At the conceptual level,
we only care about the information related to the images in the HTML document.
Rule 7 Let I = <img alt="T"> be an image link, where U is a URL
and T is a string. Then When the alt eld is missing, we
treat it as alt="".
The cases for other multimedia features are handled in a similar way.
In HTML, hypertext links are used to link to other documents. We convert such
links into linking objects as follows.
Rule 8 Let  be a hypertext link, where U is a URL
and T is a string. Then
Rule 9 Let S be a character string. Then
Example 6 Consider the following paragraph without emphasized heading:
<a href="dick.html">Dick  likes <a href="jane.html">Jane
It has three logical units and thus can be converted into the following object:
fDickhdick.htmli, likes, Janehjane.htmlig
Lists HTML supports three kinds of lists: ordered lists, unordered lists and de-
nition lists. One can also nest one kind of list inside another.
be an ordered or unordered list,
where t is either ol or ul. Then
Rule 11 Let  be a deni-
tion list. Then
Rule 12 Let I = T  T 1 . Tm  be a nested ordered or unordered
list item where t is either ol or ul. Then
Example 7 Consider the following HTML document containing nested lists:

CS Department Research

Research Areas

Artificial Intelligence

Cognitive Science  Linguistics  Reasoning

Database Systems

Query Processing  Data Models  Active DB

Research Groups and Labs

Programming Languages
Intelligent Systems
Natural Language Lab

Using Rules 4, 5, 10, and 12, we obtain the following list object:
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 59
fTitle )CS Department Research,
Research Areas )f
Articial Intelligence )f
Cognitive Science,
Linguistics,
Reasoningg,
Database Systems )f
Query Processing,
Data Models,
Active DBgg,
Research Groups and Labs )f
Programming Languages,
Intelligent Systems,
Natural Language Labggg
Example 8 Consider the following HTML document containing a denition list:

Graduate Studies in CS

General Information
The department was established in 1970
Programs of Study
It offers M.Sc, and Ph.D in Computer Science
Financial Support
A variety of scholarships are available
Facilities
The research labs have all kinds of state-of-the-art equipment

Using Rules 4 and 11, we obtain the following list object:
fTitle )Graduate Studies in CS,
General Information )The department was established in 1970,
Programs of Study )It oers M.Sc, and Ph.D in Computer Science,
Financial Support )A variety of scholarships are available,
Facilities )The research labs have all kinds of state-of-the-art equipmentgg

Tables

Tables in HTML are used to arrange data into rows and columns of cells.
Tables may have caption and column/row headings. Tables can be used in two
dierent ways: to present a list with a better layout or to present real tabular
information. We convert tables as follows.
Rule 13 Let  be a table with
a caption and T  be a table without a caption, where H is
the caption and TC is the table contents. Then
Rn be rows other than the row for column headings in the table contents
TC. Then )g. For each row R i with 1  i  n:
1 if the table has column headings H 1 ; :::; Hn and each row R i has a row heading
2 if the table has column headings H 1 ; :::; Hn , but each row R i has no row
3 if the table does not have column headings but each row R i has a row heading:
4 if the table has neither column nor row headings, then for each row R
Example 9 Consider the following table in an HTML document:

<caption

Babies Adults Total
Becket 5 22 27
Worthington 7 5 12

Using Rule 13 Case 1, we can obtain the following attributed object:
Bear Sightings )f
Northampton)fBabies )2, Adults )4, Total )6 g,
Becket )fBabies )5, Adults )22,Total )27g,
Worthington )fBabies )7, Adults )5, Total )12gg
In HTML documents, tables without column headings and row headings are often
used to arrange items for visual eects.
Consider the following portion of an HTML document:
<h2 align="center"> Faculty Profiles
<table border="0" cellpadding=3 cellspacing=3 align=center>

A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 61
<td colspan=50% align=left>
<a href="/faculty/bunt/">Rick Bunt
<td colspan=50% align=left>
<a href="/faculty/carter/">Jim Carter

<td colspan=50% align=left>
<a href="/faculty/cheston/">Grant Cheston
<td colspan=50% align=left>
<a href="/faculty/cooke/">John Cooke

Using Rule 13 Case 4 and Rule 8, we can obtain the following attributed object:
Faculty Proles )f
Rick Bunth/faculty/bunt/i,
Grant Chestonh/faculty/cheston/i,
John Cookeh/faculty/cooke/i,
Forms HTML forms enable visitors to communicate with the web server. There
are two basic parts of a form: the structure that consists of text elds, text areas,
buttons, and menus that the visitor sees and lls out on a page, and the processing
part that process the information the visitor lls out using CGI script typically
written in Perl or some other programming language.
Conceptually, we are interested in the structure part; that is, what kind of information
is presented and can be communicated with the web server. Each element
on a form has a name and a value/type associated with it. The name identies the
data that is being sent, the value is the data that is built-in the HTML document,
the type species the kind of value that comes from the visitor.
HTML supports two ways to send information to the web server: GET and POST.
The GET method appends the name-value pairs to the end of the URL and is for
small amount of data. The POST method sends a data le with the name-value
pairs to the server's standard input without size limit.
Using either GET or POST is mainly a physical level concern and does not have
much conceptual value.
A form normally has two special buttons: submit and reset. The submit button
is used to send the information and the reset button is used to reset the form.
Rule 14 Let F be a form as follows where are the elements in the form.

)g.
Note that we don't keep information about the submit and reset buttons in the
result as we make Form a reserved attribute in HTML-CM to indicate that its
value are used for communication with the web server and those two buttons are
implied.
We now discuss how to convert elements on forms. First, a text eld is a one line
area that allow the user to input text.
Rule 15 Let "> be a text eld,
where L is the label visible to the user, T is the type for the input text, N is the
name for the text eld that is not visible to the user, and V is the default value.
Field )fLabel )L, Name )N , Type )T , Value )V g.
Text areas in HTML are text elds that can span several lines. They are converted
in a similar way.
Radio buttons on forms are used to let the user make only one choice from a set
of alternatives.
Rule R be a group of radio buttons with the same name of the following
form, where L is the label for the group, N is the name, V i is the value, and L i is
the label visible to the user.
Buttons )fLabel )L, Name )N ,
Options )ffLabel )L 1 , Value )V 1 g,
fLabel )Ln ,Value )Vn gg
While radio buttons can accept only one answer per set, check boxes allow the
visitor to check as many check boxes as they like. It is converted in a similar way.
Menus allow visitors of HTML document to enter information easily. It serves
the same purpose as radio buttons or check boxes but takes up less space.
Rule 17 Let M be a menu of the following form, where L is the label for the menu
visible to the user, N is the name for the menu, V i is the value, and L i is the label
visible to the user.
<option
<option

Options )ffLabel )L 1 , Value )V 1 g,
fLabel )Ln , Value )Vn gg
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 63
Example 11 Consider the following portion of an HTML document:
<form method=post action="http://site.com/cgi-bin/get_menu">
Username:<input type="Text" name="Name" value="Enter a name here">
Age Category
<select
<option
<option
<option


It is converted into the following object in HTML-CM:
Text Field )f
Label )Username,
Name)Name,
Type )Text,
Value )Enter a name hereg,
Label )Age Category,
Name)Category,
Options )f
fLabel )13-19, Value )teenagerg,
fLabel )20-60, Value )adultg,
fLabel )over 60, Value )seniorgg
Radio Button )f
Label )Sex,
Name )Gender,
Options )f
fLabel )Female, Value )femaleg,
fLabel )Male, Value )maleggg
3. HTML-QL: A Rule-based Query Language for HTML
In this section, we present a rule-based language called HTML-QL to query web
objects, based on the conceptual model HTML-CM discussed above. First, we
dene the syntax; then we give some examples; nally, we dene the semantics. To
make our presentation simpler, we use sets instead of lists in HTML-QL, but the
results can be extended to lists too.
3.1. Syntax of HTML-QL
Besides the set U of URLs and the set C of constants, we also assume the existence
of a set V of variables started with '$' followed by a string and `$' itself is an
anonymous variable.
Denition 3. The terms are dened recursively as follows:
1 A constant is a lexical term.
If X is a constant or a variable, then Xhi is a label term.
3 If Y is a URL or a variable, then hY i is a anchor term.
4 If X is a constant or a variable, and Y is a URL or a variable, then XhY i is a
linking term, and X is called the label and Y is called the anchor of the linking
term.
5 If X and Y are terms, then X ) Y is an attributed term.
are distinct terms with n  0, then is a set term.
7 A variable is either an lexical term, a linking term, a label, an anchor, an
attributed term, or a set term depending on the context.
Example 12 The following are several examples of terms:
Lexical terms: CS Dept, John Smith, $Name
Label terms: Facultyhi, Journalshi, $Labelhi
Anchor terms: hfac.htmli, hjournals.htmli, h$URLi
Linking terms: Facultyhfac.htmli, Facultyh$Ui, $Labelh$URLi
Attributed terms: Title )CS Dept, Program )f$Dg,
$A )$V, $A )$Lh$Ui, $Ah$Ui)$V
Set terms f$Xg, f$X, Johng, fAuthorh$Uig
A term is ground if it has no variables. Note that ground terms are simply objects.
Denition 4. The expressions are dened as follows:
U be a URL or a variable, and T a term. Then U : T is a positive expression.
If P is a positive expression, then :P is a negative expression.
3 Arithmetic, string and set operation expressions are dened using terms in the
usual way.
For readers familiar with deductive databases or logic programming, the URL u
in positive expression negative expression functions as a predicate
and T in as a term. As we can use a variable in the place of u, HTML-QL is
in fact a higher-order language.
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML
Example 13 The following are several examples of expressions where u stands for
some constant URL:
Positive expressions:
Negative expressions:
Arithmetic expressions:
String expressions:
Set expressions: John 2 $Faculty,
An expression is ground if it contains no variables. A ground positive expression
is a web object.
Denition 5. A rule has the form A :{ L 1 ; :::; Ln , where A is a positive expression
each L i is a positive expression, a negative expression, or an arithmetic, string
or set operation expression dened using terms. A rule is safe if all variables in the
head are covered or limited as dened in [4, 17, 18, 29].
For a negative expression with a set term in the body of a rule, we can move
the negation sign into the set for convenience. For example, we can use
f:Faculty)fJohngg to stand for fFaculty)fJohngg. We can also combine
positive and negative expressions with the same URL for convenience. For
example, we can use the expression to
stand for in the body of a rule.
Note that the anonymous variable $ may appear several times in a rule and their
dierent occurrences in general stand for dierent variables. Thus, it cannot appear
in the head of a safe rule.
In deductive database languages, a query is normally dened as a rule with empty
head. If the query contains no variables, the query result is either true or false.
If the query contains variables, the query result is a set of bindings that make
each ground query true. However, for the web queries, we want not only the set
of bindings that make the query true but also proper restructuring of the query
results. The head of the rule can be used for this purpose. Also, complex queries
over the web objects may need more than one rule to express. Thus, we introduce
our notion of query as follows.
Denition 6. A query is a set of safe rules whose heads have the same URL.
In order to make queries easier to express, we introduce the following shorthands
for rules, terms and expressions appearing in rules:
stands for X )
stands for
3 A :{ :::  n X::: stands for the following
A :{ :::X:::
A :{ :::$:X:::
A :{ ::: $:::$ |{z}
If there are several such dot notations in a rule, then it stands for their various
combinations as outlined above.
4 A :{ :::  X::: stands for A :{ :::  c X::: for some xed number c.
stands for A :{
6 A :{ :::hXi:Y stands for A :{
In other words,  n stands for 0 to n anonymous variables in the path.
3.2. Query Examples
The following queries are based on the DBLP web object shown in Figure 2. To
make them simple, we use u l to stand for the URL http://www.informatik.uni-
trier.de/ley/db and u for the URL of the query result.
the contents of the document at the given URL u l into a local le given
by the URL
Note that no matter what document pointed by u l is, such as HTML, XML,
postscript, image, executable, etc., it is copied to the destination u
processing. If we know that the document is in HTML and we want to convert it
into HTML-CM, then we can use the following query instead:
It says that every element denoted by $X in the set is also an element in the result
set. The notion f$Xg in the body of the rule means that $X is an element in the
corresponding set whereas the notion f$Xg in the head of the rule is used to group
the result into a set. It corresponds to a partial set term in Relationlog [18].
List the objects under the attribute
The result to this query based on the web object in Figure 2 is as follows:
List the anchors (URLs) under the attribute
The result is fAnswer )fa 1 ; a 2 ; a 3 ; a 4 gg
List the labels under the attribute
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 67
The result is fAnswer )fAuthor, Title, Advanced, Home Page Searchgg. This
query can also be represented equivalently using the dot notation in HTML-QL as
follows:
List all the attributes at the rst and second levels:
The result is fAnswer )fTitle, Search, Bibliographies, .gg. This query can also
be represented equivalently using the dot notation as follows:
(Q 6 ). Obtain the URL of TODS:
The result is fAnswer )b 22 g
all the URLs in the page.
all the URLs together with their labels.
(Q 9 ). Get all the URLs reachable from the page.
Note that this query involves multiple web objects and the rules are recursive since
the result web object dened is used in the body of the second rule.
all the URLs together with their labels reachable from the page.
In order to demonstrate the expressive power of HTML-QL, let us consider the
CIA world factbook 2000 at http://www.odci.gov/cia/publications/factbook. This
web server contains detailed information about each country (and region) in the
world in HTML format, such as its location, geographic coordinates, area, land
boundaries, costline, population, age structure, birth rate, GDP, budget, etc. We
can view the web server as a set of simplied web objects as shown in Figure 3 and
therefore we can query them and infer useful information.
Title )Canada, Title )USA,
Body )f Body )f
Geographic )f Geographic )f
Land boudaries )f Land boudaries )f
border countries )fUSg border countries )fCanada, Mexicog
Title )Mexico, .
Body )f
Geographic )f franceURL: f . g
Land boudaries )f .
border countries )fUSA, .g

Figure

3. CIA World Factbook
Find countries that border both Germany and France.
border country )fGermany, Francegg
The result is fAnswer )fBelgium, Luxemburg, Switzerlandgg
countries that border Germany but not France.
border country )fGermanyg,
The result is fAnswer )fAustria, Czech Republic, Denmark, Frence, Netherlands,
Polandgg. Note that this query involves negation.
Find pairs of countries/regions that border the same countries.
countries )$Csg,
countries )$Csg,
The result to this query is as follows:
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 69
fAnswer )ffRegion1 )Bhutan, Region2 )Nepalg,
)Holy See (Vatican City), Region2)San Marinog,
fRegion1 )Hong Kong, Region2 )Macaug,
)United Arab Emirates, Region2 )Yemengg
Note that in this query, the construct fRegion1)$N1, Region2)$N2g in the hread
is used to form a pair of countries (or regions) while the outside pair of brackets is
used to group the result tuples into the set.
Find all the countries that can be reached from Canada by land transportation
means.
countries )f$Cgg
countries )f$Cgg
Note that this is another recursive query.
3.3. Semantics of HTML-QL
In this subsection, we dene the Herbrand-like logical semantics for HTML-QL. We
rst dene terminology that is needed later in this subsection.
Denition 7. The Herbrand universe UH of HTML-QL is the set of all ground
terms that can be formed.
In other words, UH is the domain of all possible objects.
Denition 8. The Herbrand base BH of HTML-QL is the set of all ground
positive expressions that can be formed using terms in UH .
That is, BH is the set of all possible web objects that can be formed.
Denition 9. A web database WDB is a subset of BH .
In other words, a web database is a set of web objects. For example, the CIA
world factbook shown in Figure 3 is a web database.
Denition 10. A ground substitution  is a mapping from the set of web variables
V f$g to UH .
The use of anonymous variables and dot notations in the body of rules allows
us to express queries easier as demonstrated in the examples above. However,
when dealing with the semantics, a ground substitution cannot map the anonymous
variable to several dierent objects. To simplify our presentation, we assume that
each occurrence of the anonymous variable is replaced by a non-anonymous variable
that never occur in the query rules so we do not have to map anonymous variable
to any object. We also assume that the rules here do not contain shorthands.
Given a web database, the positive expressions in the body of a query rule is
actually a query that is used to match part of one or more web objects. Thus, we
introduce the following notions.
Denition 11. An object o is part-of of an object denoted by
only if one of the following hold:
1 both are constants and
2 both are linking objects such that one of the following holds:
3 both are attributed objects: such that a  a 0 and
4 both are set objects such that for each
that
The part-of relationship between objects captures the fact that o is part
of
Example 14 The following are several examples:
Faculty  Faculty
Faculty  Facultyhfac.htmli
Programs )fM.Sc Programg  Programs )fPh.D Program, M.Sc Programg
fTitle )CS Deptg  fTitle )CS Dept, Facultyhfac.htmlig
We extend the part-of relationship to web objects and web databases as follows.
Denition 12. Let be two web objects. Then W is
denoted by W  W 0 , if and only if
Denition 13. Let WDB and WDB 0 be two web databases. Then WDB is part-of
denoted by WDB  WDB 0 , if and only if for each W 2 WDB WDB 0 ,
there exists W 0 2 WDB 0 WDB such that W  W 0 .
Denition 14. Let WDB be a web database. The notion of satisfaction (denoted
by j=) and its negation (denoted by 6j=) based on WDB are dened as follows.
1 For a ground positive expression only if there exists
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 71
2 For a ground negative expression only if WDB 6j=
3 For each ground arithmetic, string, or set operation expression , WDB
if and only if is true in the usual sense.
4 For a rule r of the form A :{ only if for every
ground substitution , WDB
Example 15 Let WDB denote the web database containing the DBLP web object
in Example 3. Then we have
WDB
WDB
WDB
WDB
Denition 15. Let Q be a query. A model M of Q is a web database that
satises Q. A model M of Q is minimal if and only if for each model N of Q,
M  N .
As in deductive databases, we are interested in a minimal model of the query that
can be computed bottom-up. We now continue to dene the bottom-up semantics.
Denition 16. Let WDB be a web database and Q a set of rules. The immediate
logical consequence operator TQ over WDB is dened as follows:
there exists a ground
substitution  such that WDB
Example Consider query Q 4 in the last subsection and the web database WDB
the same as in Example 15, we have
Note that the operator TQ does not perform grouping. Therefore, we introduce
the following notions.
Denition 17. Two objects are compatible if and only if one of the
following holds:
1 both are constants and are equal;
72 MENGCHI LIU AND TOK WANG LING
are compatible;
3 both are set objects.
A set of objects are compatible if and only each pair in it is compatible.
Example 17 The following pairs are compatible:
Author and Author
fAuthorg and fTitleg
Answer )fAuthorg and Answer )fTitleg
Denition 18. Two web object are compatible if and only if
are compatible. A set of web objects are compatible if and only
if each pair of them is compatible.
Example The following set of web objects are compatible.
Denition 19. Let S be a set of (web) objects and S 0 a compatible subset of
S. Then S 0 is a maximal compatible set in S if there does not exist a (web) object
that is compatible with each object in S 0 .
Denition 20. Let S be a set of objects. The grouping operator G is dened
recursively on S as follows:
1 If S is a singleton set
2 If S is a compatible set of attributed objects
3 S is a set of set objects, then
is a maximal compatible
set of objectsg
It is extended to a set of web objects as follows:
1 If S is a compatible set of web objects of the form u
2 If S is divided into maximal compatible subsets S 1 ; :::; Sn such that
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 73
Denition 21. The powers of the operation TQ over the web database WDB
are dened as follows:
Example 19 Continuing with the Example 16, we have
fAnswer )fAuthorgg,
fAnswer )fTitlegg,
fAnswer )fAdvancedgg,
fAnswer )fHome Page Searchggg)
Theorem 1 Let WDB be a web database and Q a query. Then G(TQ " !(WDB))
is a minimal model of Q.
Proof: It is essentially the same as the proof in [18]
Denition 22. Let WDB be a web database and Q a query. Then the semantics
of Q under WDB is given by G(TQ " !(WDB)).
4. Implementation
Based on the conceptual model HTML-CM and the rule-based query language
HTML-QL presented in the previous sections, we have developed a prototype system
for web search and inference. The system will soon be available from the web
site http://www.scs.carleton.ca/mengchi/HTML-QL. In this section, we brie
y
describe the system.
The high level architecture of the system is shown in Figure 4.
The system is organized into four layers. The rst layer is the entire world-wide
web on the Internet. Because HTML documents are not only generated automatically
by specic application programs such as FrontPage and CoeeCup, but also
written by human manually, it is quite common that some documents have syntactic
errors. Like commercial web browsers such as Internet Explorer and Netscape,
our system can tolerate syntactic errors.
The second layer is the Intelligent Wrapper that implements HTML-CM. It accesses
the world-wide web through the Internet, fetches HTML documents and
Browser Interface
Textual Interface
Search and Inference Processor
Intelligent Wrapper
World Wide Web
Local Data
Repository

Figure

4. High Level System Architecture
converts them into web objects in HTML-CM. In order to speed-up query process-
ing, the Intelligent Wrapper also caches web objects in the local data repository
and builds proper indexes on these web objects. It allows the user to adjust web
objects by adding, adjusting or deleting attributes or objects and it can also learn
the pattern from the user's interaction and then process similar HTML documents
accordingly. For these reasons, it is called the intelligent wrapper.
The third layer of the system is the Search and Inference Processor that implements
HTML-QL. It is mainly in charge of query processing. It obtains queries to
be processed from the user interface layer and checks whether or not web objects
involved are in the local data repository. If web objects involved are not in the local
data repository, then it invokes the Intelligent Wrapper to fetch them. Then it uses
semi-naive bottom-up x-point computation to generate the result and sends the
query result to the user interface layer for proper display.
The last layer is the User Interface. Two kinds of interfaces are supported: textual
interface and browser interface. They provide dierent kinds of environment for the
user to issue commands and express queries, perform syntactical analysis, and pass
valid commands in internal format to the Search and Inference Processor. They
also display query results generated by the Search and Inference Processor to the
user in dierent format, the web objects generated by the Intelligent Wrapper, and
original web document like lynx and Netscape respectively.
5. Conclusion
The main contributions of the paper are the following. First, we have proposed
a conceptual model HTML-CM for HTML documents. Unlike other data mod-
A CONCEPTUAL MODEL AND RULE-BASED QUERY LANGUAGE FOR HTML 75
els that mainly focus on inter-document structures and hyperlink navigation, our
conceptual model focuses on the complex hierarchical structure within the HTML
documents (intra-document structure). It only has a few simple but powerful high
level constructs that can be used to best describe the contents in HTML docu-
ments. The HTML documents represented in this conceptual model are close to
human conceptualization/visualization of the documents. We have also presented
a set of generic rules to automatically convert HTML documents into this conceptual
model. Discovering rules to structure the HTML documents has already been
addressed in the literature such as [10, 13, 15, 25, 26]. However, the rules presented
in this paper are more general and systematic. During the conversion, we ignore
many features that are used to enhance the visual aspects of the web documents. In
other words, we lose some information during conversion. Thus, we cannot convert
web documents in our conceptual model back into HTML format. However, we can
capture the essence of HTML documents in a natural and intuitive way.
Second, we have presented HTML-QL, a rule-based language for querying HTML
documents over the Internet based on HTML-CM. Unlike other web query lan-
guages, HTML-QL provides a simple but very powerful way to query both the intra-document
structures and inter-document structures and allows the query results to
be restructured. Furthermore, HTML-QL has a rm logical foundation, which is
lacking in most other web query languages. The prototype system that supports
HTML-CM and HTML-QL have been implemented and will soon be available from
the web site http://www.scs.carleton.ca/mengchi/HTML-QL. The query language
and system can be easily extended to handle XML documents.
We note that although the approach works well on many HTML documents, it
is still the case that HTML pages can be found where it is di-cult to extract
useful information. We would like to extend the functionality of HTML-QL by
incorporating other useful features to make it a really useful tool for web search
and inference and investigate the computability and complexity issues of HTML-
QL queries. Using HTML-QL, we would also like to develop data extraction and
data integration tools based on the method proposed in [22, 20]. Our objective is
to build an intelligent web search engine on top of the search and inference system.

Acknowledgments

The research was partially supported by research and equipment grants from the
Natural Sciences and Engineering Research Council of Canada (NSERC). The authors
are also grateful to Yibin Su for implementing the system.



--R

Querying Semistructured Data.
The Lorel Query Language for Semistructured Data.
WebOQL: Restructuring Documents
Set Construction in a Logic Database Language.
Extensible Markup Language (XML) 1.0.
A Query Language and Optimization Techniques for Unstructured Data.
XML Path Language (XPath) Version 1.0.


A Query Language for a Web-Site Management System
Reasoning About Web-Site Structure
Database Techniques for the World-Wide Web: A Survey
Database Techniques for the World-Wide Web: A Survey
Extracting Semistructured Information from the Web.
On a declarative semantics for web queries.
Modeling Web Sources for Information Integration.
A Declarative Language for Querying and Restructuring the Web.
ROL: A Deductive Object Base Language.
Relationlog: A Typed Extension to Datalog with Sets and Tuples.
A Conceptual Model for the Web.
A Data Model for Semistructured Data with Partial and Inconsistent Information.

Integration of Semistructured Data with Partial and Inconsistent Information.
Querying the World Wide Web.
Formal Models of Web Queries.
Hierarchical Wrapper Induction for Semistructured Information Sources.

Object Exchange across Heterogeneous Information.
Principles of Database and Knowledge-Base Systems
Document Object Model (DOM) Level 2 Speci
--TR

--CTR
Mengchi Liu , Tok Wang Ling, Towards semistructured data integration, Web-enabled systems integration: practices and challenges, Idea Group Publishing, Hershey, PA,
HTML query language;rule-based query language;fixpoint logical semantics;data model for HTML;conceptual modeling