XAI 커뮤니티는 머신러닝(ML) 모델 예측 설명을 위해 광범위한 범위의 질의와 점수들을 연구해 왔습니다. 데이터 관리 관점에서 볼 때, 이러한 설명 개념들의 증가는 그러한 개념들이 통일적으로 명시, 조합 및 분석될 수 있는 선언적 질의 언어를 요구합니다. 본 논문에서 우리는 부울(Boolean) 모델을 위한 그러한 프레임워크를 개발합니다. 먼저, 블랙박스 모델을 위한 해석 가능성 질의 언어인 FOIL을 재검토하고, 이것이 두 가지 근본적인 한계를 가지고 있음을 보여줍니다: 중앙 최적성 기반 설명 질의를 표현할 수 없고, 결정 트리(decision trees)에 대한 평가 문제가 다항 계층 구조(polynomial hierarchy)의 모든 레벨에서 어려우며(hard), 그 경우마다 어렵습니다. 그런 다음 우리는 확장된 어휘와 계층적 구조를 가진 FOIL 기반의 질의 언어인 ExplAIner를 소개합니다. ExplAIner가 가설추론적(abductive), 대조적(contrastive), 특징 기반(feature-based), 거리 기반(distance-based) 질의를 포함한 광범위한 설명 개념들을 표현할 수 있음을 보여줍니다. 또한, 우리는 ExplAIner의 각 질의에 대한 평가 문제가 기본 술어들(basic predicates)이 다항 시간 내에 평가될 수 있는 모든 부울 모델 클래스에 대해 부울 계층 구조(Boolean hierarchy)에 속함을 증명합니다. 특히, 이 속성은 결정론적(deterministic) 및 분해 가능한(decomposable) 부울 회로(Boolean circuits)에 대해서도 성립합니다. 마지막으로, 우리는 엄격 부분 순서(strict partial orders)에 대해 최소인 설명을 계산하기 위한 ExplAIner의 최적화 지향적인 조각(fragment)인 Opt-FOIL을 소개하고, 그 평가 문제가 동일한 실용성 가정 하에서 $ ext{FP}^{ ext{NP}}$에 속함을 증명합니다. 이러한 복잡도 결과는 직접적인 알고리즘적 결과를 가져옵니다: 고정된 ExplAIner 질의는 SAT 솔버(SAT solver) 호출 횟수 고정 개수로 평가될 수 있으며, Opt-FOIL에서 명시된 설명 개념은 그러한 호출들의 다항 개수로 계산될 수 있습니다. 이는 특히 SAT 솔버가 여러 클래스의 ML 모델에 대한 설명을 계산하는 데 성공적으로 사용되어 온 형식 XAI(formal XAI) 분야에서 중요합니다.