按年被提到
20162018 · 3 次2026
系统、数据库与网络›数据库与向量检索·arXiv:1608.00139 · cs.AI

A Linear Algebraic Approach to Datalog Evaluation

Taisuke Sato · 2016
开始阅读 ↗PDFalphaXiv 讨论
被提及 · 2 人首次 2018-12-02 · 最近 2024-01-23
2不同的人
3活跃月份
5讨论串
22被引(OpenAlex)
arXiv 摘要(候选层不写导读)

In this paper, we propose a fundamentally new approach to Datalog evaluation. Given a linear Datalog program DB written using N constants and binary predicates, we first translate if-and-only-if completions of clauses in DB into a set Eq(DB) of matrix equations with a non-linear operation where relations in M_DB, the least Herbrand model of DB, are encoded as adjacency matrices. We then translate Eq(DB) into another, but purely linear matrix equations tilde_Eq(DB). It is proved that the least solution of tilde_Eq(DB) in the sense of matrix ordering is converted to the least solution of Eq(DB) and the latter gives M_DB as a set of adjacency matrices. Hence computing the least solution of tilde_Eq(DB) is equivalent to computing M_DB specified by DB. For a class of tail recursive programs and for some other types of programs, our approach achieves O(N^3) time complexity irrespective of the number of variables in a clause since only matrix operations costing O(N^3) or less are used. We conducted two experiments that compute the least Herbrand models of linear Datalog programs. The first experiment computes transitive closure of artificial data and real network data taken from the Koblenz Network Collection. The second one compared the proposed approach with the state-of-the-art symbolic systems including two Prolog systems and two ASP systems, in terms of computation time for a transitive closure program and the same generation program. In the experiment, it is observed that our linear algebraic approach runs 10^1 ~ 10^4 times faster than the symbolic systems when data is not sparse. To appear in Theory and Practice of Logic Programming (TPLP).

候选层:至少 2 个不同的人、在 2 个不同月份提到过,还没到主书架的 3 人 3 个月。没有做立场标注,所以只写“被提及”。

HN 书评

推荐在前,同类按时间 · 每篇最多保留 20 条,统计用全部提及
评论espeed · 2018-12

“There's a new Datalog [1] implementation written in the language of linear algebra (similar in nature to the ideas behind GraphBLAS [2] "graph algorithms in the language of linear algebra"). Evidently the linear-algebra approach works well for Datalog too -- the paper below shows it's the fastest Datalog implementation to date, several orders faster than …”

Racklog: Prolog Style Logic Programming [pdf]原评论 ↗
评论espeed · 2018-12

“And it's not just graphs...as referenced in the linked comments above, there are now linear algebra models that encode Datalog and/or the entire typed-lambda calculus as linear algebra matrix operations (and as shown in the Datalog paper [1], the Datalog linear algebra implementation is the fastest Datalog implementation to date). But MIT and Sandia Labs…”

Ask HN: What was your experience using a graph database?原评论 ↗
评论espeed · 2019-04

“Hi Michel - You're working on a GraphBLAS Postgres implementation [0] -- here's an open question I've been pondering... [0] Postgres GraphBLAS https://github.com/michelp/pggraphblas Now that we have SOTA linear algebra models for graphs [1], logic [2] and the lambda calculus [3] that are being optimized for vectorized parallel compute on modern CPU/GPU/…”

What is GraphBLAS?原评论 ↗
评论nisa · 2024-01

“Wow 6 volumes. Added to the list. German is also fine if there is literature and I'm trying to work on my math understanding. I also found some interesting papers that solve i.e. datalog using matrices with algebraic methods. https://arxiv.org/abs/1608.00139 Guess I'll start slowly and see how far I come. Thanks!”

Differences Between miniKanren and Prolog原评论 ↗
被提交为 story · 1 次