Efficient IR-Style Keyword Search over Relational Databases
Elsevier eBooksPublished 1 January 2003
Vagelis Hristidis, Yannis Papakonstantinou, Luis Gravano
Citations536
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
This paper adapts IR-style document-relevance ranking strategies to the problem of processing free-form keyword queries over RDBMSs, and develops query-processing strategies that build on a crucial characteristic of IR- style keyword search: only the few most relevant matches are generally of interest.
Abstract
This chapter presents a system for efficient information retrieval (IR) -style keyword search over relational databases. A query in the model is simply a list of keywords and does not need to specify any relation or attribute names. The answer to such a query consists of a rank of "tuple trees," which potentially include tuples from multiple relations that are combined via joins. To rank tuple trees, this chapter introduces a ranking function that leverages and extends the ability of modern relational database systems to provide keyword search on individual text attributes and rank tuples accordingly. In particular, the ranking function appropriately combines the relational database management systems (RDBMS) provided scores of individual attributes and tuples. The chapter introduces several top-k query-processing algorithms whose relative strengths depend, for example, on whether queries have Boolean-"AND" or "OR" semantics.
Keywords
Computer Science
Computer Networks and ISDN SystemsThe anatomy of a large-scale hypertextual Web search engine
15,828 Citations1998Sergey Brin, Lawrence M. Page
This paper provides an in-depth description of Google, a prototype of a large-scale search engine which makes heavy use of the structure present in hypertext and looks at the problem of how to effectively deal with uncontrolled hypertext collections where anyone can publish anything they want.
IEEE Data(base) Engineering BulletinModern Information Retrieval : A Brief Overview
1,531 Citations2001Amit Singhal
This article is a brief overview of the key advances in the field of Information Retrieval, and a description of where the state-of-the-art is at inThe field.
Journal of Computer and System SciencesOptimal aggregation algorithms for middleware
941 Citations2003Ronald Fagin, Amnon Lotem +1 more
Keyword searching and browsing in databases using BANKS
872 Citations2003Gaurav Bhalotia, Arvind Hulgeri +3 more
BANKS is described, a system which enables keyword-based search on relational databases, together with data and schema browsing, and presents an efficient heuristic algorithm for finding and ranking query results.
Elsevier eBooksDiscover
787 Citations2002Vagelis Hristidis, Yannis Papakonstantinou
It is proved that DISCOVER finds without redundancy all relevant candidate networks, whose size can be data bound, by exploiting the structure of the schema and the selection of the optimal execution plan (way to reuse common subexpressions) is NP-complete.
XRANK
773 Citations2003Guo Lin, Feng Shao +2 more
The XRANK system is presented, designed to handle the novel features of XML keyword search, which naturally generalizes a hyperlink based HTML search engine such as Google and can be used to query a mix of HTML and XML documents.
DBXplorer: a system for keyword-based search over relational databases
731 Citations2003Sanjay Agrawal, Surajit Chaudhuri +1 more
DBXplorer, a system that enables keyword-based searches in relational databases using a commercial relational database and Web server and allows users to interact via a browser front-end is discussed.
Evaluating top-k queries over Web-accessible databases
276 Citations2003Nicolas Bruno, Luis Gravano +1 more
This paper studies how to process top-k queries efficiently in this setting, where the attributes for which users specify target values might be handled by external, autonomous sources with a variety of access interfaces.
Keyword proximity search on XML graphs
270 Citations2004Vagelis Hristidis, Yannis Papakonstantinou +1 more
This work proposes and experimentally evaluates algorithms to minimize the number of queries sent to the database to output the top-K results and provides theoretical and experimental points for the selection of the appropriate set of precomputed path relations.
PREFER
265 Citations2001Vagelis Hristidis, Nick Koudas +1 more
The results indicate that the proposed algorithms are superior in performance compared to other approaches, both in preprocessing (preparation of materialized views) as well as execution time.
Preemptive priority-based scheduling: an appropriate engineering approach
255 Citations1995Alan Burns
Scheduling theories for fixed priority scheduling are now sufficiently mature that a genuine engineering approach to the construction of hard real-time systems is possible, and a flexible computational model is adopted that can accommodate periodic and sporadic activities.
Computer NetworksIntegrating keyword search into XML query processing
225 Citations2000Daniela Florescu, Donald Kossmann +1 more
This work proposes an extension to XML query languages that enables keyword search at the granularity of XML elements, that helps novice users formulate queries, and also yields new optimization opportunities for the query processor.
Supporting Incremental Join Queries on Ranked Inputs
195 Citations2001Apostol Natsev, Yuan‐Chi Chang +3 more
This paper investigates the problem of incremental joins of multiple ranked data sets when the join condition is a list of arbitrary user-defined predicates on the input tuples and proposes an algorithm that enables querying of ordered data sets by imposing arbitrary userdefined join predicates.
Proximity Search in Databases
195 Citations1998Roy Goldman, Narayanan Shivakumar +2 more
This paper implements a prototype search engine that uses a model based on textual proximity of keywords within each document to enable keyword searches over databases, and has found it very effective for quickly finding relevant information.
Advances in real-time systems
188 Citations1995Sang H. Son
Part 1 Real-time operating systems: software overview of HARTS - a distributed real-time system a reflective architecture for real- time operating systems CHAOS -real-time objects and atomicity for multiprocessors design and implementation of maruti-II.
IEEE Transactions on Knowledge and Data EngineeringSupporting ranked Boolean similarity queries in MARS
172 Citations1998M. Ortega, Yong Rui +4 more
The ranking and retrieval algorithms developed in MARS based on the Boolean retrieval model are discussed and the results of the experiments that demonstrate the effectiveness of the developed model for image retrieval are described.
SISQL: schema-independent database querying (on and off the Web)
20 Citations2002Ute Masermann, Gottfried Vossen
A novel query language which renders it possible to formulate queries to databases in the absence of schema-knowledge, and takes parameterized SQL queries as input and dynamically generates correct SQL statements for collections of underlying schemata.