On Maintaining Priorities in a Production Rule System.

@inproceedings{DBLP:conf/vldb/AgrawalCL91,
  author    = {Rakesh Agrawal and
               Roberta Cochrane and
               Bruce G. Lindsay},
  editor    = {Guy M. Lohman and
               Am\'{\i}lcar Sernadas and
               Rafael Camps},
  title     = {On Maintaining Priorities in a Production Rule System},
  booktitle = {17th International Conference on Very Large Data Bases, September
               3-6, 1991, Barcelona, Catalonia, Spain, Proceedings},
  publisher = {Morgan Kaufmann},
  year      = {1991},
  isbn      = {1-55860-150-3},
  pages     = {479-487},
  ee        = {db/conf/vldb/AgrawalCL91.html},
  crossref  = {DBLP:conf/vldb/91},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

We present a priority system which is particularly suited for production rules coupled to databases. In this system, there are default priorities between all rules and overriding user-defined priorities between particular rules. Rule processing using this system is repeatable: for a given set of rules and priorities, the rules are considered for execution in the same order if the same set of transactions is executed twice on the same initial database state. The rule order adheres to the default order as closely as possible: rules are considered in the same order as the default order unless user-defined precedence constraints force an inversion.

We present data structures and efficient algorithms for implementing such a priority system. We show how the data structures can be incrementally maintained as user-definedpriorities are altered. We also discuss how the proposed scheme can be extended to build a multi-level hierarchical priority system.

Copyright © 1991 by the VLDB Endowment. Permission to copy without fee all or part of this material is granted provided that the copies are not made or distributed for direct commercial advantage, the VLDB copyright notice and the title of the publication and its date appear, and notice is given that copying is by the permission of the Very Large Data Base Endowment. To copy otherwise, or to republish, requires a fee and/or special permission from the Endowment.

Online Paper

• Download PDF file (www.vldb.org, Darmstadt, Germany)
• Download PDF file (www.acm.org, New York, USA)

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/vldb8997 or /cdrom

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Printed Edition

References

[1]

Rakesh Agrawal, Alexander Borgida, H. V. Jagadish: Efficient Management of Transitive Relationships in Large Data and Knowledge Bases. SIGMOD Conference 1989: 253-262 BibTeX

[2]

Rakesh Agrawal, Shaul Dar, H. V. Jagadish: Direct Transitive Closure Algorithms: Design and Performance Evaluation. ACM Trans. Database Syst. 15(3): 427-458(1990) BibTeX

[3]

Rakesh Agrawal, H. V. Jagadish: Materialization and Incremental Update of Path Information. ICDE 1989: 374-383 BibTeX

[4]

Alejandro P. Buchmann, Dennis R. McCarthy, Meichun Hsu, Umeshwar Dayal: Time-Critical Database Scheduling: A Framework For Integrating Real-Time Scheduling and Concurrency Control. ICDE 1989: 470-480 BibTeX

[5]

Wesley W. Chu, Lance M.-T. Lan: Task Allocation and Precedence Relations for Distributed Real-Time Systems. IEEE Trans. Computers 36(6): 667-679(1987) BibTeX

[6]

Donald Cohen: Compiling Complex Database Transition Triggers. SIGMOD Conference 1989: 225-234 BibTeX

[7]

Christophe de Maindreville, Eric Simon: A Production Rule-Based Approach to Deductive Databases. ICDE 1988: 234-241 BibTeX

[8]

Lois M. L. Delcambre, James N. Etheredge: The Relational Production Language: A Production Language for Relational Databases. Expert Database Conf. 1988: 333-351 BibTeX

[9]

...

[10]

Laura M. Haas, Walter Chang, Guy M. Lohman, John McPherson, Paul F. Wilms, George Lapis, Bruce G. Lindsay, Hamid Pirahesh, Michael J. Carey, Eugene J. Shekita: Starburst Mid-Flight: As the Dust Clears. IEEE Trans. Knowl. Data Eng. 2(1): 143-160(1990) BibTeX

[11]

Eric N. Hanson: An Initial Report on The Design of Ariel: A DBMS With an Integrated Production Rule System. SIGMOD Record 18(3): 12-19(1989) BibTeX

[12]

...

[13]

...

[14]

Yannis E. Ioannidis, Timos K. Sellis: Conflict Resolution of Rules Assigning Values to Virtual Attributes. SIGMOD Conference 1989: 205-214 BibTeX

[15]

...

[16]

Donald E. Knuth: The Art of Computer Programming, Volume III: Sorting and Searching. Addison-Wesley 1973, ISBN 0-201-03803-X
BibTeX

[17]

...

[18]

C. L. Liu, James W. Layland: Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment. J. ACM 20(1): 46-61(1973) BibTeX

[19]

Dennis R. McCarthy, Umeshwar Dayal: The Architecture Of An Active Data Base Management System. SIGMOD Conference 1989: 215-224 BibTeX

[20]

...

[21]

Matthew Morgenstern: Active Databases as a Paradigm for Enhanced Computing Environments. VLDB 1983: 34-42 BibTeX

[22]

...

[23]

James Clifford, Bruce G. Lindsay, David Maier (Eds.): Proceedings of the 1989 ACM SIGMOD International Conference on Management of Data, Portland, Oregon, May 31 - June 2, 1989. ACM Press 1989
Contents BibTeX

[24]

Louiqa Raschid: Maintaining Consistency in a Stratified Production System Program. AAAI 1990: 284-289 BibTeX

[25]

Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Implementing Large Production Systems in a DBMS Environment: Concepts and Algorithms. SIGMOD Conference 1988: 404-412 BibTeX

[26]

Michael Stonebraker, Eric N. Hanson, Spyros Potamianos: The POSTGRES Rule Manager. IEEE Trans. Software Eng. 14(7): 897-907(1988) BibTeX

[27]

Arie Tzvieli: On the Coupling of a Production System Shell and a DBMS. JCDKB 1988: 291-309 BibTeX

[28]

Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577 BibTeX

[29]

Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285 BibTeX

[30]

Jennifer Widom, Sheldon J. Finkelstein: Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270 BibTeX

[31]

Jia Xu, David Lorge Parnas: Scheduling Processes with Release Times, Deadlines, Precedence, and Exclusion Relations. IEEE Trans. Software Eng. 16(3): 360-369(1990) BibTeX

[32]

Yuli Zhou, Meichun Hsu: A Theory for Rule Triggering Systems. EDBT 1990: 407-421 BibTeX

Referenced by

1. Stefano Ceri, Roberta Cochrane, Jennifer Widom: Practical Applications of Triggers and Constraints: Success and Lingering Issues (10-Year Award). VLDB 2000: 254-262
2. Stanley Y. W. Su, Ramamohanrao S. Jawadi, Prashant Cherukuri, Qiang Li, Richard Nartey: OSAM*.KBMS/P: A Parallel, Active, Object-Oriented Knowledge Base Server. IEEE Trans. Knowl. Data Eng. 10(1): 55-75(1998)
3. Elena Baralis, Stefano Ceri, Stefano Paraboschi: Compile-Time and Runtime Analysis of Active Behaviors. IEEE Trans. Knowl. Data Eng. 10(3): 353-370(1998)
4. Jennifer Widom: The Starburst Active Database Rule System. IEEE Trans. Knowl. Data Eng. 8(4): 583-595(1996)
5. Roberta Cochrane, Hamid Pirahesh, Nelson Mendonça Mattos: Integrating Triggers and Declarative Constraints in SQL Database Sytems. VLDB 1996: 567-578
6. H. V. Jagadish, Alberto O. Mendelzon, Inderpal Singh Mumick: Managing Rule Conflicts in an Active Database. PODS 1996: 192-201
7. Jennifer Widom, Stefano Ceri (Eds.): Active Database Systems: Triggers and Rules For Advanced Database Processing. Morgan Kaufmann 1996, ISBN 1-55860-304-2
   Contents
8. Piero Fraternali, Letizia Tanca: A Structured Approach for the Definition of the Semantics of Active Databases. ACM Trans. Database Syst. 20(4): 414-471(1995)
9. Alexander Aiken, Joseph M. Hellerstein, Jennifer Widom: Static Analysis Techniques for Predicting the Behavior of Active Database Rules. ACM Trans. Database Syst. 20(1): 3-41(1995)
10. Ramamohanrao S. Jawadi, Stanley Y. W. Su: Incorporating Flexible and Expressive Rule Control in a Graph-Based Transaction Framework. DASFAA 1995: 350-357
11. Christine Collet, Thierry Coupaye, T. Svensen: NAOS - Efficient and Modular Reactive Capabilities in an Object-Oriented Database System. VLDB 1994: 132-143
12. Anthony J. Bonner, Michael Kifer, Mariano P. Consens: Database Programming in Transaction Logic. DBPL 1993: 309-337
13. Jennifer Widom: The Starburst Rule System: Language Design, Implementation, and Applications. IEEE Data Eng. Bull. 15(1-4): 15-18(1992)
14. Stefano Ceri, Jennifer Widom: Production Rules in Parallel and Distributed Database Environments. VLDB 1992: 339-351
15. Guy M. Lohman, Bruce G. Lindsay, Hamid Pirahesh, K. Bernhard Schiefer: Extensions to Starburst: Objects, Types, Functions, and Rules. Commun. ACM 34(10): 94-109(1991)
16. Jennifer Widom, Roberta Cochrane, Bruce G. Lindsay: Implementing Set-Oriented Production Rules as an Extension to Starburst. VLDB 1991: 275-285
17. Stefano Ceri, Jennifer Widom: Deriving Production Rules for Incremental View Maintenance. VLDB 1991: 577-589