Querying constraints

ABSTRACT

The design of languages to tackle constraint satisfaction problems has a long history. Only more recently the reverse problem of introducing constraints as primitive constructs in programming languages has been addressed. A main task that the designers and implementers of such languages face is to use and adapt the concepts and algorithms from the extensive studies on constraints done in areas such as Mathematical Programming, Symbolic Computation, Artificial Intelligence, Program Verification and Computational Geometry. In this paper, we illustrate this task in a simple and yet important domain: linear arithmetic constraints. We show how one can design a querying system for sets of linear constraints by using basic concepts from logic programming and symbolic computation, as well as algorithms from linear programming and computational geometry. We conclude by reporting briefly on how notions of negation and canonical representation used in linear constraints can be generalized to account for cases in term algebras, symbolic computation, affine geometry, and elsewhere.

REFERENCES

• A: S.Achmanov, Programmation Lindaire, Editions Mir, Moscou 1984.
• DE: G.B. Dantzig and B.C. Eaves, Fourier-Motzkin Elimination and Its Dual, Journal of Combinatorial Theory Set. A, 14 (1973) 288-297.
• F: J.B.J. Fourier, reported in: Analyse des travaux de l'Acad~mie Royale des Sciences, pendant l'ann~e 1824, Partie math~matique, Histoire de l'Acaddmie Royale des Sciences de l'lnstitut de France 7 (1827) xlviilv. (Partial English translation in: D.A. Kohler, Translation of a Report by Fourier on his work oll Linear Inequalities, Opsearch 10(1973) 38-42.)
• FRT: R.M. Freund, R. Roundy and M.J. Todd, Identifying the Set of Always- Active Constraints in a System of Linear inequalities by a Single Linear Program, Technical Report, Sloan School of Management, Massachusetts Institute of Technology, October 1985.
• GT: A.J. Goldman and A.W. Tucker, Polyhedral Convex Cones in Linear Inequalities and Related Systems. Annals of Mathematical Studies 38. Princeton University Press, 1956.
• HL: T. ttuynh and J-L. Lassez, Design and Implementation of Algorithms for Variable Elimination in Linear Arithmetic Constraints, forthcoming.
• JL: J. Jaffar , J.-L. Lassez, Constraint logic programming, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.111-119, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41635]
• JMSY: J. Jaffar, S. Michaylov, P. Stuckey and It. Yap, The CLP(~) Language and System, IBM Research Report, T.J. Watson Research Center, forthcoming.
• KKR: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages (preliminary report), Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.299-313, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298582]
• LHM: J-L. Lassez, T. Huynh and K. McAloon, Simplification and Elimination of redundant arithmetic constraints, Proceedings of NACLP 89, MIT Press.
• LM: .}-L. Lassez and M.J. Maher, On Fourier's Algorithm for Linear Arithmetic Constraints, IBM Research Report, T.J. Watson Research Center, 1988.
• LMM: J.-L. Lassez , M. J. Maher , K. Marriott, Unification revisited, Foundations of deductive databases and logic programming, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• LMc: J-L. Lassez and K. McAloon, A Constraint Sequent Calculus, submitted 1989.
• LMc88: J-L. Lassez and K. McAloon, Applications of a Canonical Form for Generalized Linear Constraints, Proceedings of the FGCS Conference, Tokyo, December 1988, 703-710.
• LMc89: Jean-Louis Lassez , Ken McAloon, Independence of Negative Constraints, Proceedings of the International Joint Conference on Theory and Practice of Software Development, Volume 1: Advanced Seminar on Foundations of Innovative Software Development I and Colloquium on Trees in Algebra and Programming, p.19-27, March 13-17, 1989
• M: M. Maher, A Logic Semantics for a class of Committed Choice Languages, Proceedings of ICLP4, MIT Press 87.
• MR: T.H. Matheiss and D.S. Rubin, A Survey of Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets, Mathematics of Operations Research, 5 (1980) 167- 185.
• S: Vijay Anand Saraswat , Dana S. Scott, Concurrent constraint programming languages, 1989

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Logic and constraint programming

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Linear programming

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming

General Terms:
Algorithms, Design, Languages, Management, Performance, Theory