Hostname: page-component-cd9895bd7-mkpzs Total loading time: 0 Render date: 2024-12-18T13:01:54.639Z Has data issue: false hasContentIssue false
  • English
  • Français

A declarative extension of horn clauses, and its significance for datalog and its applications

Published online by Cambridge University Press:  25 September 2013

MIRJANA MAZURAN ,
EDOARDO SERRA  and
CARLO ZANIOLO
MIRJANA MAZURAN
Affiliation:
Politecnico di Milano DEIB
EDOARDO SERRA
Affiliation:
University of Maryland
CARLO ZANIOLO
Affiliation:
University of California, Los Angeles
Get access Rights & Permissions [Opens in a new window]

Abstract

FS-rules provide a powerful monotonic extension for Horn clauses that supports monotonic aggregates in recursion by reasoning on the multiplicity of occurrences satisfying existential goals. The least fixpoint semantics, and its equivalent least model semantics, hold for logic programs with FS-rules; moreover, generalized notions of stratification and stable models are easily derived when negated goals are allowed. Finally, the generalization of techniques such as seminaive fixpoint and magic sets, make possible the efficient implementation of DatalogFS, i.e., Datalog with rules with Frequency Support (FS-rules) and stratified negation. A large number of applications that could not be supported efficiently, or could not be expressed at all in stratified Datalog can now be easily expressed and efficiently supported in DatalogFS and a powerful DatalogFS system is now being developed at UCLA.

Keywords

horn clausesdatalogmonotonic aggregatesstable models
Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 13 , Special Issue 4-5: 29th International Conference on Logic Programming , July 2013 , pp. 609 - 623
Copyright
Copyright © 2013 [MIRJANA MAZURAN, EDOARDO SERRA and CARLO ZANIOLO] 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Abiteboul, S., Bienvenu, M., Galland, A. and Antoine, E. 2011. A rule-based language for web data management. In PODS, 293–304.Google Scholar
Afrati, F. N., Borkar, V. R., Carey, M. J., Polyzotis, N. and Ullman, J. D. 2011. Map-reduce extensions and recursive queries. In EDBT, 1–8.Google Scholar
Agrawal, R. and Srikant, R. 1994. Fast algorithms for mining association rules in large databases. In VLDB, 487–499.Google Scholar
Barceló, P. and Pichler, R., Eds. 2012. Datalog in Academia and Industry–2nd International Workshop, Datalog 2.0. LNCS, vol. 7494. Springer.10.1007/978-3-642-32925-8CrossRefGoogle Scholar
Chomicki, J. and Imielinski, T. 1988. Temporal deductive databases and infinite objects. In PODS, 61–73.Google Scholar
Gelfond, M. and Lifschitz, V. 1988. The stable model semantics for logic programming. MIT Press, 1070–1080.Google Scholar
Gottlob, G., Orsi, G. and Pieris, A. 2011. Ontological queries: Rewriting and optimization. In ICDE, 2–13.10.1109/ICDE.2011.5767965CrossRefGoogle Scholar
Greco, S. and Zaniolo, C. 2001. Greedy algorithms in datalog. TPLP 1, 4, 381–407.Google Scholar
Hellerstein, J. M. 2010. Datalog redux: Experience and conjecture. In PODS, 1–2.CrossRefGoogle Scholar
Kolaitis, P. G. 1991. The expressive power of stratified logic programs. Inf. Comp. 90, 50–66.CrossRefGoogle Scholar
Lloyd, J. W. 1987. Foundations of Logic Programming, 2nd ed. Springer.CrossRefGoogle Scholar
Mazuran, M., Serra, E. and Zaniolo, C. 2012. Extending the power of datalog recursion. In The VLDB Journal. Springer-Verlag, 1–23.Google Scholar
Mazuran, M., Serra, E. and Zaniolo, C. July 2013. A Declarative Extension of Horn Clauses, and its Significance for Datalog and its Applications. Tech. Rep., UCLA, Computer Science Department, Technical Report No. 130011.CrossRefGoogle Scholar
Mumick, I. S., Pirahesh, H. and Ramakrishnan, R. 1990. The magic of duplicates and aggregates. In VLDB, 264–277.Google Scholar
Mumick, I. S. and Shmueli, O. 1995. How expressive is stratified aggregation? Annals of Mathematics and Artificial Intelligence 15, 407–435.CrossRefGoogle Scholar
Ross, K. A. and Sagiv, Y. 1997. Monotonic aggregation in deductive database. Journal of Computer and System Sciences 54, 1, 79–97.10.1006/jcss.1997.1453CrossRefGoogle Scholar
Shkapsky, A., Zeng, K. and Zaniolo, C. 2013. Graph queries in a next-generation datalog system. In VLDB 2013, Demo Track, 100–104.Google Scholar
van Emden, M. H. and Kowalski, R. A. 1976. The semantics of predicate logic as a programming language. Journal of the ACM 23, 4, 733–742.10.1145/321978.321991CrossRefGoogle Scholar
Zaniolo, C. 2011. The logic of query languages for data streams. In Logic and Databases 2011. EDBT 2011 Workshops, 1–2.Google Scholar
Zaniolo, C., Ceri, S., Faloutsos, C., Snodgrass, R. T., Subrahmanian, V. S. and Zicari, R. 1997. Advanced Database Systems. Morgan Kaufmann.Google Scholar
Supplementary material: PDF

Mazuaran supplementary material

Appendix

Download Mazuaran supplementary material(PDF)
PDF 391.7 KB