ACM SIGMOD Anthology TODS dblp.uni-trier.de

Semantics for Update Rule Programs and Implementations in a Relational Database Management System.

Louiqa Raschid, Jorge Lobo: Semantics for Update Rule Programs and Implementations in a Relational Database Management System. ACM Trans. Database Syst. 21(4): 526-571(1996)
@article{DBLP:journals/tods/RaschidL96,
  author    = {Louiqa Raschid and
               Jorge Lobo},
  title     = {Semantics for Update Rule Programs and Implementations in a Relational
               Database Management System},
  journal   = {ACM Trans. Database Syst.},
  volume    = {21},
  number    = {4},
  year      = {1996},
  pages     = {526-571},
  ee        = {http://doi.acm.org/10.1145/236711.236714, db/journals/tods/RaschidL96.html},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

In this paper, we present our research on defining a correct semantics for a class of update rule (UR) programs, and discuss implemanting these programs in a DBMS environment. Update rules execute by updating relations in a database which may cause the further execution of rules. A correct semantics must guarantee that the execution of the rules will terminate and that it will produce a minimal updated database. The class of UR programs is syntactically identified, based upon a concept that is similar to stratification. We extend that strict definition of stratification and allow a relaxed criterion for partitioning of the rules in the UR program. This relaxation allows a limited degree of nondeterminism in rule execution. We define an execution semantics based upon a monotonic fixpoint operator TUR, resulting in a set of fixpoints for UR. The monotionicity of the operator is maintained nby explicitly representing the effect of asserting and retracting tuples in the database. A declarative semantics for the update rule program is obtained by associating a normal logic program UR to represent the UR program. We use the stable model semantics which characterize a normal logic program by a set of minimal models which are called stable models. We show the equivalence between the set of fixpoints for UR and the set of stable models for UR. We briefly discuss implementing the fixpoint semantics of the UR program in a DBMS environment. Relations that can be updated by the rules are updatable relations and they are extended with two flags. An update rule is represented by a database query, which queries the updatable relations as well as database relaions, i.e., those relations which are not update by rules. We describe an algorithm to process the queries and compute a fixpoint in the DBMS environment and obtain a final database.

Copyright © 1996 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

ACM SIGMOD Anthology

CDROM Version: Load the CDROM "Volume 4 Issue 1, Books, VLDB-j, TODS, ..." and ... DVD Version: Load ACM SIGMOD Anthology DVD 2" and ... BibTeX

Online Edition: ACM Digital Library

[Abstract and Index Terms]
[Full Text in PDF Format, 554 KB]

References

[Abiteboul et al. 1990]
Serge Abiteboul, Eric Simon, Victor Vianu: Non-Deterministic Languages to Express Deterministic Transformations. PODS 1990: 218-229 BibTeX
[Abiteboul and Vianu 1990]
Serge Abiteboul, Victor Vianu: Procedural Languages for Database Queries and Updates. J. Comput. Syst. Sci. 41(2): 181-229(1990) BibTeX
[Abiteboul and Vianu 1991]
Serge Abiteboul, Victor Vianu: Datalog Extensions for Database Queries and Updates. J. Comput. Syst. Sci. 43(1): 62-124(1991) BibTeX
[Apt et al. 1988]
Krzysztof R. Apt, Howard A. Blair, Adrian Walker: Towards a Theory of Declarative Knowledge. Foundations of Deductive Databases and Logic Programming. 1988: 89-148 BibTeX
[Bocca 1986a]
Jorge B. Bocca: EDUCE: A Marriage of Convenience: Prolog and a Relational DBMS. SLP 1986: 36-45 BibTeX
[Bocca 1986b]
Jorge B. Bocca: On the Evaluation Strategy of EDUCE. SIGMOD Conference 1986: 368-378 BibTeX
[Ceri and Widom 1990]
Stefano Ceri, Jennifer Widom: Deriving Production Rules for Constraint Maintainance. VLDB 1990: 566-577 BibTeX
[Demolombre 1982]
...
[Delcambre and Etheredge 1988]
Lois M. L. Delcambre, James N. Etheredge: A Self-Controlling Interpreter for the Relational Production Language. SIGMOD Conference 1988: 396-403 BibTeX
[Fagin et al. 1986]
Ronald Fagin, Gabriel M. Kuper, Jeffrey D. Ullman, Moshe Y. Vardi: Updating Logical Databases. Advances in Computing Research 3: 1-18(1986) BibTeX
[Forgy 1981]
...
[Forgy 1982]
Charles Forgy: Rete: A Fast Algorithm for the Many Patterns/Many Objects Match Problem. Artif. Intell. 19(1): 17-37(1982) BibTeX
[Gelfond and Lifschitz 1988]
Michael Gelfond, Vladimir Lifschitz: The Stable Model Semantics for Logic Programming. ICLP/SLP 1988: 1070-1080 BibTeX
[Gordin and Pasik 1991]
Douglas N. Gordin, Alexander J. Pasik: Set-Oriented Constructs: From Rete Rule Bases to Database Systems. SIGMOD Conference 1991: 60-67 BibTeX
[Gupta et al. 1989]
Anoop Gupta, Charles Forgy, Allen Newell: High-Speed Implementations of Rule-Based Systems. ACM Trans. Comput. Syst. 7(2): 119-146(1989) BibTeX
[Hayes-Roth 1985]
Frederick Hayes-Roth: Rule-Based Systems. Commun. ACM 28(9): 921-932(1985) BibTeX
[Kohli et al. 1985]
...
[Kowalski and Sadri 1989]
...
[Kowalski and Sadri 1990]
Robert A. Kowalski, Fariba Sadri: Logic Programs with Exceptions. ICLP 1990: 598-613 BibTeX
[Lobo 1990]
...
[Maindreville and Simon 1988]
Christophe de Maindreville, Eric Simon: Modelling Non Deterministic Queries and Updates in Deductive Databases. VLDB 1988: 395-406 BibTeX
[Manchandra and Warren 1988]
Sanjay Manchanda, David Scott Warren: A Logic-based Language for Database Updates. Foundations of Deductive Databases and Logic Programming. 1988: 363-394 BibTeX
[Miranker 1987]
Daniel P. Miranker: TREAT: A Better Match Algorithm for AI Production System Matching. AAAI 1987: 42-47 BibTeX
[Minker 1988]
...
[Morris et al. 1986]
Katherine A. Morris, Jeffrey D. Ullman, Allen Van Gelder: Design Overview of the NAIL! System. ICLP 1986: 554-568 BibTeX
[Naqvi and Krishnamurthy 1988]
Shamim A. Naqvi, Ravi Krishnamurthy: Database Updates in Logic Programming. PODS 1988: 251-262 BibTeX
[Nicolas 1982]
Jean-Marie Nicolas: Logic for Improving Integrity Checking in Relational Data Bases. Acta Inf. 18: 227-253(1982) BibTeX
[Nicolas and Demolombre 1983]
...
[Pang and Raschid 1994]
...
[Raschid 1990]
Louiqa Raschid: Maintaining Consistency in a Stratified Production System Program. AAAI 1990: 284-289 BibTeX
[Raschid 1994]
Louiqa Raschid: A Semantics for a Class of Stratified Production System Programs. J. Log. Program. 21(1): 31-57(1994) BibTeX
[Raschid and Lobo 1994]
Louiqa Raschid, Jorge Lobo: A Semantics for a Class of Non-Deterministic and Causal Production System Programs. J. Autom. Reasoning 12(3): 305-349(1994) BibTeX
[Sellis et al. 1988]
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
[Sellis et al. 1993]
Timos K. Sellis, Chih-Chen Lin, Louiqa Raschid: Coupling Production Systems and Database Systems: A Homogeneous Approach. IEEE Trans. Knowl. Data Eng. 5(2): 240-256(1993) BibTeX
[Simon and Maindreville 1988]
Eric Simon, Christophe de Maindreville: Deciding Whether a Production Rule is Relational Computable. ICDT 1988: 205-222 BibTeX
[Stonebraker et al. 1988]
Michael Stonebraker, Eric N. Hanson, Spyros Potamianos: The POSTGRES Rule Manager. IEEE Trans. Software Eng. 14(7): 897-907(1988) BibTeX
[Tsur and Zaniolo 1986]
Shalom Tsur, Carlo Zaniolo: LDL: A Logic-Based Data Language. VLDB 1986: 33-41 BibTeX
[Ullman 1985]
Jeffrey D. Ullman: Implementation of Logical Query Languages for Databases. ACM Trans. Database Syst. 10(3): 289-321(1985) BibTeX
[van Emden and Kowalski 1976]
Maarten H. van Emden, Robert A. Kowalski: The Semantics of Predicate Logic as a Programming Language. J. ACM 23(4): 733-742(1976) BibTeX
[Widom 1991]
...
[Widom and Finkelstein 1990]
Jennifer Widom, Sheldon J. Finkelstein: Set-Oriented Production Rules in Relational Database Systems. SIGMOD Conference 1990: 259-270 BibTeX
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
TODS, ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Tue Jun 24 18:39:20 2008