On Tue, May 17, 2016 at 7:31 PM, Yusheng Wang <yshw...@vmware.com> wrote:
> > From 72e885fb895d740dc62d5ea42ced764cba527b2f Mon Sep 17 00:00:00 2001 > From: Yusheng Wang <yshw...@vmware.com> > Date: Tue, 17 May 2016 07:58:35 +0800 > Subject: [PATCH] OVN: datalog man page > > Signed-off-by: Yusheng Wang <yshw...@vmware.com> > > --- > Hi Yusheng, After listening to the podcast that you and Teemu did with Ben [1], I spent a little time educating myself on datalog, so I can better appreciate the work you did in this doc. The wiki page on datalog [2] is fine but not very rich. The datalog pages returned by google [3] were, like Teemu said in the blog, pretty grandious. With that, I had a little hard time finding something that was inline with NiciraLog (nlog). If you happen to know of any public online doc on that realm, it would be nice to make a reference to it in the commit message of this patchset. Not all that relevant, but I found pyDatalog [4] to be useful in wrapping my head of how this technology is used. Any tools like that, or maybe a pointer to "Test_interactive" will be a good asset to help folks getting their feet wet. More comments/suggestions below. I goes w/out saying but, please do ignore anything in my feedback that is not useful. [1]: http://ovsorbit.benpfaff.org/#e5 [2]: https://en.wikipedia.org/wiki/Datalog [3]: http://bfy.tw/65yd [4]: https://sites.google.com/site/pydatalog/ <snip> > diff --git a/ovn/lib/ovn-datalog.7.xml b/ovn/lib/ovn-datalog.7.xml > new file mode 100644 > index 0000000..677ca0b > --- /dev/null > +++ b/ovn/lib/ovn-datalog.7.xml > @@ -0,0 +1,491 @@ > +<?xml version="1.0" encoding="utf-8"?> > +<manpage program="ovn-datalog" section="7" title="ovn-datalog"> > + > +<h1>Name</h1> > +<p>ovn-datalog -- Open Virtual Network Datalog</p> > + > +<h1>Synoposis</h1> > +<pre fixed="yes"> > +#include "datalog.h" > +</pre> > + > +<pre fixed="yes"> > +void* datalog_init(const char* <var>rules</var>, void* > <var>ext_func</var>); > +void datalog_free(void* <var>d</var>); > +void datalog_opr(void* <var>d</var>, bool <var>query</var>); > +</pre> > + > +<pre fixed="yes"> > +bool datalog_put_table(void* <var>d</var>, bool <var>is_delete</var>, > const char* <var>name</var>); > +void datalog_put_field(void* <var>d</var>, void* <var>value</var>, > int32_t <var>size</var>); > +</pre> > + > +<pre fixed="yes"> > +bool datalog_get_table(void* <var>d</var>, bool* <var>is_delete</var>, > const char** <var>name</var>, > + int32_t* <var>n_tuples</var>, int32_t* <var>n_fields</var>); > +bool datalog_get_field(void* <var>d</var>, void** <var>value</var>, > int32_t* <var>size</var>); > +</pre> > + > +<h1>Description</h1> > + > +<p> > +The datalog_init() initializes an instance of datalog engine. > <dfn>rules</dfn> > + indicates the datalog program. <dfn>ext_func</dfn>, which is optional, > will > +specify the external function of the engine. > +</p> > + > +<p> > +Each instance of engine is defined by its program, its state, and > temporary > +data for input and output tables. The state consists of table content of > all > +input tables and intermediate tables. > nitpick: Remove redundant 'tables', so it reads like this: The state consists of table content of all input and intermediate tables. > +</p> > + > +<p> > +Datalog engine works in pipeline manner. Input table is constructed by > first > +calling the function datalog_put_table(), then followed by a serial of > function > +calls of datalog_put_field(). Data are streamed field by field, then > tuple by > +tuple. <dfn>name</dfn> indicates the name of table. <dfn>is_remove</dfn> > +indicates whether the tuples constructed by subsequent calls of > +datalog_put_field() are for addition or for deletion. > +</p> > + > <snip> > +<h1>NOTES</h1> > +<p> > +The following sections define the syntax, semantics, and run time behavior > +of the OVN datalog program. > +</p> > + > +<h2>SYNTAX OF OVN DATALOG</h2> > + > +<pre fixed="yes"> > +<token> ::= [_a-zA-Z][_a-zA-Z0-9]* > +<literal> ::= '[^']*' > +</pre> > + > +<p> > +Literals are enclosed with single quote and can extend to multiple lines. > +Comments start with pound character and end in line end. Blank characters > are > +ignored. Tokens are case sensitive. > +</p> > + > +<pre fixed="yes"> > +<table name> ::= <token> > +<field name> ::= <token> > + > +<field> ::= <field name> | <literal> | "-" > +<field list> ::= <field> | <field list> "," > <field> > + > +<table> ::= <table name> "(" <field list> ")" > +<table list> ::= <table> | <table list> > <table> > + > +<join table> ::= <table> ":" <table list> > +<union table> ::= <table> ">" <table list> > + > +<rule> ::= <join table> | <union table> > +<rule list> ::= <rule> | <rule list> ";" > <rule> > +<program> ::= <rule list> "." > +</pre> > + > +<p> > +Example: > +</p> > + > +<pre> > + Aa2(a) : a1(a, 'aa', -); > + A3(a, 'bb') : Aa2(a) a1(a, -, b) Aa2(b); > + A4(x, y) > Aa3(x, y) a2(y, x). > +</pre> > + > +<p> > +Each tuple is an ordered set of field values. Field name is only used for > A tuple is an ordered set of field values. Field list is only for > +specifying matching criteria. All tuples from a table have the same number > +of fields. The field "-" is called 'ignored' field. > +</p> > + > +<p> > +For each rule, the content of left side table, e.g., Aa2 in the above > example, > +is determined by the content of all right side tables, e.g., a1 in the > above > +example. Table could appear in left side at most once. > +</p> > + > +<p> > +When a table only appears in right side, it is called input table. When a > When a table only appears in the right side of a given rule, it is called input table. When a > +table only appears in left side, it is called output table. When a table > +appears in both left side and right side, it is called intermediate table. > +</p> > + > <snip> > +<p> > +Join. The content of left side table is the 'join' of all right side > +tables. Joining produces its result in 4 steps illustrated below. > For folks who do not know what a join operation is about, maybe refer them to a link like: https://en.wikipedia.org/wiki/Join_%28SQL%29 > +</p> > +</li> > +</ul> > + > +<pre fixed="yes"> > + Step 1 > +Example: u(a,b) v(x,y) u(a,b) v(x,y) > Instead of v(x,y) it may be easier to understand if it was shown as v(b,c) ? Example of a join operation: u(a,b) v(b,c) u(a,b) v(b,c) > + +---+---+ +---+---+ +---+---+---+---+ > +C(a,c): | 1 | 2 | | 2 | 3 | | 1 | 2 | 2 | 3 | > + u(a,b) +---+---+ +---+---+ +---+---+---+---+ > + v(b,c). | 1 | 3 | | 2 | 4 | => | 1 | 2 | 2 | 4 | > + +---+---+ +---+---+ +---+---+---+---+ > + | 3 | 3 | | 1 | 2 | 3 | 3 | > + +---+---+ +---+---+---+---+ > + | 1 | 3 | 2 | 3 | > + Step 4 Step 3 Step 2 +---+---+---+---+ > + C(a,c) u(a) v(y) u(a,b) v(x,y) | 1 | 3 | 2 | 4 | > ++---+---+ +---+---+ +---+---+---+---+ +---+---+---+---+ > +| 1 | 3 | | 1 | 3 | | 1 | 2 | 2 | 3 | | 1 | 3 | 3 | 3 | > ++---+---+ +---+---+ +---+---+---+---+ +---+---+---+---+ > +| 1 | 4 | <= | 1 | 4 | <= | 1 | 2 | 2 | 4 | <= u.b == v.x > ++---+---+ +---+---+ +---+---+---+---+ matching criteria > + | 1 | 3 | | 1 | 3 | 3 | 3 | > + +---+---+ +---+---+---+---+ > +</pre> > + > +<pre> > +Step 1: Perform full join operation over all right side tables. > +Step 2: Filter the result tuple set based on matching criteria. > +Step 3: Drop the fields that do no appear in left side table. > +Step 4: Merge duplicate tuples and reorder fields. > +</pre> > + > +<p> > +When literal appears in right side table, it indicates to only include > +those tuples whose specified field matches the literal. When it appears > +in left side table, that value is always provisioned on the specified > +field. > +</p> > + > +<p> > +'Ignored' field indicates that the specified field is neither used > +in matching criteria, nor appearing in the left side table. > +'Ignored' field never appears in left side table. > +</p> > It would be nice to have an example of a rule with join that uses 'Ignored'... > + > +<p> > +The engine works in incremental computation manner, i.e., the engine only > +accepts incremental change for a set of input tables, and it will > +compute the incremental change of output tables. The change is in form of > +adding tuples or deleting tuples. > +</p> > + > +<p> > +Example: assume initially, > +</p> > +<pre> > + u(a,b) contains { (1, 2), (1, 3) }, > + v(x,y) contains { (2, 3), (1, 3) }; then > + C(a,c) contains { (1, 3) } > +</pre> > +<p> > +If { (2, 4) } is added to v(x,y), the engine will output { (1, 4) }, > making > +the current state of C(a,c) as { (1, 3), (1, 4) }. > +</p> > It would be nice to have another example where { (2, 4) } is added to v(b,c) and the increment computation is expanded as in the example above. > + > +<h2>METHOD OF COMPUTATION</h2> > +<p> > +The test case Test_interactive is an interactive tool that shows the usage > +of the engine. > +</p> > + > This is a bit of a chicken-and-egg, but I would love to see/use "Test_interactive" to solidify my understanding of what you are explaining here. Only then I may have the ability to say something useful. ;) Still, I do get the gist of it; just not easy to sink in before playing with it for a while. > +<p> > +The following steps are performed when the engine is initialized: > +</p> > +<p> > <snip> > +<p> > +which could be used to reset its state. > +</p> > +<p> > +External function should only be used when union and join do not suffice. > +OVN datalog internal APIs must be used to do the computation. > +</p> > +</manpage> > -- > 2.7.4 > > _______________________________________________ > dev mailing list > dev@openvswitch.org > http://openvswitch.org/mailman/listinfo/dev > _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
