duplicated hints leads to duplicated result

[khoale88]

There seems a bug in hints, as hints is duplicated, result is duplicated as well

@pytest.mark.benchmark
    @pytest.mark.parametrize("graph_type", ACCEPTED_GRAPH_TYPES)
    def test_multiple_nodes_duplicated_hinted(self, graph_type):
        """
        Test the case where multiple nodes are hinted
        """
        host = graph_type()
        host.add_node(1, name="Home")
        host.add_node(2, name="Work")
        host.add_node(3, name="School")
        host.add_node(4, name="Library")
        host.add_node(5, name="Park")
        host.add_edge(1, 2)
        host.add_edge(1, 3)
        host.add_edge(2, 4)
        host.add_edge(3, 4)
        host.add_edge(4, 5)
        host.add_edge(5, 1)

        qry = """
        MATCH (A)-[r]->(B)
        RETURN A.name, B.name
        """

        gc = GrandCypher(host)
        res = gc.run(qry, hints=[{"A": 1, "B": 2}, {"A": 3, "B": 4}, {"A": 1, "B": 2}, {"A": 3, "B": 4}])   # <<<<<<<<< duplicated hints
        assert res == {"A.name": ["Home", "School"], "B.name": ["Work", "Library"]}

here is the result

>       assert res == {"A.name": ["Home", "School"], "B.name": ["Work", "Library"]}
E       AssertionError: assert {'A.name': ['Home', 'School', 'Home', 'School'], 'B.name': ['Work', 'Library', 'Work', 'Library']} == {'A.name': ['Home', 'School'], 'B.name': ['Work', 'Library']}

[j6k4m8]

Hm this is interesting — this is maybe good? If you explicitly give duplicates in your hints I think I'd expect the query engine to return duplicated results... what do you think?

[khoale88]

I feel like we need to be careful with hinting. This might not comparable result to neo4j or cypher in general.

[khoale88]

I think we can remove duplicated hints. And if there are super/subset of hints,

For example, the below hint should return only 1 result

def test_hint_superset(self):
        host = nx.DiGraph()
        host.add_node("x", name="x")
        host.add_node("y", name="y")
        host.add_node("z", name="z")
        host.add_edge("x", "z", __labels__=set())
        host.add_edge("y", "z", __labels__=set())

        qry = """
        MATCH (A) --> (B)
        where B.name = "z"
        RETURN ID(A), ID(B)
        """
        gc = GrandCypher(host)
        gc._doublecheck_hint_result = True
        res = gc.run(qry, hints=[{"A": "x"}, {"A": "x", "B": "z"}])
        assert res == {'ID(A)': ["x"], 'ID(B)': ["z"]}

[khoale88]

I am implementing a function in Hinter class to remove duplicated/subset of hinter. This will be delivered in the next PR for "extract hints in where clause".

The argument is if we have 2 hints {A: 1} and {A:1, B:2}, the 1st one is used as it covers the second hints already.

def _is_subsumed(self, small: HINT_TYPE, big: HINT_TYPE):
        # small ⊆ big
        for k, v in small.items():
            if k not in big or big[k] != v:
                return False
        return True

def eliminate_supersets(self, hints: list[HINT_TYPE]) -> list[HINT_TYPE]:
        """check and keep only subsumed hint.

        For example:
            - This is a full set [{A:1}, {B:2}, {A:1,B:2}, {A:1,B:2,C:3}]
            - This is the result [{A:1}, {B:2}]

        """
        hints = sorted(hints, key=lambda h: len(h))
        result = []
        for hint in hints:
            # If there already exists a more general binding, skip
            subsumed = False
            for res in result:
                # res is always <= b in size
                if self._is_subsumed(res, hint):
                    subsumed = True
                    break
            if not subsumed:
                result.append(hint)

        return result

[j6k4m8]

Ah, this is very smart!

My original idea was that you say, for example, "In the motif ABCD I propose the identities of ABC; tell me the remaining options for D." I like your solution way more! And I imagine it is much more compute-efficient at query-time.

[khoale88]

this is trival with hinter module. we can basically called

hints = self._hints or []
if len(hints) > 1:
    hints = hinter.eliminate_supersets(self._hints)