Open Access Open Access  Restricted Access Subscription or Fee Access

Natural Language Query Processing Based on Probabilistic Context Free Grammar

Tejashri Indarchand Jain, Shishir K. Shandilya

Abstract


The field of natural language processing (NLP) has seen a dramatic shift in both research direction and methodology in the past several years. In the past, most work in computational linguistics tended to focus on purely symbolic methods. Recently, more and more work is shifting toward hybrid methods that combine new empirical corpus-based methods, including the use of probabilistic and information theoretic techniques, with traditional symbolic methods. The main purpose of Natural Language Query Processing is for an English sentence to be interpreted by the computer and appropriate action taken. Asking questions to databases in natural language is a very convenient and easy method of data access, especially for casual users who do not understand complicated database query languages such as SQL. This paper proposes the architecture of a new NLDBI system including its probabilistic context free grammar, the inside and outside probabilities which can be used to construct the parse tree and theusage of dependency structures and verb sub categorization in analyzing the parse tree.


Keywords


Natural language database interface; Probabilistic context free grammar; Parse tree; Verb sub categorization; Dependency Structure.

Full Text:

PDF

References


Huangi, Guiang Zangi, Phillip C-Y Sheu “A Natural Language database Interface based on probabilistic context free grammar”,IEEE International workshop on Semantic Computing and Systems 2008

Akama, S. (Ed. ) Logic, language and computation, Kulwer Academic publishers, pp. 7-11, 1997.

Johnson Mark. PCFG Models of Linguistic Tree Representations.24(4): 613-631, 1998.

Hendrix, G. G. , Sacerdoti, E. D. , Sagalowicz, D. , Slocum, J. “Developing a natural language interface to complex data”, in ACM Transactions on database systems, 3(2), pp. 105-147, 1978.

Christopher D. Manning and Hinrich Schutze. Foundations of statistical natural language processing. MIT Press, Cambridge, Massachusetts London,England, 1999. Pages: 390-400.

Mitrovic, A. A knowledge-based teaching system for SQL, University of “ITECH-09” International Conference – AVCOE,

SangamnerCanterbury, 1998. Moore, J. D. “Discourse generation for instructional applications: making computer tutors more like humans”, in Proceedings AI-ED, pp. 36-42, 1995.

Suh, K. S. , Perkins, W. C. , “The effects of a system echo in a restricted natural language database interface for novice users”, in IEEE System sciences, 4, pp. 594-599, 1994.

Whenhua, W. , Dilts, D. M. “Integrating diverse CIM data bases: the role of natural language interface”, in IEEE Transactions on systems, man, and cybernetics, 22(6), pp. 1331-1347, 1992.

Dan Klein, Christopher D. Manning: Corpus-Based Induction of SyntacticStructure: Models of Dependency and Constituency. ACL 2004: 478-485.

Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. Generating Typed Dependency Parses from Phrase Structure Parses. In LREC 2006.

E. Charniak. Statistical Language Learning. MIT press, 1993.

Paul Cohen and Ed Feigenbaum. Grammatical inference. In HandBook of Artificial Intelligence, volume 3, pages 494–511.Pitman Books Limited, 1984.

T. Dunning M. Davis. Query translation using evolutionary programming for multi-lingual information retrieval II. In Proc. of the Fifth Annual Conf. on EvolutionaryProgramming. Evolutionary Programming Society, 1996.

Z. Michalewicz. Genetic algorithms + Data Structures = Evolution Programs. Springer-Verlag, 2nd edition, 1994.

I. H. Witten T. C. Smith. A genetic algorithm for the induction of natural language grammars. In Proc. IJCAI-95 Workshop on New Approaches to Learning Natural Language, pages 17–24, Montreal, Canada, 1995.

P. Wyard. Context free grammar induction using genetic algorithms. In Proc. Of the 4th Int. Conf. on Genetic Algorithms, pages 514–518, 1991.

[Abou-Assaleh and Cercone] T. Abou-Assaleh and N. Cercone.Relaxed unification—proposal. Appl. Math. Lett. To appear.

[Abou-Assaleh and Cercone2002] T. Abou-Assaleh and N. Cercone.2002. Relaxed unification—proposal. In R. Cohen and B. Spense,editors, Lect. Notes Artif. Int. : 15th Conference of theCanadian Society for Computational Studies of Intelligence, AI 2002. Springer.

[Abou-Assaleh2003] T. Abou-Assaleh. 2003. Theory of relaxed unification—proposal. Master’s thesis, School of Computer Science,University of Waterloo, Waterloo, Ontario, Canada. .

[Charniak1993] E. Charniak. 1993. Statisitical Language Learning. The MIT Press.

[Harabagiu et al. 2000] S. Harabagiu, D. Moldovan, M. Pa¸sca, R.Mihalcea, M. Surdeanu, R. Bunescu,

R. Gˆırju, V. Rus, and P. Morˇarescu. 2000. Falcon: Boosting knowledge for answer engines. In The Ninth Text REtrieval Conference (TREC 9). [Keˇselj and Cercone] V. Keˇselj and N.Cercone. A graph unification machine for NL parsing. Comput. Math.Appl. To appear. [Keˇselj and Schuurmans2001] V. Keˇselj and D.Schuurmans. 2001. Course notes cs486/686:introduction to artificial intelligence.

[Knight1989] K. Knight. 1989. Unification: A multidisciplinary survey. ACM Comput. Surv. , 21(1):93–124.

[Pereira and Warren1980] F. C. N. Pereira and D. H. D. Warren. 1980. Definite clause grammars for language analysis—a survey of the formalism and a comparison with augmented transition networks. Artif. Intell. , 13(3):231–278. [Robinson1965] J. A. Robinson. 1965.A machine-oriented logic based on the resolution principle. J. ACM, 12(1):23–41.

[TRE2003] 2003. Text REtrieval Conference (TREC). WWW:http://trec. nist. gov/.


Refbacks

  • There are currently no refbacks.