QPIAD: Query processing over incomplete autonomous databases

Hemal Khatri, Jianchun Fan, Yi Chen, Subbarao Kambhampati

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations


Incompleteness due to missing attribute values (aka "null values") is very common in autonomous web databases, on which user accesses are usually supported through mediators. Traditional query processing techniques that focus on the strict soundness of answer tuples often ignore tuples with critical missing attributes, even if they wind up being relevant to a user query. Ideally we would like the mediator to retrieve such relevant uncertain answers and gauge their relevance by accessing their likelihood of being relevant answers to the query. However, the autonomous nature of the databases poses several challenges, such as the restricted access privileges, limited query patterns, and sensitivity of database and network resource consumption in the web environment. We introduce a novel query rewriting and optimization framework QPIAD that tackles these challenges to retrieve relevant uncertain answers. Our technique involves reformulating the user query based on approximate functional dependencies (AFDs) among the database attributes and ranking these queries using value distributions learned from Naïve Bayes Classifiers. Empirical studies demonstrate the effectiveness of our approach in retrieving relevant uncertain answers with high precision, high recall and manageable cost.

Original languageEnglish (US)
Title of host publication23rd International Conference on Data Engineering, ICDE 2007
Number of pages3
StatePublished - 2007
Externally publishedYes
Event23rd International Conference on Data Engineering, ICDE 2007 - Istanbul, Turkey
Duration: Apr 15 2007Apr 20 2007

Publication series

NameProceedings - International Conference on Data Engineering
ISSN (Print)1084-4627


Other23rd International Conference on Data Engineering, ICDE 2007

All Science Journal Classification (ASJC) codes

  • Software
  • Signal Processing
  • Information Systems


  • Autonomous databases
  • Incomplete databases
  • Query rewriting
  • Querying hidden web


Dive into the research topics of 'QPIAD: Query processing over incomplete autonomous databases'. Together they form a unique fingerprint.

Cite this