如何使用 Django 和 Postgres 数据库解决 Horn 子句式标签含义

Question

我正在使用 Django 创建一个内容系统，用户可以在其中创建和发布内容。用户创建的每个文档可以有多个标签。我正在设计一个标签暗示系统，其中某些标签可以暗示其他标签的存在。

举一个简单的例子，假设“color”和“red”是标签。存在以下含义：“红色”意味着“颜色”。当用户用“红色”标记其文档时，它还会自动添加一个“颜色”标记。影响是全球性的，适用于每个用户和文档。

我想做的是让标签含义更强大，我希望能够要求存在多个标签来暗示另一个标签，例如Definite Horn 子句。

例如，我想要一个暗示，其中“红色”和“蓝色”的存在意味着标签“multiple_colors”。这可以写成像 Horn 子句一样：“red”，“blue”->“multiple_colors”。

使用Postgres和Django实现标签暗示解析，只有单个标签就可以暗示一个标签很容易实现。您只需拥有一个 Django 模型即可：

class Tag(Model):
    name = CharField()

class TagImplication(Model):
    antecedent = ForeignKey(Tag)
    consequent = ForeignKey(Tag)

要解析给定一组标签的所有隐含标签，需要采用迭代方法。您从一组标签开始，使用模型将隐含标签添加到该组标签中，然后重复直到没有添加新标签。它类似于标签含义有向图中标签的广度优先累积。

当允许类似 Horn 子句的标签含义时，模型变得更加复杂：

class Tag(Model):
    name = CharField()

class TagImplication(Model):
    consequent = ForeignKey(Tag)

class TagImplicationAntecedent(Model):
    implication = ForeignKey(TagImplication)
    antecedent = ForeignKey(Tag)

要使 TagImplication 暗示其后续标签，所有子 TagImplicationAntecedents 的先行词必须与现有/断言标签匹配。我相信，当提供一组标签（就像非 Horn 子句版本一样）时，还需要一种迭代方法来解决所有影响。

问题

如何有效地使用 Django 查询来计算类似 Horn 子句含义的标签含义的迭代？我有一个起草的算法，但查询的数量可能与算法开始的标签数量以及数据库中定义的含义数量成正比。我担心数据库性能。理想的解决方案是每次迭代使用一个查询。也许有更好的解决方案，必须使用原始 SQL 或跳过算法中的手动迭代步骤。

我起草的内容

这是我起草的一个算法，它使用 Django 查询来执行具有类似 Horn 子句含义的标签含义解析的单次迭代。 （伪Python代码）

# Let 'tags' be the set of tags that we currently have. At the end of this iteration, 'tags' will also have the directly implied tags.
tags: Set[Tag] = <current tags>
starting_tag_count = len(tags)

# Get candidate TagImplications.
# These TagImplications have at least one Antecedent matched from 'tags'
# this uses reverse relationships to query: https://docs.djangoproject.com/en/4.2/topics/db/queries/#lookups-that-span-relationships
canidate_imps = TagImplication.objects.filter(
    Q(tag_implication_antecedent__antecedent=tags[0]
    |
    ...
    |
    Q(tag_implication_antecedent__antecedent=tags[n]
)

# Get the implications that have satisfied all of their antecedents.
satisfied_imps: List[TagImplication] = []
for imp in canidate_imps:
    # this query performance being called repeatedly worries me when there are a large number of implications defined.
    # I assume that this query is easy to cache?
    # What is worse is that this loop is run for each iteration of the resolution algorithm. Each algorithm iteration can increse the number of tags and canidate implications.
    antecedents = TagImplicationAntecedent.objects(
        implication=imp
    )
    satisfied = True
    for ant in antecedents:
        if ant.antecedent not in tags:
            satisfied = False
    if satisfied:
        satisfied_imps.append(imp)

# add implied tags to current tags
for imp in satisfied_imps:
    tags.append(imp.consequent)

if starting_tag_count == len(tags):
    # stop algorithm
else:
    # do another algorithm iteration. Go to the top.

Answer 1

这类似于标签含义有向图中标签的广度优先累积。

因此，我不会尝试在数据库引擎内执行此操作，因为虽然数据库非常适合存储图的定义，但它不太擅长运行图论算法。

相反：

• 将图规范从数据库加载到任何合适的图论库中。也许您只需要执行一次。

• 使用图论库方法运行“标签广度优先累积标签广度优先累积”算法

• 将结果（新标签分配）存储到数据库

这将具有更好的性能（因为图论库中的图存储针对运行图论方法进行了优化），需要更少且更易于理解的代码，并最大限度地减少所需的测试和调试量（假设您可以信任该图）理论库）。