Querying the Web

Dateline: 05/09/00

Various technologies for intelligent information retrieval were developed recently due to the explosive growth in the amount of data available electronically. This data resides in many different forms, ranging from totally unstructured forms like free text files to highly structured formats in relational database systems. The majority of the data on the Web is semi-structured and therefore has no fixed schema. Even if some structure exists, it is often implicit, and not as regular as expected in the standard database systems. These facts raise several issues that standard query languages like SQL (Standard Query Language) do not address. Surprisingly, there are several proposals of models and query languages for semi-structured data that can enable easier development of information retrieval and information integration systems.

WebSQL is one of the most popular SQL-like query languages for extracting information from the Web. It can be used for automating many Web-related tasks that require the systematic processing of either all the links in a page, all the pages that can be reached from a given URL through paths that match a pattern, or a combination of both. The WebSQL query engine is a library of Java classes, and WebSQL queries can be easily embedded into Java programs. This allows users to access the Web from Java at a much higher level of abstraction than a bare HTTP request, combining queries with controlled automated navigation.
WebSQL models Web sites as a relational database of two relations: Document and Anchor. The Document relation has one tuple for each document in the Web and the Anchor relation has one tuple for each anchor in each document in the web. Taking all of this into account, here is a typical WebSQL query:

SELECT d.url
FROM Document d SUCH THAT "http://ai.about.com" ->* d,
WHERE d.text CONTAINS "artificial intelligence"
OR d.title CONTAINS "artificial intelligence"

This query searches for pages related to artificial intelligence in the About.com Artificial Intelligence site. The syntax "->*" denotes that all local paths (i.e. reside in the same server as this one) of any length are to be searched. Similarly, the language uses the symbols #> for a link in the same document, and => for a link to another, global site. In general, link types can be combined in full regular expressions. For more information, see the on-line paper on WebSQL that explain more advanced and powerful queries for finding broken links in a collection of documents, finding references in documents in other servers to local pages, and defining the scope of a full-text index.

In this data model the text of an HTML document is a monolithic object, and therefore its analysis and interpretation is limited to simple text matching techniques. Current work involves several extensions of the language that will make use of the document structure when it is known.

Another solution, Lorel Query Language, developed at Stanford University, is based on OQL (Object Query Language) and provides powerful path traversal operators and makes extensive use of type coercion to help yield intuitive results for all queries over XML data. While query languages such as Lorel (or even SQL) are vital for exploiting known data relationships, users are often interested in finding data based on "fuzzy" relationships. Lorel can rank database objects based on their proximity to other objects, where the proximity measures are based on distances in the graph linking the objects together.

W3QS (WWW Query System) from Computer Science Department - Technion, uses W3QL, a high level query language, viewing the Web as an ultra large database. It is a "SQL-like", Unix based system, with queries addressing both structure and content. However, the implementation of the system is still not available for download.

The Concordia Database Research Group is involved in a project whose primary aim is to design and implement WebLog, a declarative language exploiting both content and structure of Web data. Again, there is no publicly available download address.

ARANEUS project aims at developing tools for the management of data coming from the Web. The proposed techniques are based on database technology, where Web sites are described using a formal data model. Based on the model, tools and methodologies are developed for wrapping, querying, integrating, designing and implementing Web sites. The system prototype has been implemented in Java.

UnQL is a language for querying semi-structured data that can be modelled as labelled graphs. Example data sources include Web sites, semi-structured files like bibliographies, and biological databases. UnQL's semantics are specified formally by UnCAL, a calculus for unstructured data. UnQL queries are expressed in UnCAL as recursive functions over graphs. UnQL also allows users to query both a graph's structure (the relationships between linked HTML files) and its data (the values of hyperlinks and text in HTML files).

WebOQL is a system developed at the University of Toronto for extracting data from semi-structured sources. It is based on a "middleware" approach to data integration: the use of a simple and flexible, schema-less data model into which many data structures can be logically mapped, wrappers that perform the mappings, and a powerful query language that provides facilities for handling data with unknown or irregular structure.

WHIRL is a system that's designed to integrate information from various places on the Web. Rather than exploring a number of sites to get the information you want, WHIRL enables you to simultaneously query a number of related sites using a database-like interface. Technically, the main innovation in WHIRL is a new sort of "soft" database system, which uses text-matching methods developed in information retrieval to approximately match names.

World Wide Web Wrapper Factory (W4F) is a toolkit for generation of wrappers for Web sources. It consists of a retrieval language to identify Web sources, a declarative extraction language (HEL) to express robust extraction rules and a mapping interface to export the extracted information into some user-defined data-structures. To assist the user and make the creation of wrappers rapid and easy, the toolkit offers some WYSIWYG support via wizards. It has been successfully used to generate wrappers for database systems and software agents, making the content of Web sources easily accessible to any kind of application. Another service had been announced recently - recycling HTML pages into XML documents, automatically generating DTD of the generated document.

WebDB is a Web query system that supports comprehensive database-like query functionalities. WebDB supports queries on not only document level information (e.g. title, URL, keywords) but also intra-document structures (e.g. tables, forms, and images) and inter-document linkage information (e.g. URLs and anchors). A novel visual user interface, WebIFQ (Web In-Frame-Query), assists users in specifying queries and visualizing query criteria including document metadata, structures, and linkage information.

The goal of another interesting project, TSIMMIS (The Stanford-IBM Manager of Multiple Information Sources), is to develop tools that facilitate the rapid integration of heterogeneous information sources that may include both structured and semi-structured data. TSIMMIS has components that translate queries and information (source wrappers), extract data from World Wide Web sites, combine information from several sources (mediator), and allow browsing of data sources over the Web.

Given the expectation that XML data will become as prevalent as HTML documents, an increased demand for engines that can query both XML data's content and its structure is expected. Relatively new query language for XML, XML-QL, features standard SELECT-WHERE constructs and borrows features of query languages recently developed by the database research community for semi-structured data. XML-QL can express queries, which extract pieces of data from XML documents, as well as transformations, which can map XML data between DTDs and can integrate XML data from different sources.

For more information on this topic see an excellent review of the field titled "Web Query Languages, Intelligent Information Integration", written by Alan K. Dippel.

A great deal of the Web content is becoming more and more interactive and a page is presented to the user based on how they respond to prompts. All of the above models have difficulties with Web structures that change interactively. Some new solutions (like Network Query Language) have tackled this problem more successfully, but the shift from machine-readable to machine-understandable Web content will require more radical solutions. Next time we'll explore approaches for bridging this gap and making the Web more "semantic".