데이터로그 Z

Datalogger Z(Datalog Z_ℤ)는 정수 산술 및 비교 기능을 갖춘 Datalogger의 확장입니다.주어진 접지 원자(사실)가 데이터로그 프로그램에_ℤ 포함되는지 여부에 대한 결정 문제는 RE-완전(따라서, 결정할 수 없음)이며, 이는 디오판틴 ^[1]방정식으로 축소하여 나타낼 수 있습니다.

구문

데이터로그의 구문은_ℤ 정수 상수, 정수 변수 또는 더하기, 빼기 및 곱하기로 구성된 용어인 숫자 항으로 데이터로그의 구문을 확장합니다.또한_ℤ Datalogger에서 형식의 원자인 를 사용할 수 있습니다.t < s또는t <= s숫자 용어로t,s.^[2]

의미론

이 섹션은 확장이 필요합니다. 의미론의 공식적인 처리.추가하면 도움이 됩니다. (2023년 3월)

데이터로그의_ℤ 의미론은 ^[2]데이터로그의 모델 이론적(헤어브랜드) 의미론을 기반으로 합니다.

데이터로그 제한_ℤ

Datalogger의 수반_ℤ 여부를 결정할 수 없기 때문에 한계_ℤ 데이터로그를 정의할 수 있습니다.데이터로그 제한은_ℤ 술어를 최대값 또는 최소값으로 표시된 단일 숫자 위치로 제한합니다.의미론은 데이터로그의 모델 이론적(헤르브랜드) 의미론을 기반으로 합니다.의미론은 헤르브랜드 해석이 다음과 같은 의미에서 모델의 자격을 갖추도록 요구합니다. 한계 $변수$의 지면 $원자{\displaystyle }$ a $=$ (${\displaystyle {c1\mathrm{}}_{},}$ ${\displaystyle \dots ,{}_{}{c}_{}}$ )$$\$displaystyle$ a$$= $r (c_{1},$ \$ldots, c_{n})$이 주어졌을 때, 여기서 마지막 위치는 최대(응답 최소) 위치입니다.만약 $어떤{\displaystyle }$$displaystyle$$$a가$$ Herbrand $해석{\displaystyle }$I에$$$있다면$$,$k > \$displaystyle$ k$>c_{n}($응답$$)에 대한 기저 $원자{\displaystyle }$ r${\displaystyle ({c1\mathrm{}}_{},}$…,${\displaystyle k}$ $){displaystyle$ r$(c_{1,\ldots, k$)}.< { \ $displaystyle$k < $c_{n$ 또한$$I { \ $displaystyle$ I$}$에 $있어야{\displaystyle }$I { \ $displaystyle$I}이$$(가$$) 제한 ^[3]폐쇄됩니다.

예

상수가 주어짐w이항 관계edge그래프의 가장자리와 이항 관계를 나타냅니다.sp을 마지막으로 하여sp최소값, 다음 한계 Datalogger 프로그램은_ℤ 관계를 계산합니다.sp에서 가장 짧은 경로의 길이를 나타냅니다.w그래프의 다른 노드로:

sp(w, 0) :- . sp(y, m + 1) :- sp(x, m), 가장자리(x, y). 

참고 항목

• 제약 논리 프로그래밍

레퍼런스

메모들

원천

• Grau, Bernardo Cuenca; Horrocks, Ian; Kaminski, Mark; Kostylev, Egor V.; Motik, Boris (2020-02-25). "Limit Datalog: A Declarative Query Language for Data Analysis". ACM SIGMOD Record. 48 (4): 6–17. doi:10.1145/3385658.3385660. ISSN 0163-5808. S2CID 211520719.
• Kaminski, Mark; Grau, Bernardo Cuenca; Kostylev, Egor V.; Motik, Boris; Horrocks, Ian (2017-11-12). "Foundations of Declarative Data Analysis Using Limit Datalog Programs". arXiv:1705.06927 [cs.AI].
• Kaminski, Mark; Kostylev, Egor V.; Grau, Bernardo Cuenca; Motik, Boris; Horrocks, Ian (2021-12-22). "The Complexity and Expressive Power of Limit Datalog". Journal of the ACM. 69 (1): 6:1–6:83. doi:10.1145/3495009. ISSN 0004-5411. S2CID 246702614.