ftsrg/ingraph

Incremental view maintenance for openCypher graph queries.

ingraph's Issues

Add inverse edges to EMF model

e.g. input -> output

Fix build after ire->ingraph merge

Use different VariableFactories for query parts where applicable

For certain query parts, using the same name does not mean they are the same variables. So separate VariableFactory instances need to be used for:

• each singleQuery (i.e. those that are unioned together) (see also: #9)
• subqueries (i.e. those delimited by WITH or RETURN)

Note: for the subqueries, the variables present in the WITH clause are chained forward and available in the subsequent subqueries

Add TeX serialization for expand and getNodes operator

Depends on #1 and #2

Switch ON travis notifications for all unsuccessful builds

Once travis builds are corrected, switch .travis.yml/notifications/on_failure to always.

It has been silented for now in d5d8e4b.

Why do we need bags?

Let's gather some use cases for multisets/bags.

SQL keeps duplicates, because:

• Duplicates are important for aggregate queries.
• In general, bags can be more “efficient” than sets.

(source)

Include source files in JARs

Add expand operators to relational algebra model

Add getNodes operator to relational algebra model

Eliminate large constructors for the serializers

E.g. https://github.com/FTSRG/ingraph/blob/master/ingraph-relalg2tex/src/main/java/ingraph/relalg2tex/RelalgExpressionSerializer.xtend#L16

Update to Xtext 2.11

Xtext 2.11 beta will be released on 18 October, with the final version planned in January. https://blogs.itemis.com/en/xtext-2.11-release-plan-changed

2.11 fixes some issues with the web editor, see https://bugs.eclipse.org/bugs/show_bug.cgi?id=495851

Xtext's web UI support the Ace editor, which looks quite nice.

Type check for comparison expressions

Not all expression-pairs can be operand of comparison operators. Some type check needs to be done when compiling the cypher query to te relational algebra expressions.

These are legal:

• nodeVar1 = nodeVar2
• nodeVar1 != nodeVar2
• nodeVar1.numericAttribute < 5

However, these are not, and a compile-time error should be omitted:

• nodeVar1 < 5
• nodeVar1 < nodeVar2

In general, these cases should emit a warning (list can be continued):

vertex and edge variables:

• can't be tested for less than, greater than etc. with each other
• can't be compared to arithmetic expressions and string expressions
• can't be compared to attribute variables

Implement tests for queries in the openCypher specification

Add Expand(direction=BOTH) to TeX visualization

Discuss bag semantics, add distinct node to relational algebra model

Implement unit tests for ANTLR Cypher to relational algebra

Add UNWIND operator

Add operator for unwinding collections.

Support OPTIONAL MATCH as the first MATCH clause of a query

We should support single queries that has an OPTIONAL MATCH clause as their first MATCH clause.

E.g. the following should return a singlle null-row, provided, there is no vertex having the label NON_EXISTENT_LABEL.

OPTIONAL MATCH (n:NON_EXISTENT_LABEL)
RETURN n

Note: this implies that all MATCH clauses in this single query is OPTIONAL MATCH.

Handle Union in opencypher2relalg compilation

• add Union as BetaOperator to EMF model

• handle Union in cyp AST -> relalg compilation

• use different VariableFactories fo each singleQuery (i.e. those that are unioned together)

• make distinction between UNION ALL/UNION

  match (n:A)
  return n
  union
  match (n:D)
  return n
  

• add requirement: variable aliases need to be matched (see also: #16)
  otherwise exception is thrown in Neo4j, see:

  CREATE (n1:A{name:"World"}) create (n2:B{whatever:"Universe"});
  MATCH (a:A) RETURN a AS a
  UNION
  MATCH (b:B) RETURN b AS a;
  

  Neo4j: All sub queries in an UNION must have the same column names

Add allDifferent operator to relational algebra model

Synopsis: AllDifferent( list_of_edge_variables ), e.g. AllDifferent([_e1, _e2, _e3])

Implement tuple semantics for query plans

Query plans should implement tuple semantics, i.e. instead of using attribute names, they should use tuples and indices. This is required by ire.

Handle Edge label collision in Cypher2RelalgUtil.ensureLabel

See also: #10

• ensureLabel should indicate (possibly in EMF model) when a labelset is already set for a variable, and the new is incompatible.
• This has similar effect as a filter(false) condition. query optimizer can replace these branches with an empty data source of specified schema (list of variables)

Make relational algebra EMF models serializable

Drop cypxmi models

@jmarton do we need cypxmi models in the ingraph-cypxmi/ dir anymore?

Support "metaqueries"

We should definitely support labels() and type(). I am not sure about properties() and keys().

ANTLR should throw an exception instead of warnings

Currently, if ANTLR cannot parse a query, it prints warning messages to the standard error. It (or we) should throw an exception instead.

"Don't care" vs "anonymous" variables

Check this query:

MATCH ()
RETURN *

In this case, our parser generated a variable and marks it as "don't care". I don't think this is an appropriate name - we should call these variables "anonymous" variables.

Improve tech report

• Fix broken references
• Add header
• Improve description of relational algebraic operators
  • Unwind
  • Aggregation operators, e.g. collect()
  • Bag semantics
• Add new query sets
  • Train Benchmark queries
  • Social Network Benchmark queries
  • Movie database queries
  • Static analysis - JS
  • Static analysis - Java (jQAssistant)

Add support for distributed operations

We should use Docker containers and Akka remoting to support distributed query processing.
Key challenges:

• Deploy the containers (~cluster management)
• Allocate the Rete node to different machines/containers. We can rely on the cardinality estimations in https://github.com/FTSRG/ingraph/blob/06fcd4e7eb82d8e5af9bdcfae8cd1148123177d4/ingraph-relalg-xcore/src/relalg.xcore#L57
• Remotely instantiate/shutdown the Rete network

Design HTTP API

Think http://spray.io/

AllDifferent should accept variables and set of variables as well

To facilitate range edge queries, AllDifferent operator should accept edge-variables and edge list variables. On the resultset the flattened union should be tested for pairwise inequality.

• modify EMF model
• extend expand operator to have edge list variables

Allow many labels for VertexVariable and EdgeVariable

See also: #11

• improve EMF relalg model for VertexVariable
• improve EMF relalg model for EdgeVariable
• handle in compilation (Cypher2RelalgUtil.ensureLabel)
  • for VertexVariable
  • for EdgeVariable

Effective semantics of the labelset constraints:

• multiple labels of a VertexVariable are and-ed together (in the relalg model, this is the semantics of VertexLabelSet)
• multiple occurences of a VertexVariable with possible different label sets enforce a contraint that a matching variable needs to match the union of the label sets.
• multiple labels of an EdgeVariable are or-ed together (in the relalg model, this is the semantics of EdgeLabelSet)
• multiple occurences of an EdgeVariable with possible different label sets enforce a constraint that a matching variable needs to match the intersection of the label sets.
• for EdgeVariables, a clear distinction is to be made between the cases when there are no labelset constraints given for an edge variable and when their intersection is the empty set (this is handled in LabelSetStatus)

"Operator" is ambiguous

We currently use Operator multiple times in the relalg model:

• Operator, UnaryOperator, etc. are relational algebraic operators
• ArithmeticComparisonOperator, UnaryArithmeticOperator, etc. are enums

Sometimes this makes "programming by Ctrl+Space" a bit more difficult :-)

Idea: add a Type suffix to enums, e.g. ArithmeticComparisonOperatorType, UnaryArithmeticOperatorType, ...

Translate expressions to functors

https://github.com/FTSRG/ingraph/blob/7f3d59067c43c71e6b3a13b5a33229fdf924e513/ingraph-ire/src/test/scala/ingraph/ire/IntegrationTest.scala

Deploy to bintray

Issues with ExponentDecimalReal grammar rule

I tried to parse integer and double numbers. Integers were straightforward to implement (tests).

However, I had issues with parsing "exponent decimal" real numbers. I documented some strange behaviour in a minimal working example.

Nodes should work with multisets

Nodes have quite a large variation in their inputs and outputs:

Parse ORDER BY and SKIP/LIMIT expressions

In accordance with #56, we should throw an exception if a query uses SKIP/LIMIT without ORDER BY.

Before we fix the issues with sorting (e.g. parsing ASC/DESC orders), we should update to the latest version of Slizaa:
slizaa/slizaa-opencypher-xtext@f9e935d

"mutual" vs "common" attributes

Currently, we use the terminology "mutual attributes" in the code (LaTeX/Xcore) and "common attributes" in the submitted paper. We should unify this.

Add support for lists

This a tough one, so let's break it down to simpler ones.

• Add model construct to relalg.xcore
• Parse lists: see the ExpressionList grammar entity
• Implement collections in in ire
• Implement the UNWIND operator in ire: #54
• Implement the collect() function in ire: ftsrg/ire#2

First, we should aim at simple queries:

MATCH (n)
RETURN COLLECT(n) AS nodes

WITH [1,2,3] AS x
UNWIND x AS y
RETURN y

WITH [1,2,3] AS x
UNWIND x AS y
RETURN COLLECT(y) AS ys

Handle transitive closure operations

We should consider how to handle minHops and maxHops in Cypher queries: https://neo4j.com/docs/developer-manual/current/cypher/#_variable_length_relationships

-[:TYPE*minHops..maxHops]->

The default values are:

• minHops: 1
• maxHops: infinity

Possible cases (projections [π operator] omitted):

• If maxHops is limited: we should unfold the expression to a union of joins.
  • If minHops is 0 -> e:E*0..2 can be defined as r ∪ r ⨝ (E ∪ (E ⨝ E))
  • If minHops is larger than 0 -> e:E*1..3 can be defined as r ⨝ (E ∪ (E ⨝ E) ∪ (E ⨝ E ⨝ E))
• If maxHops is infinity (default):
  • If minHops is 0 -> e:E*0.. can be defined as r ∪ r ⨝ E+
  • If minHops is 1 (default), we should simply use transitive closure -> e:E*1.. can be defined as r ⨝ E+
  • If minHops is larger than 1 and maxHops is infinity, we should unfold exactly minHops hops -> e:E*2.. can be defined as r ⨝ E ⨝ E+

Implement operator: ORDER BY

ORDER BY

https://neo4j.com/docs/developer-manual/3.0/cypher/#query-order

A sub-clause following RETURN or WITH, specifying that the output should be sorted in particular way.

The user of the library should specify a list of variable-direction pairs (e.g. person-ASC, city-DESC) for the ordering.

Implement operator: UNWIND

https://github.com/FTSRG/ire/blob/master/src/main/scala/hu/bme/mit/ire/nodes/unary/UnwindNode.scala

compiler: Standard Cypher constructions

(Related ticket: #51)

Use this issue to keep track of supported Cypher constructs.

Clauses

• Pattern matching constructs
  • node pattern
  • relationship pattern of a single hop
  • relationship pattern of multiple hops
  • direction of the relationship pattern
  • attribute constraints in node and relationship patterns
• Data manipulation
  • CREATE
  • MERGE
  • SET
  • DELETE
  • DETACH DELETE
  • REMOVE
• Procedure calls
  • CALL ... YIELD (as this call may run an arbitrary Java code, there is no way we can handle these incrementally)

Sub-clauses

We can safely ignore these for now.

• ON CREATE
• ON MATCH

Operators

• String operations
  • STARTS WITH
  • CONTAINS
  • ENDS WITH
• Query constructs
  • MATCH
    • Sub-clause:
      • WHERE
    • MATCH, without OPTIONAL
    • OPTIONAL MATCH
      • as non-first MATCH clause of a single query
      • as first MATCH clause of a single query, see #40
  • RETURN
    • RETURN *
    • expression on the return list
    • alias handling
    • RETURN DISTINCT
    • Sub-clauses:
      • ORDER BY (handles variables and expressions as well as name resolution for aliased RETURN items)
      • SKIP (SKIP and LIMIT only implemented for constants)
      • LIMIT
  • UNWIND
  • WITH
    • Sub-clause:
      • WHERE #124
  • UNION
• Arithmetic comparison
  • =
  • <> (also !=, though non-standard)
  • <
  • >
  • <=
  • >=
• Arithmetic operators
  • +
  • -
  • /
  • *
  • ^
  • %
• Logical operators
  • NOT
  • AND
  • OR
  • XOR
• NULLs
  • <variable> IS [NOT] NULL
  • <expression> IS [NOT] NULL
• Accessors
  • . (property access)
  • [] (subscript) (Note: we don't support p['foo'], which is a syntax sugar for p.foo)

Expressions

• Parameters with new syntax ($)
• Literals
• Aggregation functions
  • avg()
  • collect()
  • count()
  • max()
  • min()
  • sum()
• Statistical functions
  • stdDev()
  • stdDevP()

We can safely ignore these for now:

• List comprehensions
• Pattern comprehensions

Functions

• Predicate functions
  • exists()
• Scalar functions
  • coalesce()
  • endNode()
  • head()
  • length()
  • last()
  • properties()
  • size()
  • startNode()
  • type()
  • toFloat()
• List functions
  • relationships()
  • tail()
  • keys()
  • labels()
  • nodes()
  • range()
• Numeric functions
  • abs()
  • ceil()
  • floor()
  • rand()
  • round()
  • sign()
• Logarithmic functions
  • e()
  • exp()
  • log()
  • log10()
  • sqrt()
• Trigonometric functions
  • acos()
  • asin()
  • atan()
  • atan2()
  • cos()
  • cot()
  • degrees()
  • pi()
  • radians()
  • sin()
  • tan()
• String functions
  • left()
  • lTrim()
  • trim()
  • replace()
  • reverse()
  • right()
  • rTrim()
  • split()
  • substring()
  • toLower()
  • toString()
  • toUpper()
• Statistical functions
  • percentileCont()
  • percentileDisc()
• Not included in Cypher:
  • toBoolean()
  • toInteger() (called toInt())

Types

• primitives
• list
• map
• node
• relationship
• path

How to handle "IS [NOT] NULL"

We currently have two enums for IS_NULL, IS_NOT_NULL: https://github.com/FTSRG/ingraph/blob/44e456d7f772b4cac446e9df8fcb7bd43a596b77/ingraph-relalg-xcore/src/relalg.xcore#L356

Handle expression aliases for RETURN and WITH clauses

• update EMF model to accomodate expression aliases
• WONTFIX: in EMF model, change expression aliases from String to Variable. INSTEAD that, ExpressionVariable was introdiced to the relalg EMF model to accommodate maned expressions.
• handle name collision between model variables and alias variables (see explanation below in 2nd comment)
• handle in union (see #9) either in cypher2relalg or at a later stage
• handle WITH clause
• handle WITH ... WHERE subclause (moved to #124)
• implement variable chaining

Trim quotes/apostrophes from StringLiterals

Currently, this condition

WHERE n="emfsucks"

matches if n is "\"emfsucks\""

Enable regression testing by introducing two test sets

There are a few hundred tests that we have imported from several sources. Our project, however, is a work-in-progress and succeeds only for a subset of the tests. We would like to mark those tests that are known to work at some time point (test set 1). We require these tests to pass for future commits on Travis in order to recognize if something breaks.

To achieve this, we need to

• mark tests that are required to pass (test set 1)
• run test set 1 on Travis
• create a convenient way to upgrade test set 1 from all tests with the newly covered tests

Note: test set 1 is intended to expand only, i.e. to form a set-series where each element is a superset of any previous elements.

engine: Incremental evaluation of standard Cypher constructions

(Related ticket: #35)

Use this issue to keep track of supported Cypher constructs.

Clauses

• Query constructs
  • MATCH
    • Transitive closure
  • RETURN (Production node)
  • UNWIND
  • OPTIONAL MATCH (left outer join)
  • WITH this is translated to joins in the query plan
  • UNION
• Data manipulation (moved to #170)
  • CREATE
  • MERGE
  • SET
  • DELETE
  • DETACH DELETE
  • REMOVE
• Procedure calls
  • CALL ... YIELD (as this call may run an arbitrary Java code, there is no way we can handle these incrementally)

Sub-clauses

• Conditions
  • WHERE #43
• Ordering
  • ORDER BY
  • SKIP
  • LIMIT
• Data manipulation (moved to #170)
  • ON CREATE
  • ON MATCH

Operators

• DISTINCT
• String operations
  • STARTS WITH
  • CONTAINS
  • ENDS WITH
• Arithmetic comparison #43
  • =
  • <>
  • <
  • >
  • <=
  • >=
• Arithmetic operators
  • +
  • -
  • /
  • *
  • ^
  • %
• Logical operators https://github.com/FTSRG/ingraph/tree/master/queries/ldbc-snb
  • NOT
  • AND
  • OR
  • XOR
• NULLs
  • IS NULL
  • IS NOT NULL
• Accessors
  • . (property access) not required as the query plan will be translated to tuples
  • [] (subscript)

Expressions

• List comprehensions (moved to #171)
• Pattern comprehensions (moved to #172)
• Parameters with new syntax ($) (moved to #85)
• Literals they are just constants
• Aggregation functions
  • avg()
  • count()
  • max()
  • min()
  • sum()
  • collect()

Functions

• Statistical functions
  • stdDev()
  • stdDevP()
  • percentileCont()
  • percentileDisc()
• Predicate functions
  • exists() (moved to #174)
• Scalar functions
  • toFloat()
  • head()
  • length()
  • last()
  • size()
  • coalesce()
  • startNode() (moved to #175)
  • endNode() (moved to #175)
  • properties(), (see #53)
  • type() (see #53)
• List functions
  • tail()
  • range()
  • keys() (see #53)
  • labels() (see #53)
  • relationships() (moved to #175)
  • nodes() (moved to #175)
• Numeric functions
  • abs()
  • ceil()
  • floor()
  • rand()
  • round()
  • sign()
• Logarithmic functions
  • e()
  • exp()
  • log()
  • log10()
  • sqrt()
• Trigonometric functions
  • acos()
  • asin()
  • atan()
  • atan2()
  • cos()
  • cot()
  • degrees()
  • pi()
  • radians()
  • sin()
  • tan()
• String functions
  • left()
  • right()
  • trim()
  • lTrim()
  • rTrim()
  • replace()
  • reverse()
  • split()
  • substring()
  • toString()
  • toLower() (lower())
  • toUpper() (upper())
• Not included in Cypher:
  • toBoolean()
  • toInteger() (called toInt())

Types

• primitives
• list
• map
• node
• relationship
• path

Implement SortAndTopNode operator for "ORDER BY ... SKIP/LIMIT ..." expressions

Implement a SKIP...LIMIT operator, which works on ordered expressions: https://neo4j.com/docs/developer-manual/current/cypher/#_skip_and_limit

We only support SKIP and LIMIT if they are preceded by an ORDER BY expression:
https://neo4j.com/docs/developer-manual/3.0/cypher/#query-order

A sub-clause following RETURN or WITH, specifying that the output should be sorted in particular way.
The user of the library should specify a list of variable-direction pairs (e.g. person-ASC, city-DESC) for the ordering.