On the Convergence Rate of Linear Datalogo over Stable Semirings
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2023
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866909676168282112 |
|---|---|
| author | Im, Sungjin Moseley, Benjamin Ngo, Hung Pruhs, Kirk |
| author_facet | Im, Sungjin Moseley, Benjamin Ngo, Hung Pruhs, Kirk |
| contents | Datalogo is an extension of Datalog, where instead of a program being a collection of union of conjunctive queries over the standard Boolean semiring, a program may now be a collection of sum-product queries over an arbitrary commutative partially ordered pre-semiring. Datalogo is more powerful than Datalog in that its additional algebraic structure alows for supporting recursion with aggregation. At the same time, Datalogo retains the syntactic and semantic simplicity of Datalog: Datalogo has declarative least fixpoint semantics. The least fixpoint can be found via the naïve evaluation algorithm that repeatedly applies the immediate consequence operator until no further change is possible.
It was shown in~\cite{Khamis0PSW22} that, when the underlying semiring is $p$-stable, then the naïve evaluation of any Datalogo program over the semiring converges in a finite number of steps. However, the upper bounds on the rate of convergence were exponential in the number $n$ of ground IDB atoms.
This paper establishes polynomial upper bounds on the convergence rate of the naïve algorithm on {\bf linear} Datalogo programs, which is quite common in practice. In particular, the main result of this paper is that the convergence rate of linear Datalogo programs under any $p$-stable semiring is $O(pn^3)$. Next, we study the convergence rate in terms of the number of elements in the semiring for linear Datalogo programs. When $L$ is the number of elements, we show that the convergence rate is bounded by $O(pn \log L)$. This significantly improves the convergence rate for small $L$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2311_17664 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | On the Convergence Rate of Linear Datalogo over Stable Semirings Im, Sungjin Moseley, Benjamin Ngo, Hung Pruhs, Kirk Databases Datalogo is an extension of Datalog, where instead of a program being a collection of union of conjunctive queries over the standard Boolean semiring, a program may now be a collection of sum-product queries over an arbitrary commutative partially ordered pre-semiring. Datalogo is more powerful than Datalog in that its additional algebraic structure alows for supporting recursion with aggregation. At the same time, Datalogo retains the syntactic and semantic simplicity of Datalog: Datalogo has declarative least fixpoint semantics. The least fixpoint can be found via the naïve evaluation algorithm that repeatedly applies the immediate consequence operator until no further change is possible. It was shown in~\cite{Khamis0PSW22} that, when the underlying semiring is $p$-stable, then the naïve evaluation of any Datalogo program over the semiring converges in a finite number of steps. However, the upper bounds on the rate of convergence were exponential in the number $n$ of ground IDB atoms. This paper establishes polynomial upper bounds on the convergence rate of the naïve algorithm on {\bf linear} Datalogo programs, which is quite common in practice. In particular, the main result of this paper is that the convergence rate of linear Datalogo programs under any $p$-stable semiring is $O(pn^3)$. Next, we study the convergence rate in terms of the number of elements in the semiring for linear Datalogo programs. When $L$ is the number of elements, we show that the convergence rate is bounded by $O(pn \log L)$. This significantly improves the convergence rate for small $L$. |
| title | On the Convergence Rate of Linear Datalogo over Stable Semirings |
| topic | Databases |
| url | https://arxiv.org/abs/2311.17664 |