[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
research-article

Efficient Database Access from Prolog

Published: 01 February 1989 Publication History

Abstract

In designing the interface between a relational database and a Prolog interpreter, efficiency is a major issue. The authors present a method for loading into the memory-resident database of Prolog facts permanently stored in secondary storage. The rationale of the method is to save access to the database by never repeating the same query and by storing in main memory, in a compact and efficient way, information about the past interaction with the database. The authors discuss how to reduce subsumption rests required by the method to pattern matching in many relevant cases. They also describe a simulator of the method, which validates their approach, and they discuss the results of the simulation.

References

[1]
{1} J. Allchin, A. Keller, and G. Wiederhold, "FLASH: A languageindependent portable file access system," in Proc. ACM-SIGMOD Conf., May 1980, pp. 151-156.]]
[2]
{2} M. Brodie, "On integrating logic programming and databases," in Proc. First Workshop Expert Database Systems, Kiawah Island, SC, Oct. 1984; also in Expert Database Systems, L. Kerschberg, Ed. New York: Benjamin/Cummins, 1986.]]
[3]
{3} S. Ceri and G. Pelagatti, Principles of Distributed Databases. New York: McGraw-Hill, 1984.]]
[4]
{4} S. Ceri, G. Gottlob, and G. Wiederhold: "Interfacing relational databases and Prolog efficiently," in Proc. First Int. Conf. Expert Database Systems, L. Kerschberg, Ed., Charleston, 1986.]]
[5]
{5} S. Ceri, G. Gottlob, and L. Lavazza, "Translation and optimization of logic queries: The algebraic approach," in Proc. 12th Int. Conf. Very Large Data Bases, Kyoto, Aug. 1986.]]
[6]
{6} S. Ceri, F. Gozzi, and M. Lugli, "An overview of PRIMO: A portable interface between Prolog and relational databases," Comput. Sci. School, Univ. Modena, Int. Rep., Feb. 1988.]]
[7]
{7} U. S. Chakravarthy, D. Fishman, and J. Minker, "Semantic query optimization in expert systems and database systems," in Proc. First Workshop Expert Database Systems, Kiawah Island, SC, Oct. 1984; also in Expert Database Systems, L. Kerschberg, Ed. New York: Benjamin/Cummins, 1986.]]
[8]
{8} W. F. Clocksin and C. S. Mellish; Programming in Prolog. New York: Springer-Verlag, 1981.]]
[9]
{9} V. Dahl, "On database systems development through logic," ACM Trans. Database Syst., vol. 7, no. 1, pp. 102-123, Mar. 1982.]]
[10]
{10} A. Frank, "Extending a network database with Prolog," in Proc. First Workshop Expert Database Systems, Kiawah Island, SC, Oct. 1984.]]
[11]
{11} H. Gallaire, J. Minker, and J.-M. Nicolas, "Logic and databases: A deductive approach," ACM Comput. Surveys, vol. 16, no 2, pp. 153- 185, June 1984.]]
[12]
{12} G. Gottlob, "Subsumption and implication," Inform. Processing Lett., 1985.]]
[13]
{13} G. Gottlob and A. Leitsch, "On the efficiency of subsumption algorithms," J. ACM, vol. 32, no. 2, Apr. 1985.]]
[14]
{14} B. E. Jacobs and C. A. Walczak, "A generalized query-by-example data manipulation language based on database logic," IEEE Trans. Software Eng., vol. SE-9, no. 1, pp. 40-57, Jan. 1983.]]
[15]
{15} S. Kunifuji and H. Yokota, " Prolog and relational databases for fifth generation computer systems," in Proc. Workshop Logical Bases for Databases, Toulouse, Dec. 1982.]]
[16]
{16} D. Maier, "Databases in the fifth generation project: Is prolog a database language?" in Proc. ACM-SIGMOD, 1984.]]
[17]
{17} A. Mendelzon, "Functional dependencies in logic programs," in Proc. 11th VLDB Conf., Stockolm, 1985.]]
[18]
{18} M. Missikoff and G. Wiederhold, "Towards a unified approach for expert and database systems," in Proc. First Workshop Expert Database Systems, Kiawah Island, SC, Oct. 1984; also in Expert Data-base Systems, L. Kerschberg, Ed. New York: Benjamin/Cummins, 1986.]]
[19]
{19} D. S. Moffat and P. M. D. Gray, "Interfacing Prolog to a persistent data store," in Proc. Int. Conf. Logic Programming, London, 1986.]]
[20]
{20} K. Morris, J. D. Ullman, and A. Van Gelder, "Design overview of the Nail! system," in Proc. Int. Conf. Logic Programming, London, 1986.]]
[21]
{21} S. A. Naqvi, "Prolog and relational databases: A road to data-intensive expert systems," in Proc. First Workshop Expert Database Systems , Kiawah Island, SC, Oct. 1984.]]
[22]
{22} K. Parsaye, "Logic programming and relational databases," IEEE Comput. Soc. Database Eng. Bull., vol. 6, no. 4, pp. 20-29, Dec. 1983.]]
[23]
{23} K. Ramamohanorao and J. Sheperd, "A superimposed codeword indexing scheme for very large Prolog databases," in Proc. Int. Conf. Logic Programming, London, 1986.]]
[24]
{24} D. R. Sacks and K. Ramamohanorao: "A two level superimposed coding scheme for partial match retrieval," Inform. Syst., vol. 8, no. 4, 1983.]]
[25]
{25} E. Sciore and D. S. Warren, "Towards an integrated database-Prolog system," in Proc. First Workshop Expert Database Systems, vol. 2, Kiawah Island, SC, Oct. 1984.]]
[26]
{26} J. D. Ullman, "Implementation of logical query languages for databases," ACM Trans. Database Syst., vol. 10, no. 3, pp. 289-321, Sept. 1985.]]
[27]
{27} D. H. D. Warren, "Efficient processing of interactive relational databases queries expressed in logic," in Proc. VLDB 7, Zaniolo and Delobel, Eds., Cannes. France. Sept. 1981, pp. 272-281.]]
[28]
{28} G. Wiederhold, Database Design, 2nd ed. New York: McGraw-Hill, 1983.]]
[29]
{29} G. Wiederhold, "An integration of knowledge and data representation," in On Knowledge Base Management Systems: Integrating Artificial Intelligence and Database Technologies, Brodie, Mylopoulos, and Schmidt. Eds. New York: Springer-Verlag, Feb. 1986.]]
[30]
{30} C. Zaniolo: "Prolog: A database query language for all seasons," Proc. First Workshop Expert Database Systems. Kiawah Island, SC. Oct. 1984; in Expert Database Systems, L. Kerschberg, Ed. New York: Benjamin/Cummins, 1986.]]

Cited By

View all
  • (2018)DatalogDeclarative Logic Programming10.1145/3191315.3191317(3-100)Online publication date: 1-Sep-2018
  • (2018)Declarative Logic ProgrammingundefinedOnline publication date: 1-Sep-2018
  • (2010)Logic programming languages for databases and the webA 25-year perspective on logic programming10.5555/1880413.1880423(183-203)Online publication date: 1-Jan-2010
  • Show More Cited By

Index Terms

  1. Efficient Database Access from Prolog

                        Recommendations

                        Reviews

                        Bernhard Thalheim

                        This paper presents a new approach to handling large fact bases for artificial intelligence and applies it to the design of an interface between databases and Prolog. It extends a previous paper by the authors, which was based on preanalysis. The interface acts as a loading mechanism. The authors introduce tracers in order to formalize the meta-knowledge about the structure of formulas and handle the loading of data from secondary storage during program execution more efficiently. Tracers can be partially ordered and this ordering can be used both to load the subsumed (i.e., the common) part first and, later on, to handle exceptions like negative facts. The authors implement the method as a prototype and show its effectiveness by means of comparisons. The method is new and seems to be applicable to general query and transaction handling in databases and knowledge bases as well, especially in Prolog-like environments.

                        Access critical reviews of Computing literature here

                        Become a reviewer for Computing Reviews.

                        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 15, Issue 2
                        February 1989
                        130 pages
                        ISSN:0098-5589
                        Issue’s Table of Contents

                        Publisher

                        IEEE Press

                        Publication History

                        Published: 01 February 1989

                        Author Tags

                        1. Prolog
                        2. Prolog facts
                        3. Prolog interpreter
                        4. logic programming
                        5. memory-resident database
                        6. pattern matching
                        7. program interpreters
                        8. relational database
                        9. relational databases.
                        10. secondary storage
                        11. subsumption rests

                        Qualifiers

                        • Research-article

                        Contributors

                        Other Metrics

                        Bibliometrics & Citations

                        Bibliometrics

                        Article Metrics

                        • Downloads (Last 12 months)0
                        • Downloads (Last 6 weeks)0
                        Reflects downloads up to 18 Jan 2025

                        Other Metrics

                        Citations

                        Cited By

                        View all
                        • (2018)DatalogDeclarative Logic Programming10.1145/3191315.3191317(3-100)Online publication date: 1-Sep-2018
                        • (2018)Declarative Logic ProgrammingundefinedOnline publication date: 1-Sep-2018
                        • (2010)Logic programming languages for databases and the webA 25-year perspective on logic programming10.5555/1880413.1880423(183-203)Online publication date: 1-Jan-2010
                        • (2009)Implementing Reflective Access Control in SQLProceedings of the 23rd Annual IFIP WG 11.3 Working Conference on Data and Applications Security XXIII10.1007/978-3-642-03007-9_2(17-32)Online publication date: 13-Jul-2009
                        • (2007)Deploying mobile agents in distributed data miningProceedings of the 2007 international conference on Emerging technologies in knowledge discovery and data mining10.5555/1780582.1780618(322-331)Online publication date: 22-May-2007
                        • (1994)The Design, Implementation, and Performance Evaluation of BERMUDAIEEE Transactions on Knowledge and Data Engineering10.1109/69.2730246:1(38-56)Online publication date: 1-Feb-1994
                        • (1992)Concepts and implementation of a rule-based process engineProceedings of the 14th international conference on Software engineering10.1145/143062.143126(262-279)Online publication date: 1-Jun-1992
                        • (1992)A Logic-Based Approach to Reverse Engineering Tools ProductionIEEE Transactions on Software Engineering10.1109/32.18476018:12(1053-1064)Online publication date: 1-Dec-1992
                        • (1991)An incremental access method for ViewCacheACM Transactions on Database Systems10.1145/111197.11121516:3(535-563)Online publication date: 1-Sep-1991

                        View Options

                        View options

                        Media

                        Figures

                        Other

                        Tables

                        Share

                        Share

                        Share this Publication link

                        Share on social media