Inference of Monotonicity Constraints in Datalog Programs.

Alexander Brodsky, Yehoshua Sagiv: Inference of Monotonicity Constraints in Datalog Programs. PODS 1989: 190-199

@inproceedings{DBLP:conf/pods/BrodskyS89,
  author    = {Alexander Brodsky and
               Yehoshua Sagiv},
  title     = {Inference of Monotonicity Constraints in Datalog Programs},
  booktitle = {Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, March 29-31, 1989, Philadelphia,
               Pennsylvania},
  publisher = {ACM Press},
  year      = {1989},
  isbn      = {0-89791-308-6},
  pages     = {190-199},
  ee        = {http://doi.acm.org/10.1145/73721.73741, db/conf/pods/BrodskyS89.html},
  crossref  = {DBLP:conf/pods/89},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

BibTeX

Abstract

Datalog (i.e., function-free logic) programs with monotonicity constraints on extensional predicates are considered. A monotonicity constraint states that one argument of a predicate is always less than another argument, according to some partial order. Relations of an extensional database are required to satisfy the monotonicity constraints imposed on their predicates. More specifically, a partial order is defined on the domain (i.e., set of constants) of the database, and every tuple of each relation satisfies the monotonicity constraints imposed on its predicate. An algorithm is given for inferring all monotonicity constraints that hold in relations of the intensional database from monotonicity constraints that hold in the extensional database. A complete inference algorithm is also given for disjunctions of monotonicity and equality constraints. It is shown that the inference of monotonicity constraints in programs is a complete problem for exponential time. For linear programs, this problem is complete for polynomial space.

Copyright © 1989 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.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ...

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
UNIX/LINUX/Mac: use mount point /pods8298/... or /cdrom/...

Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ...

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
UNIX/LINUX/Mac: use mount point /aDVD1/... or /cdrom/...

BibTeX

Printed Edition

Proceedings of the Eighth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, March 29-31, 1989, Philadelphia, Pennsylvania. ACM Press 1989, ISBN 0-89791-308-6
Contents BibTeX

Online Edition: ACM Digital Library

References

[A*88]: Foto N. Afrati, Christos H. Papadimitriou, George Papageorgiou, Athena Roussou, Yehoshua Sagiv, Jeffrey D. Ullman: On the Convergence of Query Evaluation. J. Comput. Syst. Sci. 38(2): 341-359(1989) BibTeX
[KiRS88]: Michael Kifer, Raghu Ramakrishnan, Abraham Silberschatz: An Axiomatic Approach to Deciding Query Safety in Deductive Databases. PODS 1988: 52-60 BibTeX
[KrRS88]: Ravi Krishnamurthy, Raghu Ramakrishnan, Oded Shmueli: A Framework for Testing Safety and Effective Computability of Extended Datalog (Extended Abstract). SIGMOD Conference 1988: 154-163 BibTeX
[RBS87]: Raghu Ramakrishnan, François Bancilhon, Abraham Silberschatz: Safety of Recursive Horn Clauses With Infinite Relations. PODS 1987: 328-339 BibTeX
[UV88]: Jeffrey D. Ullman, Allen Van Gelder: Efficient tests for top-down termination of logical rules. J. ACM 35(2): 345-373(1988) BibTeX

Referenced by

Kenneth A. Ross: Structural Totality and Constraint Stratification. PODS 1995: 184-195
Paris C. Kanellakis: Constraint Programming and Database Languages: A Tutorial. PODS 1995: 46-53
Ke Wang, Li-Yan Yuan: First-Order Logic Characterization of Program Properties. IEEE Trans. Knowl. Data Eng. 6(4): 518-533(1994)
Kirack Sohn: Constraints among Argument Sizes in Logic Programs. PODS 1994: 68-74
Alexander Brodsky, Joxan Jaffar, Michael J. Maher: Toward Practical Constraint Databases. VLDB 1993: 567-580
Kirack Sohn, Allen Van Gelder: Termination Detection in Logic Programs using Argument Sizes. PODS 1991: 216-226
Kenneth A. Ross: Modular Acyclicity and Tail Recursion in Logic Programs. PODS 1991: 92-101
Alexander Brodsky, Yehoshua Sagiv: Inference of Inequality Constraints in Logic Programs. PODS 1991: 227-240
Kenneth A. Ross: Modular Stratification and Magic Sets for DATALOG Programs with Negation. PODS 1990: 161-171
Charles Elkan: Independence of Logic Database Queries and Updates. PODS 1990: 154-160

BibTeX

ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]