Comments (8)
Hi @brurucy, the index-sharing data structure provider has not been added to the repo yet. I'll try and rectify that whenever I get a chance.
In the meantime, you can check out the docker image https://hub.docker.com/r/arashsahebolamri/byods-artifact
, which contains this code under /src/exps/ind-share
from ascent.
Perusing over byods was my main entertainment for a 13 hours flight that just landed. I think I get it now, and the index optimisation code is very portable. I'm snatching it.
Thanks @s-arash and @kmicinski.
Could you also tell me where does ascent the compiler compute the indexes? I can always guess it correctly, but the logic seems to be buried beneath so much parsing that I'm struggling to find the seemingly simple code that does that.
from ascent.
This should be in the ind_rel provider of the byods
branch. I am busy with some end-of-semester business now, but I will try to get a concrete pointer into the code by the end of the week. Arash is looking at merging the byods
branch into the main one proper--but I think that's still up in the air as to timeline.
from ascent.
Thanks Kristopher! Looking forward to it.
from ascent.
@s-arash could you also describe how do you go from Datalog program -> Indexes?
e.g. if you have the classic ancestor rule:
r1 - tc(?x, ?y) <- e(?x, ?y)
r2 - tc(?x, ?z) <- e(?x, ?y), tc(?y, ?z)
Are your indexes then ((key), (value)):
e [ ((1), (0)), ((0, 1), ) ]
tc [ ((0), (1)) ]
And plan:
r1 - Project identity
r2 - Project (e_((1), (0)) |><| tc_((0), (1)))
from ascent.
Hi Bruno,
Section 5.5 of this paper describes the key points of the implementation: https://kmicinski.com/assets/byods.pdf. There are a few differences compared to what Souffle is doing (e.g., using linked hashmaps rather than btrees/tries), but algorithmically it should follow https://www.vldb.org/pvldb/vol12/p141-subotic.pdf.
from ascent.
@brurucy, to add more context to Kris's answer, the Ascent compiler itself selects a set of logical indexes for each relation. In your example, it is as you described (i.e., for e
the indexes are [{}, {1}, {0, 1}]
). It is up to the data structure provider (index-sharing for example) to come up with physical indexes for this set. As Kris said, that process is described in the BYODS paper.
from ascent.
Could you also tell me where does ascent the compiler compute the indexes?
Look for it in ascent_hir.rs
(no parsing there). Specifically, compile_rule_to_ir_rule()
should be a good starting point.
from ascent.
Related Issues (20)
- Private type `…` in public interface (error E0446) HOT 3
- Compiling ascent at runtime HOT 2
- New release with parallel Ascent HOT 2
- ascent_macro: Upgrade syn to >= v2 HOT 1
- ascent_macro: Fix minimal versions (by upgrading syn to v1.0.109, itertools to v0.12) HOT 5
- Non-final lattice results visible to downstream rules HOT 6
- Ascent should omit trait bounds on the generated program's type declaration HOT 5
- Project's current formatting makes it hard to contribute non-trivial changes HOT 4
- Lattice constrains not enforced on input in ascent_run HOT 2
- Incorrect result? HOT 2
- Calling run() multiple times HOT 6
- Please add a license HOT 1
- Macro limitations HOT 1
- WASM compatibility: `std::time` HOT 3
- Unsoundness in `util::update` HOT 1
- Arash's current email address? HOT 1
- Composition Feature
- ascent = "0.2" broke? HOT 4
- Comparison to Crepe? HOT 4
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.
from ascent.