Self-interested database managers playing the view maintenance game

ABSTRACT

A database view is a dynamic virtual table composed of the result set of a query, often executed over different underlying databases. The view maintenance problem concerns how a view is refreshed when the data sources are updated. We study the view maintenance problem when self-interested database managers from different institutions are involved, each concerned about the privacy of its database. We regard view maintenance as an incremental, sequential process where an action taken at a stage affects what happens at later stages. The contribution of this paper is twofold. First, we formulate the view maintenance problem as a sequential game of incomplete information where at every stage, each database manager decides what information to disclose, if any, without knowledge of the number or nature of updates at other managers. This allows us to adopt a satisficing approach where the final view need not reflect 100% of the databases updates. Second, we present an anytime algorithm for calculating ε-Bayes-Nash equilibria that allows us to solve the large games which our problem translates to. Our algorithm is not restricted to games originating from the view maintenance problem; it can be used to solve general games of incomplete information. In addition, experimental results demonstrate our algorithm's attractive anytime behavior, which allows it to find good-enough solutions to large games within reasonable amounts of time.

REFERENCES

• 1: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 2: K. Selçuk Candan , Divyakant Agrawal , Wen-Syan Li , Oliver Po , Wang-Pin Hsiung, View invalidation for dynamic content caching in multitiered architectures, Proceedings of the 28th international conference on Very Large Data Bases, p.562-573, August 20-23, 2002, Hong Kong, China
• 3: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 4: C. Y. Choi and Q. Luo. Template-based runtime invalidation for database-generated web contents. In Proceedings of Advanced Web Technologies and Applications, 6^th Asia-Pacific Web Conference, AP Web 2004, Hangzhou, China, 2004.
• 5: Shaheen S. Fatima , Michael Wooldridge , Nicholas R. Jennings, Approximate and online multi-issue negotiation, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329315]
• 6: Andrew Gilpin , Tuomas Sandholm, Finding equilibria in large sequential games of imperfect information, Proceedings of the 7th ACM conference on Electronic commerce, p.160-169, June 11-15, 2006, Ann Arbor, Michigan, USA [doi>10.1145/1134707.1134725]
• 7: Ashish Gupta , Inderpal Singh Mumick , V. S. Subrahmanian, Maintaining views incrementally, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.157-166, May 25-28, 1993, Washington, D.C., United States
• 8: Michael J. Kearns , Michael L. Littman , Satinder P. Singh, Graphical Models for Game Theory, Proceedings of the 17th Conference in Uncertainty in Artificial Intelligence, p.253-260, August 02-05, 2001
• 9: M. Kearns and L. E. Ortiz. Maintaining views incrementally. In Proceedings of Advances in Neural Information Processing Systems, MA, USA, 2004.
• 10: G. Liang and S. S. Chawathe. Privacy-preserving inter-database operations. In Proceedings of the Second Symposium on Intelligence and Security Informatics, Arizona, USA, 2004.
• 11: A. Manjhi, P. B. Gibbons, A. Ailamaki, C. Garrod, B. M. Maggs, T. C. Mowry, C. Olston, A. Tomasic, and H. Yu. Invalidation clues for database scalability services. In Proceedings of the 23^rd International Conference on Data Engineering, Istanbul, Turkey, April 2007.
• 12: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.448-459, June 01-04, 1998, Seattle, Washington, United States
• 13: R. D. McKelvey, A. M. McLennan, and T. L. Turocy. Gambit: Software tools for game theory. http://gambit.sourceforge.net/, 2007.
• 14: M. Pearson and P. La Mura. Simulated annealing of game equilibria: A simple adaptive procedure leading to nash equilibrium. In Proceedings of the International Workshop on The Logic and Strategy of Distributed Agents, Trento, Italy, 2000.
• 15: Satinder Singh , Vishal Soni , Michael Wellman, Computing approximate bayes-nash equilibria in tree-games of incomplete information, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988785]
• 16: Vishal Soni , Satinder Singh , Michael P. Wellman, Constraint satisfaction algorithms for graphical games, Proceedings of the 6th international joint conference on Autonomous agents and multiagent systems, May 14-18, 2007, Honolulu, Hawaii [doi>10.1145/1329125.1329206]
• 17: T. Turocy. A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence. Games and Economic Behavior, 51:243--263, 2006.
• 18: David Vickrey , Daphne Koller, Multi-agent algorithms for solving graphical games, Eighteenth national conference on Artificial intelligence, p.345-351, July 28-August 01, 2002, Edmonton, Alberta, Canada
• 19: Andrew Chi-Chih Yao, How to generate and exchange secrets, Proceedings of the 27th Annual Symposium on Foundations of Computer Science (sfcs 1986), p.162-167, October 27-29, 1986 [doi>10.1109/SFCS.1986.25]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Heuristic methods

General Terms:
Algorithms, Economics

Keywords:
approximate Bayes-Nash equilibria, database view maintenance, games of incomplete information, sequential decision-making