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

[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)

[3]

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

[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

[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)

[6]

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

[7]

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

[8]

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

[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)

[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)

[12]

...

[13]

...

[14]

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

[15]

...

[16]

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

[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)

[19]

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

[20]

...

[21]

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

[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

[24]

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

[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

[26]

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

[27]

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

[28]

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

[29]

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

[30]

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

[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)

[32]

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