If a nonlinear program can be linearized, it is possible to process queries on the program efficiently by using well-known cost-effective techniques for linear programs. There is an already known linearization problem, called ZYT-linearizability, which is concerned with the programs with only one bilinear rule (a nonlinear rule with two recursive subgoals in its body). The general linearizability is undecidable if the complexity class P is not equal to the complexity class NC. Even though ZYT-linearizability is very simple compared to the general linearization problem, it is NP-hard.
In this dissertation, we consider linearization of bilinear programs that are nonlinear programs with multiple bilinear rules and multiple linear rules. That is, we generalize ZYT-linearizability by relaxing the restriction on the number of recursive rules. We propose a transformation, called Right-Linear-First (RLF for short) transformation, for linearizing such bilinear programs. We define a bilinear program to be RLF-linearizable if it is logically equivalent to its RLF-transformed program. We attempt two approaches in order to identify the conditions for RLF-linearizability. The first one does not impose any restriction on the EDB subgoals. The other one restricts the number of EDB subgoals in the body of recursive rules.
The former is a very general approach. To overcome the complexity of the problem induced from multiple recursive rules, we solve the problem by characterizing it as two small but typical subproblems. The first one does not involve linear rules. So, all the recursive rules are bilinear. The second one involves only one bilinear rule and only one linear rule. Using the results for the typical subproblems, we derive a sufficient condition for RLF-linearizability that can be tested in exponential time.
The form of the programs for the latter approach is a special case of that for the former. The restriction on the number of EDB subgoals makes it possible to analyze a given program syntactically. We obtain three polynomial-time sufficient conditions that are more efficient to test than the exponential time condition from the former approach. However, each of them covers only a subclass of bilinear programs that the exponential time condition does. The latter approach extends the work of Zhang et~al. [ZYT90] on ZYT-linearizability.
RLF-linearizability deals with more general nonlinear programs than ZYT-linearizability. Our condition from the general approach covers a broader class of bilinear programs than any one of the previous conditions [ZYT90, Sar89, RSUV89] on ZYT-linearizability. To our knowledge, there is no other research result in the literature about linearizability of datalog programs with multiple bilinear rules.
비선형 프로그램을 선형화할 수 있다면 지금까지 개발된 선형 순환 질의를 효과적으로 처리할 수 있는 많은 기술들을 이용하여 원래의 비선형프로그램에 대한 순환 질의를 보다 효율적으로 처리할 수 있다. 잘 알려진 비선형 프로그램의 선형화에 관한 연구로, 이중선형 규칙 (몸체에 두 개의 순환 서브골이 나타나는 비선형 규칙)의 선형화를 다루는 ZYT-선형화가능성 문제가 있다. 만일 복잡도 클래스 P가 복잡도 클래스 NC와 같지 않다면 일반적인 비선형 프로그램의 선형화는 결정불가능(undecidable)문제이다. ZYT-선형화는 일반적인 비선형 프로그램의 선형화 문제에 비하여 매우 단순함에도 불구하고 NP-hard에 속한다.
이 논문에서는 다수 개의 이중선형 규칙과 다수 개의 선형 규칙을 가지고 있는 비선형 프로그램인 이중선형 프로그램의 선형화를 다룬다. 즉, 순환 규칙의 수에 관한 제한을 완화함으로써 ZYT-선형화가능성을 일반화 한다. 그러한 이중선형 프로그램의 선형화를 위하여 우선형우선(Right-Linear-First,줄여서 RLF)변환을 제안한다. 이중선형 프로그램이 그것을 RLF-변환한 프로그램과 논리적으로 동등하면 주어진 프로그램은 RLF-선형화가 가능하다고 한다. 이 논문에서는 RLF-선형화가능성을 위한 조건을 찾기 위하여 두 가지 방법으로 시도한다. 첫 번째 방법은 EDB서스골에 대한 아무 제약조건을 가하지 않는다. 다른 한 방법은 순화 규칙의 몸체에 있는 EDB서브골의 수를 제한한다.
전자는 매우 일반적인 시도 방법이다. 다수 개의 순환 규칙으로부터 발생하는 복잡도를 극복하기 위하여 원래의 문제를 두 개의 작은 전형적인 문제로 나누어 해결한다. 첫 번째 것은 선형 규칙을 포함하지 않는 프로그램을 다룬다. 그러므로, 모든 순환 규칙은 이중선형 규칙이다. 두 번째 것은 한 개의 이중선형 규칙과 한 개의 선형 규칙을 포함하는 프로그램을 다룬다. 전형적인 작은 문제들의 결과를 이용하여, 일반적인 이중선형 프로그램의 RLF-선형화가능성을 위한 지수시간에 검사가 가능한 충분조건을 끌어낸다.
후자의 시도 방법을 위한 프로그램의 형태는 전자를 위한 프로그램의 특수한 경우이다. EDB서브골의 수를 제한함으로써, 주어진 프로그램을 형태적으로 분석할 수 있다. 다항시간에 검사가 가능한 세 가지의 충분조건을 얻으며, 이는 전자의 시도 결과인 지수시간 조건에 비하여 보다 효율적인 검사를 할 수 있다. 그렇지만, 다항시간 조건 각각은 지수시간 조건이 검사할 수 있는 이중선형 프로그램의 일부분만을 검사할 수 있다. 후자의 시도는 ZYT-선형화에 관한 Zhang등 [ZYT90]의 연구를 확장한다.
RLF-선형화가능성은 ZYT-선형화가능성보다 일반적인 비선형 프로그램을 다룬다. 일반적인 시도로부터 얻은 우리의 조건은 ZYT-선형화가능성에 관한 기존의 연구[ZYT90, Sar89, RSUV89]중의 어느 것보다 더 넓은 부류의 이중선형 프로그램을 감당한다. 우리의 지식으로는, 다수 개의 이중선형 규칙을 기지고 있는 데이터로그 프로그램의 선형화가능성에 관한 연구 결과는 아직 없다.
