This pages provides the functions that are required to translate an Abstract Syntax Tree of a SemwidgQL query, defined by SemwidQL's syntax (Railroad diagrams, ANTLR v3 Grammar) into a SPARQL query.
FUNCTION ARRAY translateSemwidgQL ( STRING semwidgQuery, ARRAY namespaces, ARRAY namedResources ) {
NODE ast = getAbstractSyntaxTreeFromQuery( semwidgQuery );
ast = replaceNamedResourcesWithURIs( ast, namedResources );
ARRAY queries = [];
WALK ast RECURSIVELY AND SAVE CURRENT NODE IN node {
IF node IS A SimpleQuery {
STRING sparqlQuery = buildQuery( node, namespaces );
queries.push( sparqlQuery );
}
}
RETURN queries;
}
FUNCTION STRING buildQuery ( NODE simpleQuery, ARRAY namespaces ) {
STRING query = '';
query += buildPrefixPart( simpleQuery, namespaces );
query += buildSelectPart( simpleQuery );
query += buildWherePart( simpleQuery );
query += buildGroupPart( simpleQuery );
RETURN query;
}
FUNCTION STRING buildPrefixPart ( NODE simpleQuery, ARRAY namespaces ) {
STRING query = '';
FOR EVERY USED NAMESPACE ns IN simpleQuery {
query += 'PREFIX ' + ns + ': <' + namespaces[ns] + '>';
}
RETURN query;
}
FUNCTION STRING buildSelectPart ( NODE simpleQuery ) {
STRING query = 'SELECT DISTINCT ';
ARRAY resourcesAndProperties = getUsedResourcesAndProperties( simpleQuery );
ARRAY hiddenElements = getHiddenElements( simpleQuery );
BOOLEAN aggregate = IS getGroupExpressions( simpleQuery ) NOT EMPTY;
FOR EACH NODE element IN resourcesAndProperties {
BOOLEAN hidden = IS element PART OF hiddenElements;
IF NOT hidden {
STRING variableName = convertQueryElementToVariableName( element );
STRING aggregateFunction = getAggregateExpressions( element );
IF element IS ANY Property OR Wildcard {
IF aggregate {
query += aggregateFunction + ' (' + variableName + ') AS ' + variableName;
} ELSE {
query += variableName;
}
} ELSE {
STRING resourceURI = element.getUri();
IF aggregate {
query += aggregateFunction + ' (<' + resourceURI + '>) AS ' + variableName;
} ELSE {
query += '(<' + resourceURI + '>) AS ' + variableName;
}
}
}
}
RETURN query;
}
FUNCTION STRING buildWherePart ( NODE simpleQuery ) {
STRING query = 'WHERE {' + buildPathExpression( simpleQuery.getResource(), simpleQuery.getPathExpression() ) + '}';
RETURN query;
}
FUNCTION STRING buildPathExpression ( NODE previousElement, NODE pathExpression ) {
STRING query = '';
IF pathExpression IS NOT EMPTY {
IF pathExpression IS A MultiplePathExpression {
FOR EACH NODE pathEx IN pathExpression {
query += buildPathExpression( previousElement, pathEx );
}
} ELSE {
NODE prop = pathExpression.getFirstProperty();
IF previousElement IS A Resource {
query += buildFirstTriple( previousElement, prop );
query += buildFilter( previousElement );
} ELSE {
query += buildTriple( previousElement, prop );
}
query += buildFilter( prop );
}
} ELSE {
IF previousElement IS A ForwardWildcard {
STRING variableName = convertQueryElementToVariableName( previousElement );
query += variableName + ' ?p ?o . ';
}
}
RETURN query;
}
FUNCTION STRING buildFirstTriple ( NODE elem1, NODE elem2 ) {
STRING query = '';
STRING value1;
IF elem1 IS A Wildcard {
value1 = convertQueryElementToVariableName( elem1 );
} ELSE {
value1 = elem1.getValue();
}
IF elem2 IS A ForwardProperty OR ForwardPropertyWithFilter {
query += value1 + ' ' + elem2.getValue() + ' ' + convertQueryElementToVariableName( elem2 ) + ' . ';
} ELSE IF elem2 IS A ReversedProperty OR ReversedPropertyWithFilter {
query += convertQueryElementToVariableName( elem2 ) + ' ' + elem2.getValue() + ' ' + value1 + ' . ';
} ELSE IF elem2 IS A ForwardWildcard OR ForwardWildcardWithFilter {
STRING propetyName = convertQueryElementToVariableName( elem1 );
query += value1 + ' ' + getUniqueVariableName( elem1, elem2 ) + ' ' + convertQueryElementToVariableName( elem2 ) + ' . ';
} ELSE IF elem2 IS A ReversedWildcard OR ReversedWildcardWithFilter {
STRING propetyName = convertQueryElementToVariableName( elem2 );
query += convertQueryElementToVariableName( elem2 ) + ' ' + getUniqueVariableName( elem2, elem1 ) + ' ' + value1 + ' . ';
}
RETURN query;
}
FUNCTION STRING buildFilter ( NODE property ) {
STRING query = '';
IF property HAS FILTER EXPRESSION {
ARRAY filterExpressions = property.getFilter();
// filter array has form [filter expression, conditional operator, filter expression, conditional operator, ..., filter expression]
FOR EACH NODE filterExpression IN filterExpressions {
query += buildFilterTriples( property, filterExpression );
}
ARRAY realFilters = getRealFilters( filterExpressions );
ARRAY pseudoFilters = getPseudoFilters( filterExpressions );
IF realFilters IS NOT EMPTY {
query += 'FILTER (';
FOR EACH NODE filterExpression, conditionalOperator IN realFilters {
query += buildFilterExpression( property, filterExpression );
query += conditionalOperator.getValue();
}
query += ') . ';
}
FOR EACH NODE filterExpression IN pseudoFilters {
IF filterExpression IS A Timeinterval {
STRING variableName = convertQueryElementToVariableName( property );
query += 'BIND(FLOOR((xsd:dateTime(' + variableName + ') - xsd:dateTime("1970-01-01T00:00:00")) / (' + filterExpression.getTimeintervalInSeconds() + ')) AS ' + variableName + '_timeinterval)';
}
}
}
RETURN query;
}
FUNCTION STRING buildFilterTriples ( NODE property, NODE filterExpression ) {
STRING query = '':
IF filterExpression IS A RelationalExpression {
ARRAY properties = [ property ].concat( filterExpression.getProperties() );
FOR EACH prop1, prop2 IN properties {
query += buildTriple( prop1, prop2 );
}
ARRAY values = filterExpression.getValue();
FOR EACH value IN values {
IF value IS A SimpleQuery {
query += buildPathExpression( value.getResource(), value.getPathExpression() );
}
}
} ELSE IF filterExpression IS A Self {
ARRAY values = filterExpression.getValue();
FOR EACH value IN values {
IF value IS A SimpleQuery {
query += buildPathExpression( value.getResource(), value.getPathExpression() );
}
}
} ELSE IF filterExpression IS A Type {
STRING variableName = convertQueryElementToVariableName( property );
query += variableName + ' rdf:type ?TypeOf_' + variableName.substr( 1 ) ' . ';
// .substr( 1 ) removes the first char ('?') from the string
}
RETURN query;
}
FUNCTION STRING buildFilterExpression ( NODE property, NODE filterExpression ) {
STRING query = "";
STRING variableName = convertQueryElementToVariableName( property );
IF filterExpression IS A Language {
query += buildFilterExpressionLanguage( filterExpression, variableName );
} ELSE IF filterExpression IS A Type {
query += buildFilterExpressionType( filterExpression, variableName );
} ELSE IF filterExpression IS A Self {
query += buildFilterExpressionSelf( filterExpression, variableName );
} ELSE IF filterExpression IS A RelationalExpression {
query += buildFilterExpressionRelationalExpression( filterExpression, variableName );
} ELSE IF filterExpression IS A Timestart {
query += buildFilterExpressionTimestart( filterExpression, variableName );
} ELSE IF filterExpression IS A Timeend {
query += buildFilterExpressionTimeend( filterExpression, variableName );
}
RETURN query;
}
FUNCTION STRING buildFilterExpressionLanguage ( NODE filterExpression, STRING variableName ) {
STRING query = "";
query += "lang(" + variableName + ") = "" || langMatches(lang(" + variableName + "), " + filterExpression.getLanguage() + ")";
RETURN query;
}
FUNCTION STRING buildFilterExpressionType ( NODE filterExpression, STRING variableName ) {
STRING query = "";
query += "?TypeOf_" + variableName.substr( 1 ) + " " + filterExpression.getOperator + " " + filterExpression.getType();
RETURN query;
}
FUNCTION STRING buildFilterExpressionSelf ( NODE filterExpression, STRING variableName ) {
STRING query = "";
ARRAY values = filterExpression.getValue();
ARRAY lastProperties = [];
FOR EACH value IN values {
IF value IS A SimpleQuery {
IF value.getPathExpression() IS NOT EMPTY {
lastProperties.push( getLastPropertiesOfPathExpression( value.getPathExpression() ) );
}
}
}
IF lastProperties IS EMPTY {
// filterExpression does not contain nested queries with path expressions
IF filterExpression.getOperator() IS "~" {
// Contains Operator
query += "CONTAINS(LCASE(STR(" + variableName + ")), LCASE(STR(";
FOR EACH NODE value IN values {
IF value IS ANY Resource {
query += convertQueryElementToVariableName( value.getResource() );
} ELSE {
query += value + " ";
}
}
query += ")))";
} ELSE {
IF value[0] IS A String {
query += "STR(" + variableName + ") ";
} ELSE {
query += variableName + " ";
}
query += filterExpression.getOperator() + " ";
FOR EACH NODE value IN values {
IF value IS A SimpleQuery {
query += value.getResource().getValue() ;
} ELSE {
query += value + " ";
}
}
}
} ELSE {
// filterExpression contains nested queries with path expressions
// if the nested query contains (another nested query with) a MultiplePathExpression, the number of filters must be calculated. Filter expressions are concatenated with a logical disjunction ("||").
INT numberOfFilters = 1;
FOR EACH ARRAY property IN lastProperties {
numberOfFilters *= property.length;
}
ARRAY propertyIndices = [];
INT loops = lastProperties.length;
FOR i = 0 TO loops {
propertyIndices.push( 0 );
}
FOR i = 0 TO numberOfFilters {
IF filterExpression.getOperator() IS "~" {
// Contains Operator
query += "CONTAINS(LCASE(STR(" + variableName + ")), LCASE(";
INT simpleQueryIndex = 0;
FOR EACH NODE value IN values {
IF value IS A SimpleQuery {
ARRAY simpleQuerysProperties = lastProperties[simpleQueryIndex];
NODE simpleQuerysProperty = simpleQuerysProperties[propertyIndices[simpleQueryIndex]];
simpleQueryIndex++;
query += convertQueryElementToVariableName( simpleQuerysProperty ) + " ";
} ELSE {
query += value + " ";
}
}
query += "))";
} ELSE {
IF values CONTAINS A StringLiteral {
query += "STR(" + variableName + ") ";
} ELSE {
query += variableName + " ";
}
query += filterExpression.getOperator() + " ";
INT simpleQueryIndex = 0;
FOR EACH NODE value IN values {
IF value IS A SimpleQuery {
ARRAY simpleQuerysProperties = lastProperties[simpleQueryIndex];
NODE simpleQuerysProperty = simpleQuerysProperties[propertyIndices[simpleQueryIndex]];
simpleQueryIndex++;
query += convertQueryElementToVariableName( simpleQuerysProperty ) + " ";
} ELSE {
query += value + " ";
}
}
}
// Define last properties indices for next iteration
BOOLEAN increaseNext = true;
FOR j = 0 TO loops {
INT val = propertyIndices[j];
INT length = lastProperties[j].length;
IF increaseNext IS true {
propertyIndices[j] = (val + 1) % length;
IF val + 1 IS propertyIndices[j] {
increaseNext = false;
} ELSE {
increaseNext = true;
}
}
}
IF THIS IS NOT LAST ITERATION {
query += " || ";
}
}
}
RETURN query;
}
FUNCTION STRING buildFilterExpressionRelationalExpression ( NODE filterExpression, STRING variableName ) {
STRING query = "";
ARRAY values = filterExpression.getValue();
ARRAY lastProperties = [];
FOR EACH value IN values {
IF value IS A SimpleQuery {
IF value.getPathExpression() IS NOT EMPTY {
lastProperties.push( getLastPropertiesOfPathExpression( value.getPathExpression() ) );
}
}
}
ARRAY properties = filterExpression.getProperties();
NODE lastProperty = LAST ELEMENT OF properties;
STRING lastPropertyName = convertQueryElementToVariableName( lastProperty );
IF lastProperties IS EMPTY {
// filterExpression does not contain nested queries with path expressions
IF filterExpression.getOperator() IS "~" {
// Contains Operator
query += "CONTAINS(LCASE(STR(" + lastPropertyName + ")), LCASE(STR(";
FOR EACH NODE value IN values {
IF value IS ANY Resource {
query += convertQueryElementToVariableName( value.getResource() );
} ELSE {
query += value + " ";
}
}
query += ")))";
} ELSE {
IF values CONTAINS A StringLiteral {
query += "STR(" + lastPropertyName + ") ";
} ELSE {
query += lastPropertyName + " ";
}
query += filterExpression.getOperator() + " ";
FOR EACH value IN values {
IF value IS A SimpleQuery {
IF value.getPathExpression() IS NOT EMPTY {
query += value.getResource().getValue() + " ";
} ELSE {
query += value + " ";
}
}
}
}
} ELSE {
// filterExpression contains nested queries with path expressions
// if the nested query contains (another nested query with) a MultiplePathExpression, the number of filters must be calculated. Filter expressions are concatenated with a logical disjunction ("||").
INT numberOfFilters = 1;
FOR EACH ARRAY property IN lastProperties {
numberOfFilters *= property.length;
}
ARRAY propertyIndices = [];
INT loops = lastProperties.length;
FOR INT i = 0 TO loops {
propertyIndices.push( 0 );
}
FOR INT i = 0 TO numberOfFilters {
IF filterExpression.getOperator() IS "~" {
// Contains Operator
query += "CONTAINS(LCASE(STR(" + lastPropertyName + ")), LCASE(";
INT simpleQueryIndex = 0;
FOR EACH NODE value IN values {
IF value IS A SimpleQuery {
ARRAY simpleQuerysProperties = lastProperties[simpleQueryIndex];
NODE simpleQuerysProperty = simpleQuerysProperties[propertyIndices[simpleQueryIndex]];
simpleQueryIndex++;
query += convertQueryElementToVariableName( simpleQuerysProperty ) + " ";
} ELSE {
query += value + " ";
}
}
query += "))";
} ELSE {
IF values CONTAINS A StringLiteral {
query += "STR(" + lastPropertyName + ") ";
} ELSE {
query += lastPropertyName + " ";
}
query += filterExpression.getOperator() + " ";
INT simpleQueryIndex = 0;
FOR EACH NODE value IN values {
IF value IS A SimpleQuery {
ARRAY simpleQuerysProperties = lastProperties[simpleQueryIndex];
NODE simpleQuerysProperty = simpleQuerysProperties[propertyIndices[simpleQueryIndex]];
simpleQueryIndex++;
query += convertQueryElementToVariableName( simpleQuerysProperty ) + " ";
} ELSE {
query += value + " ";
}
}
}
// Define last properties indices for next iteration
BOOLEAN increaseNext = true;
FOR INT j = 0 TO loops {
INT val = propertyIndices[j];
INT length = lastProperties[j].length;
IF increaseNext IS true {
propertyIndices[j] = (val + 1) % length;
IF val + 1 IS propertyIndices[j] {
increaseNext = false;
} ELSE {
increaseNext = true;
}
}
}
IF THIS IS NOT LAST ITERATION {
query += " || ";
}
}
}
RETURN query;
}
FUNCTION STRING buildFilterExpressionTimestart ( NODE filterExpression, STRING variableName ) {
STRING query = "";
query += "xsd:dateTime(" + variableName + ") >= " + readDateExpression( filterExpression.getTimestart() );
RETURN query;
}
FUNCTION STRING buildFilterExpressionTimeend ( NODE filterExpression, STRING variableName ) {
STRING query = "";
query += "xsd:dateTime(" + variableName + ") <= " + readDateExpression( filterExpression.getTimeend() );
RETURN query;
}
FUNCTION STRING buildTriple = ( NODE elem1, NODE elem2 ) {
STRING query = '';
STRING elem1Name = convertQueryElementToVariableName( elem1 );
STRING elem2Name = convertQueryElementToVariableName( elem2 );
IF elem2 IS A ForwardProperty OR ForwardPropertyWithFilter {
query += elem1Name + ' ' + elem2.getValue() + ' ' + elem2Name + ' . ';
} ELSE IF elem2 IS A ReversedProperty OR ReversedPropertyWithFilter {
query += elem2Name + ' ' + elem2.getValue() + ' ' + elem1Name + ' . ';
} ELSE IF elem2 IS A ForwardWildcard OR ForwardWildcardWithFilter {
query += elem1Name + ' ' + '?PropertyOf_' + elem1Name.substr(1) + '__' + elem2Name.substr(1) + ' ' + elem2Name + ' . ';
} ELSE IF elem2 IS A ReversedWildcard OR ReversedWildcardWithFilter {
query += elem2Name + ' ' + '?PropertyOf_' + elem2Name.substr(1) + '__' + elem1Name.substr(1) + ' ' + elem1Name + ' . ';
}
RETURN query;
};
FUNCTION STRING buildGroupPart ( NODE simpleQuery ) {
STRING query = '';
ARRAY groupExpressions = getGroupExpressions( simpleQuery );
IF groupExpressions IS NOT EMPTY {
NODE groupExpression;
FOR EACH MAP groupExpression IN groupExpressions {
IF groupExpression.get( 'filter' ) IS A Timeinterval {
STRING name = convertQueryElementToVariableName( groupExpression.get( 'element' ) ) + '_timeinterval';
query += 'GROUP BY ' + name;
query += 'ORDER BY DESC(' + name + ')';
}
}
}
RETURN query;
};
FUNCTION ARRAY getGroupExpressions ( NODE node ) {
// Returns an array of hashmaps that contain a node's and all its child nodes' filter
// expressions of type TimeInterval. The hashmap also contains a pointer to the respective node
// MAP groupExpression;
// groupExpression.map( 'filter', filter );
// groupExpression.map( 'element', node );
// groupExpressions.push( groupExpression );
};
FUNCTION ARRAY getUsedResourcesAndProperties ( NODE simpleQuery ) {
// Returns an array of all elements in simpleQuery that are not part of a filter expression
// Example:
// {r1.ns:p1(ns:p2 < {r2.ns:p3}).[ns:p4(ns:p5 < 10), ns:p6.ns:p7]}
// + + - - - + - + +
// returns an array containing the corresponding elements to r1, ns:p1, ns:p4, ns:p6 and ns:p7
}
FUNCTION ARRAY getHiddenElements ( NODE simpleQuery ) {
// Returns an array of all elements in simpleQuery where the keyword @hide has the value TRUE
// Example:
// {r1.ns:p1(@hide = false).[ns:p2(@hide = true), ns:p3.ns:p4(@hide = true)]}
// - - + - +
// returns an array containing the corresponding elements to ns:p2 and ns:p4
}
FUNTION NODE replaceNamedResourcesWithURIs ( NODE ast, ARRAY namedResources ) {
// Walks the Abstract Syntax Tree recursively and replaces every NamedResource with a
// QualifiedResource or a PrefixedResource, respectively, depending on the corresponding value
// in namedResources. The resulting Abstract Syntax Tree is returned.
}
FUNCTION NODE getAbstractSyntaxTreeFromQuery ( STRING semwidgQuery ) {
// Returns a revised version of the Abstract Syntax Tree of the SemwidgQL query which is
// defined by the SemwidgQL EBNF Syntax. To simplify the work with the AST, its nodes are
// consolidated and converted into objects (or data structures, depending on the used
// programming language. This pseudo code assumes that an object orientated programming
// language is used).
}
FUNCTION ARRAY getLastPropertiesOfPathExpression ( NODE pathExpression) {
// Returns an array of the last property of a PathExpression. If the pathExpression ends with
// a MultiplePathExpression, the array contains the last properties of the path expressions of
// the MultiplePathExpression.
}
FUNCTION STRING convertQueryElementToVariableName ( NODE node ) {
// Returns a unique but reproducible variable name for a node of the queries AST, starting
// with a question mark ("?").
// The reference implementation uses the name of the node plus a double underscore "__" plus a
// suffix that depends on the node's postion in the AST.
// Node name:
//
// If the node is defined by a fully quallified URI, enclosing angle brackets ("<", ">") are
// removed, as well as a possible trailing slash ("/"). Then, the part after the last slash or
// hash ("#") is used as name.
//
// -> MyProperty
//
// If the node is defined by a prefixed URI, the part after the last colon (":") is used as
// name.
//
// ns:MyProperty -> MyProperty
//
// If the node is a wildcard resource or property ("*"), the name is "wildcard".
//
// * -> wildcard
//
// If the node is a reversed resource or property an "Of" is appended to the name.
//
// ^ns:MyProperty -> MyPropertyOf
// Suffix:
//
// The suffix starts with an R if the node is a resource or a P if the node is a property.
// The algorithm walks the AST from top to the regarding node for which the suffix should be
// created. If the currently visited node is a "Resource", "Property", "PathExpression",
// "MultiplePathExpression", or a "SimpleQuery", an underscore ("_") plus the index of the
// node in the list of its siblings is appended.
//
// r1.ns:p1.^ns:p2 -> SimpleQuery (0) (irrelevant nodes were omitted)
// | |
// Resource (0) PathExpression (1)
// | | |
// "r1" Propery (0) Property (1)
// | |
// "ns:p1" "ns:p2"
//
// r1 -> R_0_0, ns:p1 -> P_0_1_0, ns:p2 -> P_0_1_1
// Complete name:
//
// r1.ns:p1.^ns:p2
//
// Name of ns:p2 would be: ?p2Of__P_0_1_1
}
FUNCTION ARRAY getRealFilters ( ARRAY filterExpressions ) {
// Returns an array of filter expressions whose types are not Aggregate, Hide, or Timeinterval
}
FUNCTION ARRAY getPseudoFilters ( ARRAY filterExpressions ) {
// Returns an array of filter expressions whose types are Aggregate, Hide, or Timeinterval
}
FUNCTION STRING readDateExpression ( STRING expressionString ) {
// Returns a SPARQL compliant version of the date expression
// DateExpression
// : ('now'|Iso8601DateExpression) ( '+' | '-' ) (Number ('s'|'m'|'h'|'d'|'w') Character*)*
// "now" is converted into "now()", a date expression in ISO 8601 format is encapsulated into
// a xsd:dateTime typecasting ("xsd:dateTime(Iso8601DateExpression)").
// The last parts are converted into seconds each and summed up. Instead of only 's', 'm',
// 'h', 'd', or 'w', sec or seconds etc. are also valid units.
// (s = 1, m = 60, h = 3600, d = 86400, w = 604800, everything else = 0)
// Example:
// now - 1h 30m -> now() - 5400
//
// 2016-01-01T12:00:00 - 60 min -> xsd:dateTime("2016-01-01T12:00:00.000") - 3600
}