Computation-tuple sequences and object histories

ABSTRACT

A record-based, algebraically-oriented model is introduced for describing data for “object histories” (with computation), such as checking accounts, credit card accounts, taxes, schedules, and so on. The model consists of sequences of computation tuples defined by a computation-tuple sequence scheme (CSS). The CSS has three major features (in addition to input data): computation (involving previous computation tuples), “uniform” constraints (whose satisfaction by a computation-tuple sequence u implies satisfaction by every interval of u), and specific sequences with which to start the valid computation-tuple sequences. A special type of CSS, called “local,” is singled out for its relative simplicity in maintaining the validity of a computation-tuple sequence. A necessary and sufficient condition for a CSS to be equivalent to at least one local CSS is given. Finally, the notion of “local bisimulatability” is introduced for regarding two CSS as conveying the same information, and two results on local bisimulatability in connection with local CSS are established.

REFERENCES

• 1: AFIPS O{fice Automation Conference Digests (1980-1983).
• 2: James Clifford , David S. Warren, Formal semantics for time in databases, ACM Transactions on Database Systems (TODS), v.8 n.2, p.214-254, June 1983 [doi>10.1145/319983.319986]
• 3: Clarence A. Ellis , Gary J. Nutt, Office Information Systems and Computer Science, ACM Computing Surveys (CSUR), v.12 n.1, p.27-60, March 1980 [doi>10.1145/356802.356805]
• 4: William Kent, Limitations of record-based information models, ACM Transactions on Database Systems (TODS), v.4 n.1, p.107-131, March 1979 [doi>10.1145/320064.320070]
• 5: David M. Kroenke, Database processing (4th ed.): fundamentals, design & implementation, Macmillan Publishing Co., Inc., Indianapolis, IN, 1992
• 6: Robert Purvy , Jerry Farrell , Paul Klose, The design of Star's records processing: data processing for the noncomputer professional, ACM Transactions on Information Systems (TOIS), v.1 n.1, p.3-24, Jan. 1983 [doi>10.1145/357423.357425]
• 7: SIGMOD: Proceedings on Databases for Business and Office Applications. ACM, New York, 1983.
• 8: Michael Stonebraker , Heidi Stettner , Nadene Lynn , Joseph Kalash , Antonin Guttman, Document processing in a relational database system, ACM Transactions on Information Systems (TOIS), v.1 n.2, p.143-158, April 1983 [doi>10.1145/357431.357433]
• 9: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983

INDEX TERMS

Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.4 Systems
          Subjects: Transaction processing

General Terms:
Algorithms, Theory, Verification