Sergio Flesca
Skip Abstract Section
Skip Supplemental Material SectionAbstract
The problem of extracting consistent information from relational databases violating integrity constraints on numerical data is addressed. In particular, aggregate constraints defined as linear inequalities on aggregate-sum queries on input data are considered. The notion of repair as consistent set of updates at attribute-value level is exploited, and the characterization of several data-complexity issues related to repairing data and computing consistent query answers is provided. Moreover, a method for computing “reasonable” repairs of inconsistent numerical databases is provided, for a restricted but expressive class of aggregate constraints. Several experiments are presented which assess the effectiveness of the proposed approach in real-life application scenarios.
Supplemental Material
Available for Download
pdf
a14-flesca-apndx.pdf (291.5 KB)
Online appendix to querying and repairing inconsistent numerical databases on article 14.
- Afrati, F. N. and Kolaitis, P. G. 2009. Repair checking in inconsistent databases: Algorithms and complexity. In Proceedings of the 12th International Conference on Database Theory (ICDT). 31--41. Google Scholar
Digital Library
- Agarwal, S., Keller, A. M., Wiederhold, G., and Saraswat, K. 1995. Flexible relation: An approach for integrating data from multiple, possibly inconsistent databases. In Proceedings of the 11th International Conference on Data Engineering (ICDE). 495--504. Google ScholarDigital Library
- Arenas, M., Bertossi, L. E., and Chomicki, J. 1999. Consistent query answers in inconsistent databases. In Proceedings of the 18th ACM Symposium on Principles of Database Systems (PODS). 68--79. Google ScholarDigital Library
- Arenas, M., Bertossi, L. E., and Chomicki, J. 2000. Specifying and querying database repairs using logic programs with exceptions. In Proceedings of the 4th International Conference on Flexible Query Answering Systems (FQAS). 27--41.Google Scholar
- Arenas, M., Bertossi, L. E., and Chomicki, J. 2003a. Answer sets for consistent query answering in inconsistent databases. Theory Pract. Logic Program. 3, 4-5, 393--424. Google ScholarDigital Library
- Arenas, M., Bertossi, L. E., Chomicki, J., He, X., Raghavan, V., and Spinrad, J. 2003b. Scalar aggregation in inconsistent databases. Theor. Comput. Sci. 3, 296, 405--434. Google ScholarDigital Library
- Arenas, M., Bertossi, L. E., and Kifer, M. 2000. Applications of annotated predicate calculus to querying inconsistent databases. In Proceedings of the 1st International Conference on Computing Logic (CL). 926--941. Google ScholarDigital Library
- Barceló, P. and Bertossi, L. E. 2002. Repairing databases with annotated predicate logic. In Proceedings of the 9th International Workshop on Non-Monotonic Reasoning (NMR). 160--170.Google Scholar
- Barceló, P. and Bertossi, L. E. 2003. Logic programs for querying inconsistent databases. In Proceedings of the 5th International Symposium on Practical Aspects of Declarative Languages (PADL). 208--222. Google ScholarDigital Library
- Bertossi, L. E., Bravo, L., Franconi, E., and Lopatenko, A. 2008. The complexity and approximation of fixing numerical attributes in databases under integrity constraints. Inform. Syst. 33, 4-5, 407--434. Google ScholarDigital Library
- Bohannon, P., Flaster, M., Fan, W., and Rastogi, R. 2005. A cost-based model and effective heuristic for repairing constraints by value modification. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 143--154. Google ScholarDigital Library
- Bry, F. 1997. Query answering in information systems with integrity constraints. In Proceedings of the 1st International Conference on Integrity and Internal Control in Information Systems (IICIS). 113--130. Google ScholarDigital Library
- Calì, A., Lembo, D., and Rosati, R. 2003. On the decidability and complexity of query answering over inconsistent and incomplete databases. In Proceedings of the 22nd ACM Symposium on Principles of Database Systems (PODS). 260--271. Google ScholarDigital Library
- Celle, A. and Bertossi, L. E. 2000. Querying inconsistent databases: Algorithms and implementation. In Proceedings of the 1st International Conference on Computing Logic (CL). 942--956. Google ScholarDigital Library
- Chomicki, J. and Marcinkowski, J. 2005. Minimal-Change integrity maintenance using tuple deletions. Inf. Comput. 197, 1-2, 90--121. Google ScholarDigital Library
- Chomicki, J., Marcinkowski, J., and Staworko, S. 2004. Computing consistent query answers using conflict hypergraphs. In Proceedings of the 13th ACM Conference on Information and Knowledge Management (CIKM). 417--426. Google ScholarDigital Library
- Eiter, T. and Gottlob, G. 1992. On the complexity of propositional knowledge base revision, updates, and counterfactuals. Artif. Intell. 57, 2-3, 227--270. Google ScholarDigital Library
- Fazzinga, B., Flesca, S., Furfaro, F., and Parisi, F. 2006. Dart: A data acquisition and repairing tool. In Proceedings of the International Workshop on Inconsistency and Incompleteness in Databases (IIDB). 297--317. Google ScholarDigital Library
- Flesca, S., Furfaro, F., and Parisi, F. 2005. Consistent query answers on numerical databases under aggregate constraints. In Proceedings of the 10th International Symposium on Database Programming Languages (DPBL). 279--294. Google ScholarDigital Library
- Franconi, E., Palma, A. L., Leone, N., Perri, S., and Scarcello, F. 2001. Census data repair: A challenging application of disjunctive logic programming. In Proceedings of the 8th International Conference on Logic for Programming, Artificial Intelligence, and Reasoning (LPAR). 561--578. Google ScholarDigital Library
- Fuxman, A., Fazli, E., and Miller, R. J. 2005. Conquer: Efficient management of inconsistent databases. In Proceedings of the ACM SIGMOD International Conference on Management of Data. 155--166. Google ScholarDigital Library
- Fuxman, A. and Miller, R. J. 2007. First-Order query rewriting for inconsistent databases. J. Comput. Syst. Sci. 73, 4, 610--635. Google ScholarDigital Library
- Gärdenfors, P. and Rott, H. 1995. Belief revision. In Handbook of Logic in Artificial Intelligence and Logic Programming (Vol. 4): Epistemic and Temporal Reasoning, D. M. Gabbay, C. J. Hogger, and J. A. Robinson, Eds. Oxford University Press, Oxford, UK, 35--132. Google ScholarDigital Library
- Gass, S. I. 1985. Linear Programming: Methods and Applications (5th ed.). McGraw-Hill, New York. Google ScholarDigital Library
- Greco, G., Greco, S., and Zumpano, E. 2003. A logical framework for querying and repairing inconsistent databases. IEEE Trans. Knowl. Data Engin. 15, 6, 1389--1408. Google ScholarDigital Library
- Imielinski, T. and Lipski, W. 1984. Incomplete information in relational databases. J. ACM 31, 4, 761--791. Google ScholarDigital Library
- Kendall, M. 1963. Ill-Conditioned matrices in linear programming. Metrika 6, 1, 60--64.Google ScholarCross Ref
- Kifer, M. and Lozinskii, E. L. 1992. A logic for reasoning with inconsistency. J. Autom. Reason. 9, 2, 179--215. Google ScholarDigital Library
- Lopatenko, A. and Bertossi, L. E. 2007. Complexity of consistent query answering in databases under cardinality-based and incremental repair semantics. In Proceedings of the 11th International Conference on Database Theory (ICDT). 179--193. Google ScholarDigital Library
- Papadimitriou, C. H. 1981. On the complexity of integer programming. J. ACM 28, 4, 765--768. Google ScholarDigital Library
- Papadimitriou, C. H. and Steiglitz, K. 1998. Combinatorial Optimization: Algorithms and Complexity. Dover, Mineola, New York. Google ScholarDigital Library
- Papadimitriou, C. M. 1994. Computational Complexity. Addison-Wesley, Reading, MA.Google Scholar
- Rahm, E. and Do, H. H. 2000. Data cleaning: Problems and current approaches. IEEE Data Engin. Bull. 23, 4, 3--13.Google Scholar
- Ross, K. A., Srivastava, D., Stuckey, P. J., and Sudarshan, S. 1998. Foundations of aggregation constraints. Theor. Comput. Sci. 193, 1-2, 149--179. Google ScholarDigital Library
- Wijsen, J. 2003. Condensed representation of database repairs for consistent query answering. In Proceedings of the 9th International Conference on Database Theory (ICDT). 378--393. Google ScholarDigital Library
- Wijsen, J. 2004. Making more out of an inconsistent database. In Proceedings of the 8th East European Conference on Advances in Databases and Information Systems (ADBIS). 291--305.Google ScholarCross Ref
- Wijsen, J. 2005. Database repairing using updates. ACM Trans. Database. Syst. 30, 3, 722--768. Google ScholarDigital Library
- Wijsen, J. 2006. A note on database repairing by value modification. In Proceedings of the International Workshop on Inconsistency and Incompleteness in Databases (IIDB). Position paper.Google Scholar
- Wijsen, J. 2009. Consistent query answering under primary keys: A characterization of tractable queries. In Proceedings of the 12th International Conference on Database Theory (ICDT). 42--52. Google ScholarDigital Library
- Xie, G., Dang, Z., and Ibarra, O. H. 2003. A solvable class of quadratic diophantine equations with applications to verification of infinite-state systems. In Proceedings of the 30th International Colloquium on Automata, Languages and Programming (ICALP). 668--680. Google ScholarDigital Library
Index Terms
- Querying and repairing inconsistent numerical databases
Recommendations
Repair checking in inconsistent databases: algorithms and complexity
ICDT '09: Proceedings of the 12th International Conference on Database TheoryManaging inconsistency in databases has long been recognized as an important problem. One of the most promising approaches to coping with inconsistency in databases is the framework of database repairs, which has been the topic of an extensive ...
Probabilistic query answering over inconsistent databases
This paper presents a framework for querying inconsistent databases in the presence of functional dependencies. Most of the works dealing with the problem of extracting reliable information from inconsistent databases are based on the notion of repair, ...
On the Data Complexity of Consistent Query Answering
The framework of database repairs is a principled approach to managing inconsistency in databases. In particular, the consistent answers of a query on an inconsistent database provide sound semantics and the guarantee that the values obtained are those ...
Comments