  Imperfect databases are very common in many applications due to various
reasons ranging from data-entry errors, transmission or integration errors, and
wrong instruments' readings, to faulty experimental setups leading to incorrect
results. The management and query processing of imperfect databases is a very
challenging problem as it requires incorporating the data's qualities within
the database engine. Even more challenging, the qualities are typically not
static and may evolve over time. Unfortunately, most of the state-of-art
techniques deal with the data quality problem as an offline task that is in
total isolation of the query processing engine (carried out outside the DBMS).
Hence, end-users will receive the queries' results with no clue on whether or
not the results can be trusted for further analysis and decision making. In
this paper, we propose the it "QTrail-DB" system that fundamentally extends the
standard DBMSs to support imperfect databases with evolving qualities.
QTrail-DB introduces a new quality model based on the new concept of "Quality
Trails", which captures the evolution of the data's qualities over time.
QTrail-DB extends the relational data model to incorporate the quality trails
within the database system. We propose a new query algebra, called "QTrail
Algebra", that enables seamless and transparent propagation and derivations of
the data's qualities within a query pipeline. As a result, a query's answer
will be automatically annotated with quality-related information at the tuple
level. QTrail-DB propagation model leverages the thoroughly-studied propagation
semantics present in the DB provenance and lineage tracking literature, and
thus there is no need for developing a new query optimizer. QTrail-DB is
developed within PostgreSQL and experimentally evaluated using real-world
datasets to demonstrate its efficiency and practicality.
