skip to main content
10.5555/1402298.1402345acmconferencesArticle/Chapter ViewAbstractPublication PagesaamasConference Proceedingsconference-collections
research-article

Self-interested database managers playing the view maintenance game

Published: 12 May 2008 Publication History

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]
J. A. Blakeley, P. A. Larson, and B. W. Tompa. Efficiently updating materialized views. In Proceedings of the 1986 ACM SIGMOD International Conference on Management of Data, Washington, D.C., USA, 1986.
[2]
K. Candan, D. Agrawal, O. P. W. Li, and W. Hsiung. View invalidation for dynamic content caching in multitiered architectures. In Proceedings of the 28th Very Large Data Bases Conference, Hongkong, China, August 2002.
[3]
A. K. Chandra and P. M. Merlin. Optimal implementation of conjunctive queries in relational data bases. In Proceedings of the Ninth Annual ACM Symposium on Theory of Computing, Colorado, USA, 1977.
[4]
C. Y. Choi and Q. Luo. Template-based runtime invalidation for database-generated web contents. In Proceedings of Advanced Web Technologies and Applications, 6th Asia-Pacific Web Conference, AP Web 2004, Hangzhou, China, 2004.
[5]
S. Fatima, M. Wooldridge, and N. Jennings. Approximate and online multi-issue negotiation. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multi-agent Systems, Hawaii, USA, 2007.
[6]
A. Gilpin and T. Sandholm. Finding equilibria in large sequential games of imperfect information. In Proceedings of the ACM Conference on Electronic Commerce, MI, USA, 2006.
[7]
A. Gupta, I. S. Mumick, and V. S. Subrahmanian. Maintaining views incrementally. In Proceedings of ACM SIGMOD Conference on Management of Data, Washington D.C., USA, 1993.
[8]
M. Kearns, M. Littman, and S. Singh. Graphical models for game theory. In Proceedings of the 17th Annual Conference on Uncertainty in Artificial Intelligence (UAI-01), CA, USA, 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 23rd International Conference on Data Engineering, Istanbul, Turkey, April 2007.
[12]
Y. Matias, J. Vitter, and M. Wang. Wavelet-based histograms for selectivity estimation. In Proceedings of ACM SIGMOD International Conference on Management of Data, WA, USA, 1998.
[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]
S. Singh, V. Soni, and M. Wellman. Computing approximate bayes nash equilibria in tree-games of incomplete information. In Proceedings of the ACM Conference on Electronic Commerce, 2004.
[16]
V. Soni, S. Singh, and M. Wellman. Constraint satisfaction algorithms for graphical games. In Proceedings of the 6th International Joint Conference on Autonomous Agents and Multiagent Systems, Hawaii, USA, May 2007.
[17]
T. Turocy. A dynamic homotopy interpretation of the logistic quantal response equilibrium correspondence. Games and Economic Behavior, 51:243--263, 2006.
[18]
D. Vickrey and D. Koller. Multi-agent algorithms for solving graphical games. In Proceedings of the Eighteenth National Conference on Artificial Intelligence, 2002.
[19]
A. Yao. How to generate and exchange secrets. In Proceedings of the Twenty-Seventh Symposium on Foundations of Computer Science, 1986.

Index Terms

  1. Self-interested database managers playing the view maintenance game

    Recommendations

    Comments

    Information & Contributors

    Information

    Published In

    cover image ACM Conferences
    AAMAS '08: Proceedings of the 7th international joint conference on Autonomous agents and multiagent systems - Volume 2
    May 2008
    673 pages
    ISBN:9780981738116

    Sponsors

    In-Cooperation

    Publisher

    International Foundation for Autonomous Agents and Multiagent Systems

    Richland, SC

    Publication History

    Published: 12 May 2008

    Check for updates

    Author Tags

    1. approximate Bayes-Nash equilibria
    2. database view maintenance
    3. games of incomplete information
    4. sequential decision-making

    Qualifiers

    • Research-article

    Conference

    AAMAS08
    Sponsor:

    Acceptance Rates

    Overall Acceptance Rate 1,155 of 5,036 submissions, 23%

    Contributors

    Other Metrics

    Bibliometrics & Citations

    Bibliometrics

    Article Metrics

    • 0
      Total Citations
    • 159
      Total Downloads
    • Downloads (Last 12 months)1
    • Downloads (Last 6 weeks)0
    Reflects downloads up to 14 Feb 2025

    Other Metrics

    Citations

    View Options

    Login options

    View options

    PDF

    View or Download as a PDF file.

    PDF

    eReader

    View online with eReader.

    eReader

    Figures

    Tables

    Media

    Share

    Share

    Share this Publication link

    Share on social media