Title :
Information source tracking method: efficiency issues
Author :
Sadri, Fereidoon
Author_Institution :
Dept. of Math. Sci., North Carolina Univ., Greensboro, NC, USA
fDate :
12/1/1995 12:00:00 AM
Abstract :
This paper is devoted to the study and analysis of query processing efficiency in the information source tracking (IST) technique, an approach to the representation and manipulation of uncertain and inaccurate data. We show that the efficiency depends on the average number of information sources confirming the same data in the database. If this number is close to unity, then the efficiency of query processing for the IST model is comparable to conventional relational database systems. For the case where multiple information sources confirm the same data in the database, we present a variation of IST, called the Dual IST method, which provides efficient query processing. Extended relational algebra operations are presented for Dual IST, and proven to be correct under the “alternate worlds” semantics interpretation. The complexity of reliability calculation in IST and Dual IST methods is also studied
Keywords :
data handling; database theory; query processing; relational algebra; relational databases; uncertainty handling; Dual IST method; IST model; complexity; inaccurate data; information source tracking method; information sources; query processing; query processing efficiency; relational algebra; relational database systems; reliability calculation; semantics interpretation; uncertain data; Algebra; Algorithm design and analysis; Artificial intelligence; Database systems; Decision making; Information analysis; Query processing; Relational databases; Transaction databases; Uncertainty;
Journal_Title :
Knowledge and Data Engineering, IEEE Transactions on