General Strategy for Querying Web Sources in a Data Federation Environment

Introduction

Federated databases offer information integration on demand in dynamic environments, where data warehousing approaches are not feasible (Sheth and Larson 1990, Geer 2003). In modern relational database management systems, even non-relational sources can be included in a data federation via “wrappers” so that they can be queried as if they are part of a single large database (Somani, Choy, & Kleewein 2002; Thiran, Hainaut, Houben, & Benslimane 2006). Wrappers are mechanisms by which the federated server interacts with non-relational data sources by performing operations such as connecting to a data source and retrieving data from it iteratively.

Retrieving data from web sources, however, is complicated because data is semi-structured and web sources may have requirements (e.g. they may require forms to be filled before returning data); thus general-purpose wrappers for arbitrary web pages are not provided in data federation systems. Instead the user needs to implement a custom wrapper for each web source by coding data extraction patterns and parts of the federated query planning protocol in a low-level programming language such as C. This convolution of code with the data extraction and planning knowledge turns wrapper development into a daunting task, results in code duplication, and slows down the data federation process.

Within the last decade or so, many research projects (Papakonstantinou, Gupta, & Haas 1998; Levy, Rajaraman, & Ordille 1996; Li, & Chang 2000; Zadorozhny, Bright, Vidal, Raschid, & Urhan 2002; Li 2003; Pentaris, & Ioannidis 2006) offered algorithmic solutions to “query planning with source restrictions”. The goal of these studies was to offer an expressive language to specify source restrictions, and let the federated query planner come up with an optimal plan using this knowledge. These approaches do not need any cooperation from the individual data sources other than knowing about their limitations. Had they found their way into commercial systems, they would eliminate part of the code and knowledge convolution problem: the wrapper developer would only need to code the data extraction knowledge and not worry about the query planning aspects. Yet the separation of code and knowledge would still not be satisfactorily achieved in non-cooperative federated query planners. For this study, we have chosen to work with IBM DB2’s cooperative federated query planner, which poses more challenges than the non-cooperative ones. Our focus is on improving the usability and maintenance aspects of the wrapper development process without requiring any changes in its underlying data federation technology. We do not offer yet another proposal to rewrite a state of the art distributed query planner (Kossmann 2000), or create an independent infrastructure for querying Internet data sources (Braumandl et al. 2001, Suciu 2002), but provide a non-intrusive approach that works with what is available today with minimal effort.

We have tested our prototype implementation with numerous web sites. A moderate user with no programming experience can include a typical web site into a data federation in less than an hour. The process often takes much longer when the existing procedural coding approach is used by an experienced programmer. Furthermore, explaining, learning and tutoring wrapper development become much easier, as the task changes from writing and debugging a program to specifying and debugging knowledge.

In the rest of this paper, we start with a motivational example that illustrates the need for data federation involving web sources. We then provide some background on data federation with non-relational data sources and describe the current architectural difficulties of incorporating a web source. Next, we describe our approach to wrapper development, and the algorithms used to perform planning and optimization for web sources with capability restrictions. We end with an overview of related work and future research issues.