Query Evaluation on Probabilistic Databases
IEEE Data(base) Engineering BulletinPublished 1 January 2006
Christopher Ré, Nilesh Dalvi, Dan Suciu
Citations73
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
A system that supports arbitrarily complex SQL queries with ”uncertain” predicates and the results are ranked, much like in Information Retrieval, and an optimization algorithm that can compute eciently most queries is described.
Abstract
We describe a system that supports arbitrarily complex SQL queries with ”uncertain” predicates. The query semantics is based on a probabilistic model and the results are ranked, much like in Information Retrieval. Our main focus is query evaluation. We describe an optimization algorithm that can compute eciently most queries. We show, however, that the data complexity of some queries is #P-complete, which implies that these queries do not admit any ecient evaluation methods. For these queries we describe both an approximation algorithm and a Monte-Carlo simulation algorithm.
Keywords
Computer Science
Modern Information Retrieval
11,544 Citations1999Ricardo Baeza‐Yates, Berthier Ribeiro‐Neto
ACM Computing SurveysA guided tour to approximate string matching
2,570 Citations2001Gonzalo Navarro
This work surveys the current techniques to cope with the problem of string matching that allows errors, and focuses on online searching and mostly on edit distance, explaining the problem and its relevance, its statistical behavior, its history and current developments, and the central ideas of the algorithms.
SIAM Journal on ComputingThe Complexity of Enumeration and Reliability Problems
2,086 Citations1979Leslie G. Valiant
For a large number of natural counting problems for which there was no previous indication of intractability, that they belong to the class of computationally eqivalent counting problems that are at least as difficult as the NP-complete problems.
The VLDB JournalEfficient query evaluation on probabilistic databases
979 Citations2006Nilesh Dalvi, Dan Suciu
It is shown that the data complexity of some queries is #P-complete, which implies that these queries do not admit any efficient evaluation methods, and an optimization algorithm is described that can compute efficiently most queries.
Journal of Computer and System SciencesOptimal aggregation algorithms for middleware
941 Citations2003Ronald Fagin, Amnon Lotem +1 more
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.
SIAM Journal on ComputingThe Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
749 Citations1983J. Scott Provan, Michael O. Ball
Several enumeration and reliability problems are shown to be # P-complete, and hence, at least as hard as NP-complete problems.
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.
IEEE Transactions on Knowledge and Data EngineeringThe management of probabilistic data
451 Citations1992Daniel Barbará, Héctor García-Molina +1 more
A data model that includes probabilities associated with the values of the attributes, and the notion of missing probabilities is introduced for partially specified probability distributions, offers a richer descriptive language allowing the database to more accurately reflect the uncertain real world.
ACM Transactions on Information SystemsA probabilistic relational algebra for the integration of information retrieval and database systems
406 Citations1997Norbert Fuhr, Thomas Rölleke
The concept of vague predicates which yield probabilistic weights instead of Boolean values are introduced, thus allowing for queries with vague selection conditions and implements uncertainty and vagueness in combination with the relational model.
ACM Transactions on Database SystemsProbView
345 Citations1997Laks V. S. Lakshmanan, Nicola Leone +2 more
This article characterize, using postulates, whole classes of strategies for conjunction, disjunction, and negation, meaningful from the viewpoint of probability theory, and shows that as long as the chosen strategies can be computed in polynomial time, queries in the positive fragment of the probabilistic relational algebra have essentially the same data complexity as classical relational algebra.
Information and ComputationProbabilistic logic programming
327 Citations1992Raymond T. Ng, V. S. Subrahmanian
This paper defines a logic programming language that is syntactically similar to the annotated logics of Blair et al., 1987 but in which the truth values are interpreted probabilistically, and proposes a formalism for probabilistic reasoning in logic programming, the first probabilists characterization of logic programming semantics.
ACM Transactions on Information SystemsVAGUE: a user interface to relational databases that permits vague queries
296 Citations1988Amihai Motro
VAGUE incorporates several features that enable it to adapt itself to the individual views and priorities of its users, and is its extension to the relational data model with data metrics, which are definitions of distances between values of the same domain.
Very Large Data BasesThe Theory of Probabilistic Databases
270 Citations1987Roger E. Cavallo, Michael Pittarelli
A new project-join mapping for relational databases that is based on transf orming a relational to a probabilistic database is defined and shown to have more fmed points than the standard one.
Automated Ranking of Database Query Results
236 Citations2003Sanjay Agrawal, Surajit Chaudhuri +2 more
The challenges and several approaches to enable ranking in databases, including adaptations of known techniques from information retrieval, are discussed and results of preliminary experiments are presented.
Artificial IntelligenceFrom statistical knowledge bases to degrees of belief
219 Citations1996Fahiem Bacchus, Adam J. Grove +2 more
This paper describes one approach for inducing degrees of belief from very rich knowledge bases, that can include information about particular individuals, statistical correlations, physical laws, and default rules, and shows that a number of desiderata that arise in direct inference and default reasoning follow directly from the semantics of random worlds.
ACM Transactions on Database SystemsA probabilistic relational model and algebra
213 Citations1996Debabrata Dey, Sumit Sarkar
A revised relational structure is presented and the extended algebra is shown to be closed, a consistent extension of the conventional relational algebra, and reducible to the latter.
Phonetic string matching
211 Citations1996Justin Zobel, Philip Dart
The parallels between information retrieval and phonetic matching are explained, and the new phonetics matching techniques described are compared with existing techniques to demonstrate that the new techniques are superior.
The complexity of query reliability
80 Citations1998Erich Grädel, Yuri Gurevich +1 more
It is shown that already for conjunctive queries, the reliability may become highly intractable, and it is shown, that FP#P is the typical complexity level for the reliability problems of a very large class of queries, including all second-order queries.
Lecture notes in computer scienceA simple min cut algorithm
73 Citations1994Mechthild Stoer, Frank Olaf Wagner
An algorithm for finding the minimum cut of an edge-weighted graph that has a short and compact description, is easy to implement and has a surprisingly simple proof of correctness whose runtime matches that of the fastest algorithm known.
The XXL search engine
38 Citations2002Anja Theobald, Gerhard Weikum
A core language, coined XXL, for ranked retrieval of XML data using regular element path expressions and search conditions over element contents and a new operator "~", which can be used for both element content comparisons and approximate matching of element names are developed.