Linearization of bilinear datalog programs이중선형 데이타로그 프로그램의 선형화

Cited 0 time in webofscience Cited 0 time in scopus
  • Hit : 508
  • Download : 0
DC FieldValueLanguage
dc.contributor.advisorCho, Jung-Wan-
dc.contributor.advisorWhang, Kyu-Young-
dc.contributor.advisor조정완-
dc.contributor.advisor황규영-
dc.contributor.authorKang, Ji-Hoon-
dc.contributor.author강지훈-
dc.date.accessioned2011-12-13T05:23:35Z-
dc.date.available2011-12-13T05:23:35Z-
dc.date.issued1996-
dc.identifier.urihttp://library.kaist.ac.kr/search/detail/view.do?bibCtrlNo=106122&flag=dissertation-
dc.identifier.urihttp://hdl.handle.net/10203/33049-
dc.description학위논문(박사) - 한국과학기술원 : 전산학과, 1996.2, [ iv, 98 p. ]-
dc.description.abstractIf 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 {\em 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 $\cal P$ is not equal to the complexity class $\cal NC$. Even though ZYT-linearizability is very simple compared to the general linearization problem, it is $\cal 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 {\em Right-Linear-First (RLF for short) transformation}, for linearizing such bilinear programs. We define a bilinear program to be {\em 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 E...eng
dc.languageeng-
dc.publisher한국과학기술원-
dc.subjectRight-Linear-First (RLF)-
dc.subjectRLF-transformaion-
dc.subjectRLF-linearizability-
dc.subject선형화-
dc.subject이중선형 데이타로그 프로그램-
dc.subject우선형우선-
dc.subject우선형우선 변환-
dc.subject우선형우선 선형화가능성-
dc.subjectLinearization-
dc.subjectBilinear Datalog Program-
dc.titleLinearization of bilinear datalog programs-
dc.title.alternative이중선형 데이타로그 프로그램의 선형화-
dc.typeThesis(Ph.D)-
dc.identifier.CNRN106122/325007-
dc.description.department한국과학기술원 : 전산학과, -
dc.identifier.uid000795005-
dc.contributor.localauthorCho, Jung-Wan-
dc.contributor.localauthorWhang, Kyu-Young-
dc.contributor.localauthor조정완-
dc.contributor.localauthor황규영-
Appears in Collection
CS-Theses_Ph.D.(박사논문)
Files in This Item
There are no files associated with this item.

qr_code

  • mendeley

    citeulike


rss_1.0 rss_2.0 atom_1.0