튜플 관계 계산법

안전한 튜플 관계형 계산법은 완벽한 언어인가?튜플 관계 계산법

2010-01-10 Sailaja

당신은 어떻게 생각하십니까? – avakar

goto mathoverflow.net; –

+1 좋은 질문입니다. –

안전을 잊어 버리자. Codd's theorem으로, 관계 계산법은 1 차 논리와 같습니다. FOL은 매우 제한적입니다. 어떤 그래프에서 점 A에서 점 B까지의 경로가 있다는 사실을 표현할 수 없습니다 (제한된 길이의 점 A에서 점 B까지의 경로가 있음을 표현할 수 있습니다. 예 : ∃ (x, y)와 경로 (y, z)와 경로 (z, t)와 경로 (t, b)는 길이가 4 인 경로를 의미합니다.

다른 논리의 강점에 대한 설명은 descriptive complexity을 참조하십시오.

출처

2010-01-10 17:32:50 sdcvvc

당신은 내가하는 것보다 더 많은 것을 알고있는 것 같지만, 왜 다음이 경로가 있다는 것을 표현할 수 없습니까? 그래프가 사실 집합으로 표시되는 경우 에지 (x, y) -> 경로 (x, y) -> 경로 (x, y) 에지 에지 (a, b) 및 에지 (b, c) 및 에지 (c, d) 그러면 에지 에지 (a, d)는 FOL 정리 프로버 (예 : 프롤 로그 인터프리터). –

당신은 route가 edge (x, y) -> route (x, y)를 만족하는 가장 작은 전이 관계라는 것을 말하고 있습니다. 이 정의에는 최소 고정 소수점이 필요합니다. 튜플 계산법에서 새로운 관계를 정의하려면 교차, 결합, 투영을 사용할 수 있지만 "다음 조건을 만족하는 관계입니다 ..."라는 말은 불가능합니다. 관계에 대해 계량화 할 수도 있지만, 그것은 고차원 논리이며 FOL에서는 개인에 대한 계량 만 허용됩니다. – sdcvvc

설명에 감사드립니다. sdcwc –

Codd's Theorem에 따르면 관계형 대수와 관계 계산법은 동일합니다. 관계형 대수학은 튜링 컴플리트가 아니므로 관계 계산법이 아니라는 것은 잘 알려져 있습니다.

[편집] 예를 들어, 합계 연산 (예 : 합계)을 수행하거나 관계형 대수/미적분에서 재귀 쿼리를 수행 할 수 없습니다. here (끝에 가까움)을 참조하십시오.

출처

2010-01-10 17:34:15

당신이 잘못되었거나 래리 와타나베가 있습니다. 나는 그 주제에 대해 잘 모른다. 그러나 이것은 흥미 로워지고있다! –

이제는 Turing Complete가 아닌 관계형 대수가 더 잘 알려져 있습니다. –

그러나 Codd의 정리에 대한 다른 포스터의 링크를 읽는 것부터 관계형 대수학은 관계형 수학과 동일하지 않습니다. 관계형 대수학은 본질적으로 명제 논리와 같습니다. 관계형 대수학은 FOL과 같습니다. –

튜플 관계 계산법

답변

관련 문제