Рубрики

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 32

Предположим, что расписание базы данных S включает транзакции T1,… .Tn. Построить граф приоритета S с вершинами, представляющими транзакции, и ребрами, представляющими конфликты. Если S сериализуемо, то какой из следующих порядков вершин графа предшествования гарантированно даст последовательное расписание?

(A) Топологический порядок
(B) Глубина-первый порядок
(C) Ширина в первом порядке
(D) В порядке возрастания индексов транзакций

Ответ: (А)
Объяснение: Цикл в графе приоритетов говорит о том, что расписание не конфликтуемо сериализуемо . DFS и BFS обход графа возможен, даже если граф содержит цикл. И, следовательно, DFS и BFS также возможны для не сериализуемых графов. Но топологическая сортировка любого циклического графа невозможна. Таким образом, топологическая сортировка гарантирует, что граф будет сериализуем. Вариант D недействителен, потому что в транзакции с большим количеством индексов может потребоваться опередить нижний. Также два неконфликтующих графика могут происходить одновременно.

Это объяснение внес Абхишек Кумар.
Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2016 (набор 2) | Вопрос 32

0.00 (0%) 0 votes