Query processing over relations extracted from text databases
Luis Gravano, Alpa Jain · 2008
Text documents often embed data that is structured in nature, and this structured data is increasingly exposed using information extraction systems. Information extraction systems generate structured relations from documents, thus enabling expressive, structured queries over text databases. This dissertation studies the problem of processing structured queries over relations extracted from text databases. To process structured queries over text databases, we face multiple challenges. One key challenge is efficiency: information extraction is a time-consuming process, so query processing strategies should minimize the number of documents that they process. Another key challenge is output quality: information extraction systems are often far from perfect, and might output erroneous information or miss information that they should capture, hence hurting output accuracy and completeness. At the same time, query processing decisions, such as the choice of information extraction systems or document retrieval strategies, also impact the output quality. Finally, depending on the nature of the information need, users may have varying preferences regarding the execution efficiency and quality expected from the querying process. This dissertation builds on the critical observation that, in addition to efficiency, which is important just as in traditional relational query optimization, the output quality of an execution is critical. In our extraction-based scenario, query processing can be decomposed into a sequence of basic steps: retrieving relevant text documents, extracting relations from the documents, and joining extracted relations for queries involving multiple relations. Each of these steps presents different alternatives and together they form a space of possible query execution strategies. Our goal is to consider the user-specified requirements for execution efficiency and quality, and choose an execution strategy for each query based on a principled, cost-based comparison of the alternative execution strategies. We first introduce a simple, integrative optimization approach for processing queries involving single as well as multiple extracted relations. This approach considers each execution strategy as a whole and exploits database-specific statistics to predict the execution strategy characteristics. We then move towards an in-depth understanding of the impact of each component of an execution strategy on the overall execution. With this in mind, we rigorously analyze the critical components of an execution strategy and build statistically robust representations for information extraction systems, as well as statistical models for document retrieval strategies and join processing algorithms. These models help predict the efficiency and output quality of a variety of query execution strategies. Finally, we also consider the common scenario where information extraction systems report the extracted tuple together with scores that reflect the confidence in the correctness of the extracted tuples. Specifically, we present query processing algorithms that leverage these confidence scores and efficiently produce the high-confidence tuples, in turn discarding extracted tuples that are likely to be incorrect. In summary, this thesis presents a principled query optimization approach for processing structured queries over text databases, taking into consideration both the efficiency and the output quality of the query execution strategies. Our hope is that the contributions of this work will help shrink the gap between structured databases and text databases, by enabling the seamless and expressive querying of all available information, regardless of whether it is in structured databases or embedded in natural language text.