Estimating and bounding aggregations in databases with referential integrity errors

ABSTRACT

Database integration builds on tables coming from multiple databases by creating a single view of all these data. Each database has different tables, columns with similar content across databases and different referential integrity constraints. Thus, a query in an integrated database is likely to involve tables and columns with referential integrity errors. In a data warehouse environment, even though the ETL processes take care of the referential integrity errors, in many scenarios this is generally done by including 'dummy' records in the dimension tables used to relate to the fact tables with referential errors. When two tables are joined, and aggregations are computed, the tuples with an undefined foreign key value are aggregated in a group marked as undefined effectively discarding potentially valuable information. With that motivation in mind, we extend aggregate functions computed over tables with referential integrity errors on OLAP databases to return complete answer sets in the sense that no tuple is excluded. We associate to each valid reference, the probability that an invalid reference may actually be a certain correct reference. The main idea of our work is that in certain contexts, it is possible to use tuples with invalid references by taking into account the probability that an invalid reference actually be a certain correct reference. This way, improved answer sets are obtained from aggregate queries in settings where a database violates referential integrity constraints.

REFERENCES

• 1: Marcelo Arenas , Leopoldo Bertossi , Jan Chomicki , Xin He , Vijay Raghavan , Jeremy Spinrad, Scalar aggregation in inconsistent databases, Theoretical Computer Science, v.296 n.3, p.405-434, 14 March 2003 [doi>10.1016/S0304-3975(02)00737-5]
• 2: Doug Burdick , Prasad M. Deshpande , T. S. Jayram , Raghu Ramakrishnan , Shivakumar Vaithyanathan, OLAP over uncertain and imprecise data, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 3: Andrea Calì , Domenico Lembo , Riccardo Rosati, On the decidability and complexity of query answering over inconsistent and incomplete databases, Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.260-271, June 09-11, 2003, San Diego, California [doi>10.1145/773153.773179]
• 4: Arbee L. P. Chen , Jui-Shang Chiu , Frank S. C. Tseng, Evaluating Aggregate Operations Over Imprecise Data, IEEE Transactions on Knowledge and Data Engineering, v.8 n.2, p.273-284, April 1996 [doi>10.1109/69.494166]
• 5: Gianluigi Greco , Sergio Greco , Ester Zumpano, A Logical Framework for Querying and Repairing Inconsistent Databases, IEEE Transactions on Knowledge and Data Engineering, v.15 n.6, p.1389-1408, November 2003 [doi>10.1109/TKDE.2003.1245280]
• 6: ISO-ANSI. Database Language SQL-Part2: SQL/Foundation. ANSI, ISO 9075-2 edition, 1999.
• 7: Arno J. Knobbe , Arno Siebes , Bart Marseille, Involving Aggregate Functions in Multi-relational Search, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.287-298, August 19-23, 2002
• 8: Hans-Joachim Lenz , Arie Shoshani, Summarizability in OLAP and Statistical Data Bases, Proceedings of the Ninth International Conference on Scientific and Statistical Database Management, p.132-143, August 11-13, 1997 [doi>10.1109/SSDM.1997.621175]
• 9: Hans-Joachim Lenz , Bernhard Thalheim, OLAP Databases and Aggregation Functions, Proceedings of the 13th International Conference on Scientific and Statistical Database Management, p.91-100, July 18-20, 2001
• 10: S. McClean , B. Scotney , M. Shapcott, Aggregation of Imprecise and Uncertain Information in Databases, IEEE Transactions on Knowledge and Data Engineering, v.13 n.6, p.902-912, November 2001 [doi>10.1109/69.971186]
• 11: C. Ordonez and J. García-García. Consistent aggregations in databases with referential integrity errors. In ACM IQIS, pages 80--89, 2006.
• 12: Carlos Ordonez , Javier García-García, Referential integrity quality metrics, Decision Support Systems, v.44 n.2, p.495-508, January, 2008 [doi>10.1016/j.dss.2007.06.004]
• 13: Carlos Ordonez , Javier García-García , Zhibo Chen, Measuring referential integrity in distributed databases, Proceedings of the ACM first workshop on CyberInfrastructure: information management in eScience, November 09-09, 2007, Lisbon, Portugal [doi>10.1145/1317353.1317367]
• 14: Robert Ross , V. S. Subrahmanian , John Grant, Aggregate operators in probabilistic databases, Journal of the ACM (JACM), v.52 n.1, p.54-101, January 2005 [doi>10.1145/1044731.1044734]
• 15: TPC. TPC-H Benchmark. Transaction Processing Performance Council, http://www.tpc.org/tpch, 2005.
• 16: Jef Wijsen, Database repairing using updates, ACM Transactions on Database Systems (TODS), v.30 n.3, p.722-768, September 2005 [doi>10.1145/1093382.1093385]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

General Terms:
Experimentation, Languages

Keywords:
SQL, data quality, functions