More Web Proxy on the site http://driver.im/

research-article

Prolog-Based Meta-rules for Relational Database Representation and Manipulation

Authors:

Kalervo JärvelinAuthors Info & Claims

IEEE Transactions on Software Engineering, Volume 17, Issue 8

Pages 762 - 788

https://doi.org/10.1109/32.83913

Published: 01 August 1991 Publication History

Abstract

A Prolog-based experimental system for relational databases that is not defined from the viewpoint of any specific relational topic is proposed. The idea is that the experimental system can be used in many different contexts such as query optimization, data restructuring and database design. The definition is based entirely on the theoretical foundations of the relational model. The experimental system offers a well-defined environment for studying how other systems can be integrated with relational databases. The use of the experimental system in the context of different approaches to deductive databases is considered.

References

[1]

{1} H. Abramson and V. Dahl, Logic Grammars New York: Springer-Verlag, 1989.

[2]

{2} R. Agrawal, "Alpha: an extension of relational algebra to express a class of recursive queries," in Proc. 3rd IEEE Data Eng. Conf. (Los Angeles, CA), 1987, pp. 580-590.

[3]

{3} T. Amble, Logic Programming and Knowledge Engineering. Wokingham, UK: Addison-Wesley, 1987.

[4]

{4} M. M. Astrahan and D. D. Chamberlin, "Implementation of a structured English query language," Commun. ACM, vol. 18, no. 10, pp. 580-588, 1975.

Digital Library

[5]

{5} F. Bancilhon and S. Khoshafian, "A calculus for complex objects," in Proc. 5th ACM SIGMOD-SIGACT Symp. on Principles of Database Syst., 1986, pp. 53-59.

[6]

{6} F. Bancilhon, T. Briggs, S. Khoshafian, and P. Valduriez, "FAD: a powerful and simple database language," in Proc. 13th VLDB Conf. (Brighton, UK), 1987, pp. 97-105.

[7]

{7} D. Bitton, "The effect of large main memory on database systems," in Proc. ACM SIGMOD Conf. (Washington, DC), 1986, pp. 337-339.

[8]

{8} D. Bjorner, Programming in the Meta-language: The Vienna Development Method. New York: Springer-Verlag, 1978, pp. 24-217.

[9]

{9} C. Beeri, S. Naqvi, R. Ramakrishnan, O. Shmueli, and S. Tsur, "Sets and negation in logic database language (LDL1)," in Proc. 6th ACM SIGMOD-SIGACT Symp. on Principles of Database Syst. (San Diego, CA), 1987, pp. 21-37.

[10]

{10} I. Bratko, PROLOG: Programming for Artificial Intelligence. Reading, MA: Addison-Wesley, 1986.

[11]

{11} M. L. Brodie, "Research issues in database specification," ACM Sigmod Rec., vol. 13, no. 3, pp. 42-45, 1983.

Digital Library

[12]

{12} S. Ceri and G. Gottlob, "Normalization of the relations and Prolog," Commun. ACM, vol. 29, no. 6, pp. 524-544, 1986.

Digital Library

[13]

{13} S. Ceri, G. Gottlob, and L. Tanca, Logic Programming and Databases. Berlin: Springer-Verlag, 1990.

Digital Library

[14]

{14} A. Y. Chan, "Index selection in a self-adaptive relational data base management system," MIT, Lab. Comput. Sci., Cambridge, MA, Rep. MIT/LCS/TR-166, 1976.

[15]

{15} C. L. Chang, "On evaluation of queries containing derived relations in a relational data base, in Advances in Data Base Theory, vol. 1, H. Gallaire, J. Minker, and J.-M. Nicholas, Eds. New York: Plenum, 1981, pp. 235-260.

[16]

{16} S. Christodoulakis, "Estimating record selectivities," Inform. Syst., vol. 8, no. 2, pp. 105-115, 1983.

[17]

{17} C. L. Chang and A. Walker, "PROSQL: A Prolog programming interface with SQL/DS," in Proc. 1st Int. Workshop on Expert Database Syst., L. Kerschberg, Ed., 1986, pp. 233-246.

[18]

{18} E. Clemons, "Design of an external schema facility to define and process recursive structures," ACM Trans. Database Syst., vol. 6, no. 2, pp. 295-311, 1981.

Digital Library

[19]

{19} W. Clocksin and C. Mellish, Programming in Prolog. Springer-Verlag, 1981.

Digital Library

[20]

{20} E. F. Codd, The Relational Model for Database Management: Version 2. Reading, MA: Addison-Wesley, 1990.

Digital Library

[21]

{21} V. Dahl, "On database systems development through logic," ACM TODS, vol. 7, no. 1, pp. 102-123, 1982.

Digital Library

[22]

{22} D. Delobel, "An overview of the relational data theory," in Proc. IFIP '80. Amsterdam: North-Holland, 1980, pp. 413-426.

[23]

{23} D. J. DeWitt et al., "Implementation techniques for main memory databases," in Proc. ACM Sigmod (Boston, MA), June 18-21, 1984, pp. 1-8.

[24]

{24} P. M. D. Gray, "Efficient Prolog access to Codasyl and FDM databases," in Proc. ACM Sigmod (TX), May 28-31, 1985, pp. 437-443.

[25]

{25} A. Guttman, "New features for relational database systems to support CAD applications," Ph.D. dissert., Comput. Sci. Dept., Univ. California, Berkley, June 1984.

[26]

{26} D. I. Howells, N. J. Fiddian, and W. A. Gray, "A source-to-source meta-translation system for relational query languages," in Proc. 13th VLDB Conf. (Brighton, UK), 1987, pp. 227-234.

[27]

{27} H. V. Jagadish and R. Agrawal, "A study of transitive closure as a recursion mechanism," in Proc. 1987 ACM SIGMOD Conf. (San Francisco, CA), 1987, pp. 331-334.

[28]

{28} K. Järvelin and T. Niemi, "Entity-based query construction for relational database access," Dept. Comput. Sci., Univ. Tampere, Tampere, Finland, Rep. A-1990-6, 1990.

[29]

{29} K. Järvelin, "Boolean predicate reduction for file access," in Information Modeling and Knowledge Bases, H. Kangassalo, S. Ohsuga, and H. Jaakola, Eds. Amsterdam: IOS, 1990, pp. 388-406.

[30]

{30} C. Kellog, A. O'Hare, and L. Travis, "Optimizing the rule-data interface in a KMS," in Proc. 12th VLDB Conf. (Kyoto, Japan), 1986, pp. 42-51.

[31]

{31} S. Kunifuji and H. Yokota, "Prolog and relational data bases for fifth generation computer systems," presented at the Workshop on Logical Bases for Data Bases, Tolouse, France, 1982.

[32]

{32} Y. Y. Leung and D. L. Lee, "Logic approaches for deductive databases," IEEE Expert, Winter Issue, pp. 64-75, 1988.

Digital Library

[33]

{33} D. Li, A PROLOG Database System. Letchworth, UK: Research Studies Press, 1984.

[34]

{34} R. Lucas, Database Applications Using Prolog. Chichester, UK: Ellis Horwood, 1988.

[35]

{35} D. Maier, The Theory of Relational Databases. London: Pitman, 1984.

[36]

{36} M. McCord, "Natural language processing in Prolog," in Knowledge Systems and Prolog, A. Walker et al., Eds. Reading, MA: Addison-Wesley, 1987, pp. 291-402.

[37]

{37} S. P. Navathe and J. B. Fry, "Restructuring for large databases: three levels of abstraction," ACM TODS, vol. 1, no. 2, pp. 138-158, 1976.

Digital Library

[38]

{38} P. Naur, "Formalization in program development," BIT, vol. 22, no. 4, pp. 437-453, 1982.

Digital Library

[39]

{39} T. Niemi, "Formal restructuring functions for hierarchical data bases," Int. J. Comput. Inform. Sci., vol. 12, no. 6, pp. 385-411, 1983.

[40]

{40} T. Niemi, "Specification of a query language by the attribute method," BIT, vol. 24, pp. 171-186, 1984.

Digital Library

[41]

{41} T. Niemi and K. Järvelin, "A straightforward formalization of the relational model," Inform. Syst., vol. 10, no. 1, pp. 65-76, 1985.

Digital Library

[42]

{42} T. Niemi and K. Järvelin, "A meta-information approach to relational database representation and manipulation based on Prolog," Dept. Comput. Sci., Univ. Tampere, Tampere, Finland, Rep. A-1988-11, 1988.

[43]

{43} T. Niemi and K. Järvelin, "Operation-oriented query language approach for recursive queries," Dept. Comput. Sci., Univ. Tampere, Rep. A- 1990-2, Tampere, Finland, 1990.

[44]

{44} T. Niemi and K. Järvelin, "The rule-based prototype implementation for the operation-oriented recursive query language approach and its integration with relational databases," Dept. Comput. Sci., Univ. Tampere, Tampere, Finland, Rep. A-1990-9, 1990.

[45]

{45} T. Niemi and K. Järvelin, "Advanced query processing in deductive databases," Inform Proc. Manage., to be published.

[46]

{46} S. Oshuga, "Knowledge-based systems as a new interactive computer system of the next generation," in Computer Science and Technologies. Amsterdam: North-Holland, 1982, pp. 227-249.

[47]

{47} Z. Ozsoyogly and L. Yuan, "A normal form for nested relations," in Proc. 4th Symp. Principles Database Syst., 1985, pp. 251-260.

[48]

{48} F. C. N. Pereira and D. H. D. Warren, "Definite clause grammars for language analysis--a survey of the formalism and a comparison with augmented transition networks," Artificial Intell., vol. 13, pp. 231-278, 1980.

[49]

{49} A. Pirotte, "A precise definition of basic relational notations and of the relational algebra," ACM Sigmod Rec., vol. 13, no. 1, pp. 30-45, 1982.

Digital Library

[50]

{50} A. Rosenthal, S. Heiler, U. Dayal, and F. Manola, "Traversal recursion: a practical approach to supporting recursive applications," in Proc. 1986 ACM SIGMOD Conf. (Washington, DC), 1986, pp. 166-176.

Digital Library

[51]

{51} M. A. Roth, "The design of - 1NF relational databases into nested normal form," in Proc. ACM Sigmod (San Francisco, CA), May 27-29, 1987, pp. 143-159.

[52]

{52} E. Sciore, "Database facilities for Prolog," Dept. Comput. Sci., State Univ. New York, Stony Brook, Tech. Rep. 85/012, 1985.

[53]

{53} M. Schkolnick and P. Tiberio, "A note on estimating the maintenance cost in a relational database," IBM Res. Lab., San Jose, CA, Rep. RJ 3327 (40084), 1981.

[54]

{54} E. Sciore and D. S. Warren, "Towards an integrated database-Prolog system," in Proc. 1st Int. Workshop Expert Database Syst., L. Kerschberg, Ed., 1986, pp. 293-305.

[55]

{55} P. G. Selinger et al., "Access path selection in a relational database management system," in Proc. ACM SIGMOD Conf. (Boston, MA), May 30-June 1, 1979, P.A. Bernstein, Ed., pp. 23-34.

[56]

{56} B. Shneiderman and G. Thomas, "An architecture for automatic relational database system conversion," ACM TODS, vol. 7, no. 2, pp. 235-257, 1982.

Digital Library

[57]

{57} J. M. Smith and P. Y.-T. Chang, "Optimizing the performance of a relational algebra database interface," Commun. ACM, vol. 18, no. 10, pp. 568-579, 1975.

Digital Library

[58]

{58} L. Sterling and E. Shapiro, The Art of Prolog. Cambridge, MA: MIT Press, 1986.

[59]

{59} T. J. Teorey and J. R. Fry, Design of Database Structures. Englewood Cliffs, NJ: Prentice-Hall, 1982.

Digital Library

[60]

{60} S. Tsur and C. Zaniolo, "LDL: a logic-based data-language," in Proc. 12th VLDB Conf., 1986, pp. 33-41.

[61]

{61} J. D. Ullman, Principles of Data Base Systems. Rockville, MD: Comput. Sci. Press, 1980.

[62]

{62} J. D. Ullman, "Implementation of logical query languages for databases," ACM TODS, vol. 10, no. 3, pp. 289-321, 1985.

Digital Library

[63]

{63} J. D. Ullman, Principles of Database and Knowledge Base Systems, vol. I. Rockville, MD: Comput. Sci. Press, 1988.

[64]

{64} J. D. Ullman, Principles of Database and Knowledge Base Systems, vol. II: The New Technologies. Rockville, MD: Comput. Sci. Press, 1989.

[65]

{65} H. Yokota et al., "An enhanced inference mechanism for generating relational algebra queries," in Proc. 3rd Symp. Principles of Database Syst., 1984, pp. 229-238.

[66]

{66} T. Yokomori, "A logic program schema and its applications," in Proc. 9th Int. Joint Conf. Artificial Intell., (Los Angeles, CA), 1985, pp. 723-725.

Digital Library

[67]

{67} C. T. Yu and Y. C. Lin, "Some estimation problems in distributed query processing" in Proc. IEEE Distrib. Comput. Syst. Conf., 1982, pp. 13-19.

[68]

{68} C. Zaniolo, "Prolog: a database query language for all seasons," in Proc. 1st Int. Workshop Expert Database Syst., 1986, L. Kerschberg, Ed., pp. 219-232.

[69]

{69} H. Zemanak, "Abstract architecture," in Abstract Software Specification. New York: Springer-Verlag, 1980, pp. 437-453.

[70]

{70} M. M. Zloof, "Query-by-example: operations on transitive closure," IBM, Yorktown Hts., NY, RC 5526, 1975.

Cited By

Porto A(2009)An alternative high-level approach to interaction with databasesProceedings of the 18th international conference on Applications of declarative programming and knowledge management10.5555/2008383.2008386(20-39)Online publication date: 3-Nov-2009
https://dl.acm.org/doi/10.5555/2008383.2008386
Niemi THirvonen LJärvelin K(2003)Multidimensional data model and query language for informetricsJournal of the American Society for Information Science and Technology10.1002/asi.1029054:10(939-951)Online publication date: 1-Aug-2003
https://dl.acm.org/doi/10.1002/asi.10290
Russomanno DMakki KPissinou N(1996)An automated inference approach to network derivation for AM/FM/GIS systemsProceedings of the 4th ACM international workshop on Advances in geographic information systems10.1145/258319.258344(90-97)Online publication date: 1-Nov-1996
https://dl.acm.org/doi/10.1145/258319.258344
Show More Cited By

Index Terms

Prolog-Based Meta-rules for Relational Database Representation and Manipulation

Recommendations

Coupling Production Systems and Database Systems: A Homogeneous Approach

Methods for storing and manipulating large rule bases using a relational database management systems (DBMS) are discussed. An approach to decomposing and storing the condition elements in the antecedents of rules such as those used in production rule-...
Progress in Database Search Strategies

Retrieval speed and precision ultimately determine the success of any database system. This article outlines the challenges posed by distributed and heterogeneous database systems, including those that store unstructured data, and surveys recent work. ...
On Workload Characterization of Relational Database Environments

A relational database workload analyzer (REDWAR) is developed to characterize the workload in a DB2 environment. This is applied to study a production DB2 system where a structured query language (SQL) trace for a two-hour interval and an image copy of ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Software Engineering

IEEE Transactions on Software Engineering Volume 17, Issue 8

August 1991

113 pages

ISSN:0098-5589

Editor:
Victor R. Basili
Univ. of Maryland, College Park

Issue’s Table of Contents

Copyright © Copyright © 1991 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 August 1991

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Porto A(2009)An alternative high-level approach to interaction with databasesProceedings of the 18th international conference on Applications of declarative programming and knowledge management10.5555/2008383.2008386(20-39)Online publication date: 3-Nov-2009
https://dl.acm.org/doi/10.5555/2008383.2008386
Niemi THirvonen LJärvelin K(2003)Multidimensional data model and query language for informetricsJournal of the American Society for Information Science and Technology10.1002/asi.1029054:10(939-951)Online publication date: 1-Aug-2003
https://dl.acm.org/doi/10.1002/asi.10290
Russomanno DMakki KPissinou N(1996)An automated inference approach to network derivation for AM/FM/GIS systemsProceedings of the 4th ACM international workshop on Advances in geographic information systems10.1145/258319.258344(90-97)Online publication date: 1-Nov-1996
https://dl.acm.org/doi/10.1145/258319.258344
Järvelin KNiemi TFox E(1991)Data conversion, aggregation and deduction for advanced retrieval from the heterogeneous fact databasesProceedings of the 14th annual international ACM SIGIR conference on Research and development in information retrieval10.1145/122860.122877(173-182)Online publication date: 1-Sep-1991
https://dl.acm.org/doi/10.1145/122860.122877

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents