research-article

A Generalized QSQR Evaluation Method for Horn Knowledge Bases

Authors:

Ewa Madalińska-Bugaj,

Linh Anh NguyenAuthors Info & Claims

ACM Transactions on Computational Logic (TOCL), Volume 13, Issue 4

Article No.: 32, Pages 1 - 28

https://doi.org/10.1145/2362355.2362360

Published: 01 October 2012 Publication History

Abstract

We generalize the QSQR evaluation method to give the first set-oriented depth-first evaluation method for Horn knowledge bases. The resulting procedure closely simulates SLD-resolution (to take advantages of the goal-directed approach) and highly exploits set-at-a-time tabling. Our generalized QSQR evaluation procedure is sound and complete. It does not use adornments and annotations. To deal with function symbols, our procedure uses iterative deepening search, which iteratively increases term-depth bound for atoms and substitutions occurring in the computation. When the term-depth bound is fixed, our evaluation procedure runs in polynomial time in the size of extensional relations.

Supplementary Material

PDF File (a32-madalinska-bugaj_appendix.pdf)

The proof is given in an electronic appendix, available online in the ACM Digital Library.

Download
413.50 KB

References

[1]

Abiteboul, S., Hull, R., and Vianu, V. 1995. Foundations of Databases. Addison Wesley.

Digital Library

[2]

Apt, K. 1997. From Logic Programming to Prolog. Prentice-Hall.

Digital Library

[3]

Bancilhon, F., Maier, D., Sagiv, Y., and Ullman, J. 1986. Magic sets and other strange ways to implement logic programs. In Proceedings of the ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS’86). ACM, 1--15.

Digital Library

[4]

Brodt, S., Bry, F., and Eisinger, N. 2009. Search for more declarativity. In Proceedings of the 3rd International Conference Web Reasoning and Rule Systems. A. Polleres and T. Swift Eds., Lecture Notes in Computer Science, vol. 5837, Springer, 71--86.

Digital Library

[5]

Bry, F. 1990. Query evaluation in deductive databases: Bottom-up and top-down reconciled. Data Knowl. Engin. 5, 289--312.

Digital Library

[6]

Calì, A., Gottlob, G., and Lukasiewicz, T. 2009. Datalog^±: A unified approach to ontologies and integrity constraints. In Proceedings of the International Conference on Database Theory (ICDT’09). R. Fagin Ed., ACM International Conference Proceeding Series, vol. 361, ACM, 14--30.

Digital Library

[7]

Cao, S., Nguyen, L., and Szalas, A. 2011a. On the web ontology rule language OWL 2 RL. In Proceedings of the 3rd International Conference on Computational Collective Intelligence. Technologies and Applications (ICCCI’11). P. Jedrzejowicz, N.-T. Nguyen, and K. Hoang Eds., Lecture Notes in Computer Science, vol. 6922, Springer, 254--264.

Digital Library

[8]

Cao, S., Nguyen, L., and Szalas, A. 2011b. WORL: A Web ontology rule language. In Proceedings of the 3rd International Conference on Knowledge and Systems Engineering (KSE’11). IEEE, 32--39.

Digital Library

[9]

Clark, K. 1979. Predicate logic as a computational formalism. Research rep. DOC 79/59, Department of Computing, Imperial College.

[10]

Freire, J., Swift, T., and Warren, D. 1997. Taking I/O seriously: Resolution reconsidered for disk. In Proceedings of the International Conference on Logic Programming (ICLP’97). L. Naish Ed., MIT Press, 198--212.

[11]

Lloyd, J. 1987. Foundations of Logic Programming 2nd Ed. Springer.

Digital Library

[12]

Madalińska-Bugaj, E. and Nguyen, L. 2008. Generalizing the QSQR evaluation method for Horn knowledge bases. In New Challenges in Applied Intelligence Technologies, N.-T. Nguyen and R. Katarzyniak Eds., Studies in Computational Intelligence Series, vol. 134, Springer, 145--154.

[13]

Nejdl, W. 1987. Recursive strategies for answering recursive queries - the RQA/FQI strategy. In Proceedings of the International Conference on Very Large Databases (VLDB’87). P. Stocker, W. Kent, and P. Hammersley Eds., Morgan Kaufmann, 43--50.

Digital Library

[14]

Nguyen, L. 2007. Foundations of modal deductive databases. Fundamenta Informaticae 79, 1--2, 85--135.

Digital Library

[15]

Nguyen, L. 2011. An implementation in Prolog of the generalized QSQR evaluation method for Horn knowledge bases. http://www.mimuw.edu.pl/~nguyen/GQSQR-PL.zip.

[16]

Ramakrishnan, R., Srivastava, D., and Sudarshan, S. 1992. Efficient bottom-up evaluation of logic programs. In The State of the Art in Computer Systems and Software Engineering, J. Vandewalle Ed., Kluwer Academic Publishers.

[17]

Rohmer, J., Lescouer, R., and Kerisit, J.-M. 1986. The Alexander method: A technique for the processing of recursive axioms in deductive databases. New Generation Comput. 4, 3, 273--285.

Digital Library

[18]

Ross, K. 1996. Tail recursion elimination in deductive databases. ACM Trans. Datab. Syst. 21, 2, 208--237.

Digital Library

[19]

Sagonas, K. and Swift, T. 1998. An abstract machine for tabled execution of fixed-order stratified logic programs. ACM Trans. Program. Lang. Syst. 20, 3, 586--634.

Digital Library

[20]

Sagonas, K., Swift, T., and Warren, D. 1994. XSB as an efficient deductive database engine. In Proceedings of the ACM SIGMOD Conference on Management of Data. R. Snodgrass and M. Winslett Eds., ACM Press, 442--453.

Digital Library

[21]

Shen, Y.-D., Yuan, L.-Y., You, J.-H., and Zhou, N.-F. 2001. Linear tabulated resolution based on Prolog control strategy. Theory Pract. Logic Program. 1, 1, 71--103.

Digital Library

[22]

Staab, S. 2008. Completeness of the SLD-resolution. Slides of a course on advanced data modeling, http://www.uni-koblenz.de/FB4/Institutes/IFI/AGStaab/Teaching/SS08/adm08/DB2-SS08-Slides9.ppt.

[23]

Stärk, R. 1990. A direct proof for the completeness of SLD-resolution. In Proceedings of the 3rd Workshop on Computer Science Logic (CSL’89). E. Börger, H. Büning, and M. Richter Eds., Lecture Notes in Computer Science, vol. 440, Springer, 382--383.

Digital Library

[24]

Tamaki, H. and Sato, T. 1986. OLD resolution with tabulation. In Proceedings of the International Conference on Logic Programming (ICLP’86). Lecture Notes in Computer Science, vol. 225, E. Shapiro Ed., Springer, 84--98.

Digital Library

[25]

Vieille, L. 1986. Recursive axioms in deductive databases: The query/subquery approach. In Proceedings of Expert Database Conference. 253--267.

[26]

Vieille, L. 1987. A database-complete proof procedure based on SLD-resolution. In Proceedings of the International Conference on Logic Programming. 74--103.

[27]

Vieille, L. 1989. Recursive query processing: The power of logic. Theor. Comput. Sci. 69, 1, 1--53.

Digital Library

[28]

Zhou, N.-F. and Sato, T. 2003. Efficient fixpoint computation in linear tabling. In Proceedings of the ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP’03). ACM, 275--283.

Digital Library

Cited By

Cao SPhong PAnh L(2021)Integrating Multi-threading into Query-Subquery NetsIntelligent Systems and Networks10.1007/978-981-16-2094-2_24(189-196)Online publication date: 13-May-2021
https://doi.org/10.1007/978-981-16-2094-2_24
Cao SNguyen L(2017)Query–subquery nets for Horn knowledge bases in first-order logicJournal of Information and Telecommunication10.1080/24751839.2017.12956641:1(79-99)Online publication date: 7-Mar-2017
https://doi.org/10.1080/24751839.2017.1295664
Cao SNguyen LNguyen N(2017)Extending Query-Subquery Nets for Deductive Databases under the Well-Founded SemanticsCybernetics and Systems10.1080/01969722.2016.127677748:3(249-266)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1080/01969722.2016.1276777
Show More Cited By

Index Terms

A Generalized QSQR Evaluation Method for Horn Knowledge Bases
1. Information systems
  1. Data management systems
    1. Database management system engines
      1. Database query processing
      2. Triggers and rules
2. Theory of computation
  1. Theory and algorithms for application domains
    1. Database theory
      1. Database query processing and optimization (theory)

Recommendations

Horn Knowledge Bases in Regular Description Logics with PTIME Data Complexity

Developing a good formalism and an efficient decision procedure for the instance checking problem is desirable for practical application of description logics. The data complexity of the instance checking problem is coNP-complete even for Horn knowledge ...
The possibilistic horn non-clausal knowledge bases
Abstract
Non-clausal deduction in classical logic is one of the oldest areas in artificial intelligence. It first appeared in the sixties and consequently a large body of research has been devoted to it. Within the last decades, computing with ...
Higher Order Horn Clauses

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Computational Logic

ACM Transactions on Computational Logic Volume 13, Issue 4

October 2012

212 pages

ISSN:1529-3785

EISSN:1557-945X

DOI:10.1145/2362355

Issue’s Table of Contents

Copyright © 2012 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 October 2012

Accepted: 01 December 2011

Revised: 01 September 2011

Received: 01 May 2010

Published in TOCL Volume 13, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Funding Sources

Narodowe Centrum Badan i Rozwoju

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

11
Total Citations
View Citations
130
Total Downloads

Downloads (Last 12 months)5
Downloads (Last 6 weeks)1

Reflects downloads up to 13 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Cao SPhong PAnh L(2021)Integrating Multi-threading into Query-Subquery NetsIntelligent Systems and Networks10.1007/978-981-16-2094-2_24(189-196)Online publication date: 13-May-2021
https://doi.org/10.1007/978-981-16-2094-2_24
Cao SNguyen L(2017)Query–subquery nets for Horn knowledge bases in first-order logicJournal of Information and Telecommunication10.1080/24751839.2017.12956641:1(79-99)Online publication date: 7-Mar-2017
https://doi.org/10.1080/24751839.2017.1295664
Cao SNguyen LNguyen N(2017)Extending Query-Subquery Nets for Deductive Databases under the Well-Founded SemanticsCybernetics and Systems10.1080/01969722.2016.127677748:3(249-266)Online publication date: 1-Apr-2017
https://dl.acm.org/doi/10.1080/01969722.2016.1276777
Urbani JJacobs C(2016)RDF-SQ: Mixing Parallel and Sequential Computation for Top-Down OWL RL InferenceGraph Structures for Knowledge Representation and Reasoning10.1007/978-3-319-28702-7_8(125-138)Online publication date: 3-Jan-2016
https://doi.org/10.1007/978-3-319-28702-7_8
Cao S(2015)Query-Subquery Nets with Stratified NegationAdvanced Computational Methods for Knowledge Engineering10.1007/978-3-319-17996-4_32(355-366)Online publication date: 2015
https://doi.org/10.1007/978-3-319-17996-4_32
Cao S(2015)On the Efficiency of Query-Subquery Nets with Right/Tail-Recursion Elimination in Evaluating Queries to Horn Knowledge BasesAdvanced Computational Methods for Knowledge Engineering10.1007/978-3-319-17996-4_22(243-254)Online publication date: 2015
https://doi.org/10.1007/978-3-319-17996-4_22
Cao SNguyen L(2015)An Empirical Approach to Query-Subquery Nets with Tail-Recursion EliminationNew Trends in Database and Information Systems II10.1007/978-3-319-10518-5_9(109-120)Online publication date: 2015
https://doi.org/10.1007/978-3-319-10518-5_9
Cao SNguyen L(2014)An Improved Depth-First Control Strategy for Query-Subquery Nets in Evaluating Queries to Horn Knowledge BasesAdvanced Computational Methods for Knowledge Engineering10.1007/978-3-319-06569-4_21(281-295)Online publication date: 2014
https://doi.org/10.1007/978-3-319-06569-4_21
Cao SQuyet TThanh BVan TBui MHong S(2013)On the efficiency of query-subquery netsProceedings of the 4th Symposium on Information and Communication Technology10.1145/2542050.2542085(148-157)Online publication date: 5-Dec-2013
https://dl.acm.org/doi/10.1145/2542050.2542085
Cao SNguyen LSzałas A(2013)The Web Ontology Rule Language OWL 2 RL+ and Its ExtensionsTransactions on Computational Intelligence XIII - Volume 834210.1007/978-3-642-54455-2_7(152-175)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1007/978-3-642-54455-2_7
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents