Обновления сохраненных запросов в реальном времени для большого графа

Изобретение относится к автоматическому обновлению результатов сохраненных запросов для графа данных в ответ на обновление графа. Техническим результатом является обеспечение возможности обновления в реальном времени результатов сохраненных запросов за счет минимизации количества дополнительных поисков, требуемых для поддержания корректных результатов сохраненных запросов. Система для обновления результатов сохраненных запросов в реальном времени идентифицирует целевое ограничение в ответ на обновление графа данных. Целевое ограничение определяет путь в графе данных, который включает в себя ребро, определенное в обновлении. Система определяет состояние для целевого ограничения посредством обхода графа через путь и определяет на основе состояния, что свернутое определение для первого запроса, который включает в себя ограничение, указывает, что узел-элемент отвечает на первый запрос. Затем система обновляет результат сохраненного запроса для первого запроса с использованием узла-элемента, идентифицированного во время обхода, в соответствии со свернутым определением. 3 н. и 18 з.п. ф-лы, 10 ил.

 

Перекрестная ссылка на родственную заявку

[0001] Эта заявка испрашивает приоритет обычной заявки на патент США № 14/306969, поданной 17 июня 2014 года, озаглавленной REAL-TIME SAVED-QUERY UPDATES FOR A LARGE GRAPH (ОБНОВЛЕНИЯ СОХРАНЕННЫХ ЗАПРОСОВ В РЕАЛЬНОМ ВРЕМЕНИ ДЛЯ БОЛЬШОГО ГРАФА), которая полностью включена в настоящую заявку посредством ссылки.

Уровень техники

[0002] Основанные на большом графе базы знаний представляют фактическую информацию о мире. Например, в графе данных объекты, такие как люди, места, фразы, слова, классы, факты, сущности, концепции и т.д., могут быть сохранены как узлы, и ребра между узлами могут указывать соотношение между объектами. Базовым блоком такого графа данных может являться тройка, которая включает в себя два узла, или объекта, и метку ребра. Первый узел иногда называется исходным узлом или узлом-субъектом, и второй узел иногда называется целевым узлом или узлом-объектом. Безусловно, тройка может включать в себя дополнительную информацию, такую как метаданные об объектах и/или соотношении, в дополнение к идентификации субъекта, предиката и объекта.

[0003] Пользователи могут определять запросы или коллекции для графа. Коллекция или запрос определяет ограничения, которым узел должен удовлетворять, чтобы являться элементом множества узлов, отвечающих на запрос. Ограничения обычно определяют, какое соотношение (соотношения) узел должен иметь или не иметь, чтобы являться элементом результатов запроса, например, элементом коллекции. Такие запросы (т.е. коллекции) экстенсивно используются при поиске, анализе данных, планировании объявлений, в системах рекомендаций и т.д., и принадлежность часто сохраняется, поскольку в большом графе вычисление принадлежности может быть затратным. Но по мере добавления или удаления узлов и соотношений в графе сохраненные элементы могут стать неактуальными, особенно в больших графах, которые часто обновляются.

Сущность изобретения

[0004] Некоторые реализации позволяют системе обновлять результаты сохраненных запросов в реальном времени по мере обновления ребер, например, по мере добавления троек в хранилище данных или удаления троек из хранилища данных на основе графа. Реальное время может включать в себя малую задержку (например, меньше одной минуты), чтобы позволить системе сгруппировать обновления по исходному узлу тройки. Запросы могут быть определены посредством ограничений, которые идентифицируют свойства или соотношения, которые узел должен иметь (или не иметь) в графе, чтобы относиться к результату для сохраненного запроса. Сохраненный запрос может быть определен ограничительным выражением, которое является последовательностью ограничений, соединенных логическими операциями, другими словами, булевым выражением ограничений. Система может включать в себя индекс ограничений, который индексирован по ребрам. Система может использовать индекс, чтобы определить, какие ограничения соответствуют ребру из обновленной тройки, тем самым идентифицируя целевые ограничения для этой тройки. Система использует целевые ограничения, чтобы эффективно определять, какие сохраненные результаты запросов затронуты обновлением, и приводит ли обновление к изменению результатов. Группируя обновления по субъектам, система может повторно использовать работу, например, прямые и обратные обходы в графе, при идентификации и оценке результатов запроса, затронутых обновлениями.

[0005] Один аспект раскрытия может быть воплощен в системе, которая включает в себя по меньшей мере один процессор и один или более блоков памяти. Один или более блоков памятей могут хранить граф данных, который включает в себя узлы, соединенные ребрами, и множество сохраненных запросов, каждый запрос определен одним или более ограничениями, которые должны быть удовлетворены для принадлежности результатам запроса для запроса, каждое ограничение определяет по меньшей мере одно из ребер. Один или более блоков памяти также могут хранить инструкции, которые при их исполнении по меньшей мере одним процессором побуждают компьютерную систему выполнять операции. Операции могут включать в себя идентификацию целевого ограничения в ответ на операцию, которая обновляет граф данных, с помощью исходного узла, ребра обновления и целевого узла, целевое ограничение определяет путь, который включает в себя ребро обновления и целевое ограничение, принадлежащее первому сохраненному запросу из множества сохраненных запросов. Операции также могут включать в себя оценку целевого ограничения для узла-элемента, чтобы определить состояние для целевого ограничения, посредством обхода графа через путь целевого ограничения, определение, указывает ли свернутое определение для первого сохраненного запроса на основе состояния, что узел-элемент отвечает или не отвечает на первый сохраненный запрос, и обновление результата сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, что узел-элемент отвечает или не отвечает.

[0006] Система может включать в себя один или более следующих признаков. Например, целевым ограничением может являться первое целевое ограничение, и операции также могут включать в себя идентификацию второго целевого ограничения, принадлежащего первому сохраненному запросу, второе целевое ограничение определяет путь, включающий в себя ребро обновления, второе целевое ограничение имеет длину пути больше, чем длина пути первого целевого ограничения, и установку состояния для второго целевого ограничения как состояния, указывающего, что второе целевое ограничение не разрешено. Кроме того, состоянием может являться первое состояние, и операции также могут включать в себя определение, что свернутое определение для первого сохраненного запроса на основе первого состояния не указывает, отвечает или не отвечает узел-элемент на первый сохраненный запрос, оценку второго целевого ограничения для узла-элемента, чтобы определить второе состояние для второго целевого ограничения посредством обхода графа через путь второго целевого ограничения, определение, указывает ли свернутое определение для первого запроса на основе первого состояния и второго состояния, что узел-элемент отвечает или не отвечает на первый сохраненный запрос, и обновление результата сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, что узел-элемент отвечает или не отвечает на первый сохраненный запрос.

[0007] В качестве другого примера один или более блоков памяти также могут хранить индекс ограничений по ребрам, индекс используется для идентификации целевого ограничения. В качестве другого примера операции также могут включить в себя сохранение результатов обхода графа данных и использование сохраненных результатов для оценки второго целевого ограничения, которое определяет путь, который включает в себя путь целевого ограничения. В качестве другого примера обновлением может являться первое обновление, и операции могут включать в себя сохранение результатов обхода графа данных и удаление сохраненных результатов, когда последующее обновление графа данных включает в себя исходный узел, который отличается от исходного узла первого обновления.

[0008] В качестве другого примера целевым ограничением может являться первое целевое ограничение, и состоянием может являться первое состояние, и операции могут включать в себя сохранение результата обхода графа в памяти, идентификацию второго целевого ограничения для первого запроса, второе целевое ограничение имеет путь, который включает в себя путь первого целевого ограничения, и использование сохраненного результата обхода при оценке второго целевого ограничения, чтобы определить второе состояние для второго целевого ограничения. Операции могут дополнительно включать в себя определение, указывает ли свернутое определение для первого сохраненного запроса на основе первого состояния и второго состояния, что узел-элемент отвечает или не отвечает на первый сохраненный запрос, и обновление результата сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, что узел-элемент отвечает или не отвечает на первый сохраненный запрос.

[0009] В качестве другого примера целевым ограничением может являться первое целевое ограничение, и операции также могут включать в себя идентификацию множества целевых ограничений, первым целевым ограничением является одно из множества целевых ограничений, множество целевых ограничений предназначено по меньшей мере для двух запросов, и первым сохраненным запросом является один из по меньшей мере двух запросов. Операции также могут включать в себя интеллектуальную оценку множества целевых ограничений, чтобы отсрочить обходы для целевых ограничений с более длинными путями.

[00010] В другом аспекте реализованный с помощью компьютера способ включает в себя идентификацию с использованием по меньшей мере одного процессора целевого ограничения, целевое ограничение определяет путь в графе данных, который включает в себя ребро, определенное в обновлении графа данных, идентификация инициируется посредством обновления, и определение использованием по меньшей мере одного процессора состояния для целевого ограничения посредством обхода графа через путь. Способ также включает в себя определение на основе состояния, что свернутое определение для первого запроса, который включает в себя ограничение, указывает, что узел-элемент отвечает на первый запрос, и обновление результата сохраненного запроса для первого запроса с использованием узла-элемента, идентифицированного во время обхода, в соответствии со свернутым определением. В некоторых реализациях целевое ограничение идентифицируется с использованием индекса множества ограничений, индекс организован по ребрам. Когда обновление включает в себя добавление ребра обновления между исходным узлом и целевым узлом, обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя добавление узла-элемента в результат сохраненного запроса. Когда обновление включает в себя удаление ребра обновления между исходным узлом и целевым узлом, обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя поддержание результата сохраненного запроса.

[00011] Способ может включить в себя один или более следующих признаков. Например, целевым ограничением может являться первое целевое ограничение, и способ дополнительно включает в себя идентификацию второго целевого ограничения, принадлежащего первому запросу, второе целевое ограничение определяет путь, включающий в себя ребро обновления, второе целевое ограничение имеет длину пути, которая больше, чем длина пути первого целевого ограничения, и установку состояния для второго целевого ограничения как состояния, указывающего, что второе целевое ограничение не разрешено. В некоторых реализациях состоянием может являться первое состояние, и способ дополнительно включает в себя определение, что свернутое определение для первого запроса на основе первого состояния не способно указать, отвечает или не отвечает узел-элемент на первый запрос, оценку второго целевого ограничения для узла-элемента, чтобы определить второе состояние для второго целевого ограничения посредством обхода графа через путь второго целевого ограничения, определение, что свернутое определение для первого запроса на основе первого состояния и второго состояния указывает, что узел-элемент отвечает на первый запрос, и обновление результата сохраненного запроса первого запроса с помощью узла-элемента в соответствии со свернутым определением.

[00012] В качестве другого примера целевым ограничением может являться первое целевое ограничение, состоянием может являться первое состояние, и способ также включает в себя сохранение результата обхода графа, идентификацию второго целевого ограничения для первого запроса, второе целевое ограничение имеет путь, который включает в себя путь первого целевого ограничения, и использование сохраненного результата обхода при оценке второго целевого ограничения, чтобы определить второе состояние для второго целевого ограничения. В таких реализациях определение, что свернутое определение для первого запроса указывает, что узел-элемент отвечает на первый запрос, основано на первом состоянии и втором состоянии.

[00013] В качестве другого примера способ также может включать в себя группировку множества обновлений графа данных по исходному узлу, множество обновлений происходят в течение пяти минут друг за другом, и обновление графа данных является одним из множества обновлений, причем идентификация целевого ограничения происходит в реальном времени после группировки.

[00014] В другом аспекте способ включает в себя идентификацию целевого ограничения с использованием по меньшей мере одного процессора, целевое ограничение определяет путь в графе данных, который включает в себя ребро обновления, в ответ на операцию, которая обновляет граф данных, с помощью исходного узла, ребра обновления и целевого узла. Способ также включает в себя определение с использованием по меньшей мере одного процессора состояния для целевого ограничения посредством обхода графа через путь, определение, что свернутое определение на основе состояния для первого запроса, который включает в себя ограничение, указывает, что узел-элемент не отвечает на первый запрос, и обновление результата сохраненного запроса для первого запроса с использованием узла-элемента, идентифицированного во время обхода, в соответствии со свернутым определением.

[00015] В некоторых реализациях обновление представляет собой удаление ребра обновления между исходным узлом и целевым узлом, и обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя удаление узла-элемента из результата сохраненного запроса. В некоторых реализациях обновление представляет собой добавление ребра обновления между исходным узлом и целевым узлом, и обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя поддержание результата сохраненного запроса.

[00016] В другом общем аспекте компьютерный программный продукт, воплощенный на непереходном машиночитаемом запоминающем устройстве, включает в себя инструкции, которые при их исполнении по меньшей мере одним процессором, сформированным в подложке, побуждают вычислительное устройство выполнять любые из раскрытых способов, операций или процессов. Другой общий аспект включает в себя систему и/или способ обновления результатов сохраненных запросов в режиме реального времени, в значительной степени как показано по меньшей мере на одной из фигур и/или описано в отношении по меньшей мере одной из фигур, и как более полно изложено в формуле изобретения.

[00017] Одна или более реализаций описанного здесь предмета могут быть осуществлены таким образом, чтобы реализовать одно или более следующих преимуществ. В качестве одного примера система может обновлять результаты сохраненных запросов в реальном времени, и это означает, что процесс для обновления результатов сохраненных запросов начинается в течение нескольких минут после обновления и инициируется обновлением вместо ожидания периодического, офлайнового пакетного процесса для обновления принадлежности. Реализации могут быстро и эффективно оценивать целевые ограничения, делая возможными обновления в реальном времени результатов сохраненных запросов. Другими словами, система минимизирует количество дополнительных поисков, требуемых для поддержания корректных результатов сохраненных запросов посредством использования информации при обновлении графа, чтобы идентифицировать минимальное количество дополнительных ограничений в затронутых запросах для оценки и группирования обновлений графа, чтобы повторно использовать результат предыдущей работы. Другие признаки будут очевидны из описания, рисунков и формулы изобретения.

Краткое описание чертежей

[00018] Фиг. 1 демонстрирует примерную систему в соответствии с некоторыми реализациями.

[00019] Фиг. 2 демонстрирует представление примерного графа данных с объектами как узлами и соотношениями как ребрами между узлами.

[00020] Фиг. 3 демонстрирует пример сохраненных запросов и индекс ребер запросов, совместимые с раскрытыми реализациями.

[00021] Фиг. 4 демонстрирует блок-схему последовательности операций примерного процесса для эффективного обновления принадлежности запроса в реальном времени, совместимого с раскрытыми реализациями.

[00022] Фиг. 5 демонстрирует блок-схему последовательности операций примерного процесса для интеллектуальной оценки ограничения после добавления ребра к графу, совместимого с раскрытыми реализациями.

[00023] Фиг. 6 демонстрирует блок-схему последовательности операций примерного процесса для интеллектуальной оценки ограничения после удаления ребра из графа, совместимого с раскрытыми реализациями.

[00024] Фиг. 7 демонстрирует пример обновления принадлежности запроса в реальном времени после удаления ребра в графе данных на фиг. 2.

[00025] Фиг. 8 демонстрирует пример обновления принадлежности запроса в реальном времени после добавления ребра в графе данных на фиг. 2.

[00026] Фиг. 9 показывает пример компьютерного устройства, которое может использоваться для реализации описанных методик.

[00027] Фиг. 10 показывает пример распределенного компьютерного устройства, которое может использоваться для реализации описанных методик.

[00028] Аналогичные символы на разных чертежах указывают аналогичные элементы.

Подробное описание

[00029] Фиг. 1 является блок-схемой системы 100 в соответствии с примерной реализацией. Система 100 обновляет результаты сохраненных запросов в реальном времени в ответ на обновления ребер в графе данных. Система на фиг. 1 является одной примерной реализацией, и могут использоваться другие конфигурации и приложения. Хотя система 100 может использоваться для поддержания сохраненных результатов запроса актуальными в любом графе данных, система 100 особенно полезна для больших графов, поскольку время обработки для определения результатов запросов в таких графах часто является чрезмерно затратным по стоимости и по времени.

[00030] Система 100 может представлять собой вычислительное устройство или устройства, которые принимают форму многих разных устройств. Например, система 100 может представлять собой стандартный сервер, группу таких серверов, системы клиент-сервер или серверную систему в стойке. Кроме того, система 100 может быть реализована в персональном компьютере. Система 100 может являться примером компьютерного устройства 900, изображенного на фиг. 9, или компьютерного устройства 1000, изображенного на фиг. 10.

[00031] Система 100 может включать в себя подсистему 110 графа и подсистему 150 сохраненных запросов. В некоторых реализациях каждая из подсистемы 110 графа и подсистемы 150 сохраненных запросов может представлять собой отдельное вычислительное устройство, или они могут совместно использовать компоненты, такие как процессоры и память. Например, подсистема 110 графа и подсистема 150 сохраненных запросов могут быть реализованы в персональном компьютере, сервере, одном или нескольких логических разделов компьютера и т.д. В некоторых реализациях одна или более из подсистемы 110 графа и подсистемы 150 сохраненных запросов могут представлять собой распределенные системы, реализованные в последовательности вычислительных устройств, таких как группа серверов, таких как компьютерное устройство 1000, изображенное на фиг. 10.

[00032] Система 100 может включать в себя хранилище 190 данных на основе графа. Хранилище данных на основе графа представляет собой граф данных, который хранит информацию в форме узлов и ребер, и узлы соединены ребрами. Узел в графе данных может представлять объект, например, человека, место, элемент, слово, фразу, идею, тему, абстрактное понятие, конкретный элемент, другую подходящую сущность или любую их комбинацию или свойство объекта. Таким образом, узлы могут называться объектами и наоборот. Объекты в графе могут быть соотнесены друг с другом с помощью ребер, которые могут представлять соотношения между объектами. Например, граф данных может иметь объект, который соответствует Аврааму Линкольну, и граф данных может иметь соотношение "вид_деятельности" между объектом "Авраам Линкольн" и объектом "Президент" и другое такое соотношение между объектом "Авраам Линкольн" и объектом "Адвокат". Подсистема индексации может поддерживать хранилище 190 данных на основе графа, чтобы позволить поисковой подсистеме осуществлять поиск в графе данных, например, находя объекты, относящиеся к другим объектам посредством одного или более соотношений или путей в графе. В некоторых реализациях подсистема индексации и/или поисковая подсистема могут быть включены в подсистему 110 графа. Хранилище 190 данных на основе графа может включать в себя индекс или некоторый другой способ поиска и извлечения данных из хранилища данных.

[00033] Хранилище 190 данных на основе графа может включать в себя информацию, из которой может быть создан граф, такой как граф 200, проиллюстрированный на фиг. 2. Используемая здесь ссылка на граф данных может рассматриваться как ссылка на индекс для графа данных и наоборот. Узлы графа данных могут называться объектами, и ребра могут называться соотношениями между двумя объектами. Используемый здесь термин "объект" может относиться к физическому воплощению человека, места или сущности, или к представлению физического объекта, например, к тексту или другой информации, которая относится к объекту. Например, объект может являться физическим местоположением во Франции или абстрактным понятием, которое относится к Франции. Подсистема 110 графа может включать в себя пользовательский интерфейс, который позволяет пользователям, например, пользователям клиента 170, искать, обновлять и иным образом поддерживать информацию в хранилище 190 данных на основе графа. Подсистема 110 графа также может включать в себя пакетные или офлайновые процессы, которые обновляют хранилище 190 данных на основе графа. Подсистема 110 графа может представлять собой отдельное вычислительное устройство со своим собственным аппаратным процессором 113 и памятью 114 или оно может совместно использовать один или несколько аппаратных процессоров и память с другими компонентами системы 100.

[00034] Система 100 также может включать в себя сохраненные запросы 140. Запрос определен посредством ограничительного выражения, которое может представлять собой одно ограничение или булево выражение из ограничений. Ограничительное выражение определяет запрос и, таким образом, может называться определением запроса или коллекции. Ограничительное выражение представляет условия, которым объект в хранилище 190 данных на основе графа должен удовлетворять, чтобы считаться отвечающим на запрос и включенным в результаты запроса, т.е. в качестве элемента результатов запроса. В этом смысле запрос может считаться коллекцией, а объекты, отвечающие на запрос - элементами коллекции. Таким образом, сохраненные запросы 140 могут называться сохраненными принадлежностями коллекции.

[00035] Ограничение связано с путем в графе. Путь часто имеет единичную длину, но может иметь большую длину. Ограничение может включать в себя логические операторы, такие как "равно" (==), "не равно" (!=), и может определять или не определять целевой узел. Примерами ограничения с единичной длиной пути являются ограничение "родитель" != "пусто", означающее, что узел должен быть соединен с другим узлом ребром "родитель", ограничение "родственник" == "пусто", означающее, что узел не должен иметь ребра "родственник", и ограничение "родитель" == "Джон Доу", означающее, что узел должен быть соединен с узлом "Джон Доу" посредством ребра "родитель". Ограничение также может включать в себя более длинный путь, такой как "выпускники.родитель.вид_деятельности"="Президент". Узел, удовлетворяющий этому ограничению, будет узлом, соединенным с первым целевым узлом соотношением "выпускники", при этом первый целевой узел соединен со вторым целевым узлом соотношением "родитель", и второй целевой узел соединен с узлом "Президент" соотношением "вид_деятельности". Ограничения могут быть объединены в ограничительное выражение с использованием других логических операторов, таких как "и" (&&), "или" (||) и т.д.

[00036] Система 100 может факультативно включать в себя индекс 145 ребер запросов. Индекс 145 ребер запросов может индексировать ограничения в сохраненных запросах 140 с помощью ребра. Индекс 145 ребер запросов может улучшить время обработки при определении, какие сохраненные запросы потенциально затронуты обновлением хранилища 190 данных на основе графа, но система 100 также может просто считывать ограничения из сохраненных запросов 140, чтобы определить, какие сохраненные запросы потенциально затронуты.

[00037] Фиг. 3 иллюстрирует пример информации, которая может храниться в сохраненных запросах 140, и индекс 145 ребер запросов, совместимый с раскрытыми реализациями. Сохраненные запросы 340 могут включать в себя идентификатор 305 запроса, который может включать в себя название запроса. Каждый запрос может быть определен одним или более ограничениями 310, которые могут быть объединены в ограничительное выражение 315 с использованием логических операторов. Ограничения 310 могут представлять единичную длину пути, например, "вид_деятельности" == "Президент", или большую длину пути, например, "выпускники.родитель.год_рождения.китайский_зодиак" == "бык". Для объекта, который будет считаться отвечающим на запрос, ограничительное выражение 315 должно быть расценено как "истина" для объекта.

[00038] Пример пяти сохраненных запросов проиллюстрирован в сохраненных запросах 340. Запрос Q1 иллюстрирует ограничение, которое не определяет целевой узел. Например, ограничение "год_смерти"="пусто" указывает, что узел, удовлетворяющий этому ограничению, не будет иметь ребра "год_смерти". С другой стороны, если сохраненный запрос был для умерших президентов, ограничение может представлять собой "год_смерти" != "пусто", и это означает, что узел, который удовлетворяет этому ограничению, должен иметь соотношение "год_смерти" с другим узлом, но какой это узел, не имеет значения. Запрос Q5 иллюстрирует сохраненный запрос только одним ограничением в ограничительном выражении.

[00039] Фиг. 3 также демонстрирует примерный индекс 345 ребер запросов. Индекс 345 ребер запросов является факультативным, и реализации могут не включать в себя индекс 345 ребер запросов. Индекс 345 ребер запросов хранит ограничения для каждого сохраненного запроса посредством ребра. Таким образом, например, в индексе 345 ребер запросов имеется запись "вид_деятельности". Каждое ограничение для записи "вид_деятельности" включает в себя идентификатор запроса для ограничения и само ограничение. Ограничения с единичной длиной, безусловно, связаны с записью ребра, которая связана с путем. Таким образом, ограничение "вид_деятельности" == "Президент" из запроса Q1 включено в записи для ребра вида деятельности. Если ребро вида деятельности имеет место в ограничении с более длинным путем, ограничение также включено в записи ребра. Таким образом, например, ограничение "выпускники.супруг.вид_деятельности" == "Президент из запроса Q3 также включено в запись "вид_деятельности". Это ограничение также включено в записи для ребра "выпускники" и ребра "супруг". Таким образом, когда ребро обновляется (например, добавляется или удаляется) в хранилище данных на основе графа, система может использовать индекс 345 ребер запросов, чтобы быстро идентифицировать все сохраненные запросы и целевые ограничения из сохраненных запросов, потенциально затронутых обновлением. Безусловно, в реализации без индекса 345 ребер запросов система может исследовать сохраненные запросы 340, чтобы получить ту же самую информацию.

[00040] Возвращаясь к фиг. 1, можно видеть, что система 100 также включает в себя результаты 160 сохраненных запросов. Результаты 160 сохраненных запросов идентифицируют объекты в хранилище 190 данных на основе графа, которые отвечают на запросы, идентифицированные в сохраненных запросах 140. Хотя нет необходимости для каждого сохраненного запроса иметь соответствующие элементы в результатах 160 сохраненных запросов, вследствие продолжительности времени обработки для определения результатов запроса для всех узлов в большом графе данных многие, если не все, запросы в сохраненных запросах 140 имеют соответствующие результаты, сохраненные в результатах 160 сохраненных запросов. Таким образом, система может однажды определить принадлежность к результатам запроса с использованием всего хранилища 190 данных на основе графа однажды и обновляет принадлежность по мере возникновения обновлений хранилища 190 данных на основе графа. Результаты 160 сохраненных запросов могут иметь различные форматы. В качестве одного примера каждый сохраненный запрос может быть представлен как узел в хранилище 190 данных на основе графа, и объекты, отвечающие на сохраненный запрос, могут совместно использовать ребро с узлом для сохраненного запроса. Таким образом, в некоторых реализациях результаты 160 сохраненных запросов могут являться подмножеством хранилища 190 данных на основе графа. Такая реализация проиллюстрирована в графе 200 на фиг. 2 как узел "Первые семьи" и ребра, соединяющие этот узел с другими узлами в графе 200. В качестве другого примера результаты 160 сохраненных запросов могут являться файлом или базой данных, устанавливающими соотношение идентификатора запроса с идентификаторами узлов, которые отвечают на запрос (например, результат сохраненного запроса).

[00041] Хранилище 190 данных на основе графа, результаты 160 сохраненных запросов, сохраненные запросы 140 и индекс 145 ребер запросов хранятся на материальных машиночитаемых запоминающих устройствах, например, на диске, во флэш-памяти, в кэш-памяти или их комбинации, выполненных с возможностью хранить данные в полупостоянной или непереходной форме. В некоторых реализациях хранилище 190 данных на основе графа, результаты 160 сохраненных запросов, сохраненные запросы 140 и индекс 145 ребер запросов могут быть сохранены в комбинации различных видов памяти и/или могут быть сохранены распределенным образом на нескольких физических или логических вычислительных устройствах.

[00042] Система 100 может включать в себя подсистему 150 сохраненных запросов. Подсистема 150 сохраненных запросов может включать в себя один или несколько аппаратных процессоров 153, выполненных с возможностью исполнять одну или более исполняемых на машине инструкций, или фрагменты программного обеспечения, программно-аппаратного обеспечения или их комбинации для приема сохраненных запросов 140 и обновления результатов 160 сохраненных запросов по мере обновления хранилища 190 данных на основе графа. Подсистема 150 сохраненных запросов может иметь свои собственные процессор и память, или она может совместно использовать один или более процессоров и память с другими компонентами системы 100. Подсистема 150 сохраненных запросов может собирать обновления хранилища 190 данных на основе графа, использовать обновления для идентификации сохраненных запросов, на которые повлияли обновления, и в случае необходимости модифицировать сохраненные результаты (например, принадлежность) затронутых запросов. Для обработки обновлений хранилища 190 данных на основе графа эффективным образом подсистема 150 сохраненных запросов может хранить и повторно использовать результаты поисков в графе. Подсистема 150 сохраненных запросов может сохранить результаты предыдущих поисков в графе во временных результатах 147 поиска. В некоторых реализациях предыдущие поиски могут быть сохранены посредством исходного узла, например, узла, с которого начался поиск. Поиск в графе представляет собой прямой или обратный обход графа, начинающийся от исходного узла и следующий по всем возможным путям, которые соответствуют критериям поиска. Поскольку обходы графа могут занимать много времени, сохранение обходов, относящихся к обновленному ребру, для повторного использования может значительно улучшить производительность подсистемы 150 сохраненных запросов при определении обновлений результатов 160 сохраненных запросов. В некоторых реализациях временные результаты 147 поиска могут быть удалены, когда исходный узел для обновления изменяется. Таким образом, в реализации, в которой система группирует обновления по исходному узлу, предыдущие поиски могут использоваться по обновлениям. В некоторых реализациях подсистема 150 сохраненных запросов может включать в себя пользовательский интерфейс (UI) сохраненных запросов, который принимает определения запроса, например, от клиента 170. Подсистема 150 сохраненных запросов может использовать хранилище 190 данных на основе графа для офлайнового определения результатов сохраненных запросов для недавно введенного сохраненного запроса.

[00043] Система 100 также может включать в себя другие компоненты, не проиллюстрированные для краткости. Например, система 100 может включать в себя подсистему индексации для создания и поддержания хранилища 190 данных на основе графа. Подсистема индексации может получать информационное содержание, например, из одного или более серверов и использовать информационное содержание, чтобы поддерживать хранилище 190 данных на основе графа. В некоторых реализациях серверы могут представлять собой веб-серверы, серверы в частной сети или другие источники, которые доступны для подсистемы индексации. Подсистема индексации может представлять собой одно или более отдельных вычислительных устройств, и в некоторых реализациях подсистема 110 графа может включать в себя подсистему индексации для хранилища 190 данных на основе графа. Система 100 также может включать в себя поисковую подсистему, которая использует хранилище 190 данных на основе графа, чтобы определять результаты поиска для запросов с использованием традиционных или других методик информационного поиска. В некоторых реализациях поисковая подсистема также может использовать результаты 160 сохраненных запросов для определения результатов поиска.

[00044] Система 100 может осуществлять связь с клиентом (клиентами) 170 по сети 180. Сеть 180 может представлять собой, например, Интернет, или сеть 180 может являться проводной сетью или беспроводной локальной сетью (LAN), широкомасштабной сетью (WAN) и т.д., реализованными с использованием, например, устройств шлюзов, мостов, переключателей и/или т.д. Через сеть 180 подсистема 110 графа и/или подсистема 150 сохраненных запросов могут осуществлять связь с клиентами 170 и передавать данные клиентам 170.

[00045] Фиг. 4 иллюстрирует блок-схему последовательности операций примерного процесса 400 для эффективного обновления результатов сохраненных запросов в реальном времени, совместимого с раскрытыми реализациями. Процесс 400 может быть выполнен системой, такой как система 100 на фиг. 1. Система может использовать процесс 400 для обновления результатов сохраненных запросов в реальном времени по мере того, как происходят обновления хранилища данных на основе графа, вместо того, чтобы ожидать периодического пакетного или офлайнового процесса обновления. Это позволяет системе избежать устаревания данных в принадлежности сохраненных запросов. В некоторых реализациях процесс 400 может быть выполнен подсистемой сохраненных запросов.

[00046] Процесс 400 может начаться с приема системой обновления графа, которое идентифицирует исходный узел, ребро и целевой узел (этап 405). В некоторых реализациях система может принять несколько обновлений графа и сгруппировать обновления по исходному узлу таким образом, чтобы все обновления, подразумевающие один и тот же исходный узел, были сгруппированы. Например, вместо того чтобы сразу переходить к работе после возникновения обновления графа, система может иметь малую задержку, например, до одной минуты, во время которой можно собрать обновления. Таким образом, система может использовать в своих интересах несколько обновлений, которые подразумевают один и тот же исходный узел. Система может выбрать одно или более обновлений в сгруппированных обновлениях для обработки. Например, для обновлений, которые подразумевают один и тот же исходный узел, система может выполнять процесс 400 параллельно. Затем система может идентифицировать ограничения, потенциально затронутые обновлением, также называемые целевыми ограничениями (этап 410). Целевое ограничение является ограничением, определяющим путь, который включает в себя ребро, идентифицированное в обновленной тройке.

[00047] Как только система идентифицировала целевые ограничения (например, ограничения, которые идентифицируют ребро в обновлении графа), система может определить состояние для каждого из целевых ограничений (этап 415). Состоянием ограничения является "истина", "ложь" или "неизвестно". Состояние "истина" указывает, что имеется по меньшей мере один метод удовлетворить ограничению в хранилище данных на основе графа. Например, если узел в хранилище данных на основе графа удовлетворяет ограничению с использованием добавленного ребра или удовлетворяет ограничению даже после того, как ребро удалено, ограничение является удовлетворенным. В качестве другого примера, если ограничение является отрицанием, отсутствие подграфа несмотря на добавленное ребро может удовлетворить ограничению. В случае ограничения с обратным поиском (например, исходный узел добавленного ребра является промежуточным узлом в ограничении), обратный поиск может означать, что ограничение имеет состояние "истина" более чем для одного узла. Это будет описано более подробно в отношении фиг. 7 и 8. Состояние "ложь" для ребра означает, что обновленное ребро не удовлетворяет ограничению. Состояние "неизвестно" указывает, что необходимы дополнительные поиски. Система может отсрочить поиск в графе для ограничения, которое имеет несколько отрезков пути, для эффективности, например, если ограничение является одной из строк ограничений, соединенных операциями "или", и другие ограничения имеют более короткие пути или сохраненные результаты поиска. Поскольку поиски в графе с несколькими отрезками пути являются дорогими, отсрочка более длинных поисков в графе в ограничениях с более длинными путями, когда ограничения дизъюнктивно объединены с ограничениями с более короткими путями, может сэкономить время обработки. Например, запрос Q2 включает в себя три дизъюнктивно объединенных ограничения (например, с помощью операции "или"). Первые два ограничения подразумевают длину пути, равную двум, в то время как последнее подразумевает длину пути, равную трем. Если исходный узел добавленного ребра делает первое ограничение "истиной", поиск по более длинному пути не является необходимым. Таким образом, система может установить состояние ограничения с более длинным путем как "неизвестно", и выполнить поиск, только если поиск в графе не способно соответствовать одному из первых двух ограничений. В некоторых реализациях система может использовать интеллектуальный процесс выбора, такой как процесс 500 на фиг. 5 или процесс 600 на фиг. 6.

[00048] Как только целевые ограничения были оценены, и им были присвоены состояния, система может выполнить поиск определения запроса для сохраненного запроса по меньшей мере для одного из целевых ограничений и свернуть ограничительное выражение для запроса (этап 420). Например, запрос Q2 на фиг. 3 имеет три ограничения в своем ограничительном выражении. Если ограничение "родитель.вид_деятельности" == "Президент" является целевым ограничением с состоянием "истина" для узла "Джек Доу", система заменит состояние первого ограничения для первого ограничения в ограничительном выражении и определит, может ли ограничительное выражение быть приведено. Например, сворачивание определения запроса для C2 с использованием упомянутого выше примера будет таким: ("истина" || "супруг.вид_деятельности" == "Президент" || "родитель.родитель.вид_деятельности" == "Президент"). Свернутое определение запроса C2 приводит к "истине", поскольку одно ограничение в дизъюнкции ограничений является "истиной".

[00049] Система может определить, приведено ли свернутое ограничительное выражение к "истине" или "лжи" (этап 425). Как продемонстрировано выше, это может произойти, когда одно ограничение в последовательности дизъюнктивных ограничений является "истиной". В этом случае системе не требуется оценивать другие ограничения, поскольку одного ограничения, имеющего состояние "истина", достаточно, чтобы сделать ограничительное выражение "истиной". Аналогичным образом, если одно ограничение в последовательности конъюнктивных ограничений является "ложью", системе не требуется оценивать другие ограничения. Если ограничительное выражение не приведено ни к "истине", ни ко "лжи" (этап 425, нет), система может выбрать одно или более неразрешенных ограничений в ограничительном выражении и определить состояние для неразрешенных ограничений (440). В некоторых реализациях система может использовать интеллектуальный процесс выбора, такой как процесс 500 на фиг. 5 или процесс 600 на фиг. 6. Затем система может свернуть ограничительное выражение (этап 420) с использованием состояния (состояний), определенного для одного или более ограничений. Таким образом, этапы 420-440 представляют итеративную оценку ограничений, поиски в графе и сворачивание ограничительного выражения, чтобы определить, какие узлы могут быть элементами результатов запроса, затронутых обновлением графа. Такой итеративный процесс позволяет системе выполнять минимальные поиски в графе, сокращая время обработки, потраченное на определение, какие результаты сохраненных запросов затронуты обновлением графа.

[00050] Если ограничительное выражение приведено либо к "истине", либо ко "лжи" (этап 425, да), система может обновить сохраненную принадлежность для запроса (этап 430). Чтобы обновить принадлежность для добавленного ребра, когда ограничительное выражение приведено к "истине", система может добавить подходящий исходный узел (узлы) к результатам сохраненных запросов, если исходный узел (узлы) еще не существует в сохраненных результатах для запроса. Чтобы обновить принадлежность для удаленного ребра, когда ограничительное выражение приведено ко "лжи", система может удалить подходящий исходный узел (узлы) из результатов сохраненных запросов, если он существует в результатах сохраненного запроса. В ином случае система может поддержать результаты запроса или, другими словами, оставить результаты запроса, как они есть, поскольку результаты не затронуты посредством обновленной тройки.

[00051] Если имеются другие запросы с целевыми ограничениями (этап 435, да), система может выбрать другой запрос для одного или более оставшихся целевых ограничений и повторить этапы 420-440 для того запроса. В ином случае процесс 400 заканчивается, и система имеет обновленные затронутые результаты сохраненных запросов в ответ на обновление графа.

[00052] Фиг. 5 иллюстрирует блок-схему последовательности операций примерного процесса 500 для интеллектуального выбора и оценки ограничений после добавления ребра к графу, совместимого с раскрытыми реализациями. Процесс 500 может быть выполнен подсистемой сохраненных запросов системы как часть этапа 415 или 440 на фиг. 4. Система может использовать процесс 500 для интеллектуального выбора ограничений для оценки и повторного использовать обходы графа, выполненные для других ограничений, чтобы более эффективно определять изменения в результатах сохраненных запросов после обновления хранилища данных на основе графа. Система может выполнить процесс 500 для ограничения в ограничительном выражении для запроса, который имеет по меньшей мере одно целевое ограничение. Процесс 500 может начаться с определения, является ли ребро обновления единственным ребром в ограничении (этап 505). Другими словами, если ребро в обновлении графа соответствует единственному ребру в ограничении (этап 505, да), системе не требуется выполнять поиск в графе, и она может установить узел-элемент как исходный узел обновления и целевой узел-элемент как узел-объект обновления (этап 510). Узел-элемент - это узел, который является потенциальным элементом множества узлов в результатах запроса, которое включает в себя оцениваемое ограничение. Целевой узел-элемент - это узел, который достигается из узла-элемента через путь, определенный в ограничении. В ограничении с одиночным ребром исходный узел обновленной тройки представляет собой узел-элемент, и целевой узел обновленной тройки представляет собой целевой узел-элемент, поскольку любые другие узлы, достигнутые из исходного узла обновленной тройки через ребро обновленной тройки, не затронуты обновлением. Другими словами, принадлежность не изменяется, и для системы нет необходимости повторно проверять эту принадлежность. Аналогичным образом, если ребро в обновлении является первым ребром в ограничении с длиной пути более 1, исходный узел обновления по-прежнему является единственным потенциальным узлом-элементом, поскольку любые поиски в графе будут включать в себя только прямые обходы в графе от исходного узла в обновлении. В этой ситуации целевой узел обновленной тройки не является целевым узлом-элементом. Целевые узлы-элементы в этой ситуации идентифицируются посредством обхода графа от узла-объекта через путь, определенный в ограничении, до одного или более целевых узлов-элементов. Если система не способна достигнуть по меньшей мере одного целевого узла-элемента, следуя по пути, определенному в ограничении, целевой узел-элемент для узла-элемента является пустым ("пусто") и это означает, что граф не включает в себя путь от узла-элемента ни до какого другого узла, который соответствует пути в ограничении.

[00053] Узлы-элементы не всегда являются исходными узлами добавленной тройки. Например, когда ребро в добавленной тройке не является первым ребром на пути ограничения, поиск в графе будет предусматривать обратный обход от исходного узла обновленной тройки, и узлами-элементами будут один или более узлов, достигнутых при обратном обходе. Целевыми узлами-элементами в такой ситуации будут узлы, достигнутые от узлов-элементов через добавленную тройку, как будет описано более подробно ниже.

[00054] Система может установить состояние ограничения для каждого узла-элемента на основе обхода (этап 550). Удовлетворяет ли узел-элемент ограничению, зависит от целевого узла-элемента (или узлов-элементов), идентифицированного для узла-элемента. Например, если узел-элемент связан по меньшей мере с одним целевым узлом-элементом, который удовлетворяет ограничению, состояние ограничения для того узла-элемента - "истина", иначе - "ложь". По своему замыслу целевые узлы-элементы представляют собой узлы, достигнутые от узла-элемента через обновление графа (например, источник, ребро и целевой узел обновления графа). Это может дать в результате систему, приводящую при обходе к нолю, одному или более целевым узлам-элементам на каждый узел-элемент. Пока один целевой узел-элемент соответствует ограничительным условиям, состояние ограничения для узла-элемента - "истина". Как только система устанавливает состояние ограничения, процесс 500 заканчивается для этого ограничения.

[00055] Если ребро обновления не является единственным ребром в ограничении (этап 505, нет), система может определить, включает ли в себя ограничение поиски с одиночным ребром (этап 515). Одиночное ребро включает в себя ограничение, в котором ребро обновления является частью ограничения с длиной пути, равной двум. Например, если обновление графа представляет собой <Джек Доу, родитель, Джейн Доу>, и ограничение представляет собой "выпускники.родитель" == ʺДжейн Доуʺ, система может рассматривать это как поиск с одиночным ребром, поскольку только по ребру "выпускники" должен быть выполнен обратный обход, чтобы найти узлы-элементы. В таком примере целевым узлом-элементом является "Джейн Доу", и прямой обход не требуется. Аналогично, если ограничение представляет собой "родитель.вид_деятельности" == "Президент", система может рассматривать это как поиск с одиночным ребром, поскольку узлом-элементом является "Джек Доу", и необходим только прямой поиск от "Джейн Доу" через ребро "вид_деятельности", чтобы идентифицировать целевой узел-элемент (целевые узлы-элементы). Если ребро "вид_деятельности" не существует для "Джейн Доу", система может установить целевой узел-элемент как "пусто". Кроме того, если ребро обновления графа представляет собой среднее ребро ограничения с длиной пути, равным трем, система может считать это одиночным ребром, например, одиночным обратным ребром и одиночным прямым ребром. Например, если ограничение представляет собой "выпускники.вид_деятельности" == "Президент", и добавленная тройка представляет собой <Джек Доу, родитель, Джейн Доу>, добавленная тройка выполняет среднее ребро в ограничении, и система может выполнить обход одного ребра от "Джейн Доу" через ребро "вид_деятельности", чтобы определить потенциальные целевые узлы-элементы и выполнить обход графа от узла "Джек Доу" через ребро "выпускники", чтобы определить узлы-элементы. В соответствии с этим, если ограничение представляет собой поиск с одиночным ребром (этап 515, да), система может выполнить обход графа, чтобы идентифицировать узлы-элементы и целевые узлы-элементы (этап 520), как только что описано. В некоторых реализациях система может сохранить результаты поиска во временной таблице поиска (этап 545). Это позволяет системе снова использовать результаты поиска в будущих оценках других ограничений.

[00056] Система может установить состояние ограничения для каждого узла-элемента на основе обхода (этап 550). Например, если обход графа, начинающийся с узла-элемента, указывает, что ребро не существует для узла-элемента, и ограничение включает в себя условие "== "пусто"", система может установить состояние "истина" для узла-элемента. Если ограничение включает в себя условие "!= "пусто"", система может установить состояние "ложь" для этого узла-элемента. Если ограничение определяет заданный узел как целевой узел, и целевой узел-элемент (целевые узлы-элементы) не соответствует узлу, определенному в ограничении, система устанавливает состояние "ложь" для узла-элемента, и "истина" в ином случае. Например, если ограничение включает в себя условие "== Президент", и целевой узел-элемент (целевые узлы-элементы) не включает в себя узел "Президент", система может установить состояние "ложь". Если целевой узел-элемент (целевые узлы-элементы) включает в себя узел "Президент", система может установить состояние "истина". Система может соединить узел-элемент с подходящим состоянием таким образом, чтобы она могла отследить, какие узлы-элементы удовлетворяют ограничению. Затем процесс 500 заканчивается для ограничения.

[00057] Если ограничение не включает в себя одиночный поиск (этап 515, нет), система может определить, включает ли в себя ограничение путь с сохраненными результатами поиска (этап 525). Например, система может временно сохранить результаты предыдущих поисков в графе, например, в хранилище данных, таком как временные результаты 147 поиска на фиг. 1. Это позволяет системе повторно использовать работу, выполненную для предыдущего ограничения. Это особенно эффективно, когда система группирует обновления по исходному узлу, чтобы сохраненные поиски могли использоваться по нескольким обновлениям графа. Сохраненные поиски могут включать в себя исходный узел, пройденный путь и любые целевые узлы, достигнутые через путь.

[00058] Если ограничение включает в себя путь, имеющий соответствующий сохраненный результат поиска (этап 525, да), система может использовать сохраненные результаты поиска, чтобы определить узлы-элементы и целевые узлы-элементы для ограничения (этап 530). Как указано выше, узлы-элементы - это узлы, которые являются узлами, которые могут потенциально удовлетворить ограничению и, таким образом, потенциально отвечают на запрос (например, являются потенциальными элементами множества узлов в результатах сохраненных запросов). Каждый сохраненный результат поиска может включать в себя исходный узел и любые целевые узлы, достигнутые через сохраненный путь от исходного узла. Исходные узлы в сохраненных поисках могут быть узлами-элементами или могут использоваться для определения узлов-элементов, в зависимости от ограничения. Например, если обновление графа представляет собой <Билл Клинтон, вид_деятельности, Президент>, и оцениваемое ограничение представляет собой "выпускники.родитель.вид_деятельности" == "Президент", и сохраненные поиски включают в себя обратный поиск от "Билл Клинтон" через ребро "родитель", то "Челси Клинтон" может являться целевым узлом, сохраненным во временных результатах поиска. Таким образом, при оценке ограничения "выпускники.родитель.вид_деятельности" системе может потребоваться только оценить путь от "Челси Клинтон" через путь "выпускники", чтобы определить узлы-элементы, например, "Колумбия" и "Стэнфорд", используя примерный граф на фиг. 2. С другой стороны, если оцениваемое ограничение представляет собой "родитель.вид_деятельности", то целевой узел "Челси Клинтон", который находится в сохраненных поисках для "Билл Клинтон-> родитель", является узлом-элементом. При обходе графа системе может потребоваться выполнить прямой и обратный обход, как описано выше в отношении поисков с одиночным ребром на этапе 515. Прямые и обратные обходы могут сами включать в себя более чем одиночный поиск. В некоторых ситуациях ограничение может включать в себя обратный обход, который сохранен, и прямой обход, который не сохранен, или наоборот. Таким образом, использование результатов сохраненного поиска предыдущего обхода графа может включать в себя дополнительные поиски в графе, чтобы определить либо узлы-элементы, либо целевые узлы-элементы, в зависимости от того, какой обход сохранен. Система может установить состояние ограничения для каждого идентифицированного узла-элемента на основе обхода (этап 550), как описано выше.

[00059] Если ограничение не включает в себя сохраненный поиск (этап 525, нет), система может определить, имеет ли ограничение наименьшую не приведенную длину пути для определения запроса (этап 535). Например, запрос Q4 на фиг. 3 включает в себя два ограничения с длиной пути, равной пяти, и одно ограничение с длиной пути, равной трем. В некоторых реализациях система может использовать структуру ограничительного выражения, чтобы определить, имеет ли ограничение наименьшую не приведенную длину пути для конкретной части ограничительного выражения. Таким образом, например, если выражение представляет собой дизъюнктивную последовательность ограничений, система может определить, имеет ли ограничение наименьшую длину пути из ограничений в последовательности ограничений. Если процесс 500 вызван только при оценке целевых ограничений (например, этап 415 на фиг. 4), система может определить, имеет ли ограничение длину кратчайшего пути из целевых ограничений для сохраненного запроса, а не полное определение запроса. Если система определяет, что ограничение имеет наименьшую длину пути (этап 535, да), система может выполнить обход графа, чтобы идентифицировать узлы-элементы и их соответствующий целевой узел-элемент (целевые узлы-элементы), если таковые имеются. Как описано выше, это может включать в себя и прямой обход в графе и обратный обход. Система может сохранить результаты поиска (поисков), сделанного во время обхода (этап 545), с тем чтобы результаты могли быть использованы повторно. Система может установить состояние ограничения для каждого узла-элемента (этап 550), как описано ранее.

[00060] Если система определяет, что ограничение не имеет наименьшего пути (этап 535, нет), система может установить состояние ограничения "неизвестно" (этап 555). Это означает, что система будет ожидать оценки ограничения в более позднее время, если такая оценка будет необходима. Таким образом, система может отложить более сложные обходы, если такие обходы не являются необходимыми, чтобы разрешить реакцию конкретного узла-элемента на сохраненный запрос.

[00061] Процесс 500, проиллюстрированный на фиг. 5, является одним примером интеллектуальной оценки ограничений. Безусловно, в некоторых реализациях система может полностью оценивать каждое ограничение по мере того, как оно встречается, сохраняя результаты любых обходов графа по мере необходимости. В таких реализациях система может использовать сохраненные поиски при их наличии (например, этапы 525 и 530), а в ином случае выполнять обход графа (например, этап 540) и сохранять результаты обхода (этап 545), никогда не устанавливая состояние "неизвестно". Кроме того, из этого раскрытия может быть очевидно, что могут использоваться другие модификации при оптимизации оценки ограничения, например, всегда выполнять поиски с длиной, равной двум, вместо лишь одиночных поисков, как часть этапа 515, и т.д. Кроме того, подразумевается, что в некоторых реализациях установка статуса ограничения для узла-элемента (этап 550) может быть выполнена как часть идентификации узлов-элементов и/или целевых узлов-элементов. Таким образом, порядок этапов, проиллюстрированных на фиг. 5, является лишь примерным, и реализации не ограничены иллюстрированным порядком.

[00062] Фиг. 6 иллюстрирует блок-схему последовательности операций примерного процесса 600 для интеллектуального выбора и оценки ограничения после удаления ребра из графа, совместимого с раскрытыми реализациями. Процесс 600 может быть выполнен подсистемой сохраненных запросов системы как часть этапа 415 или 440 на фиг. 4. Система может использовать процесс 600 для интеллектуального выбора ограничения для оценки и повторно использовать обходы графа, выполненные для других ограничений, чтобы более эффективно определять изменения в результатах сохраненных запросов после обновления хранилища данных на основе графа. Система может выполнить процесс 600 для ограничения в ограничительном выражении сохраненного запроса, который имеет по меньшей мере одно целевое ограничение. Процесс 600 может начаться с определения, является ли удаленное ребро единственным ребром в ограничении (этап 605). Другими словами, если ребро в обновлении графа соответствует единственному ребру в ограничении (этап 605, да), система может установить узел-элемент в исходный узел удаленного ребра и выполнить поиск целевых узлов-элементов (этап 610). В отличие от добавленной тройки, целевой узел удаленной тройки не является приемлемым целевым узлом-элементом, поскольку ребро больше не существует в графе. Таким образом, система может выполнить обход графа от узла-элемента (например, исходного узла из удаленной тройки), чтобы определить, соединен ли он с другим узлом посредством ребра, которое соответствует ограничительному ребру. Например, если удаленная тройка представляет собой <Джек Доу, родитель, Джон Доу>, и ограничение представляет собой "родитель" != "пусто", система может определить, имеется ли другое ребро "родитель" от узла "Джек Доу" до узла, отличающегося от узла "Джон Доу". Если имеется, то другой узел является целевым узлом-элементом. Система может установить состояние ограничения для узла-элемента на основе обхода (этап 650). Как и в случае с добавлением к графу, тот факт, удовлетворяет ли узел-элемент ограничению, зависит от идентифицированного целевого узла-элемента (или целевых узлов-элементов) или неспособности идентифицировать целевой узел-элемент для узла-элемента. Продолжая приведенный выше пример, если узел-элемент не связан по меньшей мере с одним другим узлом через родительское соотношение, целевой узел-элемент является пустым ("пусто"), и ограничение "родитель != "пусто"" не удовлетворено и примет состояние "ложь". Как только система устанавливает состояние ограничения, процесс 600 для этого ограничения заканчивается.

[00063] Если ребро обновления не является единственным ребром в ограничении (этап 605, нет), система может определить, включает ли в себя ограничение поиски с одиночным ребром (этап 615). Как и в случае добавленной тройки, одиночное ребро для удаленной тройки включает в себя ограничение, в котором ребро удаленной тройки является частью ограничения с длиной пути, равным двум. Но в отличие от добавленной тройки ограничение, в котором ребро удаленной тройки представляет собой среднее ребро ограничения, не является поиском с единичным ребром. Это вызвано тем, что удаленная тройка больше не выполняет требование среднего ребра. Вместо этого система должна выполнить обратный поиск, чтобы идентифицировать все потенциальные узлы-элементы (если таковые имеются), и выполнить прямой поиск, следуя по пути, предписанному этими тремя ребрами, чтобы определить любые возможные целевые узлы-элементы. Таким образом, требуется прямой поиск по меньшей мере с тремя ребрами, и такое ограничение может не удовлетворить поиску с одиночным ребром. Если ограничение представляет собой поиск с одиночным ребром (этап 615, да), система может выполнить обход графа, чтобы идентифицировать узлы-элементы и целевые узлы-элементы (620), как только что описано. В некоторых реализациях система может сохранить результаты поиска во временной таблице поиска (этап 645). Это позволяет системе повторно использовать результаты поиска в будущих оценках других ограничений. Система может установить состояние ограничения для каждого узла-элемента на основе обхода и идентифицированных целевых узлов-элементов (этап 650). Система может соотнести узел-элемент с подходящим состоянием таким образом, чтобы она могла отслеживать, какие узлы-элементы удовлетворяют ограничению. Затем процесс 600 для ограничения заканчивается.

[00064] Если ограничение не включает в себя единственный поиск (этап 615, нет), система может определить, включает ли в себя ограничение путь с сохраненными результатами поиска (этап 625). Например, система может временно сохранить результаты предыдущих поисков в графе, например, в хранилище данных, таком как временные результаты 147 поиска на фиг. 1. Это позволяет системе повторно использовать работу, выполненную для предыдущего ограничения, и особенно эффективно, когда система группирует обновления по исходному узлу, с тем чтобы сохраненные поиски могли использоваться в нескольких обновлениях графа. Сохраненные поиски могут включать в себя исходный узел, пройденный путь и любые целевые узлы, достигнутые через путь. Система может удалить любые сохраненные поиски, когда исходный узел графа обновляет изменения.

[00065] Если ограничение включает в себя сохраненный поиск (этап 625, да), система может использовать целевые узлы сохраненного поиска, чтобы определить узлы-элементы и целевые узлы-элементы для ограничения (этап 630), как описано выше в отношении фиг. 5, за исключением того, что удаленное ребро не может использоваться для обхода графа. Система может установить состояние ограничения для каждого идентифицированного узла-элемента и целевого узла-элемента (целевых узлов-элементов) на основе обхода (этап 650), как описано выше.

[00066] Если ограничение не включает в себя сохраненный поиск (этап 625, нет), система может определить, имеет ли ограничение наименьшую не приведенную длину пути для определения запроса (этап 635), как описано выше в отношении фиг. 5. Если система определяет, что ограничение имеет наименьшую длину пути (этап 635, да), система может выполнить обход графа, чтобы идентифицировать узлы-элементы и целевой узел-элемент (целевые узлы-элементы) по мере необходимости, как описано выше в отношении фиг. 5, за исключением того, что обход сначала включает в себя выполнение любого обратного обхода, чтобы идентифицировать узлы-элементы, и выполнение прямого обхода от каждого узла-элемента с использованием пути, определенного в ограничении, чтобы идентифицировать потенциальные целевые узлы-элементы. Безусловно, когда для ограничения существует более чем один узел-элемент, ограничение может иметь состояние "истина" для одного узла-элемента и состояние "ложь" для другого узла-элемента. Система может сохранить результаты обратного и прямого поиска (поисков), сделанных во время обхода (этап 645), с тем чтобы результаты могли быть повторно использованы. Система может установить состояние ограничения для каждого узла-элемента (этап 650), как описано ранее.

[00067] Если система определяет, что ограничение не имеет наименьшего пути (этап 635, нет), система может установить состояние ограничения "неизвестно" (этап 655). Это означает, что система будет ожидать оценки ограничения в более позднее время, если такая оценка будет необходима. Таким образом, система может отложить более сложные обходы, если такие обходы не являются необходимыми, чтобы разрешить быструю реакцию конкретного узла-элемента на сохраненный запрос.

[00068] Аналогично процессу 500 процесс 600, проиллюстрированный на фиг. 6, представляет собой один пример, и реализации могут объединять этапы, изменять порядок этапов, выполнить только некоторые этапы и т.д., и реализации не ограничены порядком или проиллюстрированными этапами.

[00069] Фиг. 7 и 8 иллюстрируют пример обновления принадлежности к запросу в реальном времени с использованием графа данных, показанного на фиг. 2, и примерных сохраненных запросов 340, показанных на фиг. 3. В примере на фиг. 7 тройка <Дьюк, выпускники, Джек Доу> из фиг. 2 удаляется из графа 200. Таким образом, обновленная тройка представляет собой <Дьюк, выпускники, Джек Доу>. В некоторых реализациях система может обновить результаты сохраненных запросов, затронутые удалением, в ответ на обновление, и в некоторых реализациях система может сгруппировать обновления, которые происходят за короткий период времени, например, менее 5 минут, и затем обновляет результаты сохраненных запросов на основе группы обновлений. Группировка может быть сделана по исходному узлу обновленной тройки. В любой реализации обновление инициирует процесс обновления результатов сохраненных запросов. Таким образом, результаты сохраненных запросов происходят в реальном времени.

[00070] После приема удаленной тройки система может идентифицировать целевые ограничения. Как указано выше, целевые ограничения представляют собой ограничения, которые включают в себя ребро, идентифицированное удаленной тройкой. В некоторых реализациях система может использовать индекс, такой как индекс 345 ребер запросов на фиг. 3, чтобы идентифицировать целевые ограничения. Например, используя индекс 345, система может найти запись для ребра "выпускники" в индексе и идентифицировать записи для ребра "выпускники" как целевые ограничения. В некоторых реализациях система может считывать сохраненные запросы 340 и выполнять поиск ограничений, которые включают в себя ребро "выпускники". На основе графа 200 на фиг. 2, сохраненных запросов 340 и, факультативно, индекса 345 ребер запросов система может идентифицировать целевые ограничения 705. Затем система может оценить целевые ограничения. В некоторых реализациях система может интеллектуально оценить ограничения. Например, каждое из двух ограничений для запроса Q3 имеет длину, равную трем, - таким образом, каждое из них представляет собой кратчайший путь для целевых ограничений запроса Q3, и система может выполнить обход графа, чтобы определить узлы-элементы и состояние ограничения для каждого узла-элемента. Поскольку ребро удаленной тройки представляет собой "выпускники", и ребро "выпускники" является первым ребром каждого целевого ограничения в запросе Q3, узлом-элементом является "Дьюк", исходный узел удаленной тройки. Таким образом, обход графа для этих ограничений подразумевает прямой обход в графе от узла "Дьюк".

[00071] С использованием графа на фиг. 2 узел "Дьюк" теперь включает в себя только одно ребро "выпускники", когда удалено ребро <Дьюк, выпускники, Джек Доу>. Таким образом, при оценке первого ограничения система следует по ребру "выпускники" к узлу "Джон Доу". Узел "Джона Доу" имеет соотношение "родитель" с узлом "Джека Доу", но узpел "Джека Доу" не имеет ребра "вид_деятельности". Таким образом, система присваивает целевому узлу-элементу значение "пусто". Поскольку ограничение "выпускники.родитель.вид_деятельности" == "Президент" указывает, что условием для принадлежности является целевой узел-элемент "Президент", целевой узел-элемент "пусто" не способен удовлетворить ограничению, и, таким образом, система устанавливает состояние ограничения "ложь" для узла-элемента "Дьюк". Подразумевается, что граф на фиг. 2 является ненаправленным графом. В некоторых реализациях граф может быть направленным, например, ребро "родитель" может вести только от дочернего узла к родительскому узлу (например, только от "Джек Доу" к "Джон Доу"). В таком графе система не увидит соотношение "родитель", ведущее от узла "Джек Доу", что по-прежнему приведет к пустому ("пусто") целевому узлу-элементу и состоянию "ложь" для этого ограничения.

[00072] Затем система может оценить второе ограничение для запроса Q3. Узел "Дьюк" имеет соотношение "выпускники" с узлом "Джон Доу", который имеет соотношение "супруг" с узлом "Джейн Доу". Узел "Джейн Доу" имеет соотношение "вид_деятельности" с узлом "Президент", и это делает узел "Президент" целевым узлом-элементом для узла-элемента "Дьюк". Поскольку целевой узел-элемент "Президент" соответствует условию в ограничении, система устанавливает состояние ограничения "выпускники.супруг.Вид_деятельности" == "Президент" как "истина" для узла-элемента "Дьюк".

[00073] Система также может оценить целевые ограничения для запроса Q4. Целевые ограничения включают в себя два ограничения с длиной пути, равной пяти, и один с длиной пути, равной двум. Система может выбрать ограничение "выпускники.выпускники" != "пусто" для оценки и установить состояние оставшихся двух целевых ограничений как "неизвестно", поскольку их длина пути больше. Поскольку соотношение "выпускники" представляет собой первое соотношение на пути ограничения "выпускники.выпускники" != "пусто", система может установить узел-элемент как "Дьюк", исходный узел удаленной тройки. Система может выполнить обход графа и определить, что узел "Дьюк" имеет соотношение "выпускники" с другим узлом - с узлом "Джона Доу". В некоторых реализациях система может использовать сохраненный поиск в графе, чтобы определить, что это соотношение существует. Узел "Джона Доу" имеет соотношение "выпускники" с узлом "Мичиган". Таким образом, целевым узлом-элементом является "Мичиган". Поскольку целевой узел-элемент не пустой ("пусто"), ограничение удовлетворено, и система устанавливает состояние ограничения для узла "Дьюк" как "истина".

[00074] Наконец, система может оценить целевое ограничение для запроса Q5. Это ограничение имеет одно ребро, таким образом, система может выполнить обход графа от узла "Дьюк" до узла "Джона Доу" через ребро "выпускники". Это конец пути, таким образом, узел "Джона Доу" является целевым узлом-элементом. Поскольку целевым узлом-элементом не является "Джек Доу", как определено ограничением, система устанавливает состояние для этого ограничения как "ложь" для узла-элемента "Дьюк".

[00075] Система может свернуть различные определения запросов, заменив состояние ограничений для ограничения в определении запроса. Это приводит к свернутым определениям 710 на фиг. 7. Система может оценить свернутые определения, чтобы определить, оценивается ли ограничительное выражение как "истина" или "ложь", или требуются дополнительные поиски. Как проиллюстрировано на фиг. 7, ограничительное выражение для запроса Q3 приводится к "истине" для "Дьюк", и ограничительное выражение для запроса Q5 приводится ко "лжи" для "Дьюк". Ограничительное выражение для запроса Q4 еще не приведено, поскольку требуются дополнительные поиски. Следует отметить, что если ограничение "выпускники.выпускники" != "пусто" оценено как "ложь", не потребуются никакие дополнительные поиски, поскольку свернутое ограничительное выражение для C4 будет приведено ко "лжи".

[00076] Система может обновить результаты сохраненных запросов для приведенных запросов на этапе 715. Поскольку запрос Q5 приведен ко "лжи", и это удаление тройки, узел "Дьюк" должен быть удален из запроса Q5. Поскольку запрос Q3 приведен к "истине", и это удаление тройки, не требуются никакие изменения (например, удаление не затронуло принадлежность), и система может поддержать принадлежность для сохраненных результатов запроса Q3. Хотя фиг. 7 иллюстрирует этапы оценки, свертки и обновления, работающие на группах ограничений в разных сохраненных запросах, подразумевается, что в некоторых реализациях система может оценить, свернуть и обновить принадлежность одного запроса за один раз. Например, система может оценить ограничения для запроса Q3, свернуть определение запроса для Q3 и затем обновить принадлежность Q3, прежде чем оценить ограничения Q4, свернуть определение запроса Q4 и т.д. Таким образом, реализации не ограничены последовательностью, продемонстрированной на фиг. 7.

[00077] Поскольку запрос Q4 еще не был приведен, система может оценить ограничения с состоянием "неизвестно", или ограничения, которые не были целевыми ограничениями в запросе. В примере на фиг. 7 имеются два ограничения для оценки, каждое с одинаковой длиной пути. Таким образом, система может начать обход в графе от узла "Дьюк", следуя по пути, идентифицированному в ограничении "выпускники.родитель.год_рождения.китайский_зодик" == "бык". Поскольку с удалением в графе на фиг. 2 такой путь не существует, целевой узел-элемент является пустым ("пусто"), и это не удовлетворяет ограничению, и система устанавливает состояние ограничения "ложь" для узла-элемента "Дьюк". Система может иметь сохраненные результаты поиска, например, указывающие, что такой путь не существует, и система может повторно использовать эти результаты, чтобы определить, что ограничение "выпускники.родитель.год_рождения.китайский_зодиак" == "собака" также не удовлетворено для узла "Дьюк". Таким образом, система также может установить состояние этого ограничения как "ложь" для узла "Дьюк". Затем система может свернуть определение запроса и определить, что оно оценивается как "ложь". Поскольку оно оценивается как "ложь", и обновление представляет собой удаленную тройку, система может удалить узел "Дьюк" из результатов сохраненного запроса Q4. Теперь система имеет обновленные результаты сохраненного запроса, затронутые удалением тройки, и может идти дальше, чтобы обработать следующую тройку в группе, или может ожидать другого обновления графа данных.

[00078] В примере на фиг. 8 тройка <Джек Доу, родитель, Джейн Доу> была добавлена к графу 200 на фиг. 2. Таким образом, обновленная тройка представляет собой <Джек Доу, родитель, Джейн Доу>. В некоторых реализациях система может обновить результаты сохраненных запросов, затронутые дополнением, в ответ на обновление, и в некоторых реализациях система может сгруппировать обновления, которые происходят за короткий период времени, например, менее 5 минут, и затем обновляет результаты сохраненных запросов на основе группы обновлений. Группировка может быть сделана по исходному узлу обновленной тройки. Пример, фиг. 8 использует граф 200, проиллюстрированный на фиг. 2, без удаления, описанного в отношении фиг. 7. Таким образом, пример фиг. 8 независим от примера фиг. 7. Однако подразумевается, что если бы удаление действительно произошло до событий, изображенных на фиг. 8, узел "Дьюк" не являлся бы приемлемым узлом-элементом, поскольку его соотношение "выпускники" с узлом "Джек Доу" больше не существовало бы.

[00079] После приема добавленной тройки система может идентифицировать целевые ограничения. Как указано выше, целевые ограничения представляют собой ограничения, которые включают в себя ребро, идентифицированное добавленной тройкой. В некоторых реализациях система может использовать индекс, такой как индекс 345 ребер запросов на фиг. 3, чтобы идентифицировать целевые ограничения. Например, используя индекс 345 ребер запросов, система может найти запись для ребра "родитель" в индексе и идентифицировать записи для ребра "родитель" как целевые ограничения. В некоторых реализациях система может считывать сохраненные запросы 340 и выполнять поиск ограничений, которые включают в себя ребро "родитель". На основе графа 200 на фиг. 2, сохраненных запросов 340 и, факультативно, индекса 345 ребер запросов система может идентифицировать целевые ограничения 805. Затем система может оценить целевые ограничения. В некоторых реализациях система может интеллектуально оценить ограничения. Другими словами, система может выбрать ограничения с меньшими путями поиска или ограничения, которые могут повторно использовать сохраненную работу для оценки. Например, одно целевое ограничение для запроса Q2 имеет длину пути, равную двум, и другое имеет длину пути, равную трем. Система может выбрать ограничение с меньшей длиной пути или может выбрать ограничение "родитель.вид_деятельности" == "Президент", поскольку оно подразумевает поиск с одиночным ребром (добавленная тройка удовлетворяет первому ребру на пути). Система может принять решение ожидать оценки ограничения "родитель.родитель.вид_деятельности"== "Президент" запроса Q2 и установить состояние для этого ограничения "неизвестно" в настоящее время. Чтобы оценить ограничение "родитель.вид_деятельности" == "Президент", система может установить узел "Джек Доу" как узел-элемент и следовать по только что добавленному ребру "родитель" к узлу "Джейн Доу". Следующее ребро в ограничении - это ребро "вид_деятельности", которое приводит к узлу "Президент". Это целевой узел-элемент, и он удовлетворяет условию ограничения, таким образом, система устанавливает состояние ограничения "родитель.вид_деятельности" == "Президент" как "истина" для узла "Джек Доу". В некоторых реализациях система может сохранить узел-элемент (например, "Джек Доу") и целевой узел-элемент (например, "Президент") для пути "родитель.вид_деятельности" во временных результатах поиска.

[00080] Система также может оценить целевое ограничение для запроса Q3. Целевое ограничение для запроса Q3 включает в себя обратный обход по одиночному ребру в графе, например, от узла "Джек Доу" через ребро "выпускники", и прямой обход через "родитель.вид_деятельности". В некоторых реализациях система может повторно использовать обход "родитель.вид_деятельности" от целевого ограничения для запроса Q2, чтобы идентифицировать целевой узел-элемент как "Президент". Таким образом, система может выполнить только обратный обход, чтобы определить узлы-элементы для этого ограничения. Используя граф 200 из фиг. 2 в качестве примера, система может следовать по ребру "выпускники" от узла "Джек Доу" до обоих из узлов "Дьюк" и "Колумбия". Таким образом, система может идентифицировать два узла-элемента: "Дьюк" и "Колумбия". Поскольку целевой узел-элемент "Президент" удовлетворяет ограничению, система может установить статус "истина" для узла-элемента "Дьюк" и для узла-элемента "Колумбия". В некоторых реализациях система может сохранить обратный обход от узла "Джек Доу" до узлов "Дьюк" и "Колумбия" через ребро "выпускники" во временных результатах поиска.

[00081] Система также может оценить целевые ограничения для запроса Q4. Длины путей двух целевых ограничений равны и являются самыми короткими для запроса, таким образом, система может оценить каждое ограничение. Поскольку добавленное ребро "родитель" не является первым ребром в ограничительном пути, система выполняет обратный обход с использованием ребра "выпускники". В некоторых реализациях система может использовать временные результаты поиска, чтобы идентифицировать узлы-элементы "Дьюк" и "Колумбия" для обратного обхода, например, поскольку система выполнила этот обход при оценке целевого ограничения для запроса Q3. Система может запустить прямой обход от узла "Джейн Доу" для ограничения "выпускники.родитель.год_рождения.китайский_зодиак" == "собака", следуя по ребру "год_рождения" к узлу "1961", и по ребру "китайский_зодиак" к узлу "бык". Поскольку это конец пути в ограничении, узел "бык" является целевым узлом-элементом для узлов-элементов "Дьюк" и "Колумбия". Система может сохранить узлы-элементы "Дьюк" и "Колумбия" с целевым узлом-элементом "бык" для пути "выпускники.родитель.год_рождения.китайский_зодика", например, во временных результатах поиска. Поскольку целевой узел-элемент "бык" не удовлетворяет этому ограничению, система может установить состояние "ложь" для узла-элемента "Колумбия" и узла-элемента "Дьюк".

[00082] Затем система может оценить второе ограничение для запроса Q4. В некоторых реализациях система может использовать результаты предыдущего поиска, например, из временных результатов поиска, чтобы идентифицировать узлы-элементы узлов "Колумбия" и "Дьюк" и целевой узел-элемент узда "бык". Таким образом, системе не требуется фактически выполнять дальнейшие обходы в графе, чтобы оценить ограничение "выпускники.родитель.год_рождения.китайский_зодиак" == "бык", и она может использовать сохраненный поиск, чтобы установить состояние этого ограничения как "истина" для узлов-элементов "Дьюк" и "Колумбия", поскольку целевой узел-элемент узла "бык" действительно удовлетворяет ограничению. Если система не сохраняет поиски, система может выполнить обход графа, как описано выше, чтобы идентифицировать узлы-элементы и целевой узел-элемент.

[00083] Система может свернуть определения запросов с использованием состояний, определенных для целевых ограничений. Как проиллюстрировано посредством свернутых определений 810 на фиг. 8, запросы Q2 и Q3 свертываются в "истину" без дополнительных поисков. В соответствии с этим система может обновить принадлежность к запросу Q2, чтобы добавить узел-элемент "Джек Доу", и принадлежность к запросу Q3, чтобы добавить узлы-элементы "Колумбия" и "Дьюк", предполагая, что узлы-элементы уже не находятся в сохраненных результатах соответствующих запросов.

[00084] Свернутое определение запроса для запроса Q4 не приводит к "истине" или "лжи", а к ограничению "выпускники.выпускники" != ""пусто"". В соответствии с этим система может оценить ограничение "выпускники.выпускники" != ""пусто"" для узлов-элементов "Колумбия" и "Дьюк", которые являются узлами-элементами, имеющих состояние "истина" для другого ограничения в определении запроса. Используя граф 200 на фиг. 2 в качестве примера, система может начать с узла "Колумбия", следовать по ребру "выпускники" к узлу "Джек Доу" и следовать по ребру "выпускники" от узла "Джек Доу" к узлу "Дьюк". Таким образом, система может определить, что для узла-элемента "Колумбия" целевым узлом-элементом является "Дьюк". Поскольку это удовлетворяет ограничению != ""пусто"", система может установить состояние "истина" для узла-элемента "Колумбия". Система также может выполнить обход графа от узла "Дьюк" через ребро "выпускники" к узлу "Джек Доу" и от узла "Джек Доу" до узла "Колумбия" через другое ребро "выпускники". Таким образом, для узла-элемента "Дьюк" целевым узлом-элементом является "Колумбия". Поскольку это удовлетворяет ограничению, система может установить состояние ограничения "истина" для узла-элемента "Дьюк". Система также может последовать по пути от узла "Дьюк" до узла "Джон Доу" через ребро "выпускники" и от узла "Джон Доу" к узлу "Мичиган" через другое ребро "выпускники". Однако, как только состояние ограничения становится "истиной", системе не требуется выполнять обход каждого возможного пути.

[00085] Система может свернуть определение запроса Q4 с использованием статуса ограничений, как проиллюстрировано свернутыми определениями 815. Определение запроса сворачивается в "истину" для обоих узлов-элементов "Колумбия" и "Дьюк", таким образом, система может добавить узлы-элементы "Колумбия" и "Дьюк" к результатам сохраненных запросов. Теперь система имеет обновленные результаты сохраненных запросов, затронутых добавлением тройки, и может идти дальше, чтобы обработать следующую тройку в группе, или может ожидать другого обновления графа данных.

[00086] Для удобства чтения приведенные выше примеры ссылаются на узлы и соотношения по именам или описанию. Следует понимать, что система может использовать другие идентификаторы в структурах данных, индексах, ограничениях и т.д., без отступления от раскрытых реализаций.

[00087] Фиг. 9 показывает пример универсального компьютерного устройства 900, которое может представлять собой систему 100 и/или клиент 170 на фиг. 1, которое может использоваться с описанными здесь методиками. Вычислительное устройство 900 предназначено для представления различных примерных форм вычислительных устройств, таких как ноутбуки, настольные компьютеры, рабочие станции, карманные персональные компьютеры, сотовые телефоны, смартфоны, планшеты, серверы и другие вычислительные устройства, в том числе носимые устройства. Показанные здесь компоненты, их соединения и соотношения и их функции подразумеваются только в качестве примеров и не подразумеваются для ограничения реализаций изобретений, описанных и/или заявленных в этом документе.

[00088] Вычислительное устройство 900 включает в себя процессор 902, память 904, запоминающее устройство 906 и порты 910 расширения, соединенные через интерфейс 908. В некоторых реализациях вычислительное устройство 900 может включать в себя приемопередатчик 946, интерфейс 944 связи и модуль 948 приемника GPS (системs глобального позиционирования) среди других компонентов, соединенных через интерфейс 908. Устройство 900 может осуществлять беспроводную связь через интерфейс 944 связи, который в случае необходимости может включать в себя схему цифровой обработки сигналов. Каждый из компонентов 902, 904, 906, 908, 910, 940, 944, 946 и 948 может быть смонтирован на общей системной плате или другими подходящими методами.

[00089] Процессор 902 может обрабатывать инструкции для исполнения в вычислительном устройстве 900, в том числе инструкции, сохраненные в памяти 904 или на запоминающем устройстве 906, для отображения графической информации для графического пользовательского интерфейса (GUI) на внешнем устройстве ввода/вывода, таком как дисплей 916. Дисплей 916 может представлять собой монитор или плоский дисплей с сенсорным экраном. В некоторых реализациях по мере необходимости могут использоваться несколько процессоров и/или несколько шин наряду с несколькими экземплярами памяти и типами памяти. Кроме того, несколько вычислительных устройств 900 могут быть соединены, и каждое устройство обеспечивает части необходимых операций (например, как банк серверов, группа сверхкомпактных серверов или многопроцессорная система).

[00090] Память 904 хранит информацию в вычислительном устройстве 900. В одной реализации память 904 является блоком или блоками энергозависимой памяти. В другой реализации память 904 является блоком или блоками энергонезависимой памяти. Память 904 также может представлять собой другую форму машиночитаемого носителя, такого как магнитный или оптический диск. В некоторых реализациях память 904 может включать в себя дополнительную память, обеспеченную через интерфейс расширения.

[00091] Запоминающее устройство 906 способно обеспечивать хранилище большой емкости для вычислительного устройства 900. В одной реализации запоминающее устройство 906 может представлять собой или содержать машиночитаемый носитель, такой как устройство на гибком диске, устройство на жестком диске, устройство на оптическом диске или устройство на магнитной ленте, флэш-память или другое подобное устройство твердотельной памяти или массив устройств, включающий в себя устройства в сети хранения данных, или другие конфигурации. Компьютерный программный продукт может быть материально воплощен в таком машиночитаемом носителе. Компьютерный программный продукт также может содержать инструкции, которые при их исполнении выполняют один или несколько способов, таких как описанные выше. Компьютерный или машиночитаемый носитель представляет собой запоминающее устройство, такое как память 904, запоминающее устройство 906 или память на процессоре 902.

[00092] Интерфейс 908 может представлять собой высокоскоростной контроллер, который управляет операциями на широкой полосе пропускания для вычислительного устройства 900, или низкоскоростной контроллер, который управляет операция с низкой полосой пропускания, или комбинацию таких контроллеров. Внешний интерфейс 940 может быть обеспечен для обеспечения ближней связи устройства 900 с другими устройствами. В некоторых реализациях контроллер 908 может быть соединен с запоминающим устройством 906 и портом 914 расширения. Порт расширения, который может включать в себя различные порты связи (например, USB, Bluetooth, Ethernet, беспроводной Ethernet), может быть соединен с одним или более устройствами ввода/вывода, такими как клавиатура, манипулятор, сканер, или с сетевым устройством, таким как коммутатор или маршрутизатор, например, через сетевой адаптер.

[00093] Вычислительное устройство 900 может быть реализовано во многих различных формах, как показано на фигуре. Например, оно может быть реализовано как стандартный сервер 930 или один из группы таких серверов. Оно также может быть реализовано как часть серверной системы в стойке. Кроме того, оно может быть реализовано в персональном вычислительном устройстве, таком как настольный компьютер 934, портативный компьютер 932 или планшет или смартфон 936. Вся система может быть составлена из нескольких вычислительных устройств 900, осуществляющих связь друг с другом. Возможны другие конфигурации.

[00094] Фиг. 10 показывает пример универсального компьютерного устройства 1000, которое может представлять собой систему 100 на фиг. 1, которое может использоваться с описанными здесь методиками. Вычислительное устройство 1000 предназначено представлять различные примерные формы крупномасштабных устройств обработки данных, такие как серверы, сверхкомпактные серверы, центры обработки данных, мэйнфреймы и другие крупномасштабные вычислительные устройства. Вычислительное устройство 1000 может представлять собой распределенную систему, имеющую несколько процессоров, возможно включающую в себя узлы сетевого хранилища данных, которые связаны одной или более сетями связи. Показанные здесь компоненты, их соединения и соотношения и их функции подразумеваются только в качестве примеров и не подразумеваются для ограничения реализаций изобретений, описанных и/или заявленных в этом документе.

[00095] Распределенная вычислительная система 1000 может включать в себя любое количество вычислительных устройств 1080. Вычислительные устройства 1080 могут включать в себя сервер или серверы в стойке, мэйнфреймы и т.д., осуществляющие связь по локальной или глобальной сети, выделенным оптическим каналам, модемам, мостам, маршрутизаторам, переключателям, проводным или беспроводным сетям и т.д.

[00096] В некоторых реализациях каждое вычислительное устройство может включать в себя несколько стоек. Например, вычислительное устройство 1080a включает в себя несколько стоек 1058a-1058n. Каждая стойка может включать в себя один или несколько процессоров, таких как процессоры 1052a-1052n и 1062a-1062n. Процессоры могут включать в себя процессоры данных, устройства сетевого хранилища данных и другие управляемые компьютером устройства. В некоторых реализациях один процессор может работать в качестве основного процессора и управлять задачами планирования и распределения данных. Процессоры могут быть взаимосвязаны через один или более стоечных переключателей 1058, и одна или более стоек могут быть соединены через переключатель 1078. Переключатель 1078 может обрабатывать связь между несколькими связанными вычислительными устройствами 1000.

[00097] Каждая стойка может включить в себя память, такую как память 1054 и память 1064, и устройство хранения, такое как устройства 1056 и 1066. Устройства 1056 и 1066 хранения могут обеспечивать хранилище большой емкости и могут включать в себя энергозависимую или энергонезависимую память, такую как присоединенные по сети диски, гибкие диски, жесткие диски, оптические диски, ленты, флэш-память или другие подобные устройства твердотельной памяти или массив устройств, включающий в себя устройства в сети хранения данных, или другие конфигурации. Устройства 1056 или 1066 хранения могут совместно использоваться несколькими процессорами, несколькими стойками или несколькими вычислительными устройствами и могут включать в себя машиночитаемый носитель, хранящий инструкции, исполняемые одним или более процессорами. Память 1054 и 1064 может включать в себя, например, блок или блоки энергозависимой памяти, бок или блоки энергонезависимой памяти и/или другие формы машиночитаемых носителей, такие как магнитные или оптические диски, флэш-память, кэш, оперативное запоминающее устройство (ОЗУ; RAM), постоянное запоминающее устройство (ROM) и их комбинации. Память, такая как память 1054, также может совместно использоваться процессорами 1052a-1052n. Структуры данных, такие как индекс, могут быть сохранены, например, в устройстве хранения 1056 и памяти 1054. Вычислительное устройство 1000 может включать в себя другие не показанные компоненты, такие как контроллеры, шины, устройства ввода/вывода, модули связи и т.д.

[00098] Вся система, такая как система 100, может быть составлена из нескольких вычислительных устройств 1000, осуществляющих связь друг с другом. Например, устройство 1080a может осуществлять связь с устройствами 1080b, 1080c и 1080d, и они могут быть совместно известны как система 100. В качестве другого примера система 100 на фиг. 1 может включать в себя одно или более вычислительных устройств 1000 как подсистему 150 сохраненных запросов. Кроме того, некоторые вычислительные устройства могут быть расположены географически близко друг к другу, и другие могут быть расположены географически удаленно. Схема расположения компонентов системы 1000 является лишь примером, и система может принимать другие схемы расположения компонентов или конфигурации.

[00099] Различные реализации могут включать в себя реализацию в одной или более компьютерных программ, которые являются исполняемыми программой и/или интерпретируемыми в программируемой системе, включающей в себя по меньшей мере один программируемый процессор, который может иметь специальное или общее назначение, соединенный для приема данных и инструкций от системы хранения и передачи данных и инструкций системе хранения, по меньшей мере одно устройство ввода и по меньшей мере одно устройство вывода.

[000100] Эти компьютерные программы (также известные как программы, программное обеспечение, прикладные программы или код) включают в себя машинные инструкции для программируемого процессора и могут быть реализованы на процедурном и/или объектно-ориентированном языке программирования высокого уровня и/или на языке ассемблера/машинном языке. Используемый здесь термин "машиночитаемый носитель" относится к любому непереходному компьютерному программному продукту, устройству и/или прибору (например, к магнитным дискам, оптическим дискам, к памяти (в том числе к оперативному запоминающему устройству (ОЗУ; RAM) и постоянному запоминающему устройству (ПЗУ; ROM)), к программируемым логическим устройствам (PLD)), используемым для обеспечения машинных инструкций и/или данных программируемому процессору.

[000101] Описанные здесь системы и методики могут быть реализованы в вычислительной системе, которая включает в себя внутренний компонент (например, сервер данных), или которая включает в себя промежуточный компонент (например, сервер приложений), или которая включает в себя интерфейсный компонент (например, клиентский компьютер, имеющий графический пользовательский интерфейс или веб-браузер, через который пользователь может взаимодействовать с реализацией описанных здесь систем и методик), или любую комбинацию такого внутреннего, промежуточного или интерфейсного компонентов. Компоненты системы могут быть связаны любой формой или средством связи цифровых данных (например, сетью связи). Примеры сетей связи включают в себя локальную сеть (LAN), широкомасштабную сеть (WAN) и Интернет.

[000102] Вычислительная система может включать в себя клиенты и серверы. Клиент и сервер в общем случае удалены друг от друга и обычно взаимодействует через сеть связи. Соотношение клиента и сервера возникает на основании компьютерных программ, работающих на соответствующих компьютерах и имеющих соотношение "клиент-сервер" друг с другом.

[000103] Были описаны несколько реализаций. Тем не менее, могут быть сделаны различные модификации без отступления от сущности и объема изобретения. Кроме того, логические потоки, изображенные на фигурах, не требуют конкретного показанного порядка или последовательного порядка, чтобы достигнуть желаемых результатов. Кроме того, могут быть обеспечены другие этапы, или этапы могут быть устранены из описанных потоков, и другие компоненты могут быть добавлены к описанным системам или удалены из описанных систем. В соответствии с этим другие реализации находятся в рамках следующей формулы изобретения.

1. Компьютерная система для обновления результатов сохраненных запросов в реальном времени, содержащая:

по меньшей мере один процессор; и

по меньшей мере одну память, хранящую:

граф данных из узлов, соединенных ребрами,

множество сохраненных запросов, каждый запрос определен одним или более ограничениями, которые должны быть удовлетворены для принадлежности к результатам запроса для запроса, каждое ограничение определяет по меньшей мере одно из ребер, и

инструкции, которые при их исполнении по меньшей мере одним процессором предписывают системе:

идентифицировать целевое ограничение в ответ на операцию, которая обновляет граф данных, с помощью исходного узла, ребра обновления и целевого узла, целевое ограничение определяет путь, который включает в себя ребро обновления, и целевое ограничение принадлежит первому сохраненному запросу,

оценивать целевое ограничение для узла-элемента, чтобы определить состояние для целевого ограничения, посредством обхода графа через путь целевого ограничения,

определять, указывает ли свернутое определение для первого сохраненного запроса на основе состояния, отвечает или не отвечает узел-элемент на первый сохраненный запрос, и

обновлять результат сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, отвечает или не отвечает узел-элемент.

2. Система по п. 1, в которой память дополнительно хранит индекс ограничений по ребрам, индекс используется для идентификации целевого ограничения.

3. Система по п. 1, в которой целевое ограничение представляет собой первое целевое ограничение и память дополнительно хранит инструкции, которые при их исполнении по меньшей мере одним процессором предписывают системе:

идентифицировать второе целевое ограничение, принадлежащее первому сохраненному запросу, второе целевое ограничение определяет путь, включающий в себя ребро обновления, второе целевое ограничение имеет длину больше, чем длина пути первого целевого ограничения; и

устанавливать состояние для второго целевого ограничения как состояние, указывающее, что второе целевое ограничение не разрешено.

4. Система по п. 3, в которой состоянием является первое состояние и память дополнительно хранит инструкции, которые при их исполнении по меньшей мере одним процессором предписывают системе:

определять, что свернутое определение для первого сохраненного запроса на основе первого состояния не способно указать, отвечает или не отвечает узел-элемент на первый сохраненный запрос;

оценивать второе целевое ограничение для узла-элемента, чтобы определить второе состояние для второго целевого ограничения, посредством обхода графа через путь второго целевого ограничения; и

определять, указывает ли свернутое определение для первого запроса на основе первого состоянии и второго состояния, что узел-элемент отвечает или не отвечает на первый сохраненный запрос, и

обновлять результат сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, что узел-элемент отвечает или не отвечает.

5. Система по п. 1, в которой целевым ограничением является первое целевое ограничение, состоянием является первое состояние и память дополнительно хранит инструкции, которые при их исполнении по меньшей мере одним процессором предписывают системе:

сохранять результат обхода графа в памяти;

идентифицировать второе целевое ограничение для первого запроса, второе целевое ограничение имеет путь, который включает в себя путь первого целевого ограничения;

использовать сохраненный результат обхода при оценке второго целевого ограничения, чтобы определить второе состояние для второго целевого ограничения;

определять, указывает ли свернутое определение для первого сохраненного запроса на основе первого состояния и второго состояния, что узел-элемент отвечает или не отвечает на первый сохраненный запрос; и

обновлять результат сохраненного запроса первого сохраненного запроса с помощью узла-элемента в соответствии со свернутым определением, когда свернутое определение указывает, что узел-элемент отвечает или не отвечает.

6. Система по п. 1, в которой обновлением является первое обновление и память дополнительно хранит инструкции, которые при их исполнении по меньшей мере одним процессором предписывают системе:

сохранять результаты обхода графа данных; и

удалять сохраненные результаты, когда последующее обновление графа данных включает в себя исходный узел, который отличается от исходного узла первого обновления.

7. Система по п. 1, в которой память дополнительно хранит инструкции, которые при их исполнении по меньшей мере одним процессором предписывают системе:

сохранять результаты обхода графа данных; и

использовать сохраненные результаты для оценки второго целевого ограничения, которое определяет путь, который включает в себя путь целевого ограничения.

8. Система п. 1, в которой целевым ограничением является первое целевое ограничение и память дополнительно хранит инструкции, которые при их исполнении по меньшей мере одним процессором предписывают системе:

идентифицировать множество целевых ограничений, первым целевым ограничением является одно из множества целевых ограничений, множество целевых ограничений предназначено по меньшей мере для двух запросов, первым сохраненным запросом является один из по меньшей мере двух запросов; и

интеллектуально оценивать множество целевых ограничений, чтобы отсрочить обходы для целевых ограничений с более длинными путями.

9. Способ для обновления результатов сохраненных запросов в реальном времени, содержащий этапы, на которых:

идентифицируют с использованием по меньшей мере одного процессора целевое ограничение, целевое ограничение определяет путь в графе данных, который включает в себя ребро, определенное в обновлении графа данных, причем этап идентификации инициируется посредством обновления;

определяют с использованием по меньшей мере одного процессора состояние для целевого ограничения посредством обхода графа через путь;

определяют на основе состояния, что свернутое определение для первого запроса, который включает в себя ограничение, указывает, что узел-элемент отвечает на первый запрос; и

обновляют результат сохраненного запроса для первого запроса с использованием узла-элемента, идентифицированного во время обхода, в соответствии со свернутым определением.

10. Способ по п. 9, в котором целевое ограничение идентифицируется с использованием индекса множества ограничений, индекс организован по ребрам.

11. Способ по п. 9, в котором обновление включает в себя добавление ребра обновления между исходным узлом и целевым узлом и обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя добавление узла-элемента в результат сохраненного запроса.

12. Способ по п. 9, в котором обновление включает в себя удаление ребра обновления между исходным узлом и целевым узлом и обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя поддержание результата сохраненного запроса.

13. Способ п. 9, в котором целевое ограничение включает в себя первое целевое ограничение и способ дополнительно содержит этапы, на которых:

идентифицируют второе целевое ограничение, принадлежащее первому запросу, второе целевое ограничение определяет путь, включающий в себя ребро обновления, второе целевое ограничение имеет длину больше, чем длина пути первого целевого ограничения; и

устанавливают состояние для второго целевого ограничения как состояние, указывающее, что второе целевое ограничение не разрешено.

14. Способ по п. 13, в котором состояние включает в себя первое состояние и способ дополнительно содержит этапы, на которых:

определяют, что свернутое определение для первого запроса на основе первого состояния не способно указать, отвечает или не отвечает узел-элемент на первый запрос;

оценивают второе целевое ограничение для узла-элемента, чтобы определить второе состояние для второго целевого ограничения, посредством обхода графа через путь второго целевого ограничения;

определяют, что свернутое определение для первого запроса на основе первого состояния и второго состояния указывает, что узел-элемент отвечает на первый запрос; и

обновляют результат сохраненного запроса первого запроса с помощью узла-элемента в соответствии со свернутым определением.

15. Способ по п. 9, в котором целевым ограничением является первое целевое ограничение, состоянием является первое состояние и способ дополнительно содержит этапы, на которых:

сохраняют результат обхода графа;

идентифицируют второе целевое ограничение для первого запроса, второе целевое ограничение имеет путь, который включает в себя путь первого целевого ограничения; и

используют сохраненный результат обхода при оценке второго целевого ограничения, чтобы определить второе состояние для второго целевого ограничения,

причем определение, что свернутое определение для первого запроса указывает, что узел-элемент отвечает на первый запрос, основано на первом состоянии и втором состоянии.

16. Способ по п. 9, в котором обновлением является первое обновление и способ дополнительно содержит этапы, на которых:

сохраняют результаты обхода графа данных; и

удаляют сохраненные результаты, когда последующее обновление графа данных включает в себя исходный узел, который отличается от исходного узла первого обновления.

17. Способ по п. 9, способ дополнительно содержит этапы, на которых:

сохраняют результаты обхода графа данных; и

используют сохраненные результаты для оценки второго целевого ограничения, которое определяет путь, который включает в себя путь целевого ограничения.

18. Способ по п. 9, способ дополнительно содержит этап, на котором:

группируют множество обновлений графа данных по исходному узлу, множество обновлений происходят в течение пяти минут друг за другом и обновление графа данных является одним из множества обновлений, причем идентификация целевого ограничения происходит в реальном времени после группировки.

19. Способ для обновления результатов сохраненных запросов в реальном времени, содержащий этапы, на которых:

в ответ на операцию, которая обновляет граф данных с помощью исходного узла, ребра обновления и целевого узла, идентифицируют с использованием по меньшей мере одного процессора целевое ограничение, причем целевое ограничение определяет путь в графе данных, который включает в себя ребро обновления;

определяют с использованием по меньшей мере одного процессора состояние для целевого ограничения посредством обхода графа через путь;

определяют, что свернутое определение на основе состояния для первого запроса, который включает в себя ограничение, указывает, что узел-элемент не отвечает на первый запрос; и

обновляют результат сохраненного запроса для первого запроса с использованием узла-элемента, идентифицированного во время обхода, в соответствии со свернутым определением.

20. Способ по п. 19, в котором обновление представляет собой удаление ребра обновления между исходным узлом и целевым узлом и обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя удаление узла-элемента из результата сохраненного запроса.

21. Способ по п. 19, в котором обновление представляет собой добавление ребра обновления между исходным узлом и целевым узлом и обновление результата сохраненного запроса в соответствии со свернутым определением включает в себя поддержание результата сохраненного запроса.