datalog

ผมแทบจะไม่สนใจ Prolog เลย แต่ว่าเป็น TA วิชา knowledge representation ก็เลยต้องมาอ่าน แล้วก็พบว่ามี Datalog ด้วยซึ่งเป็น subset ของ Prolog อีกที [1] อันนี้ที่อ้างไปเขาไปอ้างงานปี 1982 ีอกทีผมยังหาอ่านไม่ได้

datalog ก็เอามาใช้ในงาน query ต่าง ๆ คล้าย SQL นี่เอง, datalog เป็นของเก่าแต่กลายเป็นว่ากลับมานิยมในยุคนี้ เก่ากว่า SQL; Clojure นี่ Datatomic ก็ใช้ datalog ด้วยแต่ว่าก็ปรับ syntax ให้กลายเป็น Clojure แบบเนียน ๆ

datalog แน่นอนว่าเขียนแบบ logic แล้วก็ recursive ได้[2] [4] เขาเอามา define path จาก edge แบบ recursive ก็ดูสวยงามดี สั้นด้วย


Path(t, d) :- Edge(1, t, d).
Path(t, d) :- Path(s, d1), Edge(s, t, d2), d=d1+d2

แต่ผมไม่แน่ใจว่าถ้า recursive ไม่ได้ออกมาเป็นแบบไหน

อีกประเด็นหนึ่งที่อ่านเจอคือ complexity ของ SQL query evalulate เป็น NP-complete [5] ส่วนของ Ground positive Datalog เป็น PTIME-complete ซึ่งผมก็ยังงง ๆ ว่า ground positive คืออะไร ptime นี่คือ space ไม่ P หรือเปล่า ?

อีกเป็นที่เจอใน Wikipedia[6] คือ datalog ไม่มี cut แบบใน Prolog เพราะรับประกันได้ว่าโปรแกรม query จะหยุดถ้า query บน finite set ทำให้ Datalog นี้เป็น declarative ยิ่งกว่า Prolog อีก

ผมว่า Datalog มันน่าสนใจว่า Prolog ที่เรียน ๆ ไปนอกจากจะยังไม่ตายแล้วแล้วมันก็คึกคักในวงการวิจัยมาหลายปี ดู ๆ แล้วในภาควิสาหกิจ (Enterprise) ก็จะเริ่มเอาไปใช้แล้วด้วย

ป.ล. ถึงผมจะไม่ค่อยรู้เรื่องก็ตาม SQL:1999 ก็ recursive ได้ [3] แต่เขียนใส่ MySQL แล้วผมก็ไม่แน่ใจว่ามันจะได้หรือเปล่า (ยังไม่ได้ลอง)

[1] https://pdfs.semanticscholar.org/6304/44d76e5aa81867344cb11aaddaab8dc8174c.pdf
[2] https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5470845/
[3] http://www.seas.upenn.edu/~cse400/CSE400_2006_2007/GuptaSyrotkin/writeup.pdf
[4] https://suif.stanford.edu/~courses/cs243/lectures/l12-socialite.pdf
[5] http://www.dis.uniroma1.it/~rosati/krst/comparison.pdf
[6] https://en.wikipedia.org/w/index.php?title=Datalog&oldid=799521469

Advertisements
This เรื่อง was posted in ไม่มีหมวดหมู่. Bookmark the permalink.

ใส่ความเห็น

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / เปลี่ยนแปลง )

Twitter picture

You are commenting using your Twitter account. Log Out / เปลี่ยนแปลง )

Facebook photo

You are commenting using your Facebook account. Log Out / เปลี่ยนแปลง )

Google+ photo

You are commenting using your Google+ account. Log Out / เปลี่ยนแปลง )

Connecting to %s