Repository: RDFLib/rdflib

Issue:
DESCRIBE query not working
Apparently DESCRIBE queries are not fully implemented yet? This is what I get with two different queries:
###### 

1) g.query('DESCRIBE http://www.example.org/a')
...
/usr/lib/python2.7/site-packages/rdflib/plugins/sparql/algebra.pyc in translate(q)
    530 
    531     # all query types have a where part
--> 532     M = translateGroupGraphPattern(q.where)
    533 
    534     aggregate = False

/usr/lib/python2.7/site-packages/rdflib/plugins/sparql/algebra.pyc in translateGroupGraphPattern(graphPattern)
    261     """
    262 
--> 263     if graphPattern.name == 'SubSelect':
    264         return ToMultiSet(translate(graphPattern)[0])
    265 

AttributeError: 'NoneType' object has no attribute 'name'

2) g.query('DESCRIBE ?s WHERE {?s ?p ?o FILTER (?s = http://www.example.org/a)}')

...
/usr/lib/python2.7/site-packages/rdflib/plugins/sparql/evaluate.pyc in evalPart(ctx, part)
    260 
    261     elif part.name == 'DescribeQuery':
--> 262         raise Exception('DESCRIBE not implemented')
    263 
    264     else:

Exception: DESCRIBE not implemented
###### 

The graph is created via this sequence:

import rdflib
from rdflib import RDF

ex = rdflib.Namespace('http://www.example.org/')
g = rdflib.Graph()
g.add((ex['a'], RDF['type'], ex['Cl']))


Discussion:
coveralls: 
[![Coverage Status](https://coveralls.io/builds/56591947/badge)](https://coveralls.io/builds/56591947)

Coverage: 90.682% (+0.02%) from 90.662% when pulling **6566af336a664a7053c4ab9d5476fb3fd67e13b7 on corning-incorporated:sparql-describe-implementation** into **9625ed0b432c9085e2d9dda1fd8acf707b9022ab on RDFLib:main**.

aucampia: Just for reference, two previous abandoned attempts at doing this: 

- https://github.com/RDFLib/rdflib/pull/1913
- https://github.com/gjhiggins/rdflib/commit/5fb6f43e6b1d2264ac5015c260b32fc4e7dbf240#
aucampia: pre-commit.ci run

Patch:
diff --git a/rdflib/plugins/sparql/algebra.py b/rdflib/plugins/sparql/algebra.py
index 1429012b..5f6a774a 100644
--- a/rdflib/plugins/sparql/algebra.py
+++ b/rdflib/plugins/sparql/algebra.py
@@ -335,7 +335,11 @@ def translateGroupGraphPattern(graphPattern: CompValue) -> CompValue:
     """
 
     if graphPattern.name == "SubSelect":
-        return ToMultiSet(translate(graphPattern)[0])
+        # The first output from translate cannot be None for a subselect query
+        # as it can only be None for certain DESCRIBE queries.
+        # type error: Argument 1 to "ToMultiSet" has incompatible type "Optional[CompValue]";
+        #   expected "Union[List[Dict[Variable, str]], CompValue]"
+        return ToMultiSet(translate(graphPattern)[0])  # type: ignore[arg-type]
 
     if not graphPattern.part:
         graphPattern.part = []  # empty { }
@@ -623,7 +627,7 @@ def translateValues(
     return Values(res)
 
 
-def translate(q: CompValue) -> Tuple[CompValue, List[Variable]]:
+def translate(q: CompValue) -> Tuple[Optional[CompValue], List[Variable]]:
     """
     http://www.w3.org/TR/sparql11-query/#convertSolMod
 
@@ -635,9 +639,27 @@ def translate(q: CompValue) -> Tuple[CompValue, List[Variable]]:
 
     # TODO: Var scope test
     VS: Set[Variable] = set()
-    traverse(q.where, functools.partial(_findVars, res=VS))
 
-    # all query types have a where part
+    # All query types have a WHERE clause EXCEPT some DESCRIBE queries
+    # where only explicit IRIs are provided.
+    if q.name == "DescribeQuery":
+        # For DESCRIBE queries, use the vars provided in q.var.
+        # If there is no WHERE clause, vars should be explicit IRIs to describe.
+        # If there is a WHERE clause, vars can be any combination of explicit IRIs
+        # and variables.
+        VS = set(q.var)
+
+        # If there is no WHERE clause, just return the vars projected
+        if q.where is None:
+            return None, list(VS)
+
+        # Otherwise, evaluate the WHERE clause like SELECT DISTINCT
+        else:
+            q.modifier = "DISTINCT"
+
+    else:
+        traverse(q.where, functools.partial(_findVars, res=VS))
+
     # depth-first recursive generation of mapped query tree
     M = translateGroupGraphPattern(q.where)
 
diff --git a/rdflib/plugins/sparql/evaluate.py b/rdflib/plugins/sparql/evaluate.py
index aafd0fe7..06fc170d 100644
--- a/rdflib/plugins/sparql/evaluate.py
+++ b/rdflib/plugins/sparql/evaluate.py
@@ -309,7 +309,7 @@ def evalPart(ctx: QueryContext, part: CompValue):
         return evalServiceQuery(ctx, part)
 
     elif part.name == "DescribeQuery":
-        raise Exception("DESCRIBE not implemented")
+        return evalDescribeQuery(ctx, part)
 
     else:
         raise Exception("I dont know: %s" % part.name)
@@ -585,6 +585,41 @@ def evalConstructQuery(ctx: QueryContext, query) -> Dict[str, Union[str, Graph]]
     return res
 
 
+def evalDescribeQuery(ctx: QueryContext, query) -> Dict[str, Union[str, Graph]]:
+    # Create a result graph and bind namespaces from the graph being queried
+    graph = Graph()
+    # type error: Item "None" of "Optional[Graph]" has no attribute "namespaces"
+    for pfx, ns in ctx.graph.namespaces():  # type: ignore[union-attr]
+        graph.bind(pfx, ns)
+
+    to_describe = set()
+
+    # Explicit IRIs may be provided to a DESCRIBE query.
+    # If there is a WHERE clause, explicit IRIs may be provided in
+    # addition to projected variables. Find those explicit IRIs and
+    # prepare to describe them.
+    for iri in query.PV:
+        if isinstance(iri, URIRef):
+            to_describe.add(iri)
+
+    # If there is a WHERE clause, evaluate it then find the unique set of
+    # resources to describe across all bindings and projected variables
+    if query.p is not None:
+        bindings = evalPart(ctx, query.p)
+        to_describe.update(*(set(binding.values()) for binding in bindings))
+
+    # Get a CBD for all resources identified to describe
+    for resource in to_describe:
+        # type error: Item "None" of "Optional[Graph]" has no attribute "cbd"
+        graph += ctx.graph.cbd(resource)  # type: ignore[union-attr]
+
+    res: Dict[str, Union[str, Graph]] = {}
+    res["type_"] = "DESCRIBE"
+    res["graph"] = graph
+
+    return res
+
+
 def evalQuery(graph: Graph, query: Query, initBindings, base=None):
 
     initBindings = dict((Variable(k), v) for k, v in initBindings.items())
diff --git a/rdflib/plugins/sparql/parser.py b/rdflib/plugins/sparql/parser.py
index 2035b4f0..2a897f82 100644
--- a/rdflib/plugins/sparql/parser.py
+++ b/rdflib/plugins/sparql/parser.py
@@ -1479,7 +1479,7 @@ DescribeQuery = Comp(
     "DescribeQuery",
     Keyword("DESCRIBE")
     + (OneOrMore(ParamList("var", VarOrIri)) | "*")
-    + Param("datasetClause", ZeroOrMore(DatasetClause))
+    + ZeroOrMore(ParamList("datasetClause", DatasetClause))
     + Optional(WhereClause)
     + SolutionModifier
     + ValuesClause,


Test patch:
diff --git a/test/test_sparql/test_sparql.py b/test/test_sparql/test_sparql.py
index 32cc82d7..7d66f2c1 100644
--- a/test/test_sparql/test_sparql.py
+++ b/test/test_sparql/test_sparql.py
@@ -867,3 +867,95 @@ def test_queries(
     result = rdfs_graph.query(query)
     logging.debug("result = %s", result)
     assert expected_bindings == result.bindings
+
+
+@pytest.mark.parametrize(
+    ["query_string", "expected_subjects", "expected_size"],
+    [
+        pytest.param(
+            """
+            DESCRIBE rdfs:Class
+            """,
+            {RDFS.Class},
+            5,
+            id="1-explicit",
+        ),
+        pytest.param(
+            """
+            DESCRIBE rdfs:Class rdfs:subClassOf
+            """,
+            {RDFS.Class, RDFS.subClassOf},
+            11,
+            id="2-explict",
+        ),
+        pytest.param(
+            """
+            DESCRIBE rdfs:Class rdfs:subClassOf owl:Class
+            """,
+            {RDFS.Class, RDFS.subClassOf},
+            11,
+            id="3-explict-1-missing",
+        ),
+        pytest.param(
+            """
+            DESCRIBE ?prop
+            WHERE {
+                ?prop a rdf:Property
+            }
+            """,
+            {
+                RDFS.seeAlso,
+                RDFS.member,
+                RDFS.subPropertyOf,
+                RDFS.subClassOf,
+                RDFS.domain,
+                RDFS.range,
+                RDFS.label,
+                RDFS.comment,
+                RDFS.isDefinedBy,
+            },
+            55,
+            id="1-var",
+        ),
+        pytest.param(
+            """
+            DESCRIBE ?s
+            WHERE {
+                ?s a ?type ;
+                   rdfs:subClassOf rdfs:Class .
+            }
+            """,
+            {RDFS.Datatype},
+            5,
+            id="2-var-1-projected",
+        ),
+        pytest.param(
+            """
+            DESCRIBE ?s rdfs:Class
+            WHERE {
+                ?s a ?type ;
+                   rdfs:subClassOf rdfs:Class .
+            }
+            """,
+            {RDFS.Datatype, RDFS.Class},
+            10,
+            id="2-var-1-projected-1-explicit",
+        ),
+        pytest.param("DESCRIBE ?s", set(), 0, id="empty"),
+    ],
+)
+def test_sparql_describe(
+    query_string: str,
+    expected_subjects: set,
+    expected_size: int,
+    rdfs_graph: Graph,
+) -> None:
+    """
+    Check results of DESCRIBE queries against rdfs.ttl to ensure
+    the subjects described and the number of triples returned are correct.
+    """
+    r = rdfs_graph.query(query_string)
+    assert r.graph is not None
+    subjects = {s for s in r.graph.subjects() if not isinstance(s, BNode)}
+    assert subjects == expected_subjects
+    assert len(r.graph) == expected_size