Token-Templates and Logic Programs for Intelligent Web Search.
We present a general framework for the information extraction from web pages based on a special wrapper language, called token-templates. By using token-templates in conjunction with logic programs we are able to reason about web page contents, search and collect facts and derive new facts from various web pages. We give a formal definition for the semantics of logic programs extended by token-templates and define a general answer-complete calculus for these extended programs. These methods and techniques are used to build intelligent mediators and web information systems.
Introduction
In the last few years it became appearant that there is an increasing need for more intelligent
World-Wide-Web information systems. The existing information systems are mainly document
search engines, e.g. Alta Vista, Yahoo, Webcrawler, based on indexing techniques
and therefore only provide the web user a list of document references and not a set of facts
he is really searching for. These systems overwhelm the user with hundreds of web page
candidates. The exhausting and highly inconvenient work to check these candidates and to
extract relevant information manually is left to the user. The problem gets even worse if
the user has to take comparisons between the contents of web pages or if he wants to follow
some web links on one of the candidate web pages that seem to be very promising. Then
he has to manage the candidate pages and has to keep track of the promising links he has
observed.
To build intelligent web information systems we assume the WWW and its web pages
to be a large relational database, whose data and relations can be made available by the
definition and application of special extraction descriptions (token-templates) to its web
pages. A library of such descriptions may then offer various generic ways to retrieve facts
from one or more web pages. One basic problem we are confronted with is to provide means
to access and extract the information offered on arbitrary web pages, this task is well known
as the process of information extraction (IE). The general task of IE is to locate specific
pieces of text in a natural language document, in this context web pages. In the last few years
many techniques have been developed to solve this problem [1, 6, 10, 11, 15, 21, 30], where
wrappers and mediators fulfill the general process to retrieve and integrate information
from heterogeneous data sources into one information system.
We focus our work on a special class of wrappers, which extract information from web
pages and map it into a relational representation. This is of fundamental interest because
it offers a wide variety of possible integrations into various fields, like relational databases,
spreadsheet applications or logic programs. We call this information extraction process
fact-retrieval, due to logic programming the extracted information is represented by ground
atoms. In this article we present a general framework for the fact retrieval based on our
special wrapper language, called token-templates. Our general aim was to develop a description
language for the IE from semi-structured documents, like web pages are. This
language incorporates the concepts of feature structures [25], regular expressions, unifi-
cation, recursion and code calls, to define templates for the extraction of facts from web
pages.
How does this contributes to logic programming? The key idea of using logic programs
for intelligent web browsing is as follows: Normally the user is guided by his own domain
specific knowledge when searching the web, manually extracting information and
comparing the found facts. It is very obvious that these user processes involve inference
mechanisms like reasoning about the contents of web pages, deducing relations between
web pages and using domain specific background knowledge.Therefore he uses deduction,
based on a set of rules, e.g. which pages to visit and how to extract facts. We use logic
programs in conjunction with token-templates to reason about the contents of web pages,
to search and collect relevant facts and to derive new facts from various web pages. The
logic programming paradigm allows us to model a background knowledge to guide the web
search and the application of the extraction templates. Furthermore the extracted facts in
union with additional program clauses correspond to the concept of deductive databases
and therefore provide the possibility to derive new facts from several web pages. In the
context of wrappers and mediators [30], token-templates are used to construct special wrappers
to retrieve facts from web pages. Logic programs offer a powerful basis to construct
mediators, they normalize the retrieved information, reason about it and depending on the
search task to fulfill, deduce facts or initialize new sub searching processes. By merging
token-templates and logic programs we gain a mighty inference mechanism that allows us
to search the web with deductive methods. We emphasize the well defined theoretical background
for this integration, which is given by theory reasoning [2] [26] in logical calculi,
whereas token-templates are interpreted as theories.
This article is organized as follows: in Section 2 we describe the language of token-
templates for the fact-retrieval from web pages. In Section 3 the integration of token-
templates into logic programs and the underlying T T Calculus is explained. Section 4
describes how logic programming techniques can be used to enhance the fact-retrieval
process with deductive techniques. A practical application of our developed methods, a
LogicRobot to search private advertisements, is briefly presented in Section 5. Related
approaches and conclusions are given in Section 6.
2. A Wrapper Language for Web Documents
In this section we describe our information extraction language, the token-templates. We
assume the reader to be familiar with the concepts of feature structures [25] and unification
2.1. The Fact Retrieval
We split the process of fact-retrieval into several steps, whereas the first step is the preprocessing
of the web page to be analyzed. We transform a web page as shown in Figure 1
into a list of tokens which we will explain in detail in section 2.2. In our existing system
(Section 5) this is done by the lexical analyzer FLEX [17] (by the definition of a FLEX
grammar to build tokens in extended term notation). We want to emphasize that we are not
bound to a special lexical analyzer generator tool like FLEX, any arbitrary tool can be used
as long as it meets the definition of a token.

Figure

1. An advertisement web page
This methods allows us to apply our techniques not only to HTML-documents, but also
to any kind of semi-structured text documents. Because we can construct arbitrary tokens,
our wrapper language is very flexible to be used in different contexts.
After the source code transformation of the web document, the matching and extraction
process takes place. Extraction templates built from tokens and special operators are applied
to the tokenized documents. According to the successful matching of these extraction
templates the relevant information is extracted by means of unification techniques and
mapped into a relational representation. We will now explain the basic element of our web
wrapper language, the token.
2.2. The Token
A token describes a grouping of symbols in a document. For example the text  Pentium
90  may be written as the list of tokens:
[token(type=html,tag=b), token(type=word,txt='Pentium'),
token(type=whitespace,val=blank), token(type=int,val=90),
token(type=html end,tag=b)]
We call a feature structure (simple and acyclic feature structure) a token, if and only if it
has a feature named type and no feature value that consists of another feature. A feature
value may consist of any constant or variable. We write variables in capital letters and
constants quoted if they start with a capital letter. Furthermore, we choose a term notation
for feature structures (token), that is different from that proposed by Carpenter in [4].
We do not code the features to a fixed00110011001100110000000000000000000000111111111111111111111100000000000000000000001111111111111111111111
token
type
tag a
html
Graph Notation Extended Term Notation
token(href=X,type=html,tag=a)

Figure

2. Token notations
argument position, instead we extend the
arguments of the annotated term, by the
notation
this offers us more flexibility in the handling
of features. Figure 2 shows the graph
notation of a token and our extended term
notation of it. In the following we denote
a token in extended term notation, simply
token.
2.3. Token Matching
In the following let us assume, that an arbitrary web page transformed into a token list
is given. The key idea is now to recognize a token or a token sequence in this token
list. Therefore we need techniques to match a token description with a token. For feature
structures a special unification, the feature unification was defined in [23]. For our purposes
we need a modified version of this unification, the token-unification.
and
tokens.
Let A 1 and A 2 be the feature-value sets of the tokens T 1 and T 2 that is A
and A
Further let be the set of features T 1 and T 2 have in common.
The terms T 0
are defined as follows: T 0
The tokens T 1 and T 2 are token-unifiable iff the following two conditions hold:
1 is unifiable with T 0
. The most general unifier (mgU)  of T 1 and T 2 is the mgU of
2 wrt. the usual definition [16, 13]
If (1) or (2) does not hold, we call T 1 and T 2 not token-unifiable, written T 1
6 tT 2 . We
token-unifiable with T 2 and  is the mgU of the unification from
.
The motivation for this directed unification 1 is to interpret the left token to be a pattern to
match the right token. This allows us to set up feature constraints in a easy way, by simply
adding a feature to the left token. On the other hand we can match a whole class of tokens,
if we decrease the feature set of the left token to consist only of the type feature.
Example:
token(type=word, int=X)
href='http://www.bmw.de') with
For ease of notation we introduce an alternative notation t k for a token of type k (the feature
type has value k), that is given by k or k(f are
the features and values of t k where n is the number of features of t k . We call this notation
term-pattern and define a transformation V on term-patterns such that V transforms the term-
pattern into the corresponding token. For example us
the token This transformation exchanges the
functor of the term-pattern, from type k to token and adds the argument to the
arguments. Now we can define the basic match operation on a term-pattern and a token:
be a term-pattern and T a token in extended term
notation. The term-pattern t k matches the token T , t k <  T , iff V(t k ) is token-unifiable
with T . The term-match is defined as follows:
Example: For the demonstration of the term-match operation, consider the three examples
mentioned above and the following modification:
word <  token(type=word, txt='Pentium') with
word(int=X) 6<  token(type=word,txt='Pentium')
html(href=Y) <  token(type=html, tag=a, href='http://www.bmw.de')
with
6 BERND THOMAS
2.4. Token Pattern
If we interpret a token to be a special representation of text pieces, the definition of term-matching
allows us to recognize certain pieces of text and extract them by the process of
unification. This means the found substitution  contains our extracted information.
But yet we are not able to match sequences of tokens in a tokenized web page. Therefore
we define the syntax of token-pattern, which will build our language to define templates for
the information extraction from web documents.
The language of token-patterns is built on a similar concept as regular expressions are.
The difference is, that the various iteration operators are defined on tokens. Beside these
basic operators we define greedy and moderate operators. These two operator classes
determine the enumeration order of matches. Greedy Operators are: ?; + and . Moderate
Operators are: !; and #. For example a token-pattern like word, matches zero or
arbitrary many tokens of type word, but the first match will try to match as many tokens of
type word as possible (greedy). Whereas the pattern #word will try in its first attempt to
match as less tokens as possible (moderate). This makes sense if a pattern is just a part of a
larger conjunction of patterns. Another advantage is given by the use of unification, which
in fact allows us with the later described concept of recursive token-templates to recognize
context sensitive languages.
In

Figure

2.4 we give an informal definition 2 for the semantics of token-patterns. Assume
that a tokenized document D is given. A match of a token-pattern p on D, p  D, returns
a set of triples (MS; RS; ), where MS is the matched token sequence, RS is the rest
sequence of D and  is the mgU of the token unifications applied during the matching
process.
We emphasize, that we compute all matches and do not stop after we have found one
successful match, though this can be achieved by the use of the once operator.
Example: Let us have a closer look at the source code of the advertisement web page (D)
shown in Figure 4 and the corresponding token-pattern (p) given in 5. This token-pattern
extracts the item name of the offered object (Item) and the description (Description) of the
item. For this small example our set of matches consists of a set with two tuples, where we
will leave out the matched sequence MS and the rest sequence RS, because we are only
interested in the substitutions  of each
2.5. Token-Templates
A token-template defines a relation between a tokenized document, extraction variables and
a token-pattern. Extraction variables are those variables used in a token-pattern, which are of
interest due to their instantiation wrt. to the substitutions obtained from a successful match.
pattern semantics
then the matched sequence is the list containing exactly
one element D(1) and RS is D without the first element. D(n) denotes the
n-th element of the sequence D.
?p1 Matches the pattern p1 once or never; first the match of p1 then the empty
match sequence is enumerated.
!p1 Matches the pattern p1 once or never; first the empty match sequence then
the match of p1 is enumerated.
+p1 Matches the pattern p1 arbitrarily often but at least once; uses a decreasing
enumeration order of the matches according to their length, starting with the
longest possible match.
p1 Matches pattern p1 arbitrarily often but at least once; uses an increasing
enumeration order of the matches according to their length, starting with the
shortest possible match.
p1 Matches the pattern p1 arbitrarily often; uses a decreasing enumeration order
of the matches according to their length, starting with the longest possible
match.
#p1 Matches the pattern p1 arbitrarily often; uses a increasing enumeration order
of the matches according to their length, starting with the shortest possible
match.
tn) The not operator matches exactly one token t in D, if no t
exists, such that t i < t holds. The token are excluded from the
match.
times(n; t) Matches exactly n tokens t.
any Matches an arbitrary token.
once(p1) The once operator 'cuts' the set of matched tokens by p1 down to the first
match of p1 ; useful if we are interested only in the first match and not in all
alternative matches defined by p1 .
Unification of X and the matched sequence of p1 ; only successful if p1 is
successful and if MS of p1 is unifiable with X .
p1 and p2 Only if p1 and p2 both match successfully, this pattern succeeds. The
matched sequence of p1 and p2 , is the concatenation of MS of p1 and
MS of p2 .
p1 or p2 p succeeds if one of the pattern p1 or p2 is successfully matched. The
matched sequence of p is either the matched sequence of p1 or p2 . The
and operator has higher priority than the or operator, (e.g. a and b or c
(a and b) or c)
Extended Token Patterns
token-template t1 to tn (see Section 2.5.1)
functions c1 to cn (see Section 2.5.1)

Figure

3. Language of Token-Patterns
<IMG SRC=img/bmp_priv.gif> Pentium 90  48 MB RAM,
Soundblaster AWE 64, DM 650,-. Tel.: 06743/ 1582

Figure

4. HTML source code of an online advertisement
#any and html(tag = img) and html(tag
and

Figure

5. Token-pattern for advertisement information extraction
Extraction variables hold the extracted information obtained by the matching process of the
token-pattern on the tokenized document.
Definition 3 (Token-Template). Let p be a token-pattern, D an arbitrary tokenized document
and in p. For applying the
substitution  to ~v. A token-template r is defined as follows:
Template definitions are written as: template r(D;
r is called the template name, ~v  is the extraction tupel and v are called extraction
variables.
Example: Consider the case where we want to extract all links from a web page. Therefore
we define the following token-template:
template link(D; Link; Desc) := #any
The first sub pattern #any will ignore all tokens as long as the next token is of type html and
meets the required features tag = a and href . After the following subexpression matched
and a substitution  is found, Link and Desc hold the extracted information. Now further
alternative matches are checked, for example the #any expression reads up more tokens
until the rest expression of the template matches again.
2.5.1. Extending Token-Templates
To be able to match more sophisticated syntactic structures, we extend the token-templates
with the three major concepts of Template Alternatives, Code Calls and Recursion
Template Alternatives: To gain more readability for template definitions we enhanced
the use of the or operator. Instead of using the or operator in a token-pattern like in the
template template t(D;~v) := alternatively define two templates:
template
template
where the templates t 1 and t 2 have the same name. In fact this does not influence the calculation
of the extraction tuples, because we can easily construct this set by the union of t 1 and t 2 .
Code Calls: A very powerful extension of the token-pattern language is the integration
of function/procedure calls within the matching process. We named this extension, code
calls. A code call may be any arbitrary boolean calculation procedure that can be invoked
with instantiated token-pattern variables or unbound variables that will be instantiated by
the calculation procedure. The following example demonstrates the use of a code call to
an database interface function db, that will check if the extracted Name can be found in
the database. On success it will return true and instantiates Birth to the birthday of the
person, otherwise the match fails. In this example we will leave out the token-pattern for
the recognition of the other extraction variables and will simply name them p 1 to
template person(D ; Name;
Especially the use of logic programs as code to be called during the matching process, can
guide the information extraction with additional deduced knowledge. For example, this can
be achieved by a given background theory and facts extracted by preceeding sub-patterns.
Template Calls & Recursive Templates: To recognize hierarchical syntactic structures in
text documents (e.g. tables embedded in tables) it is obvious to use recursive techniques.
Quite often the same sub-pattern has to be used in a template definition, therefore we
extended the token-pattern by template calls. A template call may be interpreted as an
inclusion of the token-pattern associated with the template to be called. For example the
first example template matches a HTML table row existing of 3 columns, where the first two
are text columns and the third contains price information. The terms set in squared brackets
function as template calls. Repeated application of this pattern, caused by the sub pattern
#any, gives us all table entries. The second template demonstrates a recursive template
call, that matches correct groupings of parenthesises.For a more detailed description of the
token-template language the reader is referred to [27].
template table row(D; Medium; Label; P rice) := ( #any
and [text col(Medium); text col(Label); price col(P rice)]
and html end(tag = tr))
template correct paren(D;
(word or  word and [correct paren( )] and  word )
and paren close )
3. Logic Programs and Token-Templates
In this section we will explain how token-templates can be merged with logic programs
(LP's). The basic idea of the integration of token-templates and LP's is to extend a logic
program with a set of token-templates (extended LP's), that are interpreted as special program
clauses. The resulting logic program can then answer queries about the contents
of one or more web documents. Intuitively token-templates provide a set of facts to be
used in logic programs. Extended LP's offer the possibility to derive new facts based on
the extracted facts from the WWW. From the implementational point of view these token-
template predicates may be logical programs or modules that implement the downloading
of web pages and the token matching. From the theoretical point of view we consider these
template sets to be axiomatizations of a theory, where the calculation of the theory (the
are performed by a background reasoner.
In the following we refer to normal logic programs when we talk about logic programs.
In Section 3.1 we describe how token-templates are interpreted in the context of first order
predicate logic. The extension of a calculus with template theories, which will lead to the
Calculus, is defined in Section 3.2. Section 4.1 and 4.2 will give some small examples
for the use of token-templates in logic programs.
We assume the reader to be familiar with the fields of logic programming [16] and theory
reasoning [2] [26].
3.1. Template Theories
In the context of first order predicate logic (PL1) we interpret a set of token-templates to be
an axiomatization of a theory. A token-template theory T T is the set of all template ground
atoms, that we obtain by applying all templates in T . For example, consider the template
set ft(D; v; p)g. Assume p to be an arbitrary token-pattern and v an extraction tupel. A
template theory for T is given by T ft(D;v;p)g := ft(D; v p)g.
This interpretation of token-templates associates a set of ground unit clauses with a given
set of token-templates. The formal definition is as follows:
Definition 4 (T emplate Theory, T T Interpretation, TT Model). Let T be a set of
token-templates: )g. A token-template
theory T T for T is defined as follows:
Let P be a normal logic program with signature , such that  is also a signature for
A  Interpretation I is a TT  Interpretation iff I
A Herbrand T T  Interpretation is a T T  Interpretation, that is also a herbrand
interpretation.
A TT  Interpretation I is a TT Model for P iff I
Let X be a clause, wrt. X is a logic T T Consequence from P , P
Example: Consider a token-template advertise with the token-pattern given in Figure 5
and the extraction variables Item and Description for the example web source code shown
in

Figure

1. The corresponding template theory for the template advertise is the set:
3.2. The TT Calculus
So far we have shown when a formula is a logical consequence from a logic program and
a template theory. This does not state how to calculate or check if a formula is a logical
consequence from an extended logic program. Therefore we have to define a calculus for
extended logic programs. But instead of defining a particular calculus we show that any
sound and answer-complete calculus for normal logic programs can serve as calculus for
extended logic programs.
K be a sound and answer-complete calculus for normal
logic programs and ' is the derivation defined by K. Let P be a normal logic program, T
a set of token-templates and TT the template theory for T . A query 9 Q with calculated
substitution  is TT derivable from P , P ' TT Q, iff Q is derivable from P [ TT ,
calculus K, with TT Derivation is called TT Calculus.
Theorem 1 (Soundness) Let K be a T T Calculus and ' TT the derivation relation
defined by K. Let T be a set of token-templates, T T the template-theory for T and Q a
query for a normal program P . Further let  be a substitution calculated by ' TT . Then
Theorem 2 (Completeness) Let K be T T Calculus and' TT the derivation relation
defined by K. Let T be a set of token-templates, T T the template-theory for T and Q a
query for a normal program P . Let  be a correct answer for Q,  a calculated answer
and
a substitution.
Soundness and Completeness: Let K be a T T Calculus and ' TT the derivation relation
defined by K. Let T be a set of templates , T T the template theory of T and Q a query on
the normal program P . Let  be a calculated substitution for Q such that:
sound/completness of '
To prove: P [ TT
logical consequence
Consequence
Example: In Figure 6 an example T T Derivation based on the SLD-Calculus [12] is
shown. The calculation of the template theory is done by a theory box [2], this may be any
arbitrary calculation procedure, that implements the techniques needed for token-templates.
Furthermore this theory boxhas to decide if a template predicate, like institute('http://www.uni-
koblenz.de',Z,P) can be satisfied by the calculated theory. Let us have a closer look at the
logic program P given in Figure 6:
b(uni,'http://www.uni-koblenz.de') A given web page containing some information about
a university.
a(X,Z) b(X,Y), institute(Y,Z,P) An institution X has an department Z if there exists
an web page Y describing X and we are able to extract department names Z from Y .
With this given logic program and the template definition T we can find a SLD T T Derivation,
assumed our template theory is not empty. What this example shows is: modeling knowledge
about web pages by logic programs and combining this with token-templates allows
us to query web pages.
Fact-Retrieval
Goal:
Template
P:
T:
Theory
Applying the template
gives
Answer:
template institute(Document,Z,P) := tokenpattern

Figure

4. Deductive Techniques for Intelligent Web Search
Logic programming and deduction in general offer a wide variety to guide the web search
and fact-retrieval process with intelligent methods and inference processes. This section
describes some of these techniques.
4.1. Deductive Web Databases
Assume we know two web pages of shoe suppliers, whose product descriptions we want
to use as facts in a deductive database. Additionally we are interested in some information
about the producer of the product, his address and telephone number that can be retrieved
from an additional web page. Therefore we define two token-templates, price list and
address. To simplify notation we leave out the exact token-pattern definitions instead we
The following small deductive database allows us to ask for articles and to derive new
facts that provide us with information about the product and the producer. We achieve this
by the two rules article and product, which extract the articles offered at the web pages and
will derive new facts about the article and the producer.
14 BERND THOMAS
template price list(Document ; Article; Price;
template address(Document
web page( 0 ABC Schuhe
web page( 0 Schuhland
article(Supplier
web page(Supplier ; Document);
price list(Document ; Article; Price; ProducerUrl ; Pattern)
product(Supplier
article(Supplier
Example: Here are some example queries to demonstrate the use of the deductive web
database:
Select all products with article name "Doc Martens" that cost less than 100:
rice < 100
Select all products offered at least by two suppliers:
4.2. Optimizing Web Retrieval
The following example shows how a query optimization technique proposed by Levy [19]
can be implemented and used in extended logic programs. To avoid the fetching of senseless
web pages and starting a fact-retrieval process we know for certain to fail, Levy suggests
the use of source descriptions. For the fact retrieval from the WWW this might offer a great
speed up, because due to the network load the fetching of web documents is often very time
intensive. In the context of extended logic programs, we can easily apply these methods,
by the definition of rules, whose body literals define constraints on the head arguments
expressing our knowledge about the content of the web pages. The following example
illustrates these methods:
rice > 20000; P rice < 40000;
rice > 40000; P rice <
template cars(WebPage; P rice; Country)
Assuming we are interested in american cars that costs 50000 dollars, the query prod-
will retrieve the according offers. Because of the additional constraints
on the price and the country given in the body of the rule offer, the irrelevant web page
with german car offers is left out. By simple methods, provided by the logic programming
paradigm for free, we are able to guide the search and fact retrieval in the world wide web
based on knowledge representation techniques [3] and we are able to speed up the search
for relevant information.
4.3. Conceptual Reasoning
Many information systems lack of the ability to use a conceptual background knowledge
to include related topics of interest to their search. Consider the case that a user is interested
in computer systems that cost less than 1000 DM. It is obvious that the system
should know the common computer types and descriptions (e.g. IBM, Toshiba, Compaq,
Pentium, Notebook, Laptop) and how they are conceptually related to each other. Such
knowledge will assist a system in performing a successful search. One way to represent
such knowledge is by concept description languages or in general by means of knowledge
representation techniques. In the last few years it showed up that logic is a well suited
analytic tool to represent and reason about represented knowledge. Many formalisms have
been implemented using logic programming systems, for example PROLOG.
For example a simple relation is a can be used to represent conceptual hierarchies to
guide the search for information. Consider the following small knowledge base:
is a(notebook; computer)
is a(desktop; computer)
is a(X; notebook) notebook(X)
relevant(Q; Z) is a(Z; Q)
relevant(Q; Z) is a(Y; Q); relevant(Y; Z)
Assume our general query to search for computers less than 100 DM is split into a sub
query like relevant(computers; X) to our small example knowledge base. The query
computes a set of answers:
This additional inferred query information  can be used in two different ways:
1. The derived conceptual information  is used to search for new web pages, e.g. by
querying standard search engines with elements of  as search keywords. On the
returned candidate pages further extended logic programs can be applied to extract
facts.
2. The information extraction process itself is enhanced with the derived information  by
reducing the constraints on special token features in the token-templates to be applied.
Consider the case where only a single keyword Q is used with a token pattern to
constrain the matching process e.g. word(txt=Q). We can reduce this constrainedness
by constructing a more general (disjunctive) pattern by adding simple term-patterns,
whereas their feature values consist of the deduced knowledge , e.g. word(txt=Q) or
That means we include to the search
all sub concepts (e.g. computer instances (e.g. 0 ThinkPad 0 )
of the query concept.
5. The LogicRobot
This section will give a short overview of an application we implemented using the described
methods and techniques. A brief explanation of a domain dependent search engine for an
online advertisement newspaper is given.
5.1. The Problem
Very often web pages are organized by a chain of links the user has to follow to finally reach
the page he is interested in. Or the information the user wants to retrieve is split into many
pages. In both cases the user has to visit many pages to finally reach the intended page or to
collect data from them. To do this manually is a very exhausting and time consuming work
and furthermore it is very difficult for the user to take comparisons between the information
offered on the various web pages. Therefore an automatic tool to follow all links, to collect
the data and to provide the possibility to compare the retrieved information is needed to
free the user from this annoying work.
We call web information systems based on logic programs and token-templates Logi-
cRobots. Similar to physical robots they navigate autonoumasly through their environment,
the web. According to their ability to analyze and reason on web page contents and the
incorporation of knowledge bases they are able to percept their environment, namely what's
on a web page. Due to the underlyinglogic program and the used AI techniques, e.g. knowledge
representation, default reasoning etc., they act by collecting facts or follow up more
promising links. The problem we focused on was to build a LogicRobot for a web vendor
offering private advertisements. Some of the offered columns forces the user to follow
about 80 to 100 links to see all advertisements, which is of course not very user-friendly.
A more elegant way would be to offer a web form where the user can specify the column
or columns to be searched either by entering a specific name or a keyword for a column
name, a description of the item he is searching for, a price constraint like less, greater or
equal to and finally a pattern of a telephone number to restrict the geographical area to be
searched. Figure 7 depicts the three main templates used for extracting information about
advertisements similar to those shown in Figure 4. The LogicRobot web interface for this
special task is presented in Figure 8 and a sample result page is given in Figure 9.
template price(Price) := once( # any and ? (word(value='VB') or word(value='FP'))
and word(value='DM') and ( (int(value=P) and fcfloat(P,Price)g)
or (float(value=P) and fprice
template telefon(T) := # any and word(value='Tel') and ? punct(value='.')
and ? punct(value=':') and
and ? (punct or op) and +int)))
template product description(Article,Desc) := # any and html(tag=img) and html(tag=b)
and
and

Figure

7. Templates used for telefon number, price and advertised product extraction

Figure

8. The LogicRobot web interface
5.2. Implementational Notes
The LogicRobot for the search of advertisements is based on the logic programming library
TXW3 [28] that implements the techniques presented in this paper using ECLIPSE-Prolog
[8]. ECLIPSE supports modularized logic programming, so we modularized the architecture
of the LogicRobot into two main modules, the first module containing all needed
token-template definitions and the second the prolog program implementing the appropriate
template calls, the evaluation of the price constraints and further control operations. This
prolog module is executed by the CGI mechanism and communicates with the local http
daemon via stdin/stdout ports. So there is no additional server programming or network
software needed to setup a search engine based on extended logic programs.
By only 5 template definitions and approx. 200 lines of prolog code we implemented this
LogicRobot. The tests we carried out with our application are very promising. For example
the query answering time, which contains fetching, tokenizing, extracting and comparing
is beneath 2 minutes for 100 web pages of advertisements (Figure 1) . We think this is a
very promising way for a domain specific search tool, that can be easily extended by AI
methods, that offers a flexible and fast configurability by means of declarative definitions
(e.g. using PROLOG) and most important this concept of LogicRobots can be applied to
various information domains on the World Wide Web.
6. Related Work and Conclusion
We presented the token-template language for the IE from semistructured documents, especially
from web pages. We showed how our wrapper language can be merged with logic
programs and gave a formal definition for the extension of an arbitrary answer complete first
order logical calculus with template theories. In conjunction with the area of logic programming
and deductive databases we can use these wrapper techniques to obtain inferences or
new deductively derived facts based on information extracted from the WWW. Furthermore
these methods can be used to build intelligent web information systems, like LogicRobots,
that gain from the closely related areas like deductive databases, knowledge representation
or logic programming based AI methods. We also showed how already developed
query optimization techniques (Section 4.2), can easily be integrated into our approach.
Our methods have been successfully integrated and used in the heterogeneous information
system GLUE [20] to access web data and integrate it into analytical and reasoning processes
among heterogeneous data sources (e.g. relational databases, spreadsheets, etc. In
addition to our theoretical work we also implemented a logic programming library TXW3
that provides the language of token-templates and various other logic modules to program
LogicRobots for the WWW.
Several web information systems have been developed in the last few years. One class
of applications called Softbots, which are domain specific automated search tools for the
WWW, searching autonomously for relevant web pages and user requested informations,
are similar to our concept of a LogicRobot. But such existing systems like Ahoy! [24] or
Shopbot use either tailored extraction techniques (Ahoy!) that are very domain specific or
their extraction techniques are based on highly restrictive assumptions about the syntactical
structure of a web page (Shopbot). Both systems do not follow the concept of a general

Figure

9. Query result page
purpose extraction language like token-templates are. Token-templates are applicable to
any kind of semistructured text documents, and hence not restricted to a specific domain.
Systems like IM [18] or W3QS [14] also provide means to query web information sources.
Though Levy et. al. also choose a relational data model to reason about data, and show
several techniques for source descriptions or constructing query plans, they leave the problem
of information extraction undiscussed in their work. We showed solutions for both the
extraction of facts and reasoning by extended logic programs. The W3QS system uses a
special web query language similar to the relational database query language SQL. W3QS
uses enhanced standard SQL commands, e.g. by additional external unix program calls or
HTML related commands. Though an additional construction kit for information extrac-
tion processes is given, this seems to be focused only on the detection of hyper links and
their descriptions. The concept of database views for web pages is also introduced, but
no information about recursive views is provided, whereas extended logic programs offer
these abilities.
Heterogeneous information systems, like DISCO [29], GLUE [20], HERMES [22], Infomaster
[9] or TSIMMIS [5] all use special mediator techniques to access web information
sources among other data sources. These systems use their own mediator model (language)
to interface with the special data source wrappers. The system HERMES for example is
based on a declarative logical mediator language and therefore is similar to our approach
using extended logic programs as mediators and token-templates as special wrapper lan-
guage. The advantage of our presented approach is simply, that the above named systems
except TSIMMIS and GLUE do not incorporate a general purpose wrapper language for
text documents. Additionally work on the expressive power of the mediator languages and
the used wrapper techniques of the other systems is of interest.
Different from the template based extraction languages described in [11] and [6] or the
underlying language used in the wrapper construction tool by Gruser et. al. [10], token-
templates incorporate the mighty concepts of recursion and code calls. These concepts allow
the recognition and extraction of arbitrary hierarchical syntactic structures and extends the
matching process by additional control procedures invoked by code calls. Especially logic
programs used as code calls can guide the extraction process with a manifold of AI methods
in general.
Notes
1. In the sense that the feature set of the left token must be a subset of the feature set of the right token.
2. see [27] for a detailed formal definition.



--R

Wrapper generation for semistructured internet sources.
Theory Reasoning in Connection Calculi and the Linearizing Completion Approach.
Principles of Knowledge Representation.
Typed Feature Structures: an Extension of First-order Terms
The TSIMMIS project: Integration of heterogeneous information sources.
Relational Learning of Pattern-Match Rules for Information Extraction
A scalable comparison-shoppingagent for the world-wide web
International Computers Limited and IC-Parc
An Information Integration System.
A wrapper generation toolkit to specify and construct wrappers for web accesible data.
Extracting semistructured information from the web.
Linear Resolution with Selection Function.
A multidisciplinary survey.
A query system for the world-wide web
Wrapper Induction for Information Ex- traction
Foundations of Logic Programming.


Querying HeterogeneousInformation Sources Using Source Descriptions.

A flexible meta-wrapper interface for autonomous distributed information sources
HERMES: Reasoning and Mediator System
An Introduction to Unification-Based Approaches to Grammar
Dynamic reference sifting: A case study in the homepage domain.
Records for Logic Programming.
Automated Deduction by Theory Resolution.

The txw3-module
Scaling Heterogeneous Databases and the Design of Disco.
Mediators in the architecture of future information systems.
--TR

--CTR
Steffen Lange , Gunter Grieser , Klaus P. Jantke, Advanced elementary formal systems, Theoretical Computer Science, v.298 n.1, p.51-70, 4 April
logic robots;softbots;information extraction;template based wrappers;logic programming;mediators;deductive web databases;theory reasoning