The LyriC language: querying constraint objects

ABSTRACT

We propose a novel data model and its language for querying object-oriented databases where objects may hold spatial, temporal or constraint data, conceptually represented by linear equality and inequality constraints. The proposed LyriC language is designed to provide a uniform and flexible framework for diverse application realms such as (1) constraint-based design in two-, three-, or higher-dimensional space, (2) large-scale optimization and analysis, based mostly on linear programming techniques, and (3) spatial and geographic databases. LyriC extends flat constraint query languages, especially those for linear constraint databases, to structurally complex objects. The extension is based on the object-oriented paradigm, where constraints are treated as first-class objects that are organized in classes. The query language is an extension of the language XSQL, and is built around the idea of extended path expressions. Path expressions in a query traverse nested structures in one sweep. Constraints are used in a query to filter stored constraints and to create new constraint objects.

REFERENCES

• BJM93: Alexander Brodsky , Joxan Jaffar , Michael J. Maher, Toward Practical Constraint Databases, Proceedings of the 19th International Conference on Very Large Data Bases, p.567-580, August 24-27, 1993
• BVCS93: M. Benjamin, T. Viana, K. Corbett, A. Silva, Satisfying Multiple Rated- Constraints in a Knowledge Based Decision Aid, Proc. IEEE Conf. on Artificial Intelligence Applications, Orlando, 1993.
• CHIP: M. Dincbas, P. Van Hentenryck, H. Simnis, A. Aggoun, T. Graf, F. Berthier, The Constraint Logic Programming Language CHIP, Proc. Fifth Generation Computer Systems, Tokyo, Japan, 1988.
• CKW89: W. Chen, M. Kifer, and D.S. Warren, HiLog: A First Order Semantics for Higher-Order Logic Programming Constructs, In 2-nd lntl. Workshop on Database Programming Languages, Morgan-Kaufmann, June 1989.
• End72: H.B. Enderton. A Mathematical Introduction to Logic. Academic Press, 1972.
• Gut89: R. H. Güting, Gral: an extensible relational database system for geometric applications, Proceedings of the 15th international conference on Very large data bases, p.33-44, July 1989, Amsterdam, The Netherlands
• HaC91: Laura M. Haas , William F. Cody, Exploiting Extensible DBMS in Integrated Geographic Information Systems, Proceedings of the Second International Symposium on Advances in Spatial Databases, p.423-450, August 28-30, 1991
• HHLB89: M. R. Hansen , B. S. Hansen , P. Lucas , P. van Emde Boas, Integrating relational databases and constraint languages, Computer Languages, v.14 n.2, p.63-82, Aug. 1989 [doi>10.1016/0096-0551(89)90014-3]
• JaL87: 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]
• JMSY92: J. Jaffar, M.J. Maher, P.J. Stuckey R.H.C. Yap, Output in CLP(T~.), Proc. Int. Conf. on F~flh Generatzon Computer Systems 1992, Tokyo, Japan, Vol. 2, 1992, 987-995.
• KKR93: Paris C. Kanellakis , Gabriel M. Kuper , Peter Z. Revesz, Constraint query languages, Journal of Computer and System Sciences, v.51 n.1, p.26-52, Aug. 1995
• KKS92: Michael Kifer , Won Kim , Yehoshua Sagiv, Querying object-oriented databases, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.393-402, June 02-05, 1992, San Diego, California, United States
• KLW90: Michael Kifer , Georg Lausen , James Wu, Logical foundations of object-oriented and frame-based languages, Journal of the ACM (JACM), v.42 n.4, p.741-843, July 1995 [doi>10.1145/210332.210335]
• KS93: D. Kemp, P. Stuckey, Bottom Up Constraint Logic Programming Without Constraint Solving, Technical Report, Dept. of Computer Science, University of Melbourne, 1992.
• LMA: Jean-Louis Lassez , Ken McAloon, A canonical form for generalized linear constraints, Journal of Symbolic Computation, v.13 n.1, p.1-24, Jan. 1992 [doi>10.1016/0747-7171(92)90002-L]
• LS92: Alon Levy , Yehoshua Sagiv, Constraints and redundancy in datalog, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.67-80, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137111]
• MFPR: Inderpal Singh Mumick , Sheldon J. Finkelstein , Hamid Pirahesh , Raghu Ramakrishnan, Magic conditions, Proceedings of the ninth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.314-330, April 02-04, 1990, Nashville, Tennessee, United States [doi>10.1145/298514.298584]
• OrM88: J. A. Orenstein , F. A. Manola, PROBE Spatial Data Modeling and Query Processing in an Image Database Application, IEEE Transactions on Software Engineering, v.14 n.5, p.611-629, May 1988 [doi>10.1109/32.6139]
• Prolog3: Alain Colmerauer, An introduction to Prolog III, Communications of the ACM, v.33 n.7, p.69-90, July 1990 [doi>10.1145/79204.79210]
• Sch86: Alexandeer Schrijver, Theory of linear and integer programming, John Wiley & Sons, Inc., New York, NY, 1986
• Sri92: D. Srivastava, Subsumption and Indexing in Constraint Query Languages with Linear Arithmetic Constraints, Annals of Mathematics and Artificial Intelligence, to appear.
• SrR92: Divesh Srivastava , Raghu Ramakrishnan, Pushing constraint selections, Proceedings of the eleventh ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.301-315, June 02-05, 1992, San Diego, California, United States [doi>10.1145/137097.137897]
• SRR94: Divesh Srivastava , Raghu Ramakrishnan , Peter Z. Revesz, Constraint Objects, Proceedings of the Second International Workshop on Principles and Practice of Constraint Programming, p.218-228, May 02-04, 1994

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models
      H.2.3 Languages
          Subjects: Query languages
          Nouns: SQL

General Terms:
Algorithms, Languages