ABSTRACT
In massively collaborative projects such as scientific or community databases, users often need to agree or disagree on the content of individual data items. On the other hand, trust relationships often exist between users, allowing them to accept or reject other users' beliefs by default. As those trust relationships become complex, however, it becomes difficult to define and compute a consistent snapshot of the conflicting information. Previous solutions to a related problem, the update reconciliation problem, are dependent on the order in which the updates are processed and, therefore, do not guarantee a globally consistent snapshot.
This paper proposes the first principled solution to the automatic conflict resolution problem in a community database. Our semantics is based on the certain tuples of all stable models of a logic program. While evaluating stable models in general is well known to be hard, even for very simple logic programs, we show that the conflict resolution problem admits a PTIME solution. To the best of our knowledge, ours is the first PTIME algorithm that allows conflict resolution in a principled way. We further discuss extensions to negative beliefs and prove that some of these extensions are hard. This work is done in the context of the BeliefDB project at the University of Washington, which focuses on the efficient management of conflicts in community databases.
- L. E. Bertossi. Consistent query answering in databases. SIGMOD Record, 35(2):68--76, 2006. Google ScholarDigital Library
- L. E. Bertossi and L. Bravo. The semantics of consistency and trust in peer data exchange systems. In LPAR, 2007. Google ScholarDigital Library
- J. Chomicki. Consistent query answering: Five easy pieces. In ICDT, 2007. Google ScholarDigital Library
- E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Complexity and expressive power of logic programming. ACM Comput. Surv., 33(3):374--425, 2001. Google ScholarDigital Library
- A. Fuxman, P. G. Kolaitis, R. J. Miller, and W. C. Tan. Peer data exchange. ACM Trans. Database Syst., 31(4):1454--1498, 2006. Google ScholarDigital Library
- M. Garey and D. Johnson. Computers and Intractability: A Guide to the Theory of NP-completeness. W. H. Freeman, San Francisco, 1979. Google ScholarDigital Library
- W. Gatterbauer, M. Balazinska, N. Khoussainova, and D. Suciu. Believe it or not: Adding belief annotations to databases. PVLDB, 2(1):1--12, 2009. Google ScholarDigital Library
- W. Gatterbauer and D. Suciu. Data conict resolution using trust mappings. Technical report, UW-CSE-09-11-01, Nov. 2009. http://db.cs.washington.edu/beliefDB/.Google Scholar
- T. J. Green, G. Karvounarakis, Z. G. Ives, and V. Tannen. Update exchange with mappings and provenance. In VLDB, 2007. Google ScholarDigital Library
- T. Imielinski and W. L. Jr. Incomplete information in relational databases. J. ACM, 31(4):761--791, 1984. Google ScholarDigital Library
- L. Kot and C. Koch. Cooperative update exchange in the youtopia system. PVLDB, 2(1):193--204, 2009. Google ScholarDigital Library
- N. Leone, G. Pfeifer, W. Faber, T. Eiter, G. Gottlob, S. Perri, and F. Scarcello. The DLV system for knowledge representation and reasoning. ACM Trans. Comput. Log., 7(3):499--562, 2006. Google ScholarDigital Library
- V. W. Marek and M. Truszczynski. Autoepistemic logic. J. ACM, 38(3):588--619, 1991. Google ScholarDigital Library
- F. Naumann and M. Häussler. Declarative data merging with conict resolution. In IQ, 2002.Google Scholar
- G. L. Possehl. The Indus Age: The Writing System. University of Pennsylvania Press, Philadelphia, 1996.Google Scholar
- Y. Qi, K. S. Candan, and M. L. Sapino. FICSR: Feedback-based inconsistency resolution and query processing on misaligned data sources. In SIGMOD, 2007. Google ScholarDigital Library
- R. P. N. Rao, N. Yadav, M. N. Vahia, H. Joglekar, R. Adhikari, and I. Mahadevan. Entropic evidence for linguistic structure in the Indus script. Science, 324(5931):1165, May 2009.Google ScholarCross Ref
- R. E. Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput., 1(2):146--160, 1972.Google ScholarDigital Library
- N. E. Taylor and Z. G. Ives. Reconciling while tolerating disagreement in collaborative data sharing. In SIGMOD, 2006. Google ScholarDigital Library
Index Terms
- Data conflict resolution using trust mappings
Recommendations
Conflict Resolution: A First-Order Resolution Calculus with Decision Literals and Conflict-Driven Clause Learning
This paper defines the (first-order) conflict resolution calculus: an extension of the resolution calculus inspired by techniques used in modern Sat-solvers. The resolution inference rule is restricted to (first-order) unit propagation and the calculus ...
Several shades of conflict
AbstractRecently, the measurement of conflict between belief functions has been given an axiomatic foundation by Destercke and Burger, resulting in conflict being measured as the inconsistency of their conjunctive combination and excluding ...
Priority-Based Conflict Resolution for Hardware Transactional Memory
CANDAR '14: Proceedings of the 2014 Second International Symposium on Computing and NetworkingLock-based thread synchronization techniques have been commonly used in parallel programming on multi-core processors. However, lock can cause deadlocks and poor scalabilites, and Transactional Memory (TM) has been proposed and studied for lock-free ...
Comments