Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
The VLDB Journal
Erschienen in: The VLDB Journal 4/2013

01.08.2013 | Regular Paper

Extending the power of datalog recursion

verfasst von: Mirjana Mazuran, Edoardo Serra, Carlo Zaniolo

Erschienen in: The VLDB Journal | Ausgabe 4/2013

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Supporting aggregates in recursive logic rules represents a very important problem for Datalog. To solve this problem, we propose a simple extension, called Datalog\(^{FS}\,\)(Datalog extended with frequency support goals), that supports queries and reasoning about the number of distinct variable assignments satisfying given goals, or conjunctions of goals, in rules. This monotonic extension greatly enhances the power of Datalog, while preserving (i) its declarative semantics and  (ii) its amenability to efficient implementation via differential fixpoint and other optimization techniques presented in the paper. Thus, Datalog\(^{FS}\,\)enables the efficient formulation of queries that could not be expressed efficiently or could not be expressed at all in Datalog with stratified negation and aggregates. In fact, using a generalized notion of multiplicity called frequency, we show that diffusion models and page rank computations can be easily expressed and efficiently implemented using Datalog\(^{FS}\,\).
Vorheriger Artikel Recommending XML physical designs for XML databases
Nächster Artikel QoS-aware optimization of sensor network queries

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
A good example of this problem due to Ross and Sagiv [8] is given at the end of Sect. 2—see Example 3.
 
2
Naturally, by “least fixpoint” of a program, we mean “least fixpoint of its immediate consequence operator” [9].
 
3
This example illustrates that these problems are caused by the non-monontonic nature of count. In fact, the following program where count is replaced by our running-FS operator has as unique minimal model \(\{ \mathtt p(a),q(a),p(b),q(b) \}\):
$$\begin{aligned}&\begin{array}{ll} \mathtt{\quad p(b). }&\mathtt{q(b). } \\ \mathtt{\quad p(a) } \leftarrow&\mathtt{1\!:\![q(X)]. } \\ \mathtt{\quad q(a) } \leftarrow&\mathtt{1\!:\![p(X)]. } \\ \end{array} \end{aligned}$$
 
4
Observe that while N+1 can be viewed as a call to an arithmetic functions, we can stay in the framework of pure logic programs and view it as the postfix functor +1 applied to N, as in Datalog\(_{1S}\) [16]; this also supports comparison between positive integers without assuming a totally ordered universe.
 
5
This discussion suggests that the formal semantics of Datalog\(^{FS}\,\)can also be defined without using lists–that is, in terms of Herbrand bases and interpretations that only use the constants and predicates in the programs and no function symbols. This interesting topic is left for future research.
 
6
If this information was stored in SQL tables, then the head of the rule would be updated using the following information:
$$\begin{aligned} \mathtt{select~cassb.Part,~sum(cassb.Qty*cbasic.K) }\\ \mathtt{\quad \quad from\,cassb,\,cbasic\,where\,cassb.Sub=cbasic.Sub }\\ \mathtt{\quad \quad group\,by\,cbasic.Sub } \end{aligned}$$
.
 
7
Determining local and global variables is already part of the binding passing analysis performed by current Datalog compilers [24].
 
8
A boolean function B(T) is monotonic w.r.t. the integer values T whenever \(B(T)\) evaluating to true implies that \(B(T^{\prime })\) is true for every \(T^{\prime }> T\).
 
9
For instance, this function can be used to express the fact that an agent who sees, say, all his 89 partners switching to B experiences a much stronger push than another twitter user who sees his only partner moving to B (although percentage-wise the two situations are the same).
 
10
A somewhat more efficient computation could be achieved via ordered lists. This approach however is undesirable inasmuch as it requires a totally ordered universe and compromises genericity [18].
 
Literatur
1.
Hellerstein, J.M.: Datalog redux: experience and conjecture. In: PODS, pp. 1–2 (2010)
2.
de Moor, O., Gottlob, G., Furche, T., Sellers, A.J.: Datalog Reloaded-First International Workshop, Datalog 2010, Oxford, UK, 16–19 March 2010, Springer 2011
3.
Huang, S.S., Green, T.J., Loo, B.T.: Datalog and emerging applications: an interactive tutorial. In: SIGMOD Conference, pp. 1213–1216 (2011)
4.
Loo, B.T., Condie, T., Garofalakis, M.N., Gay, D.E., Hellerstein, J.M., Maniatis, P., Ramakrishnan, R., Roscoe, T., Stoica, I.: Declarative networking. Commun. ACM 52(11), 87–95 (2009)CrossRef
5.
Gottlob, G., Orsi, G., Pieris, A.: Ontological queries: rewriting and optimization. In: ICDE, pp. 2–13 (2011)
6.
Afrati, F.N., Borkar, V.R., Carey, M.J., Polyzotis, N., Ullman, J.D.: Map-reduce extensions and recursive queries. In EDBT, pp. 1–8 (2011)
7.
Zaniolo, C.: Logical foundations of continuous query languages for data streams. Datalog 2012. pp. 177–189 (2012)
8.
9.
10.
Van Gelder, A.: Foundations of aggregation in deductive databases. In: DOOD, pp. 13–34 (1993)
11.
Kanellakis, P.C.: Elements of Relational Database Theory. Technical report, Providence, RI (1989)
12.
Ullman, J.D.: Principles of Database and Knowledge-Base Systems. Computer Science Press, Inc., New York (1988)
13.
Gelfond, M., Lifschitz, V.: The Stable Model Semantics for Logic Programming. MIT Press, London, pp. 1070–1080 (1988)
14.
Van Gelder, Allen, Ross, K.A., Schlipf, J.S.: The well-founded semantics for general logic programs. J. ACM 38(3), 619–649 (1991)MathSciNetCrossRef
15.
Zaniolo, C., Faloutsos, S.C.S.C., Snodgrass, R.T., Subrahmanian, V.S., Zicari, R.: Advanced Database Systems. Morgan Kaufmann (1997)
16.
Chomicki, J., Imielinski, T.: Temporal deductive databases and infinite objects. In: PODS, pp. 61–73 (1988)
17.
Hirsch, J.E.: An index to quantify an individual’s scientific research output that takes into account the effect of multiple coauthorship. Scientometrics 85(3), 741–754 (2010)CrossRef
18.
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)MATH
19.
Mumick, I.S., Hamid, Pirahesh, H., Ramakrishnan, R.: The magic of duplicates and aggregates, In: VLDB, pp. 264–277 (1990)
20.
21.
Dahlhaus, E.: Skolem Normal Forms Concerning the Least Fixpoint. Springer, London (1987)
22.
23.
Mazuran, M., Serra, E., Zaniolo, C.: Graph Languages in \(\text{ Datalog}^{FS}\): From Abstract Semantics to Efficient Implementation. Technical report, UCLA (2011)
24.
Arni, F., Ong, K.L., Tsur, S., Wang, H., Zaniolo, C.: The deductive database system ldl++. TPLP 3(1), 61–94 (2003)MathSciNetMATH
25.
Zaniolo, C., Ceri, S., Faloutsos, C., Snodgrass, R.T., Subrahmanian, V.S., Zicari, R.: Advanced Database Systems. Morgan Kaufmann, Los Altos (1997)
26.
Angles, R., Gutiérrez, C.: Survey of graph database models. ACM Comput. Surv. 40(1) (2008)
27.
Cruz, I.F., Mendelzon, A.O., Wood P.T. A graphical query language supporting recursion. In: SIGMOD Conference, pp. 323–330 (1987)
28.
Consens, M.P., Mendelzon, A.O. : Graphlog: a visual formalism for real life recursion. In: PODS, pp. 404–416 (1990)
29.
Paredaens, J., Peelman, P., Tanca, L.: G-log: a graph-based query language. IEEE Trans. Knowl. Data Eng. 7(3), 436–453 (1995)CrossRef
30.
Jackson, M.O., Yariv, L.: Diffusion on Social Networks. Economie Publique (2005)
31.
Shakarian, P., Subrahmanian, V.S., Sapino, M.L.: Using generalized annotated programs to solve social network optimization problems. In: ICLP (Technical Communications), pp. 182–191 (2010)
32.
Ramakrishnan, R., Gehrke, J.: Database Management Systems. WCB/McGraw-Hill, New York (1998)
33.
Ullman, J.D., Widom, J.: A First Course in Database Systems. Prentice-Hall, Prentice (1997)
34.
Zaniolo, C., Arni, N., Ong, K.: Negation and aggregates in recursive rules: the ldl++ approach. In: DOOD, pp. 204–221 (1993)
35.
Lausen, G., Ludäscher, B., May, W.: On active deductive databases: the statelog approach. In: Transactions and Change in Logic Databases, pp. 69–106 (1998)
36.
Ganguly, S., Greco, S., Zaniolo, C.: Minimum and maximum predicates in logic programming. In: PODS, pp. 154–163 (1991)
37.
Giannotti, F., Pedreschi, D., Saccà, D., Zaniolo, C.: Non-determinism in deductive databases. In: DOOD, pp. 129–146 (1991)
38.
Metadaten
Titel
Extending the power of datalog recursion
verfasst von
Mirjana Mazuran
Edoardo Serra
Carlo Zaniolo
Publikationsdatum
01.08.2013
Verlag
Springer Berlin Heidelberg
Erschienen in
The VLDB Journal / Ausgabe 4/2013
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-012-0299-1

Weitere Artikel der Ausgabe 4/2013

The VLDB Journal 4/2013 Zur Ausgabe

Regular Paper

Outsourcing shortest distance computing with privacy protection

Regular Paper

Recommending XML physical designs for XML databases

Regular Paper

Modeling the execution semantics of stream processing engines with SECRET

Regular Paper

Top-k queries over web applications

Regular Paper

Super-EGO: fast multi-dimensional similarity join

Regular Paper

QoS-aware optimization of sensor network queries