We propose a description language capturing a simple but central aspect of the possible “lives” (the behavior) of a database application, namely the ability for the relations to grow, shrink, or keep the same size. We first consider arbitrary behaviors and investigate the basic properties of such descriptions. We characterize consistency, redundancy, and subsumption, and show that every behavior has a unique minimal complete description. We then consider the problem of computing the minimal complete description of a given database application. We model such applications as collections of procedures, specified by update programs based on relational algebra. The general problem is undecidable, even for an application consisting of a single procedure with a single update language statement. We also identify decidable cases and provide partial complexity characterisations.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Analyzing the Behavior of Database Applications Through Size Descriptions

  • Jan Van den Bussche,
  • Emmanuel Waller

摘要

We propose a description language capturing a simple but central aspect of the possible “lives” (the behavior) of a database application, namely the ability for the relations to grow, shrink, or keep the same size. We first consider arbitrary behaviors and investigate the basic properties of such descriptions. We characterize consistency, redundancy, and subsumption, and show that every behavior has a unique minimal complete description. We then consider the problem of computing the minimal complete description of a given database application. We model such applications as collections of procedures, specified by update programs based on relational algebra. The general problem is undecidable, even for an application consisting of a single procedure with a single update language statement. We also identify decidable cases and provide partial complexity characterisations.